Sunday, April 9, 2017

A dominator week

First of all, please note that there's still a bit more than 3 hours left in the Google Code Jam qualification. You can still hop on the Code Jam train!

The last week was of the extremely busy type. First off, Codeforces Round 407 took place on Wednesday (problems, results, top 5 on the left, analysis). -XraY- and Um_nik stood out from the pack by solving all problems, and slightly better speed has earned -XraY- his first - but definitely not his last - victory of the week. Congratulations!

A Swiss-resident-only Helvetic Coding Contest 2017 took place on Saturday (results, top 5 on the left). Just like last year, the problems will be used for an online mirror some time later, so I will not spoil you the fun of solving them.

AtCoder Grand Contest 012 took place at the same time (problems, results, top 5 on the left, analysis). -XraY-'s second (but still not his last) victory was more clear-cut than the first one, as he managed to solve five problems fifteen minutes faster than everybody else, and was the only one at the top without any penalty minutes. Well done!

A few hours later TopCoder Open 2017 has taken off with its Round 1A (problems, results, top 5 on the left). With the top 250 active coders receiving a bye into Round 2, the contest has once again given semi-retired veterans a chance to shine, and it seems that ACRush did not forget how to win TopCoder rounds :) Congratulations!

Sunday took off with Open Cup 2016-17 Grand Prix of Tatarstan (problemsresults, top 5 on the left), where -XraY- has earned his third and final victory of the week, this time together with his team - amazing!

Problem E was of the kind that I prefer to give on my own contests, as it makes preparing the testcases very easy: with just two numbers in the input :) On a more serious side, here's what it was about: you are given two numbers n and k. You need to choose the smallest amount of pairs (a,b) such that 1<=a,b<=k for each pair, and such that any sequence of n not necessarily distinct numbers, each between 1 and k, will contain at least one of your chosen pairs as a subsequence.

Can you see the solution? Can you prove it?

Finally, Russian Code Cup 2017 Qualification Round 1 wrapped up the week on Sunday evening (problems, results, top 5 on the left, analysis). Even though the main goal here was to get into the top 200, there was still a scoreboard and it was possible to get the first place - which eatmore did thanks to flawless execution without any incorrect attempts. Way to go!

In my previous summary, I have mentioned a couple of problems. The first one went like this: you are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from i-th tree to the (i+1)-th tree, for all i (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 109+7?

Let's say we picked the edge x-y in the first tree. After we add it to the second tree, a cycle consisting of this edge and the (only) simple path from x to y in the second tree will be formed, so we need to remove any edge in the said simple path to obtain a tree again. This edge in turn will define a path on the third tree where we need to pick an edge to remove, and so on. After we make a full cycle, we need to get back to the first edge.

If we fix the edge we pick in the first tree, we can use dynamic programming to find the number of ways to pick the edge to remove in the first a trees, such that b-th edge of the a-th tree is removed. This dynamic programming has O(n2) states, each state can be processed in O(n) (we need to traverse the corresponding path in the next tree), and we have O(n) outside iterations for the edge of the first tree, so the total running time is O(n4).

However, we can notice that the innermost O(n) is used to support an operation "add a constant to all edges of the tree along the given path". Here's how we can do it faster. Every path in a tree always goes towards the root until we reach the lowest common ancestor, then away from root. Now, instead of having values on edges and adding a constant c to the entire path from x to y, we can have values in vertices in such a way that the value for each edge is computed as the sum of values of vertices in the corresponding subtree, and then in order to add a constant to a path we need to add c to vertices x and y, and subtract 2c from lca(x, y) - just 3 numbers to be updated. This makes handling of each dynamic programming state O(1), and the total running time is now O(n3).

The second problem was: you are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex v of the graph, you have to answer a question: is it true that v is guaranteed to be reachable from vertex 1, no matter which arc we remove?

This problem is closely related to the concept of dominator tree. Here, we would define that arc a dominates vertex v, if one must pass through a when going from 1 to v. Our goal is to tell if there are any dominating arcs for each vertex.

It turns out the following approach (corrected by Shubham in comments below - thanks!) works: assuming we have topologically sorted our graph from left to right, let's compute the leftmost dominating arc (or the fact there's no dominating arc) for each vertex. The computation will also go from left to right, and work like this for vertex u: if for each vertex reachable from 1 that have arcs into u the leftmost dominating arc is the same, then this arc is the leftmost dominating arc for u as well. If that's not the case, but there's just one vertex v reachable from 1 that has an arc into u, then the arc from v to u is the leftmost dominating arc for u (note that in this case v has no dominating arcs).

