A doubles week

The March 28 - April 3 week was ignited by Monday's VK Cup 2016 Round 1 on Codeforces (problems, results, top 5 on the left, parallel round results, analysis). Tourist and subscriber left little doubt as to who's the favorite of the entire VK Cup, solving five problems in 1 hour and 6 minutes, while it took other teams at least 1 hour and 41 minutes to do the same!

Just a few hours later, in the early hours of Tuesday morning TopCoder SRM 686 allowed algorithmists from other time zones to enjoy some problem solving (problems, results, top 5 on the left, solutions discussion). jcvb has denied matthew99a his second consecutive win — congratulations to both on great performance!

On Sunday, the penultimate Open Cup 2015-16 round, the Grand Prix of Moscow, challenged teams with some really difficult, if a bit tedious, problems (results, top 5 on the left, analysis). Team SPb SU Base demolished the competition, solving half of their problems in the last hour!

My personal favorite in this round is problem A. Its submission stats: 296 submitted, 0 accepted. And the problem was just about implementing binary search on n choices in log₂(n) time :)

More precisely, one needed to interactively guess a hidden number between 1 and n (which was up to 10⁹) spending at most log₂(n+1)+0.1 steps on average. One guess was asking "is the hidden number less than x?" for any value of x. The guessing was repeated 10000 times with possibly different (and possibly the same) hidden numbers to compute the average.

Where's the catch? In the lack of rounding. Normal binary search requires ceil(log₂(n)) steps in the worst case, and we can't afford that much here. If the hidden number was also random, then we'd get the required number of steps on average — but it's not.

For example, suppose n=6. Normal binary search requires 2 or 3 steps: it starts by splitting the numbers into [1,2,3] and [4,5,6]. Suppose the hidden number is in [1,2,3]. Then it splits the numbers into, say, [1] and [2,3], and in case the hidden number is 1, we've found it in 2 steps, while for 2 and 3 we require 3 steps. We could've split the triple into [1,2] and [3] instead, solving 3 in 2 steps and 1 and 2 in 3 steps, so one might expect that randomizing this choice will make our solution work under our limit of log₂7+0.1=2.907... on average. But on closer examination, we always require 3 steps for the number 2 (and for 5)! So if we're always asked to find 2 or 5, then we will not fit under the required average number of steps.

In other words, for n=6 we have to split the numbers into 2+4 instead of 3+3 sometimes! And to add insult to injury, we also have to take our previous decisions into account as the binary search narrows down. For example, suppose n=5. Most probably we'd start with 2+3 or 3+2 split for the first request, for symmetry reasons with probability 50% for each decision. Note that all numbers are not equal now: if number 3 is hidden, then we'll always get the bigger segment as the answer for our query! So in order to get a good number of steps on average when 3 is hidden, we have to prefer splitting the remaining numbers as [1,2] vs [3], as opposed to [1] vs [2,3]!

This is where our team got stuck at the actual contest :) Can you see how to progress further?

Thanks for reading, and check back soon for last week's summary and this problem's solution!

A toroidal week

The March 21 - March 27 week was much more relaxed than previous ones.

TopCoder Open 2016, one of the most important tournaments of the year, kicked off on Saturday with Round 1A (problems, results, top 5 on the left). Top 250 contestants who have competed in at least one SRM in 2016 have been automatically qualified to Round 2, so Round 1s are often a chance for mostly retired contestants to come back in style. This time it was nika who combined very good problem solving with excellent challenging to get the first place — awesome job! Please tell your friends at MemSQL that they should come back, too :)

The first problem mentioned in the previous summary, about high-school geometry, has an editorial explaining my approach, so I won't go into more detail here. The second problem, though, is worth discussing.

You were given a 8x8 grid, with three points on this grid designated as "houses", and three as "wells". You need to pick a positive integer d<=1000, subdivide each square of the grid into d times d small squares, obtaining a 8d times 8d grid, and then draw nine non-intersecting paths on this grid: from each house to each well. Of course, the problem as stated is impossible to solve since K_3,3 is not planar; to make it solvable, the grid was toroidal: the left edge was identified with the right edge, and the top edge was identified with the bottom edge (picture on the left from the original problem statement).

This problem has two parts: topological and combinatorial. The topological part is concerned with laying out nine required curves on a toroidal square in such a way that they don't intersect; the combinatorial part is placing those paths on a (subdivided) grid.

