SRM 530

Match Summary

Round Overview
Discuss this match

Obviously you can skip this…, m…, “animation”. (This contains the winners and statistics of the match, in the obvious places). This is made using flash.

UPD: Oops, unbing has a correct D1-hard solution instead of a D1-medium solution. Sorry for this mistake in the… um… “animation”.

There are a couple of events during the match. We apologize for accidentally issuing a clarification that was meant only for division 1 to division 2. Also, during the intermission, we accidentally hit “System Test”. This allows some coders to read source code before the challenge phase. However, we thought that since this only happens in like, 30 seconds, the effect is minor and making this round unrated will do more harm than good.

GogoXBallsAndBinsEasy

Used as: Division Two - Level One:

Let S_i be the number of balls in bin i in the initial configuration, and let T_i be the number of balls in bin i in the final (or sorted) configuration.

Minimum number of moves

Given S and T, what is the minimum number of moves we need? Let’s consider a single bin i. Obviously we need to move at least |S_i - T_i| either from or into this bin. This applies to all bins. Since a single move can affect at most 2 bins, we get a lower bound on our answer: the sum over |S_i - T_i|, divided by 2. We claim that this is always possible.

Indeed, if S_i is less than T_i, it means that there are more balls in the final configuration. Hence, Gogo can simply pick balls from another bin j such that S_j is greater than T_jand put it here. There must exist such a bin, since T is a permutation of S. Hence, in a single move, we have succeeded in decreasing the sum over |S_i - T_i| by exactly 2, namely one each in bin i and bin j.

So, we have reduced the problem. Given a sorted sequence T, find a permutation S of it such that the sum over |S_i - T_i| is maximum. This is quite easy.

Absolute difference

We want to maximize sum of |S_i - T_i|. Now, consider an element of T = T_i. Since S is a permutation of T, this element will appear in this sum exactly twice, one as T_i, one as S_j, for a particular j. Furthermore, in |A - B|, there are two possibilites. Either |A - B| = A - B, or |A - B| = B - A. The important thing is, |X - Y| means that X will appear in the final summation as either +X or -X.

Now consider T_i. We’ve argued that it’ll appear twice in the summation. Both occurrences can either appear as +T_i or -T_i.

In a single |A - B|, exactly one of them will appear positive and exactly one of them will appear negative. Hence, in the summation of |S_i - T_i|, exactly N terms must appear positive and exactly N terms must appear
negative.

Recall that each T_i will appear exactly twice in our summation. Since we want to maximize |S_i - T_i|, we want the largest N terms to be positive and the smallest N terms to be negative. This is clearly the maximum possible answer, should there exists such sequence S that has this property. It turns out that such sequence is always possible.

If the number of elements is odd, the two occurrences of the middle element in our summation will be one positive and one negative (according to the paragraph above). Hence, we can let S_i be equal to T_i and it’ll have this property. So, suppose the number of elements is even. Then, the first half of T should have both occurrences negative, and the second half of T should have both occurrences positive (recall that T is given in a sorted order). Clearly this is possible by letting The first half of S be any permutation of the second half of T, and the second half of S be any permutation of the first half of T.

Hence, a possible solution looks as follows.

1
2
3
4
5
6
7
8
ret = 0
for i in 0..n - 1:
  if (i < n / 2):
    ret -= T[i] * 2
else if (i >= n - n / 2):
  ret += T[i] * 2

return ret / 2

References

Any S that fullfills the condition we stated before will maximize our sum. One of this is to reverse T, as can be found in AlinaPNTU’s solution.

Finally, since n ≤ 10, trying all possible 10! possible permutations is possible. Consult vasja_p’s solution.

Remarks

… I guess I did it. Does it break record as the longest possible statement for a d2-250? But perhaps not, since most of the paragraphs are short. Incidentally, this problem was proposed as a d2-250 in SRM 527, alongside with the d1-hard problem (it was proposed as d1-med back then).

Anyway, this is a really hard problem (relative to other d2-250 of course) - in my opinion. But all problems in the division 2 this time is sort of evil (but nice! but evil! but nice!), so this one fits nicely in the (accidentally) “evil” theme of this SRM >:).

GogoXCake

Used as: Division Two - Level Two:

Used as: Division One - Level One:

Solution

Let’s suppose John really eat the cake using the cutters. We will show how we can reach contradiction if he didn’t actually do that.

Consider the topmost row of the cake that contains at least one ‘.’. Consider the leftmost ‘.’ in that row. Since this is a ‘.’, it means that John must’ve eaten this. Furthermore, by the way we pick this ‘.’, there are no more ‘.’ to the left or to the up of this cell in the cake. What are the possible positions of the cutter that John may have used to eat this cell?

