What a beatiful solution for D )

Someone plz explain me the solution for Carrot Cakes ?

Can you please explain the problem D bit more? Edit: I got it

First, we should find the intersection points of the line with the polygon, it is a known problem which can be solved in .

Could someone explain this algorithm?

For Carrot Cakes, can someone explain how do we get the value (n+k-1)/k*t ?

We don't need to use bin search in C if we precalcaulated two better fountains for each p <= c and p <= d (I named it C_dp[c+1][2], D_dp[d+1][2]). Then, first ans will be (C_dp[c][0] + D_dp[d][0]) if both of them are non-zero.

Another two cases — we will check each sorted fountain buying for C, and if its cost < p (we still have some money), trying to by second fountain C_dp[c — p][0] (if b of current fountain == C_dp[c — p][0], then we use C_dp[c — p][1]). Also checking if it is non-zero.

The same with D's.

Summary: O(C + D + C * log(C) + D * log(D)) (log for sorting). http://codeforces.net/contest/799/submission/27062024

Overtaking editorial for E:

1. Take all the items which both players like or k of them, whichever is less.
2. Take remaining items which only one of the players like to collect k items for each player.
3. Take the best items to collect m of them -> remember how many additional items (more than k) each of the players got.

If we were able to get to this point, the answer clearly exists — now improve it.

Notice that if we have k items which both players like, then we choose nothing in 2. and we got all the best in 3. So we may remove some of the items taken in 1., to improve the result.

If we got less than k items in step 1, notice that we got all the best in 2. and 3. We obviously don't remove anything from 3. We also don't remove anything from 2 — we took all the best items, to meet the requirement that both of players have to get at least k items.

Which means that we can improve our answer by removing things we got in 1.

We do this in 2 ways:

A. Check the balance of each player. If it has more than k items, you can try to remove item liked by both. There are 2 cases, when you can remove: A.1. Both players have more than k items, then you can replace the current worst item collected in 1. with the best item not collected yet and decrease the number of items for both players.

A.2. If only one player (call him p1) has more than k items, the other has exactly k items (call him p2) but there are still some items which p2 likes (obviously we will not choose anything liked by both, as we selected all the best such items in 1. and now we remove them). We can remove item from 1. and get the best item which p2 likes. Decrease the status for p1 and nothing changed for p2 — it sill has k items.

B. Once we removed everything by A., both players have exactly k items and we can't decrease the status anymore. We still can improve the answer though. We need to remove 2 items taken so far. One of them must be from 1., so the other must not be liked by any player. We replace them with 2 best items: 1 of them liked by p1 and the other by p2. In this way we do not change the number of items which both players like (they still have k of them) and we keep the set of m items.

After A. and B. we finish with the best set possible.

"After that we need to calculate linear dynamic where di equals to maximum width which we got for the length i. Let's iterate through extensions in sorted order and recalculate d." I did'nt find this to be clear enough. Can someone please explain this ?

This worst case O(n²) solution for C has passed. It should not have if the test cases had been a little stronger.

Should be noted that for E you don't need any particular data structure (such as a stl set) to keep your data. You can just use arrays and remember the last index of pushed "must-have" elements so you can't push them on further steps (in order to mentain O(n)) steps. This way you get O(n) as opposed to O(n log n). Not much of an improvement but it's something.

I don't understand problem C's solution, why should we consider p1 equals p2? In fact, I accepted without considering this case (My code)).

Задачу F по идее можно решить за O(m+n) по памяти и времени, или за O(nlgn) по времени если делать сортировку, но зачем дерево отрезков и запросы на интервалах не понятно.

Задачу G по идее можно решить за O(nlgn+lgn*lgE). Ведь пересечь луч с выпуклым мноноуг-м можно за O(lgn) и найти площади разделения можно за O(lgn) при предпросчете.

Can you please explain the solution for D?

I have seen solutions of C using fenwick tree( also called Binary Indexed Tree or BIT) such as this one : (http://codeforces.net/contest/799/submission/27019364) Can somebody explain this ?

can anyone give a code with explanation for [problem:D].

Problem D:

I found this is the easiest soln to understand. Note this gets TLE...So first one gets AC just for optimization

Great solution for Problem D!

However, mine is different and I would like to share it.

We reduce the problem to the subproblem: given an array $$$arr[]$$$ and a number $$$X$$$, find a subsequence $$$b[1]$$$, $$$b[2]$$$, ..., $$$b[k]$$$ of $$$arr[]$$$ such that $$$P=b[1]b[2]...b[k] \geq X$$$ and the $$$P$$$ is the smallest possible.

To solve it, we use DP. Sort the array in decreasing order. DP state:

$$$dp[j][ceil(X/i)]$$$ is the answer for $$$arr[1...j]$$$. Then transition is $$$dp[j][ceil(X/i)]=min(dp[j-1][ceil(X/i)], dp[j-1][ceil(X/(iv[j])]*v[j])$$$.

That's it!

103627148