The key insight for the topological part is that it's actually very easy, and there are a lot of ways to do it. Why? Because we can embed a much more complex graph into a torus: K₇! Because of this, we can adopt the following approach for the topological part: let's draw the paths one by one in random order, and in case we fail, just try again. This is likely to work because there are so many possible topological configurations.

How do we draw the paths combinatorially? Let's start by simply drawing shortest paths using breadth-first search. Of course, this can fail - at some point there will be no path on the grid between the two points that we want to connect. But what can be the reason for that? There are two cases:

1) There's no path even if we forget about the grid restriction - the graph that we have drawn doesn't allow to connect the points, meaning that we've failed topologically.

2) There's a path, but as soon as we try to embed it into the grid, it disappears.

Our goal now is to avoid the failures of the second type. As mentioned above, in case we get a failure of the first type, we'll just restart the process from scratch with a different random ordering of paths.

The key idea now is that we can subdivide the grid as we go, instead of doing this at the start. In other words, first we build paths on the original grid. As soon as we can't build some path, we can subdivide each square of the grid into a 2x2 subgrid. As a result, now there will be free grid points between every two existing paths, and thus it's very unlikely that we can't draw a path because of combinatorial restrictions.

More precisely, the only combinatorial restriction that can still exist after that is around the endpoints of the path. If two existing paths enter an endpoint at 90 degrees to each other, then even after subdividing the grid we can't insert a third path between them. But since we need to draw only three paths for each endpoint, we can fix this issue by restricting the second path to exit it at 180 degrees compared to the first path. Then we will always be able to eliminate combinatorial obstacles by subdividing the grid!

I'm pretty sure there are many other approaches possible in this problem. Please share yours!

And of course, check back soon for the following week's summary, and don't forget to participate in the Google Code Jam 2016 Qualification Round — there are still a few hours left!

A Helvetic week

The weekdays of the March 14 - March 20 week were quite calm, but that was more than compensated by the super packed weekend.

Before we dive further into that March week, though, let me remind you that Google Code Jam Qualification Round starts in a few minutes. Google Code Jam's problems are always among the most interesting (yeah, I'm biased since I help create them, too), so consider giving it a try! You can already register, and the problems will appear in a few minutes. This round lasts for 27 hours, but you don't need to be present all that time - a few hours at a convenient time should work just fine. Good luck!

The competitive programming extravaganza started Friday evening with the Elimination Round of the 2016 CROC Championship on Codeforces (problems, results, top 5 on the left, parallel round results). The deciding problem G, quite surprisingly, involved high-school-style geometry.

You were given a set of 100000 points, and needed to draw a line through some two of them. The line you draw must have the lowest imbalance out of all possibilities. The imbalance of a line is defined as the maximum over all points X on that line of |XP-XQ|, where P and Q are two additional given fixed points.

At the first sight, this looks like a very strange definition. However, as you progress through the layers of this problem, the solution ends up being quite exciting, so I encourage you to try :)

Early on Saturday, Codeforces ran another company round, called IndiaHacks 2016 (problems, results, top 5 on the left). Once again TooDifficult earned the most points; note that he did earn the most in the above CROC round too, he was just participating in the parallel unofficial track — congratulations!

A bit later on Saturday an onsite Swiss competition called Helvetic Coding Contest 2016 took place in Lausanne (results, top 5 on the left). To the best of my knowledge, the problems will be used for an online contest soon, so I will not spoil them.

Instead, I'd like to mention that it's really nice to see such "local" competitions spread all over the world, helping build algorithmic programming communities and thus enabling the enthusiasts to make new friends and discover new opportunities. Thanks a lot for the organizers from EPFL PolyProg for this exciting event!

TopCoder SRM 685 wrapped up the Saturday (problems, results, top 5 on the left). ACRush has continued his climb back to the top of the rankings, but it was matthew99a who did the best this time — congratulations to all winners!

And finally, Open Cup 2015-16 Grand Prix of Baltics wrapped up the week on Sunday (results, top 5 on the left). Without Warsaw Eagles participating, team Past Glory is unstoppable — congratulations on another victory!

Problem B was the most exciting in this round for me. You were given a 8x8 grid, with three points on this grid designated as "houses", and three as "wells". You need to pick a positive integer d<=1000, subdivide each square of the grid into d times d small squares, obtaining a 8d times 8d grid, and then draw nine non-intersecting paths on this grid: from each house to each well. Of course, the problem as stated is impossible to solve since K_3,3 is not planar; to make it solvable, the grid was toroidal: the left edge was identified with the right edge, and the top edge was identified with the bottom edge.

