When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

dolphinigle's blog

By dolphinigle, 13 years ago, In English

Time Capsule Remarks (planted before the contest)

Due to popular demand, today's problem statements are made to be as short as possible without too many (but existing!) embellishment. All of them are thinking-based problems (i.e., implementation is the easier of the two) - so I'm generally happy with the problems :). I hope nobody found them to be too easy :S

As you may have noticed, we decided not to give devastatingly weak pretests. I guess it's just really evil to give weak pretests for my first match.

And so, the editorial begins...

Remarks

I'm sorry - but I don't have access to my usual graphic editing tool and so, the graphics are fairly limited :) (Example: Lawnmower's pictures must be the ugliest lawnmower I have ever seen! (Is it even a lawnmower?) Not to mention I don't look like the actor at all...)

D2-A: Tram

If we know the number of people inside the tram at all possible time, then the answer is the maximum of such. We observe that the number of people inside the tram changes only at tram stops. The conclusion is that the answer will be the maximum of the number of people inside the tram directly before arriving at a particular stop and directly after leaving a particular stop (the more observant readers can notice that using only one of these is sufficient).

It's sufficiently easy to calculate the number of people inside the tram directly before and after leaving a tram stop.

D2-B: N Little Pigs

No... not maximum matching ;)

So, an equivalent less-evil rewording of the problem would be: "Return the number of wolves that are adjacent to at least one pig".

To see this, since each pig has at most one wolf adjacent to it (the constraints impose that) we don't need to worry at a single pig may get eaten by two different wolves. Hence, each wolf can eat any of the pig adjacent to it.

Remarks

It's more interesting to reverse this problem isn't it:

Each pig will be adjacent to at most one wolf

becomes

Each wolf will be adjacent to at most one pig

Can you solve this one? (Of course, not using network flow mind you ;) - that's overkill)

D2-C / D1-A Party

We let an employee without a manager called as root. There's an edge from a manager to an employee that he/she manages.

First notice that the graph is a collection of directed trees. Hence, we can assign a depth label to each node - denoting the number of nodes on the simple path from the root to it. The answer is then the maximum depth a node has.

Why?

First, the answer is bounded below by this number because any pair of employees in this path cannot be in the same group. Second, since the graph is a tree, each node in the graph has a unique depth label assigned to it. Simply put all nodes with the same depth in the same group. It's fairly easy to see that no one will be the superior of another within a group, for otherwise their depths will not be equal.

Remark

You might notice that there exist an O(N) implementation of the above algorithm, yet the constraint is 2000. Well, this problem was swapped with the D1-B because the previous D1-A was thought to be harder than expected. And so, in the process, we also decrease the constraint for N from 200,000 to 2,000. I hope you like it :)

D2-D / D1-B: Lawnmower

First, let's observe a particular strategy that turns out to be optimal at the end of our discussion.

Suppose we're on a row, facing right. This strategy say that we need to move to the right as long as there is a weed to the right of us either on this row or on the row directly below us.

The idea is that we need to mow that weed, hence, we need to move there. If it's in the same row as us, it's fairly obvious we have to mow that before going down. If it's at the row directly below us, since we can't move to the right in the row below us (since we'll be facing left there) we need to move there before going down.

The strategy then says that if we no longer need to move right, we go down, and face left. Repeat this until all weeds are mowed (replacing left and right in the discussion above) - and we have our strategy.

This strategy is optimal. Proof is using induction - but it's not particularly interesting, so the idea is given instead.

Suppose we're on a row, facing right, again. If there exist a weed to the right in this row or below us, then any solution will necessarily move right as far as our strategy goes (for the reason we discussed above). Some solution however choose to go further right despite having no weed in this row or the row directly below us. This solution is not optimal if we need to go left directly after going down, for we can just simply go down instead of going right-down-left. On the other case, if we don't need to go left directly after going down, then it means that we go down twice-in-a-row! Hence, instead of moving right in this row, we go down twice, then move right there. And then the induction can continue and the proof can follow.

Remarks

I guess the actor should be Toastman instead :).

Anyway, so sorry to disappoint you, but we decided to add some pretty strong pretest to this problem, despite the fact that many solutions will probably forget to take care of two consecutive empty rows. But still, the pretest we gave only consist of one column, so feel free to hack the stragglers :) (not that this suggestion matters after the contest but still...)