Consider the topmost row of the cutter that contains at least one ‘.’. Consider the leftmost ‘.’ in that row. We claim that this ‘.’ in the cutter is the only possible cell of the cutter that John may have used to eat the cake at our cell. The proof is by supposing not. Suppose this cell in the cake was cut by another cell X in the cutter. Then, since we didn’t use the cell in the cutter that we described earlier, there must exist another ‘.’ in the cutter either to the left of X or in the row above from X. However, in the first paragraph, recall that we pick the cell such that there are no more ‘.’ to the left or to the top of the cell. Hence, X must coincides with a ‘X’ in the cake. However, a ‘X’ in the cake means that that cell was never cut, a contradiction.

So, there’s only one possible way for that cell to be eaten. Hence, since this is the only possible way to do that, we are safe to undo this action, and repeat. So the algorithm goes like this.

1
2
3
4
5
6
7
8
9
10
while (true):
  if all cells in cake are 'X':
  return "YES"
find the top - leftmost '.' in cake.
find the top - leftmost '.' in cutter.
align the cutter with the cake in this position.
if all used cells in the cutter coincides with '.':
  undo the cut
else:
  return "NO"

Implementation Details

There are a couple of possible implementations of that algorithm. The most ubiquitous implementation is by aligning the cutter on the cake from top-left to bottom-right, and in each position, check if all used cells in the cutter coincides with ‘.’ in the cake. In that case, undo the cut. Finally, when done, check if the cake contains a ‘.’. In that case, the answer is “NO”, otherwise it’s “YES”. To see the correctness, you can equatize this algorithm with the algorithm that we described earlier by seeing how their outputs match in both “YES” and “NO” cases. For example, consider Pasqual45’s solution.

Remarks

Some coders thought that the constraints forces cutter[0][0] as a ‘.’. By coincidence, no example contradicts this. This is unintentional. Initially, this problem does not have the: “all borders contains ‘.’” constraint, and has an example to exemplify this (in particular, cutter[0][0] is ‘X’ here). However, testers think that this may lead to confusion and so we remove it. Unfortunately, it turns out that on all other examples, cutter[0][0] is ‘.’. I really apologize for this :(.

The original statement has the following sentence: “Unfortunately, John wants a piece of cake”. That’s confusing, so it’s deleted. But I grow fond of that sentence for some unknown reason :)

GogoXReimuHakurai

Used as: Division Two - Level Three:

The solution is exactly the same with D1-medium. In the D1-medium, the graph is a general graph instead of a Directed Acyclic Graph as in this problem. Also, the actor is not “Reimu Hakurai” but “Marisa Kirisame”. Aside from that, they are the same and so, please see the editorial for D1-medium instead. However, it is arguably easier to come up with the solution if the graph is assumed to be a directed acyclic graph and hence, we differ the D1-med and D2-hard.

Remarks

Pretty amazingly, even though 100+ coders submitted solution to this problem, none is correct. I think this is thanks to the weak examples. I deliberately used weak examples in greedy problems in Division 2 since most Division 2 coders tend to use whatever greedy algorithm that comes to their mind without proofing its correctness. Hence, if we design the examples to be too strong, we are afraid that coders will use the “While not pass example, try another algorithm” algorithm to solve this problem. I don’t like that algorithm very much.

Note that since the solution to this problem is exactly the same with the D1-medium, it is very unlikely that the author’s intended solution is wrong.

GogoXMarisaKirisima

Used as: Division One - Level Two:

Nice graph

If stage N-1 is not reachable from stage 0, the answer is clearly 0. Also, if we can’t reach a stage i or if stage N-1 is not reachable from stage i, then clearly any of our playthroughs will never visit stage i.

So, in the following discussions, we assume that:

• All stages are reachable from Stage 0.

• Stage N-1 is reachable from all stages.

Trivia: admins call this a “nice graph”.

Finally, assume that our nice graph has at least 3 nodes. C’mon, the N=2 case is pretty obvious.

Nice solution

Okay, so under our assumption, the solution is one line. Suppose the number of stages is N and the number of choices is M. Then, the algorithm would be:

1
return M\ - N + 2

Um… yeah… um… okay… um… why?

Uh proof

There are (N-2) other stages aside from stage 0 and stage N-1. Since we want to maximize the number of playthroughs, at the end of all playthroughs, all these (N-2) stages must be visited in at least one playthrough. We will now assign each stage a state of either “visited” or “not visited”. Initially, all stages are “not visited”. If a playthrough consists of visiting a stage, then that stage becomes “visited”.

M, the number of choices, is an obvious upper bound on our answer. The reason that we cannot have exactly M playthroughs is because of the N-2 stages. If a stage is “not visited”, then a playthrough that visits this stage for the first time will use a new choice to lead to this stage, and another new choice that leads out of this stage.