Every time a problem requires one to come up with some not necessarily optimal structure (for example in this problem the paths don't have to be the shortest), the added freedom usually means that the solution requires more creativity than usual, so I hope you will enjoy solving it! To test your solution, you can just generate random locations of houses and wells on the 8x8 grid many times.

I've mentioned two interesting problems in my last summary. The first one was quite unusual:you're given an array of N<=50 positive integers, summing up to M<=1000. For each of N! possible permutations of the array, we compute the value M!/(a[0]+a[1])/(a[0]+a[1]+a[2])/.../(a[0]+a[1]+...+a[N-1]) - dividing M! by the product of partial sums of the permuted array, except the first one. What is the sum of those values over all N! permutations?

First, we try to solve the problem where the first partial sum is not skipped, in other words when the expression above is also divided by a[0]. Instead of dividing the factorial by the partial sums, we'll simply remove the corresponding numbers a[0], a[0]+a[1], ..., a[0]+a[1]+...+a[N-1] from the factorial's product. The last removed number is M=a[0]+a[1]+...+a[N-1], the next one is M-a[N-1], and so on. Which combinatorial objects does such a product count?

Experienced contestants might recognize the pattern of almost-factorial with some numbers skipped. It arises when we try to count permutations by cycles. Suppose we have a permutation on numbers between 1 and M. Consider its cycle passing through 1. There are M-1 choices for the next element in the cycle, M-2 choices for the element after it, which corresponds to our product, and when the number M-a[N-1] is skipped, we say that the cycle goes back to number 1, and then we consider the cycle passing through the smallest untouched number, and so on until we build all cycles.

So our product counts permutations where the cycle passing through 1 has a[N-1] elements, the cycle passing through the smallest number untouched by the first cycle has a[N-2] elements, and so on. When we sum those products over all permutations of array a, we simply get the total number of permutations with the given cycle lengths (a[0], a[1], ..., a[N-1]), where cycles of the same length also have an order on them.

This is where the key simplification happened: after summing by all permutations of a, we actually have to count combinatorial objects that are easier to describe! To solve the problem, we must now adjust for the divisor a[0] being missing (hint: now instead of counting permutations, we need to sum the lengths of the cycle with the largest smallest number), and learn how to count the sum quickly (hint: dynamic programming with state "how many cycles we've already processed, what is the position of the number that is destined to become the largest smallest number in a cycle").

The second problem from the last summary was more standard, but not less beautiful: you're given two strings of 0s and 1s with at most 10000 characters in each. You're allowed to take any substring of a string which has an even amount of 1s, and reverse it. Can you obtain the second string from the first string?

Let's go from left to right, and find the first positions where the strings don't match: one of them has a 0 in that position, and the other has a 1. Let's find the next two ones in the string that contains 0 there, and reverse the substring starting with this 0 and ending with the second one. Now both strings have ones in this position, and we can continue going to the right.

When would this approach stop working? When there's less than two ones left in one of the strings (and thus in the other, too, if they have the same amount of ones). It's tempting to say that if the sole remaining ones in the two strings match, then we're done, otherwise there's no solution. But how to prove that?

During the actual competition, our team tried to prove this for some time, failed to do so, tried to come up with a counterexample, also failed to do so, and decided to take chances and submit this solution - and it was accepted!

After the competition ended, we were still very much interested to prove why this solution works, and finally found the invariant: if we look at positions of ones in the string, and make an alternating sum out of them (p₁-p₂+p₃-p₄+...), then the value of this alternating sum doesn't change when we flip a string with an even amount of ones in it! And it's quite obvious that this sum is different when all ones match except one.

Thanks for reading, and check back soon for more algorithms!

An inverse combinatorics week

The March 7 - March 13 week was quite busy with competitions. First off, Codeforces Round 345 featured problems from a contest for high school students in Moscow (problems, results, top 5 on the left). Tourist has continued his string of Codeforces victories, despite taking a bit longer than second-placed TooDifficult to solve all problems.

Just a few hours later, TopCoder SRM 684 featured problems by Adam 'subscriber' (problems, results, top 5 on the left). The deciding hard problem presented a very unusual challenge: given a formal description for counting some unknown combinatorial objects, find out which combinatorial objects are being counted and then come up with a faster way to count them.

Here's the problem statement: you're given an array of N<=50 positive integers, summing up to M<=1000. For each of N! possible permutations of the array, we compute the value M!/(a[0]+a[1])/(a[0]+a[1]+a[2])/.../(a[0]+a[1]+...+a[N-1]) - dividing M! by the product of partial sums of the permuted array, except the first one. What is the sum of those values over all N! permutations?

Coming up with the combinatorial description is pretty hard here, so let me give you a vert small hint: what if the first partial sum wasn't missing - in other words, if the above formula was also divided by a[0]? Which objects does such formula count?

To wrap up the week, Open Cup Grand Prix of Tatarstan presented teams preparing for the ICPC World Finals in Thailand one more chance to test their skills (results, top 5 on the left). Team Past Glory has earned another convincing victory, while team Dreadnought from Shanghai JTU was the first among the teams coming to Thailand - congratulations all!

Problem K was a nice mathematical puzzle. You're given two strings of 0s and 1s with at most 10000 characters in each. You're allowed to take any substring of a string which has an even amount of 1s, and reverse it. Can you obtain the second string from the first string?

I'm sorry for yet another long pause, and hope to get back into the rhythm soon, so check back for new posts!

A London week

TopCoder SRM 683 was the first round of this week (problems, results, top 5 on the left). Two successful solutions for the hard problem seems like an unusually high number these days :) jiry_2 has won with a big margin because of being the only one to solve all three - congratulations!

