Codeforces Round 398

Codeforces Round 398 screen cast by eddy1021

Solved A in 3 mins.

B is a tricky implementation problem. Given a time range [ts,tf] at which a receptionist will be available, the receptionist will spend t for each visitor. You also know the time at which n visitors will come. You should find the time that you should go s.t. the time you need to wait in the queue is minimized.
Just iterating through all possible order you will be served. That is, you are the first one, second one, and so on. Then, the rest of thing is to deal with those corner case and be careful to all the details among the description.

C is a dp problem. I somehow stuck on it for a while. Given a vertex weighted tree, you should cut out two edge s.t. the sum of weight of each part is equal.
There's only two cases: If one cut edge is an ancestor of the other one, we know that sum of all weight of the subtree of the lower one should be total sum / 3, and the sum of upper one should be total sum * 2 / 3. In the other case, sum of each subtree should be total sum / 3. Then, it's a classical tree dp problem.

D is an implementation problem. Given the expiration day of n milks you have and m milks in the store and you can drink at most k milks each day, you should find the maximum number of milk you could buy s.t. no milks of your will be expired.
The main key is that there should be at most i*k milks with expiration day before i. Thus we can first check whether we can drink those milk we already have without wasting. Then, we can greedily buy milk with the most late expiration day and be sure that we won't break the condition described above.

E is a nice greedy problem. You have infinite 100$ and m 1$ and going to spend c_i $ on day i. If you get a_i $ change on day i, you will gain a_i * w_i dissatisfaction. Your goal is to minimize total dissatisfaction.
First, we can see that we will only give c_i / 100 100$ and c_i mod 100 1$ or \ceil{c_i/100} 100$ on the i-th day. For the second case, we will gain dissatisfaction. Thus, we can greedily choose first case if we can. Then, once we doesn't have enough 1$ to spend in first case. We can consider to not choose first case in previous days. No matter we choose which day to roll back to second case, we will always gain back exactly 100 1$. Thus, we just choose the one with minimum dissatisfaction one.

Rank 1 on final standing.
Should be stronger and bounce back in following official round!