Claim: We can have M - (N-2) playthroughs

To see this, imagine the (N-2) loss in the number of playthroughs as “cost” to turn a “not-visited” stage into “visited” stage. That is, we claim that there exists a series of playthroughs that can transform all “not visited” stages into “visited” stages by losing only (N-2) choices. It’s as follows.

While there is a “not visited” stage, pick one that is reachable from a “visited” stage VIS through exactly one new choice (there must exist such stage since we assume our graph to be nice). Because VIS is “visited”, we can reach this stage using only used choices. Then, we use this choice to move to our “not visited” stage. From here, we pick any simple path that leads from this stage to either stage N-1 or another “visited” stage such that the stages in our simple path (except the last) are all “not visited”. There must exist such path since our graph is nice. From the last node, since it’s “visited” or N-1, there exists a path from that stage to stage N-1 that uses only used choices. And this completes our playthrough.

What is the result of that playthrough? The only place where we used new choices is in the simple path. Furthermore, since all nodes in the simple path except the first and the last node are “not visited”, all choices are new. Suppose there are K “not visited” nodes in this simple path. Then, our playthrough used exactly K+1 new choices. However, as a consequence, K “not visited” stages are transformed into “visited” stages. Hence, this is in line with what we claim, since we are able to turn K “not visited” stages into K “visited” stages by losing only K new choices (remember that this is a playthrough and hence, we deduct 1 from the K+1 new choices we make).

After we are done, all stages are “visited”. We can then proceed to create a new playthrough for every new choices left, and since we only lost (N-2) new choices, we have M - (N-2) playthroughs.

We must have at most M - (N-2) playthroughs

This is a consequence of the fact that if we perform the maximum number of playthroughs, all stages must be “visited” in the end. Initially, we have N-2 “not visited” stages. The first time a playthrough visits this stage, it must use a new choice. Furthermore, it must still use at least one new choice to lead it out from this stage. Hence, each “not visited” stage lost at least one new choice and hence, the maximum number of playthroughs possible is M - (N-2), since (N-2) is the initial number of “not visited” stages.

And that’s it!

So, because there may be at most M - (N-2) playthroughs, and we have shown the existance of that playthroughs, we can safely say that the answer is M - (N-2). pieguy’s solution clearly illustrates this short solution.

Harder version

Assume the graph is nice. Suppose that the playthroughs may begin not in stage 0, but in any stage given in an array. Furthermore, the playthroughs may end not in stage N-1, but in any stage given in another array (not necessarily disjoint with the first array). What is the maximum number of playthroughs possible?

For example, suppose the available choices are:

1
2
3
4
0\ - > 1
1\ - > 2
2\ - > 0
3\ - > 4

The possible starting stages are:

1
2
3
{
  stage 0, stage 3
}

The possible finishing stages are:

1
2
3
{
  stage 0, stage 1, stage 4
}

Then, the maximum number of playthroughs are 3:

1
2
3
0\ - > 1
0\ - > 1\ - > 2\ - > 0
3\ - > 4

Not a hint: This is harder to proof and no longer 1 line.

Remarks

The original problem proposed has this graph nice-ness in the statement. However, we decided that one-line answer is too crazy (literally) for a D2-hard and D1-medium. I mean, c’mon…

For all die-hard Touhou fans, the names is an intentional typo to avoid copyright infringement. So it’s not a mistake :). Reimu Hakurei and Marisa Kirisame are the main “protagonists” of Touhou and have a rather… eccentric personality and reasons to “fight”.

By the way, Touhou Project is a very infamous game that asks players to dodge umm… bullets. But the amount of bullets is huge that it was given the name “Bullet Hell”. I personally like to call it “Firework” (officially, they call it “Spell cards”). Oh okay, why are we suddenly talking about this game?

Trivia: Everything in Touhou Project (music, graphics, code) is developed by one man only.

GogoXBallsAndBins

Used as: Division One - Level Three:

When I’m writing this, I have no idea how to explain this problem.

Minimum number of moves

If we know S and T, what is the minimum number of moves? We just state without proof that it’s equal to the sum of |S_i - T_i|, divided by 2. It’s not because I’m lazy (mind you ;) ), but because it’s quite easy to see and I have explained it in the editorial for the D2-250 problem (yes, believe me, this particular author is “evil” enough to put this “kind” of problem as D2-250 >:). I can’t believe it myself).

We will call the above sum the ANSWER.

So, we now ask. What is the number of permutations of T such that the above sum is equal to moves * 2?.

The answer

Skippable note: If you have read the editorial for D2-250, you will get deja vu. (Yes, this particular author is “evil” enough to put a similar explanation of the hardest problem in the match inside the easiest problem in the match >:). I can’t believe it myself).

So, let’s transform this problem (provided by again… rng_58). Imagine we have two rows of numbers as follows.