D2-E / D1-C Plumber

To solve this problem, let's imagine that the left and top sides of the grid also determines whether the pipe adjacent to that side has an end connecting it to the side or not. There are 2^(N+M) ways to pick them. We claim that if we fix them (i.e., pick one of the possible 2^(N+M) ways, then the entire grid's pipes are fixed).

To see this, notice that each pipe segment will have either one vertical end (it either have end on the top or end on the bottom) and one horizontal end (left or right). We can pick any 4 combinations of them. Suppose we pick a row, and determine whether the leftmost pipe should have an end to the left of it, or not. Suppose it doesn't have an opening to the left. It means that the leftmost pipe should have an opening to the right, the next pipe should have an opening to the left, the next pipe to the right, and so on. Continuing this way, we have fixed the horizontal ends for an entire row - and only that. Hence, if we pick one of the possible 2^(N+M) ways to pick the ends, then the horizontal ends of each row and vertical ends of each column is fixed. Since there is exactly one pipe segment that has a particular configuration of ends, there is exactly one possible completed grid for each of the 2^(N+M) ways to pick the ends.

Hence, the solution works by first checking if a solution exists. Any pre-assigned pipe simply sets whether or not its corresponding row and column has an end at the left and top side. We need to check that no two pipes sets this value contradictorily. If any of them are contradictory, then we return the answer as 0. Otherwise, we return 2^(number of rows without preassigned cell + number of columns without preassigned cell).

D1-D Unambiguous Arithmetic Expression

This problem is solved using Dynamic Programming. The somewhat straightforward dynamic programming is to represent the state as {start_pos, end_pos}, which represents the number of unambiguous arithmetic expression on the substring of the input starting at start_pos and ending at end_pos. This however has a complexity of O(N^3) and is not suitable for our problem.

The solution uses the state {pos, braces}. This state is somewhat tricky to explain. This means that we have read the first pos characters in the input. We're expected to read a single unambiguous arithmetic expression, close it with some number of brackets that we don't care (to be explained below), and then, if braces is zero, that's it. Otherwise, we're then expected to read a binary operator (either + - * or /), then open a bracket, then move the state to {pos + some_value, braces-1}. That is, braces keeps track on the number of second operands of binary expression that we need to make.

For an example how this works, let's try to solve a particular test case:

"++0*+1"

Let's denote with quotes the part of the input that we haven't processed. We're going to create the unambiguous arithmetic expression by scanning it left to right and making some choices.

There are three choices:

1) Create a unary expression. In the example above,

"++0*+1" -> +("+0*+1"

We don't really care about where the closing bracket is yet.

2) Create a binary expression. In the example above,