So far, everything is somewhat intuitive and easy to prove, but here comes the insight: in all other cases, there are no dominating arcs for u! Suppose it's not the case, and some arc a dominates u. We have at least two vertices reachable from 1 that have arcs into u, and the don't have the same dominating arc. Thus a can't be directly incoming to u, and at least one of the vertices that have arcs to u doesn't have a as its dominating arc, which leads to a contradiction since then we can bypass a on our way to u, too.

Thanks for reading, and check back next week!

Saturday, April 1, 2017

A moejy0viiiiiv week

Last week's contests started with Codeforces Round 406 on Thursday (problems, results, top 5 on the left, analysis). Quite surprisingly, this time the winning strategy involved going with the cheaper problem in the end instead of the more expensive one, although that might have involved squeezing through a solution that was not supposed to pass :) Nevertheless, congratulations to moejy0viiiiiv on his amazing non-asymptotic optimization skills!

TopCoder SRM 711 took place on Saturday (problems, results, top 5 on the left, my screencast). This time I've recorded the usual silent screencast, but it didn't seem to improve my results :) There was a moment with about 30 minutes left in the coding phase when I had 1224 points, which would be enough for the second place in this SRM. However, there was quite a bit of uncertainty: the solution I've submitted for the hardest problem was theoretically O(n4) with n up to 300, although it seemed to behave more like O(n3) on random testcases, and even that already took 1.5 seconds.

I've tried to come up with a case where it would time out, could not do that, but it seemed very likely that such cases exist, so I've decided that the authors would see the obvious O(n4) approach and make sure it fails, and implemented and submitted a true O(n3) solution losing lots of points but avoiding the possible loss of all points for that problem. After the contest ended, I've submitted my possibly-O(n4) solution in the practice room, and guess what? It passed the system tests as well. I could have pulled a moejy0viiiiiv :)

The natural question, of course, is this: can you challenge that solution? It should be available in the practice room, submitted by me. The problemsetter mentions a possible idea that could make this solution fail, but I'm wondering if it actually fails in practice.

I should also mention that even without the resubmission I could not challenge rng_58 for the first place, and his solution for that problem was O(n3) from the start. Congratulations on the well-deserved victory!