We have to pair the numbers in the bottom row with the numbers in the top row. For each pairing (T[X], T[Y]), the score is T[max(X, Y)] - T[min(X, Y)]. By the way how we construct the table, max(X, Y) is the rightmost element amongst the two.

The solution is by Dynamic Programming.

The state

We will proceed from left to right in the table, pairing the elements of the table as we sweep them left to right.

We let (POS, WAIT_UP, WAIT_DOWN, SCORE) be our state. It means roughly that we have processed all columns before T[POS], and there are exactly WAIT_UP elements of the top row preceding T[POS], to be matched with an element of the bottom row, not preceding T[POS] (similarly, WAIT_DOWN for elements of the bottom row). Our current ANSWER is SCORE.

Here’s what we do. At our state, we want to try to pair the two elements in column POS. Consider the element in the top row. There are three possibilites:

• It can be paired with an element of bottom row that we have processed.

• It can be paired with an element of bottom row that we have not yet processed.

• It can be paired with an element of bottom row that we are currently processing.

The trick is, if we consider the second possibility, we do not necessarily to make the decision with whom we will pair it with. This is because since it has not yet been processed, it is located to the right of the column and hence, we can determine that the score that this element will contribute to ANSWER is -T[i]. That is, the score does not depend on the exact value of its pair, it only depends that its pair has a higher value that T[0].

Similarly, if we consider the first possibility, the score it will contribute to ANSWER is +T[i].

Finally, we can similarly treat the element in the bottom row like that, and we now have five possibilities. So, our transition from (POS, WAIT_UP, WAIT_DOWN, SCORE) looks like this.

• There is one way to pair the above T[POS] with the lower T[POS], reaching state (POS+1, WAIT_UP, WAIT_DOWN, SCORE).

• There are WAIT_DOWN ways to pair the above T[POS] with one of the unpaired bottom row elements, and to pair the below T[POS] with an element we have yet to process. Note that SCORE will be unchanged since one T[POS] will contribute as a positive number, while the other as a negative number. Hence, this will reach state ( POS+1, WAIT_UP, WAIT_DOWN, SCORE).

• Similarly, there are also WAIT_UP ways to reach state ( POS+1, WAIT_UP, WAIT_DOWN, SCORE).

• We can also pair both elements to unpaired elements. There are WAIT_DOWN * WAIT_UP ways do to so, and we will reach ( POS+1, WAIT_UP-1, WAIT_DOWN-1, SCORE + 2 * T[POS]).

• Finally, we can pair both elements to elements we have yet to process. Since we don’t assign the pair now, there’s only 1 way to do that. Hence, we will reach ( POS+1, WAIT_UP+1, WAIT_DOWN+1, SCORE - 2 * T[POS]).

Finally, notice that WAIT_UP and WAIT_DOWN will always be equal (as you can verify from the transitions). Hence, we can compute the value of our state bottom-up as follows.

1
2
3
4
5
6
7
8
9
10
11
(POS = 0, WAIT = 0, SCORE = 0) = 1
for POS = 0 to N - 1:
  for each(POS, WAIT, SCORE) > 0:
  (POS + 1, WAIT, SCORE) += (POS, WAIT, SCORE)
  (POS + 1, WAIT, SCORE) += WAIT * (POS, WAIT, SCORE)
  (POS + 1, WAIT, SCORE) += WAIT * (POS, WAIT, SCORE)
if (WAIT > 0):
  (POS + 1, WAIT - 1, SCORE + 2 * T[POS]) += WAIT * WAIT * (POS, WAIT, SCORE)
  (POS + 1, WAIT + 1, SCORE - 2 * T[POS]) += (POS, WAIT, SCORE)

return (N, 0, moves * 2)

Since SCORE can be between -100 * N to 100 * N (recall that the maximum value of T[i] is 50) our total complexity is N * N * (200 * N), which will definitely fit the time limit. msg555’s solution is similar to what we have described, but it is constructed top-bottom instead.

Remarks

This is probably the easiest D1-hard that I’ve ever authored. Indeed this problem was originally proposed as a D1-medium (in SRM 527), which is evil. Indeed if you may recall, the hard problem in SRM 527 was only solved by 2 people. If you put this problem as a medium, wow, I can see a pretty ugly aftermath ;).

The examples weren’t ultra strong. This is since we thought this problem is easy and it’s not necessary to give ultra strong examples. I had my doubts, but I think it’s okay since if it’s easy, then challenges may as well come to play. Besides, I don’t know if there’s any corner cases in DP problems anyway.

UPD: Okay, after the match, I guess we underestimated everything again. So, this is definitely not the easiest hard I’ve authored. Before the contest, I predicted 100 corrects on 500 and 30 corrects on hard, which is very far off. :/