+("+0*+1" -> +(("+0*+1"

How does this tells that we will need to create a binary expression? The second open bracket does not have any operator preceeding it. The only thing that can makes this a proper prefix of an unambiguous arithmetic expression is that if this bracket belongs to the first operand of a binary expression.

For our example, we suppose we read another unary expression

+(("+0*+1" -> +((+("0*+1"

3a) Read an integer. In our example above,

+((+("0*+1" -> +((+(0))*("+1"

There are two questions. a) how do we know the number of closing brackets we have to make? This is actually easy - for every open bracket we have, if it's for a unary expression, we simply close and repeat. Otherwise it's a closing bracket for possibly the first operand to a binary expression, so we close it, and we read a binary operator (* in the example above), and try to read the second operand of the binary expression.

Finally:

+((+(0))*("+1" -> +((+(0))*(+("1"

3b) We try to read an integer again and we have no open brackets that belongs to the first operand of a binary expression, and we have ourself a possible answer.

+((+(0))*(+("1" -> +((+(0))*(+(1)))

So, in the state {pos, braces}, pos determines the starting location of the remaining unprocessed input. braces indicates the number of open brackets that belongs to a binary expression. So, in the examples above:

1)

"++0*+1" -> +("+0*+1" is represented by

{0, 0} -> {1, 0}

More specifically, for unary expressions, {pos, braces} -> {pos+1, braces}

2)

+("+0*+1" -> +(("+0*+1" is represented by

{1, 0} -> {1, 1}

More specifically, for binary expressions, {pos, braces} -> {pos, braces+1}

3a)

+((+("0*+1" -> +((+(0))*("+1"

{2, 1} -> {4, 0}

More specifically, {pos, braces} -> {pos + length_of_integer + 1, braces-1}

3b)

+((+(0))*(+("1" -> +((+(0))*(+(1)))

{5, 0} -> Done

More specifically, {pos, braces} -> done if braces is zero and the remaining input forms a single integer.

Remarks

My favorite problem of this match (because it's hard-to-think and easy-to-code) ;). This turns out to be the hardest problem of the match.

During the match, three coders (shikivan.popelyshev, and watashi) submitted solutions which I think works in N^2. Petr submitted a solution that (I think) uses Catalan number, while Egor submitted a solution which uses polynomial to quickly count each of the dp values (see his comment in the Editorial). tourist submitted a solution which uses a highly-optimized inner loop with no branching and expensive operations (only a single multiplication) - he cleverly avoid branching in his code.

D1-E Races

We process the roads one by one. Associated with each road is the races whose UBi is that road (i.e., races that 'ends' at that road). We will discuss the Dynamic Programming solution first, then improve it with a data structure into the optimal solution.

Let's say we're going to process a road. Our state is this : DP[X] is the maximum possible profit such that the last X roads before this road are fixed and the X+1-th road before this road is NOT fixed. We are going to compute the value of DP for the next iteration, let's call this FUTURE. FUTURE[0] is obtained if we don't fix this road, FUTURE[0] = maximum amongst the value of DP. Otherwise, if we decide to fix this road, then for each of DP[X], FUTURE[X+1] >?= DP[X] - cost to fix the road + all races' profit that ends at this road and whose starting point is not before X roads from current road (i.e., all the races that is contained and ends at this road). This should work in N^2 + N * M. It can be improved to N^2 + M

The data structure approach is slightly different. We will use a segment tree that allows finding a maximum value in a subset and modifying the values of a range, all of which should work in either O(1) or O(log N). The segment tree will consist of N+1 leaves. However, not all the leaves are active at the start of the algorithm. At the start, only one leaf is active and it corresponds to the initial value of DP[0]. Next, we can compute the maximum value amongst all active leaves in O(log N). Then, we create a new active leaf that corresponds to FUTURE[0]. This will be located in the same tree however, the values represented by the leaves will be shifted one to the right - this is done implicitly (for example, we use the last node as DP[0] for the first iteration, but treat it as DP[1] for the next, and so on). These shifted values will correspond to FUTURE[X], since we notice that FUTURE[X] = DP[X-1] - cost to fix the road + races that this series contains and ends at this current road (i.e., it's value directly depends on the leaf BEFORE it was shifted). Next, we decrement the value of all these new leaves (except FUTURE[0]) by the cost to fix the road (in O(log N)). Finally, for each race that ends at this road, we increment the value of the leaves that contains this race. This will be continuous, i.e., FUTURE[X] for X in [race_len, INFINITY]. This can also be done in O(log N). Since a race ends at at most one road, the total complexity this will contribute is M log N.

The answer will then simply the maximum value amongst all members of the tree.

Remarks

This is one of the problems I submitted to this year's IOI but didn't got accepted - I sort of agree that this doesn't suit IOI very well. IOI likes a non-numeric output :) #goparrots!

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Very fast editorial :")
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
So fast! I love it!
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I love the D2-E problem! The solution is so easy, but only few people have solved it.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Very nice problems :)
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
D2-D / D1-B: Lawnmower : Any ideas how to solve if we are also allowed to move up ( and flip direction ) ? For the original version we try moving row-by-row. If we also try column-by-column and take minimum of these two, does it solve the modified version ( i.e., additional move-up step ) ?
13 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

There's also an alternative solution for D1-E races.
One can model this problem as a minimum cut problem with an m by n bipartite graph. (there are also sink node and source node on each side)
Then it's possible to solve mincut using greedy strategy using heap.
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Your solution is really great, would you give more explanation about the greedy strategy with heap? 'cause I still can't figure out your code, though it's simply enough.
    • 13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      One must find minimum cut (= maximum flow) in a convex bipartite graph. You just need to process vertices in the end-of-the-race order and (greedy) find all augmenting paths from a particular vertex... This way you can find maximum flow using at most n+m paths.
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What are then the weights of the edges?
13 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem DIV 1 Problem E.. I use a naive Maximum Weight Closure of a Graph algorithm during the contest ...
.( which fail at the system causs I don't have enough memory to store the edges.)..

I wonder is there any method to build a spase Graph on this problem.

PS: D is a good problem ... and it seems harder than E for me ..





13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Missing links for the problems.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For Pigs and Wolves: what if "Each wolf will be adjacent to at most one pig"?
Then the answer is the number of pigs that have a wolf as a neighbor.  Correct?

For Lawnmower I'm glad there was a pretest where the bottom rows didn't contain weed. :)

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I enjoyed this contest a lot  .. Hope to see more CF rounds by you :) 
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Very nice contest. Neat and concise problem statements, and neat and balanced problems themselves. I too hope to see more matches from you.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Love the contest~~~
D1 C,D,E are all hard-to-think and easy-to-code.
Hope to see more matches from you :D
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't understant problem C div 1 solution. I have 2 tests:
4 1
3
.
.
4

Answer is 4.

And second test:
4 1
3
.
.
2

Answer is 0.
How can we obtain this results? Thanks
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    We need to check that no two pipes sets this value contradictorily. If any of them are contradictory, then we return the answer as 0.

    So, the first pipe segment in your second test say that the topmost segment is a '3', which also say that for that column, the topmost pipe segment in that column must not have an end to the top. However, the last segment ('2') has an end at the bottom. Hence, the segment above it has to have an end at the top, above it to the bottom, and above it to the top. Hence, the second segment says that the topmost pipe in that column must have an end to the top - contradicting the fact proposed by the first segment. Hence, return 0.
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you, now I am understand. I thought, only cells with more than one fixed neighbors may cause contradiction.
13 years ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

I found there is a Insightly Greedy Algorithm For Div 1 Problem E..!..

We imagine that Alice and Bob are two Player on this problem, Alice is going to mmaximize the profit (Defence) and Bob is do oppisite (Attack). We scan the intervial from left to right, and every time, when Bob make a attack Cost[i], ( every road has a cost), Alice will select the left-most "troop" (from intervials that covers i) so that she can save as much strength as possible for the future.
...

This solution is only 200+-ms execution time, and ..
much more easy to implement ..


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

Very nice contest and editorial, but I don't understand the div1-E dp part of the editorial exactly. Of course it's my fault .. Somebody could show me an implementation of that?

I think it would be great if the writer's send their solution in the practice room, because understand the editorials would be easier,

Thank you.

  • 12 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry - I tried to submit but looks like it doesn't show up in the regular standings. I guess this is because I'm the author.


    Anyway you could see any solution that uses segment tree and it's likely to use the DP algorithm above.

    Edit: Plus, my solution is badly written :)
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I failed to understand the actual output of div-2 "C " problem. here mentioned that "Print a single integer denoting the minimum number of groups that will be formed in the party. " .

But in editorial the author said output is the maximum depth instead of minimum groups

I am totally confused.Please someone explane this .

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

    Well, as far as I consider, I think the author meant that we could implement BFS to find out the maximum depth D. Note that when we find out this depth, we in fact have also found a path consisting of different nodes, which has this depth D. If we denote these nodes as a1, a2, ..., aD, then ai is the manager of ai + 1. Thus, if we only have T groups, where T < D, it is obvious that these D nodes can not be divided into these T groups, since at least two of them will belong to the same group. If T ≥ D, then it can be proved that all the people can always be divided into T groups. Therefore, D is just the minimum number of groups.

    Proof for T ≥ D: for a1, a2, ..., aD, we can safely divide them into T groups; while for any other paths a1, a2, ..., at, we have t < D since D is the maximum depth, and thus a1, a2, ..., at can be safely divided into T groups as well.

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

Thanks. good editorial

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

Thanks for the tutorial! I am solving D2-C / D1-A Party question but getting RUNTIME_ERROR, this is my solution can you help?

Thanks in advance.