Here's the actual problem I've talked so much about. You are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from i-th tree to the (i+1)-th tree, for all i (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 109+7?

Open Cup 2016-17 Grand Prix of Poland has wrapped up the week on Sunday (results, top 5 on the left). Makoto continued to be on fire, winning a team contest right after winning the individual one on Saturday. Congratulations again!

This round had several nice problems, but if I have to pick one, it would be problem C. You are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex v of the graph, you have to answer a question: is it true that v is guaranteed to be reachable from vertex 1, no matter which arc we remove?

In my previous summary, I have mentioned a Codeforces problem. You are given a grid with two rows and n columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. n is up to 300000.

First, we can find all rectangles with zero sum. Of course, there might be too many of those, but we can notice that for each "type" of rectangle (row 1, row 2, or both rows) we can find the partial sums from column 0 to column i, and a zero-sum rectangle corresponds to two equal partial sums, and since in the maximum answer there would never be a rectangle that can be split into two, we only need to consider pairing each partial sum with one previous occurrence of the same value, and thus have at most n useful rectangles per type, at most one ending in each column.

That observation yields a straightforward O(n2) dynamic programming solution: we'll compute aij - the maximum number of rectangles that we can choose in the first i cells of the first row, and in the first j cells of the second row. In order to compute this value, we consider whether we take the single-row rectangles ending in columns i and j, and also the double-row rectangle in case i=j. But O(n2) is obviously too slow with n=300000, so how to speed this up further?

The next idea is based on the fact that we currently have too much leeway in constructing the optimal solution. Whenever we pick the single-row rectangles between two double-row ones, we can pick them in any order, and the current solution effectively considers all such ways. But let's assume we always pick them "from right to left": if our current state is (i,j) and i>j, then we'll consider what happens with cell i in the first row, and if i<j, we'll consider what happens with cell j in the second row. If we do that, then the states that are important for computing the final answer have a peculiar property: if i<j, then ajj-1<=aij<=ajj (and similar for i>j), because if aij<=ajj-2, we could have skipped the last rectangle we took in the first row (that led us to i), and get a better answer.

Because of this, we just need to compute the "diagonal" ajj of the matrix, and also for each j find the smallest i that aij is still equal to ajj, and the smallest i that that aji is still equal to ajj, which we can do with binary search to obtain a O(nlogn) solution.

Finally, please note that Google Code Jam 2017 is just around the corner - the qualification round starts on April 7! I'm setting some of the problems this year, and I hope you'll find them interesting.  

A week with two rows

On the Mar 13 - Mar 19 week, VK Cup 2017 started with its Round 1 (problems, results, top 5 on the left, parallel Codeforces round results, my screencast of the Codeforces round with commentary, analysis). Congratulations to Zlobober and zemen on the win!

I've made a second attempt at explaining myself to the camera during the competition, and this time it it went even worse. I've managed to implement an incorrect solution for C before realizing it and rewriting from scratch, and if that wasn't bad enough followed up with doing the same - implementing an incorrect solution that needs to be dropped on the floor - twice for problem D. Maybe talking is indeed incompatible with critical thinking?..

Here is problem D that has stopped me in my tracks. You are given a grid with two rows and n columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. n is up to 300000.

In my previous summary, I have mentioned a cute AtCoder problem. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number k such that n can be represented as a sum of k numbers with non-decreasing decimal representation (for example, 1157888).

The approach I talk about in my screencast is a bit vague, and I like the approach from the editorial more. First, we notice that numbers with non-decreasing decimal representation are exactly those numbers that can be represented as a sum of 9 numbers which consist only of ones (like 1 or 1111; we will also count 0 as such a number with zero ones) - the main Young diagram trick strikes back :) So our goal is to represent n as a sum of 9k such numbers.

Each such number is equal to (10m-1)/9 for some m, so we actually need to represent 9n+9k as a sum of exactly 9k numbers of form 10m. The smallest amount of such numbers needed to achieve 9n+9k is naturally given by the sum of digits in the decimal representation of 9n+9k, and is divisible by 9. We can then repeatedly replace a power of 10 with ten smaller powers to get any bigger amount divisible by 9, up to 9n+9k (when the sum is all ones). We need to achieve 9k which is also divisible by 9, so we just need to check if the sum of digits in the decimal representation of 9n+9k is less than or equal to 9k.

Now that we know how to check any given k, we can use binary search to find the minimum possible value of k. VoilĂ !

Thanks for reading, and check back soon for the last week's summary.

Monday, March 27, 2017

A speaking week

Before I switch to the Mar 6 - Mar 12 week, let me correct a mistake in my previous summary: there was in fact a Codeforces round on Sunday, March 5 - but it somehow disappeared from clist.by, and my memory turned out to be too short :)

Codeforces Round 403 was the forgotten round (problems, results, top 5 on the left, analysis). Right after the round, I was sure that I needed a lot more debugging to get the last problem accepted - but it turned out that I was super close: the only issue was the often forgotten case of a=0 when solving a quadratic inequality ax2+bx+c<=0. In absence of people solving the last problem during the round it was the speed on the first five that mattered, and V--o_o--V was the quickest - congratulations!

Now we can go back to the subject week. Early on Friday, TopCoder SRM 710 took place (problems, results, top 5 on the left, analysis). Just like the previous round, the hardest problem did not budge, and the round was decided on the first two. Congratulations to al13n on the victory!

And finally, AtCoder held its Grand Contest 011 on Sunday (problems, results, top 5 on the left, my screencast with commentary, analysis). Egor has won the contest thanks to a superior strategy, as he went for the hardest problem in the last minutes of the contest instead of the second hardest. Well done!

I have attempted something new for this round: in addition to the screen content, I've included a camera feed in the screencast, and tried to explain aloud what I'm thinking and doing. I had two big hopes when I decided to do that: that I would actually be able to come up with more polished solutions that take less time to code if I explain them aloud first, and that my mumbling will be interesting to the viewers. The results of the round show that the first hope was likely unfounded, so now I'm really curious about the second one :)