On Thursday, 25 finalists gathered in London for the Facebook Hacker Cup 2016 Onsite Final Round (problems with Facebook login, results, top 5 on the left). The round contained 6 solvable problems, but with quite a few tricks and extremely simple example cases, so the room for failure was huge. Well done to Makoto on avoiding the failures and winning convincingly!

Bruce, who was one of the contestants to solve all 6 problems, only to end up with 0 accepted solutions, explains what happened to his solutions here, and what are the correct approaches here. Let me cover my part of the failure story:

In the problem "Boomerang Crews", I've made a mistake that comes up again and again for me: tried to use a TreeSet as a multiset. In the problem "RNG", I've checked if a vertex has any outgoing edges before actually reading the edges from the input - so all vertices got marked as "no outgoing edges". Finally, in problem "Grundy Graph" my solution was a bit further from the correct one - I forgot to add the reverse edges, and to check if one Bob's vertex is reachable from another.

Failing like this in an important round naturally makes one think about better ways to avoid such mistakes. Bruce mentions that one of his failures was due to an integer overflow, and I've protected myself against that via CHelper plugin's ability to use Cojac library to detect integer overflows in Java at runtime. However, one wonders whether any other bugs mentioned above by myself or by Bruce are preventable by building better tools?

One relatively straightforward idea I had was to define a TreeSet class in my library which raises an exception when trying to add duplicates, and tune IDEA's auto-completion to offer it above the system one. In most cases where ignoring duplicates is a good thing, a HashSet is a more natural fit, and adding duplicates to a TreeSet seems to be a mistake more often than not.

Please share your suggestions!

A strategic week

The last week started with the middle-of-the-night SRM 682 on Tuesday (problems, results, top 5 on the left). Continuing the recent trend, the hardest problem did not crack, and the winner was decided during the challenge phase, where subscriber has squeezed the victory - congratulations!

The week ended with two contests on Sunday: first, the Open Cup Grand Prix of Bashkortostan catered to the team contest lovers (results, top 5 on the left). Past Glory team was unstoppable once again, making just one incorrect attempt over 12 solved problems!

Problem F's statement is so short that I'll quote it verbatim: "For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice". The graph had 300 vertices. Is this a textbook problem?

And finally, Codeforces hosted the Final Round of 8VC Venture Cup 2016 for those who prefer to compete on their own (problems, results, top 5 on the left). The round had a $2500 prize for the first place, which tourist has won convincingly thanks to some super fast problem solving - great job!

My story in this round is all about strategy and tactics. Having solved problem A, I've read the statement for problem B first, which looked quite tedious, so I've decided to check other problems. Having read problem C, I've realized that it's a well-known problem which I don't remember the solution to, so solving it at this point would put me at a disadvantage. Finally, problem D also looked tedious but at least brought 2x more points than problem B.

I've glanced at the scoreboard at this point, and it turned out that tourist has already submitted B. It was pretty obvious at this point that following his strategy would not give me a win, since he was quite a bit ahead in time, so in order to win I needed a different strategy, so I've decided to implement D, then E, and then attempted F. My hope when starting F with almost 1 hour to go was to solve it, and then come back to either B or C, while tourist would not be able to finish F in time because he'd spend a lot of time on A-E.

