dalex's blog

By dalex, 10 years ago, translation, In English

Link to announcement and discussion.

And here is the problem analysis.

A div 2: 378A - Playing with Dice

Make three counters: for wins of both players and for a draw. Iterate over all six ways how they can throw a dice. For each way determine who wins or there is a draw and increment the corresponding counter.

B div 2: 378B - Semifinals

You can think a bit and understand that you should consider only corner cases: k = 0 and . All other cases will be something between them.

If k = 0, we should choose n biggest elements from two sorted lists, one of the ways is to use two pointers method. And if , we just mark first people in each list.

A div 1 / C div 2: 377A - Maze

Start BFS or DFS from any free cell. As the maze is connected, this search will visit all s free cells. But we can stop the search when it visits s - k free cells. It's obvious that these s - k cells are connected to each other. Remaining k cells can be transformed into the walls.

Solutions which every move transform the cell which has the minimal number of neighbours passed pretests. However, it's wrong. Here is the counter-test:

....
.#..
..##
..##

Top-left cell has no more neighbours than any other cell but we cannot transform it into the wall.

B div 1 / D div 2: 377B - Preparing for the Contest

It's obvious that the time needed to fix all bugs is the monotonic function: if we can do it for some time, we can do it for greater time. So we can use binary search in these problem. We should learn how to check if some time t is enough.

At first sort all bugs by their complexity and all students by their skills. Let's consider the hardest bug. Who can fix it? It can be fixed by student whose skills is not less that this bug's complexity. Push all such students into the priority queue (sorted by students' price) and pop the cheapest student. As we check time t, this student must fix t hardest bugs (he definitely can do it). Save that information and go to the next bug which has not been fixed yet. Again push all students which can fix it to the priority queue and pop the cheapest one. And so on. If at some moment priority queue is empty, time t is not enough. If we spent too much 'money' — it's not enough as well. Otherwise we get the correct schedule.

C div 1 / E div 2: 377C - Captains Mode

There are some observations that do the problem very simple. The first one is that we always should pick the strongest hero. But we cannot say something similar about the bans — in different situations different bans are the best. But the most important observation is that we should consider only m strongest heroes. Indeed, in every game where only strongest heroes are picked, no hero except m strongest can be picked. That's why we don't need to ban them and therefore we don't need to consider them.

So now we have only 20 heroes. It means we can solve the problem using the dynamic programming with bitmasks: dpmask will be the difference between the teams' strengths when only those heroes are picked or banned whose bits are set to 1 in the mask. At every state we try to pick or ban every available hero and go to the other state. The simpliest way to implement it is the recursion with memoization. The answer will be stored in dp2m - 1.

Unfortunately, we couldn't estimate the real complexity of this problem (despite it has the simple solution, this solution is not so easy to think of — standard 1500 points for problem C would be better) and set too big TL (many solutions written in C++ whose complexity is m2·2m passed — we should have been set TL to 1 second or even to 0.75 seconds). So if you solved it in m2·2m, you may assume that you're just lucky and your correct verdict is Time Limit Exceeded.

Why it can be solved in m·2m? There is no point of missing a ban — if we ban the weakest hero, nothing will change since the weakest hero won't be picked.

Also this problem has weak pretests so you could hack solutions without bitmasks with almost any big random test.

D div 1: 377D - Developing Game

Let's note that every answer is characterized with two numbers L and R so that max{li} ≤ L, R ≤ min{ri}, and L ≤ vi ≤ R. If we know L and R, we can check every person and choose those who satisfies the conditions above.

Let's imagine a plane with the coordinate axes: one of the axes will be L, and the other will be R. If the point (L, R) on this plane is the optimal answer, people included in this answer for sure satisfy the conditions li ≤ L ≤ vi and vi ≤ R ≤ ri. These conditions specify the rectangle on the plane. Since we should find the maximum number of people, we should find such point (L, R) that it is inside the maximum number of the specified rectangles.

Now it's the standard problem that can be solved using the scanline through one axis and the segment tree built on the other axis. The hardest part is to reduce the original problem to it.

E div 1: 377E - Cookie Clicker

First of all, throw away the buildings which cannot be used in any optimal answer: for each vi remain only one building that has speed equal to vi and minimal ci. Also throw away all buildings whose speed is less than the speed of the fastest building which has ci = 0.

It's fairly obvious that at any time we should use the fastest building. And if some building is used in the optimal answer, it should be bought and used immediately when we have enough money (I will use the word 'money' instead of 'cookies').

Let's imagine the plane (x, y) where x axis stands for the time and y axis stands for the money. We will maintain the graph of the function y = f(x) — 'maximal number of money that can be obtained at the time x' and process the buildings one by one, changing the graph. This function is the union of the line segments with the slopes equal to vi, and each of these line segments is active on a certain segment [xli, xri] of the axis x.

For example, at the beginning the graph is just the line y = v1x, where v1 is the speed of building that can be bought for 0 units of money. Let the next building's price is c2. Find the minimal point x02 where value of our function is greater or equal to y = f(x02) ≥ c2 and buy this building at the moment x02. Then we should make the line y = y02 + v2x where y02 = f(x02) - c2 is the amount of money remaining after the purchase. Now we have two lines. Till some moment the first line is better (not till x02, maybe later), but as v2 > v1 there exists a moment of time (it's ceil(x12) where x12 is the x-coordinate of the lines' intersection) when the second line becomes better. Now we know the segments where a particular line is better than the others.

Continue add all buildings to the graph this way. Line segments should be stored in stack, as in all problems with convex hull, and every step remove unnecessary line segments from the stack (these are the lines those position in the stack is after the line which has an intersection with the currently added line). After we process all buildings, we use our graph to find the minimal time when we have S untis of money.

If we also should say which building we must use, we can store for any line segment its 'parent' — the line segment which was active when the current one was bought. With such parent array it's not hard to restore the sequence of buildings in the answer. We removed this part from the problem to make it a bit easier.

  • Vote: I like it
  • +60
  • Vote: I do not like it

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

In problem C: "no hero except m strongest cannot be picked". I think there should be "no hero except m strongest can be picked".

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

    Yeah. Probably there are lots of errors in my english translation.

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

In E we can use funny trick and add an artificial building with cost S and slope infinity and all we need to obtain a result is to check whether our current building's cost is equal to S, and if so, print the first moment we can buy it. This makes another solution a bit easier since we don't need any additional loop to obtaining result after processing all buildings.

Very nice problemset!

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

I think that the tag of problem E div1 should rather be geometry or convex hull than be DP ...

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

a

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

Thanks for the counterexample in Div2C.

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

In DIV1 what is s in s-k?