As far as problems go, let me highlight problem E. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number k such that n can be represented as a sum of k numbers with non-decreasing decimal representation (for example, 1157888).

Thanks for reading, and check back soon for the next week's contests!

An all-black week

In stark contrast to the previous week, the Feb 27 - Mar 5 week had no contests that I'd like to mention. However, we can of course still discuss the problems I mentioned in my previous summary.

The AtCoder one was concerned with a square n times n matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?

First, we can notice that if a certain column of the matrix is already all black, there's never a need to replace it, since it satisfies the final condition, and it's also the most optimal for other operations as the corresponding cell in all rows will be black.

Second, any other column can become all black only if we have a row that is all black. Moreover, as soon as we have a row that is all black, we should immediately start replicating it to all non-all-black columns (note that the number of non-all-black columns stays constant up to this point). So the problem has been reduced to: what is the minimum number of steps required to make one row all-black?

Now, each operation changes only one cell in each row. So if a row has k white cells, we will require at least k operations to make it all-black. Moreover, if each column has at least one black cell, then we require exactly k operations to make it all-black (since for each cell in this row we can replicate the row that has a black cell in the corresponding column). We can iterate over all rows and pick the one where this number is minimized. So the only unsolved case is when there's one or more all-white columns.

For each all-white column, we need at least one operation to put at least one black cell in it. If the column corresponding to the row we're making all-black has at least one black cell, then we have a row which serves two purposes: when replicating it to an all-white column, we both make it not-all-white, and also put a black cell in the row we're making all-black, so in that case no extra move is needed and we can still make the row all-black in exactly k operations.

Now, the very specific remaining case is: we want to make a certain row all-black, and the corresponding column is initially all-white. Then if we look at the first move that replaces this column, it's clear that the cell on the intersection of the all-black-to-be row and this column will stay white, meaning that we waste 1 move and require at least k+1 operation to make the row all-black. But it's easy to waste exactly one move: we just replicate any non-all-white row to the problematic column as the first move. Of course, if the board is initially all-white then there's no solution.

That completes the solution for this problem. As you can see, each particular step is relatively straightforward and not very hard to come up with. However, one has to stitch together quite a few of those, and that's where the difficulty - and beauty - of this problem lies.

The Open Cup problem was concerned with a permutation of size n. For each number, we can compute its radius: the largest number r such that r numbers to the left of our number, and r numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?

The solution depends on one main insight: let's look for n (the largest number) in the permutation. Since it is the largest number, it "stops" all other radii, and thus the problem decomposes into two independent problems to the left and to the right of this number. Just this idea leads to a O(n3) dynamic programming solution which solves the problem for each segment and tries all positions of the largest number.

Since this was a tiny bit too slow, one needed to optimize this approach. Since the radius of the largest number always reaches either to the left or to the right boundary, and no other radius should cover the largest number, in each segment there are at most two candidates for the largest number: the rightmost position with radius reaching the left boundary, and the leftmost position with radius reaching the right boundary. Since now we have just 2 candidates to check for each segment instead of n, the solution works in O(n2) which is fast enough.

Thanks for reading, and check back soon for the next week's summary!

Sunday, February 26, 2017

A 7x week

This week was extremely packed with competitions - I think this might be the new record for the number of scoreboards in one summary. Consequently, there were a couple nice problems, so if you haven't solved all of this week's competitions (:P), read on!

First off, Codeforces held its Round 399 on Monday (problems, results, top 5 on the left, analysis). y0105w49 and W4yneb0t had a fiery challenge competition and have managed to overtake the only contestant who solved all problems, V--o_o--V. Congratulations to all three!

TopCoder SRM 709 on Tuesday offered the deceptively little 800 points for the hard problem (problems, results, top 5 on the left, my screencast). Just 3 competitors have managed to grab (some part of) those points, and thus -XraY-'s dominating victory is even more impressive!

Codeforces Round 400 on Thursday continued the non-stop week (problems, results, top 5 on the left, analysis). The challenges were not in abundance this time, and thus the coding speed and accuracy came to the forefront. ainta was a tiny bit faster this time, and made fewer submissions that didn't pass pretests - congratulations on the win!