My prediction about tourist's result turned out to be correct, but I couldn't execute on my strategy - problem F did not crack in 1 hour :( After the contest, I required 20-30 more minutes to get my solution to work.

Here's the tricky problem: you are given a tree with n nodes, one of the nodes being empty and other nodes containing all numbers between 1 and n-1 exactly once. One is allowed to add at most one arbitrary edge to the tree, and then move the numbers along the resulting graph, where at each move we can move a number to an adjacent empty node, and the goal is to reach the given ending state from the given starting state in the least number of moves. Implementation details aside, can you find the algorithmic solution in 1 hour?

I hope I won't need to rely on unusual strategies in today's Hacker Cup final round, which starts in less than 2 hours :) There should be at least a scoreboard, and maybe more live coverage at the competition page.

A solution week

The Feb 15 - Feb 21 week, somewhat surprisingly, didn't have any algorithmic contests among the ones that I usually cover. However, let's use this opportunity to dive into the solutions of the problems I mentioned before.

The first one was: you are given a set with 200000 numbers, and need to find the subset of that set where the difference between the mean and the median is the highest. The most tricky part of this problem is the median: unlike the mean, it's hard to update incrementally, so the natural idea is to start by iterating over which number will be the median (let's assume we'll pick an odd-sized subset for now). Having fixed the median, we need to add k numbers smaller than it and k numbers larger than it, maximizing the mean. Now it's easy to see that those numbers should be as large as possible: k larger numbers, plus k largest numbers right before out median in the sorted order. Now, if we iterate over all possible values of k, we obtain a O(n²) solution.

In order to speed up this solution, let's look more closely what happens when we increase k. We add two numbers to our set - the kth largest one, and the kth largest one among the ones before the median. Let's call those two numbers a and b. The mean before adding those numbers is c/d (where d is 2k+1 or something like that), and now it becomes (c+a+b)/(d+2). Is it smaller or larger than c/d? Well, the mediant inequality tells that this number lies between c/d and (a+b)/2. So if (a+b)/2 is larger than the current mean, the mean will increase, otherwise it will not. The final step is to notice that (a+b)/2 is always going down since we pick a smaller number for both a and b at each subsequent step. Because of this, we can see that the mean is a bitonic function of k: first increases, then decreases.

This allows us to use binary search on k, comparing c/d with (a+b)/2 inside to see if we should go to the left or to the right (of course, we could just compare two adjacent means, but that might overflow the 64-bit integer type), and obtaining a O(nlogn) solution for the problem.

The second one was: given a bipartite graph with 45 vertices, find how many subsets of its vertices are vertex-dominating. A subset of vertices is vertex-dominating if any vertex of the graph either lies on this subset, or has a neighbor in this subset, or both.

Given that we have 45 vertices, the logical first step is to pick the smaller of its two parts, which will contain at most 22 vertices. Now we need to find something that works in O(2ⁿ) or similar complexity.

We can now afford to iterate over which subset of this part will be included in the dominating set. Having fixed that, we still have to cover:

1. The vertices in the first part that are not included in the subset.
2. The vertices in the second part that are not adjacent to any vertex from the subset.

Part 2 is easy: we must just include all those vertices into our dominating set. Those vertices, in turn, will cover some vertices from part 1, but there might be some more left over. Now our state is: we have already included some subset A of the first part and some subset B of the second part in the dominating set, the entire second part is covered, and in the first part there's some uncovered subset C which we're still to cover using the some subset of the set D of the vertices of the second part, where D is the complement of B.

This could again be solved via dynamic programming in O(|D|*2^|C|) time, yielding overall O(n*3^n/2) complexity for the entire problem. However, for n=45 that is too slow.

Here comes the most magical moment of this solution: actually, the set D doesn't matter that much, so we can do this dynamic programming just once instead of separately for every A. One might say that of course D does matter, as we can otherwise pick a vertex from B when covering C, and overcount. However, from the construction above we can notice that vertices from B and C don't have any edges between them, and thus don't affect the cover - we can take an arbitrary subset of B in addition to some subset of D. Because of this, we'll actually count each solution exactly 2^|B| times, and we can just divide the result of the inner dynamic programming by 2^|B| to get the required count! Now we have a O(n*2^n/2) solution.

Thanks for reading, and please cheer for me in the upcoming Hacker Cup onsite final round, which is scheduled to begin at 13:30 London time today!