436A - Feed with Candy
Tutorial author: Fefer_Ivan
In this problem types of eaten candies must alternate. It means that the type of first eaten candy dictated the types of all the following candies. There are only two possible types so we should consider each type as a type of first eaten candy separatelly and then pick the most optimal. So, what if Om Nom wants to eat a candy of type t and can jump up to h? It is obvious that best option is to eat a candy with maximal mass among all the candies he can eat at this time.
436B - Om Nom and Spiders
Tutorial author: Fefer_Ivan
Let us number columns with integers from 0 from left to right and rows from 0 from top to bottom. In the cell (x, y) at the time t only four spiders can be at this cell:
- Spider, which is moving left and started at (x, y + t).
- Spider, which is moving right and started at (x, y - t).
- Spider, which is moving up and started at (x + t, y).
- Spider, which is moving down and started at (x - t, y).
Let iterate through all possible starting positions of Om Nom. Consider that he starts at column y. At time 0 all spiders are on their initial positions and Om Nom is at (0, y). There is no spiders at row 0, so at time 0 Om Nom can not meet any spiders. When Om Nom is at cell (x, y), it means that x units of time passed after the start. So to calculate the number of spiders, that Om Nom meets it is enought to check only 4 cells stated above.
436C - Dungeons and Candies
Tutorial author: Fefer_Ivan
Let's consider a weighted undirected graph with k + 1 vertex. Label the vertices with numbers from 0 to k. Vertices from 1 to k correspond to levels. For each pair of levels i and j add an edge between vertices i and j with weight equal to the cost of transferring one level as a difference from the other level. For each level i add an edge from vertex 0 to vertex i with weight equal to n·m, i.e. cost of transmitting the whole level. Each way to transmit levels defined an spanning tree of this graph. So to solve the problem, we must find a minimal spanning tree of this graph.
436D - Pudding Monsters
Tutorial author: Fefer_Ivan
This problem can be solved using dynamic programming. Let's introduce some designations: sum(l, r) — number of special cells on the segment [l, r], zi — maximal number of covered special cells using only first i monsters, di — maximal number of covered special cells using only first i monsters and with i-th monster not moving.
How to calculate di. Let's denote i-th monster position as r. Let's iterate through all special cells to the left of i-th monster. Let's denote current special cell position as l. Let's consider the situation when this cell is the leftmost special cell in the block of monsters with i-th monster in it. So we need r - l additional monsters to get to this cell from monster i. So the value of di can be updated with zi - (r - l) + sum(l, r).
Now, after we computed new value of di, we need to update some values of zj. Let's denote i-th monster position as l. Let's iterate through all special cells to the right of i-th monster. Let's denote current special cell position as r. Let's consider the situation when this cell is the rightmost special cell in the block of monsters with i-th monster in it. So we need r - l additional monsters to get to this cell from monster i. So we can update the value zi + (r - l) with di + sum(l + 1, r). Also, zi should be updated with zi - 1.
So the solution works in O(n·m) because for each of n monsters we iterate through all m special cells and for a fixed monster-cell pair all computing is done in O(1).
There are some details about monsters, that are merged at the initial state, but they are pretty easy to figure out.
436E - Cardboard Box
Tutorial author: Gerald, Nerevar
In this task you have to come with the proper greedy algorithms. Several algorithms will fit, let's describe one of them:
- From that point we will consider that the levels are sorted by increasing value of b.
- Let's look at some optimal solution (a set of completed levels). From levels that we completed for two stars, select the level k with the largest b[k]. It turns out that all levels that stand before k (remember, the levels are sorted) should be completed for at least one star. Otherwise, we could complete some of the previous levels instead of the level k. This won't increase the cost.
- Let's fix a prefix of the first L levels and solve the problem with the assumption that each of the selected levels should be completed. Additionally, we will assume that all levels that are completed for two stars are within this prefix (as was shown before, such prefix of L levels always exists for some optimal solution).
- As we will surely complete this L levels, we can imagine that we have initially completed all of the for just one star. So, we have w - L more stars to get. We can get these stars either by completing some of the levels that are outside our prefix for one star, or by completing some of the first L levels for two stars instead of one star.
- It's clear that we just have to choose w - L cheapest options, which correspond to w - L smallest numbers among the following: b[i] - a[i] for i ≤ L and a[i] for i > L. Computing the sum of these smallest values can be done with a data structure like Cartesian tree or BIT.
The described solution has time completixy of O(n log n).
436F - Banners
Tutorial author: Gerald, Nerevar
Task F was the hardest one in the problemset. To better understand the solution, let's look at the task from the geometrical point of view. Imagine that people are point in the Opc plane (value of p and q are points' coordinates). Then for each line horizontal c = i we have to find such vertical line p = j that maximizes some target function. The function is computed as follows: (number of points not below c = i, multiplied by w·i) plus (number of points below c = i and not to the left of p = j, multiplied by j).
Let's move scanning line upwards (consider values c = 0, then c = 1, etc). For each value of p we will store the value d[p] — the value of the target function with the current value of c and this value of p. The problem is: if we have such array d[] for the value c, how to recompute it for the value c + 1?
Let's look at all people that will be affected by the increase of c: these are the people with b[i] = c. With the current c they are still using free version, after the increase they won't. Each of these people makes the following effect to the array: d[1] + = 1, d[2] + = 2, ..., d[b[i]] + = b[i]
Now the task can be reduced to the problem related with data structures. There are two types of queries: add the increasing arithmetical progression to the prefix of the array and retrieve the maximum value of the array. One of the way to solve it is to use sqrt-decomposition.
Let's divide all queries into groups of size sqrt(q). Let's denote the queries from the group as a sequence: p1, p2, ..., pk (k = sqrt(q)). For query pi we should perform assignments d[1] + = 1, d[2] + = 2, ..., d[pi] + = pi. Imagine we already preformed all the queries. Each value of new array d[] can be represented as d[i] = oldD[i] + i·coef[i], where coef[i] is the number of pj (pj > i).
One can notice that array coef contains at most sqrt(q) distinct values, additionally this array can be splitted into O(sqrt(q)) parts such that all elements from the same part will be the same. This is the key observation. We will divide array coef into parts. And for each part will maintain lower envelope of the lines y = d[i] + i·x. So, we will have O(sqrt(q)) lower envelopes. Each envelope will help us to get maximum value among the segment of array d[i](oldD[i] + i·coef[i]). As for each i from some segment factor coef[i] is containt we can just pick y-coordinate with x = coef[i] of corresponding lower envelope.
Described solution has time complexity of O(MAXX·sqrt(MAXX)), where MAXX is the maximum value among a[i] and b[i]. With best regards, Ivan.
please hurry to write the report about other question.
Very offensive statement...
Yes.It's too rude
You need to be banned for having multiple accounts.
It's sad that this comment has too many negative votes. worfzyq 's initial comment was "Sorry", which may imply that he was also quakerzyq.
AlexanderBolshakov probably meant that, which is understandable. worfzyq should get negative votes for completely changed the meaning of his comment instead..
Also: 6801504 6883269
Now I understand that anything that is written here should be written in such a way that even those who don't like to think (or can't do this) will still understand what you've meant. And this is really sad.
Well, just like on habrahabr :)
Why so hurry? Solving these 3 problems are very enough for a high rank in this contest... (at least to increase my rating to be red! :))
lol I just got red after Zepto Code round, too! I'm looking forward to seeing you at Taiwan.
Haha congrats. Vietnamese IOI team have a red coder then :) Unfortunately I won't go to Taiwan. IOI 2013 is my last IOI :( Now my world is ACM-ICPC :) Well let's meet at other opportunity :)
You should go to NUS next year to see him :)
Images in the problem statements were so good that I wish they (or similar ones) were present in the editorials too ;)
Anudeep, Its very unfortunate that ur problem A failed otherwise you would have been in top 50.Hard luck,bro.:(
I have this habit of locking a solution as soon as i submit. I did the same with A. Then when I was implementing B (or C), I understood that my A will fail, quickly finished that problem and started hacking solutions with a case that my solution will fail. There were many others who did the same mistake, Got 7 hacks ;)
I'm surprised that C can be solved by bruteforce :O
My solution for problem E:
Consider the levels with ascending a(i) and iterate through them. Let's say, we're now at level i, we have some decision to make here:
Choose 0 star here. It's easy to see that from now on, if we choose a 1-star level, let's call j, we have a(j)>a(i), which make swapping i and j lead to a better solution. So from now on we only choose 2-stars levels. Among all the remaining levels, we choose the ones with b(i) minimum to satisfy the required stars.
Choose 1 star here. Create a fake level with a=b(i)-a(i), b=+inf. Insert that fake level in our box.
To maintain the levels and take out the one with minimum a(i), we can use a heap (priority_queue) with two value a(i) and b(i).
Awesome, coupled with noticing that you resolve the issue of adding the cost of all minimun b(i) with a Fenwick tree, I managed to get a working solution Thank you, have my like.
Can someone show a short Java implementation of C using minimum spanning trees?
http://codeforces.net/contest/436/submission/6876229
Guys why the answer of the last example of 436D - Pudding Monsters is 1? Do we count the number of covered stars only when all the monsters combine in a single block? Can an optimal game finish before we combine them all?
We can stop the game at any time. Even if we did not make a single move. In the second example seconds and third monsters are already merged in one block and can not be separated.
with D can O(n*m) pass the systest? i thought the complexitiy is too large so used much time to think of wrong O(m^2 lg n) sol
Yes, time limit is 5 seconds bro.
It is only 2·108. And operations are pretty simple. Integer addition and multiplication in straight-forward for-loops. My solution in C++ runs only 500 ms.
Here comes a line I'm often repeating: "Algorithmic problems are divided into two groups. Those were n log n TLEs for n<=10^6 and those were organizers say "It is only 2*10^8, today's computer do it in a 0,5s"" :P. Indeed in a very short period I experienced also my O(n log n) submission TLEing and my "favorite" organizer's excuse for ridiculously big constraints.
It is known, that there is always a constant multiplier behind big-O notation. One can not just ignore it. In this problem thr constant is small. In FFT algorithm, for example, it is bigger.
In World Finals problem D had 25*25*10^6 ~ 6*10^8 solution that can or can not pass the tests depending on implementation. We experienced both options.
I spent a few hours on Problem C to figure out how to find minimum spanning tree, so I decided to share what I've found out.
If you don't know how to find minimal spanning tree, this tutorial on YouTube will be really helpful.
I implemented my solution based on this editorial and the tutorial. I hope this helps if you are having trouble understanding/implementing!
can you explain me this : MST is O((n*M*k)^2) which will go out of time bound ?
Kruskal's algorithm of minimum spanning tree runs in O(logE) time, and here maximum value of E is 10^3 * 10^3. Therefore, it will not exceed time limit. A better question to ask would be how building the graph would not exceed time limit-it takes around 10^8 operations, and while in here it does fit in time limit, I've seen other judges where it might've timed out.
@Fefer_Ivan can you please provide the links to the solutions of the above problems(specially to the D and E)??
http://codeforces.net/contest/436/status/F http://codeforces.net/contest/436/status/E
thank you for the link, But I was looking for the editorial author's solution so that I can understand concept in the editorial and how they implemented it.