On Saturday, Mujin Programming Challenge 2017 on AtCoder offered monetary prizes for the top performers (problems, results, top 5 on the left, analysis, my screencast). Tourist has claimed the first prize by being way ahead of everybody on the hardest problem - well done!

I think problem B in this round provided a nice way to practice one's skill for dissecting a problem step by step until it becomes trivial. You were given a square n times n matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?

Right after the AtCoder round ended, Codechef held its February Lunchtime 2017 competition (problems, results, top 5 on the left, my screencast). The problems were a bit easier than in other competitions mentioned in this summary, but still provided a nice challenge!

Codeforces Round 402 started at the same time with the Open Cup round (problems, results, top 6 on the left). As a result, many active ACM ICPC participants have skipped the Codeforces Round, but the competition remained fierce. Congratulations to bmerry on finding a unique set of problems to solve and winning thanks to that strategy!

Finally, the aforementioned Open Cup 2016-17 Grand Prix of Wroclaw also took place today (results, top 5 on the left). Problem F was right in the middle by difficulty level, and required a nice observation to come up with a O(n2) solution.

Consider a permutation of size n. For each number, we can compute its radius: the largest number r such that r numbers to the left of our number, and r numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?

Thanks for reading, and check back next week! (which promises to be much calmer)

Monday, February 20, 2017

A casino week

Codeforces Round 397 was the highlight of this week (problems, results, top 5 on the left, analysis). Merkurev has created a comfortable margin for himself thanks to fast solutions of the first five problems and two successful challenges - congratulations on the victory!

In my previous summary, I have mentioned two interesting problems. The first was a TopCoder problem about distinguishing optimal strategy and random play: you are playing a betting game in a casino. You start with a dollars, and your goal is to reach b dollars. You can play at most k rounds. In each round, you bet some integer (possibly zero) amount of dollars not exceeding the amount you have now, then with probability 50% you lose that amount, and with probability 50% you gain that amount. As soon as you reach your goal (have at least b dollars), you leave the casino.

There are of course many strategies to place your bets. In this problem we're concerned with two of them: one is an optimal strategy, where you place each bet to maximize the probability that you will reach your goal by the end of the k-th round or earlier. Note that there might still be several choices for each bet in an optimal strategy that all lead to the same probability of achieving the goal. One of the optimal strategies can be somewhat easily googled. The other strategy we're concerned with is the fully random one: for each bet, we choose the number of dollars between 0 and our amount of money uniformly at random.

Now, you've chosen to use the fully random strategy, and played it to completion (end of k-th round, or getting at least b dollars). An outside observer (who knows the values of a, b and k), however, was assuming that you're actually following an optimal strategy - and did not find evidence otherwise observing your fully random play (in other words, each time you randomly chose a bet that leads to the maximum probability of achieving the goal). What is the probability of such situation?

a and b are up to 100000, and k is at most 5.

A quadratic dynamic programming solution is straightforward: given the amount of money we have and the number of rounds remaining, we will compute what's the probability of winning, and what's the probability that a random play will look optimal. In order to compute those probabilities, we will iterate over all possible bets and see what state to we get into if we win and if we lose.

The key insight required to speed it up is: the probability of winning is always a rational number with denominator 2k (because our play consists of k events each with 50-50 chances). Because of this, it has at most 2k+1 possible values. On the other hand, it's not hard to see that this probability will not decrease if we increase the amount of money we have. That means that for a fixed k, the probabilities of winning for each a form a set of at most 2k+1 segments, each with the same value. And that, in turn, allows to speed up the dynamic programming: instead of considering possible bets one by one, we will consider them in groups: a group is determined by which segments on level k-1 we land on if we win, and if we lose. There will be at most 2*(2k-1+1) such groups, and thus the total running time will be O(b*k*2k) which is fast enough.

The second problem from the previous summary was a purely mathematical puzzle: you are given an undirected graph with at most 200000 vertices and at most 200000 edges. Consider its spanning subsets of edges: such subsets of its edges that connect all its vertices. Is the number of such subsets odd or even?

The solution here is completely magical. It turns out that the number of spanning subsets of edges is odd if and only if the graph is bipartite. A couple of different proofs can be found in this Codeforces thread, but I think they don't fully answer the natural question: what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here.

Thanks for reading, and check back next week!