By Fefer_Ivan, 10 years ago, In English

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.

Tutorial of Zepto Code Rush 2014
  • Vote: I like it
  • +117
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it -54 Vote: I do not like it

please hurry to write the report about other question.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Very offensive statement...

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    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! :))

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      lol I just got red after Zepto Code round, too! I'm looking forward to seeing you at Taiwan.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 :)

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        You should go to NUS next year to see him :)

»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Images in the problem statements were so good that I wish they (or similar ones) were present in the editorials too ;)

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Anudeep, Its very unfortunate that ur problem A failed otherwise you would have been in top 50.Hard luck,bro.:(

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 ;)

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm surprised that C can be solved by bruteforce :O

»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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).

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone show a short Java implementation of C using minimum spanning trees?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, time limit is 5 seconds bro.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain me this : MST is O((n*M*k)^2) which will go out of time bound ?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
10 years ago, # |
  Vote: I like it -7 Vote: I do not like it

@Fefer_Ivan can you please provide the links to the solutions of the above problems(specially to the D and E)??