[PCMS 130 invitational]Fish Shop

Difficulty Ratings

Idea Creativity: 1/5
Techniques Used: 1/5
Implementation : 1/5
I realised that there is a wide variety of audience for my blogs, so now I made this nobody can complain...
This problem is by some alumni of PCMS that I am not aware of.

Simplified Statement

(Interactive problem) You have a bag that can hold $87$ balls. Now, $0 \le Q \le 1024$ people come to you one by one and the following happens.
1. The person gives you a ball with a number which is $3$, $4$ or $5$ written on it.
2. You look at it and you can either put into your bag or ignore. You can only put into your bag if there is less than $87$ balls beforehand.
3. The person disappears.
Your objective is to maximize the sum of balls in your bag. Let $sum$ be the value you obtain and let $opt$ be the theoretical maximum (sum of the largest $min(87,Q)$ balls). If after the $Q$ people come, you have $1.45*sum \ge opt$ then you can get AC. Note that $Q$ is not given, and your bag can have less than 87 balls at the end.
Subtask (45%): There will be no balls of $4$.

Intuition

So obviously you wil always want to balls with larger number. However, assume the $Q$ people all come to you and offer a $3$. If you dont take any you'll lose. However, if you take too many balls of small number and your bag is full, and after that $87$ people came and offer you a $5$ then you are doomed. Therefore, it is reasonable to think that you set some thresholds $X$ and $Y$, where you cannot take more than $X$ balls of $3$ and $Y$ balls of $3$ or $4$, and you will take if the threshold isnt full.

Subtask

You basically have to find $X$ such that $3 \times X \times 1.45 \ge 3 \times 87$ and $(3 \times X + 5 \times (87-X)) \times 1.45 \ge 5 \times 87$, which are the two worse scenarios. You can solve it and realise that any $X$ within $[60,67]$ will work. So what you do is
- if a $5$ comes then you should take it - otherwise if a $3$ comes and you have not taken $60$ $3$s yet and your bag is not full, then you should take it
- otherwise you should ignore that dude.

Full solution

This time you have to solve $3 \times X \times 1.45 \ge 3 \times 87$ and $(3 \times X + 4 \times (Y-X)) \times 1.45 \ge 4 \times 87$ and $(3 \times X + 4 \times (Y-X) + 5 \times (87-Y) ) \times 1.45 \ge 5 \times 87$. You can realise that $X = 60$ and $Y = 75$ are the only solution. Therefore, the final algorithm is:
- take when none of $f(3) \gt 60$, $f(3)+f(4) \gt 75$ and $f(3)+f(4)+f(5) \gt 87$ happens if you take
- or discard otherwise
where f(x) is the number of balls of number $x$ you have taken.

"亂搞/Luangao/Lyun6 Gaau2"

By using the general idea that taking less balls give you more option, some claimed that they passed with greedies like "ignore unless $sum \times 1.45 \lt opt$ will happen". I am very lazy unskillful and i didn't prove this method. So prove or disprove is left as an exercise to readers...