Sunday, September 2, 2018

A Skyglow week

Codeforces Round 497 took place during the Jul 9 - Jul 15 week (problems, results, top 5 on the left, analysis). The last 3 problems were, shall we say, more challenging than usual: only 9 accepted solutions for C, 3 for D, and 0 for E. Yosupo was one of those 12 people, and he solved the right set of problems in the right order to claim the first place. Congratulations!

Just a day later, AtCoder held its Grand Contest 026 (problems, results, top 5 on the left, analysis). yutaka1999 was unbeatable on the day, finishing all problems more than half an hour before anybody else. Congratulations on the dominant win!

I found the last problem very nice: two players play a game on an array of integers ai with at most 300000 elements. The players make alternating turns, and on each turn a player takes a number from the array that is not previously taken. Moreover, when possible, a player must take a number adjacent to a number taken by the other player on the last turn. When taking such adjacent number is not possible (on first turn, or after a player has taken a number which has both neighbors either taken or nonexistent), any number can be taken. The game ends when all numbers have been taken, and each player tries to maximize the sum of the numbers they take. Which sum will each player get if both play optimally?

Thanks for reading, and check back for the solution!

A week without centroids

The Jul 2 - Jul 8 week upped the stakes in the TopCoder Open 2018 race: only the top 50 would advance from Round 3A on Saturday (problems, results, top 5 on the left, parallel round results, analysis). With the hard problem having a much simpler solution than the one the problemsetters have anticipated, the scores were a lot higher than usual, and seeing this simple solution quickly was the key to victory. Congratulations to Blue.Mary on the win!

In my previous summary, I have mentioned a Codeforces problem: you are given a tree with n<=2000 vertices. How many cycles of length 1, 2, ..., k (k<=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered different.

The general approach is somewhat on the surface: let's do dynamic programming that would count said cycles for each subtree. When we're processing the subtree rooted at some vertex v, each cycle either doesn't touch v, in which case it's a cycle in one of the smaller subtrees, or it does touch v, in which case it looks like v->u (some child of v)->some cycle passing through u->u->v->...

In order to be able to count the cycles of each length passing through v, we need to know the number of cycles of each length passing through each of its children, so we need to compute two things in our dynamic programming for each subtree: the total number of cycles, and the number of cycles passing through the root of the subtree.

This gives a rough overview of the solution, but the details of the dynamic programming transition are still unclear: how do we make sure we correctly count the cycles differing only by the starting point?

Each cycle passing through v can decomposed into blocks between consecutive occurrences of v in the cycle. Each such block is obtained by taking a cycle passing through some child u of v, and adding a v->u edge in the beginning and a u->v edge in the end, so for a child cycle of length x the block has x+2 edges.

Actually, to make the previous statement entirely correct in the world where cycles differing by the starting point are considered different, we need to adjust it a bit: replace "cycle passing through v" and "cycle passing through u" by "cycle starting and finishing in v" and "cycle starting and finishing in u". Then our dynamic programming checks out, and we can find the answer for v given the answers for all its children by first adding up the answers for children to obtain the number of blocks of each size, and then doing an inner knapsack-style dynamic programming that counts the ways to combine the blocks.

However, since we have changed the definition of what we compute, we can no longer just add up those numbers to get the overall number of cycles in the tree. Here comes the most magic part of the solution in my opinion: in order to get the overall number of cycles in the subtree passing through v from the number of cycles that start and end in v, we need to just multiply that number by the size of the last block in the inner knapsack dynamic programming!

Indeed, this way we count the ways to choose the starting point within the last block. Why must it be within the last block? Because the cases where the starting point is in another block will be counted when we consider a cyclical shift of the blocks. To look at this from another angle, any cycle passing through v can be transformed into a cycle starting and ending in v by cyclically shifting it so that the first occurrence of v becomes the beginning of the cycle, and the number of ways to get each cycle doing this is equal to the size of the last block.

Here's the relevant part from my solution during the round:

static class Vertex {
    List adj = new ArrayList<>();

    public Description doit(Vertex skip, int k) {
        Description res = new Description();
        res.overallCycles = new long[k + 1];
        res.cyclesFromRoot = new long[k + 1];
        res.cyclesFromRoot[0] = 1;
        res.overallCycles[0] = 1;
        long[] singleStep = new long[k + 1];
        for (Vertex child : adj) {
            if (child == skip) continue;
            Description desc = child.doit(this, k);
            for (int i = 0; i <= k; ++i) {
                res.overallCycles[i] = (res.overallCycles[i] + desc.overallCycles[i]) % MODULO;
                if (i + 2 <= k) singleStep[i + 2] = (singleStep[i + 2] + desc.cyclesFromRoot[i]) % MODULO;
            }
        }
        for (int old = 0; old <= k; ++old) {
            long w = res.cyclesFromRoot[old];
            for (int a = 2; old + a <= k; ++a) {
                res.cyclesFromRoot[old + a] = (res.cyclesFromRoot[old + a] + w * singleStep[a]) % MODULO;
                res.overallCycles[old + a] = (res.overallCycles[old +a] + w * singleStep[a] % MODULO * a) % MODULO;
            }
        }
        return res;
    }
}

Thanks for reading, and check back for more!

Sunday, August 12, 2018

A week in memory of Leo

The Jun 25 - Jul 1 week presented the last of the last chances to progress in TopCoder Open 2018 with its Round 2C on Tuesday (problems, results, top 5 on the left, parallel round results with 2/3 shared problems, analysis). This round was ran in honor of Leopoldo Taravilse, who has tragically passed away recently. It was really sad to hear this news, and I express my sincere sympathy to Leopoldo's family and friends.

fruwajacybyk has squeezed out the first place through challenges from Min,lu and tozangezan who led after the coding phase. Well done!

Codeforces held its Round 493 on Sunday (problems, results, top 5 on the left, analysis). fjzzq2002 dominated the proceedings, solving all problems with 20 minutes to spare while everybody else could manage at most four. Congratulations on the impressive performance!

Problem D, after removing a somewhat artificial complication, boiled down to the following cute combinatorial puzzle: you are given a tree with n<=2000 vertices. How many cycles of length 1, 2, ..., k (k<=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered different.

In my previous summary, I have mentioned another Codeforces problem: you are given a prime modulo p up to 109 and two numbers u and v between 0 and p-1. In one step, you can either add one modulo p, subtract one modulo p, or take inverse modulo p. You need to obtain v from u in at most 200 steps (the solution doesn't need to be the shortest).

This problem allows many approaches, so I'd like to share a bit more how my thinking went. I've started to write down which numbers we can get in a few steps, like u+1 or 1/(u+1) or 1+1/(u+1)=(u+2)/(u+1). Then I've noticed that if we represent our current number as x/y, then the three operations we have are x->x-y, x->x+y, and swap(x,y). This has strongly resembled the Euclidean algorithm, which can go from (x,y) to (0,gcd(x,y)) using those operations. Now I had a sketch of the solution: we'll represent u as (u*k mod p)/k, then apply the Euclidean algorithm to go from u to 0. Now we do the same for v, and since all operations are reversible, we can now go from u to 0 to v.

However, the Euclidean algorithm takes a small (logarithmic) number of steps only if we have the modulo operation available. With just subtraction, it can take a lot of steps - for example, if we pick k=1, then we'll start with u/1 and need u steps to get to 0 just subtracting 1 every time. So we need to choose k wisely so that the number of steps to get from u to 0 will not exceed 100.

First I tried to find k so that (u*k mod p)/k is as close to the golden ratio as possible, as the golden ratio is the case where the Euclidean algorithm proceeds in the fastest way. However, this did not work as sometimes just being close is not enough, and on last steps we still start making too many subtractions. But then I've realized that I can just try random values of k until I find one that works, and this ended up working flawlessly.

Thanks for reading, and check back for more!

Saturday, July 28, 2018

A too simple week

The Jun 18 - Jun 24 week had Codeforces Round 492 (problems, results, top 5 on the left, analysis). I've also included myself in the standings on the left to highlight the fact that OO0OOO00O0OOO0O00OOO0OO's performance was so amazing that he got all 6 problems accepted before I got any one of those :) Well done!

Right after this round, Scott Wu and Andrew He streamed a post-contest discussion on twitch (CF post). Unfortunately the recording is no longer available, but the concept is exciting and I've enjoyed listening to a part of it.

The round had a few mathy problems, but I'd like to highlight problem E which had a more algorithmic flavor: you are given a prime modulo p up to 109 and two numbers u and v between 0 and p-1. In one step, you can either add one modulo p, subtract one modulo p, or take inverse modulo p. You need to obtain v from u in at most 200 steps (the solution doesn't need to be the shortest). Do you see a way?

Thanks for reading, and check back for more!

Wednesday, July 25, 2018

A week without automorphisms

The Jun 11 - Jun 17 week was supposed to present the last chance to qualify for further TopCoder Open 2018 rounds in Round 2B (problems, results, top 5 on the left, parallel round resultsanalysis). However, because of technical issues an extra Round 2C was added two weeks later. Those issues notwithstanding, congratulations to gs14004 on creating just enough cushion during the coding phase to withstand the challenge push from maroon_kuri, sky_love_high and FizzyDavid! sky_love_high in particular actually had 1262.53 points after four minutes of the challenge phase, which would be enough for the first place.

Codeforces had its own share of issues with Round 488 on Saturday (problems, results, top 5 on the left, analysis), this time not technical but with an incorrect reference solution for the hardest problem. It turned out that the test data was luckily correct anyway, so this ended up being a somewhat theoretical discussion that did not affect the round. Congratulations to Um_nik and Errichto on solving all problems!

In my previous summary, I have mentioned an exciting Code Jam problem. You are given a number n between 10 and 50, and need to print a connected simple undirected graph with n vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled.

This is another example where there are two main ways: either solve it "on paper", or try various random-looking things at the computer until one works. Since there are only 41 possible inputs, it's quite easy to verify if an approach works or not.

It turns out that in this problem even the expected solution went the random way. First, we have to come up with a way we'll use to identify the vertices. Then, we'll try random connected graphs with all degrees equal to 4 until we can uniquely identify all vertices in one. Of course, this last step also requires some way of generating such graphs.

As a way to identify the vertices, we can use an iterative approach: initially all vertices start with the same label. Then we compute some function for all vertices that depends on the existing labels and the structure of the graph, but does not change when we permute the vertices. In case the values of the function for some vertices is different, we can update their labels to be different, and repeat the process. Eventually we need for all labels to become different.

The function we compute can't just depend on the neighbors of the node: since every node has exactly 4 neighbors, and initially they all have the same values, we will never get different function values. However, we can look further and for example check how many of those 4 neighbors are connected to each other, or what set of labels we have at distance 2,3,... from the vertex, and then one of those ideas will be enough to find a solution for all 41 possible testcases (see the official analysis for more details).

Finally, in order to quickly generate such graphs, we can also use various approaches. I find the following one the most logical: start with any such graph, and then repeatedly apply random local modifications that don't change the degrees of the vertices (again, check out the official analysis for more details).

I have also enjoyed the way this problem used the interactive problem paradigm to encode the "challenge-response" setup that is not usually seen in programming contests.

Thanks for reading, and check back for more!

Tuesday, July 24, 2018

An obtuse week

The Jun 4 - Jun 10 week was the week of the Google Code Jam: the onsite advancers were determined both in the normal and in the distributed competition.

First off, the Google Code Jam 2018 Round 3 took place on Saturday (problems, results, top 5 on the left, analysis). Somewhat surprisingly, none of the full scores stood during the system testing. Errichto.rekt and ifsmirnov lost the least points at that stage :) Congratulations!

I found the problem Name-Preserving Network really exciting. You are given a number n between 10 and 50, and need to print a connected simple undirected graph with n vertices, and each vertex having degree exactly 4. The interactor will then randomly permute the vertices of your graph and give it back to you, and you need to then restore the permutation that was used. In other words, you need to find such graph without automorphisms, and be able to identify its vertices after they're shuffled. How would you approach this one?

The Distributed Code Jam 2018 Online Round followed a day later (problems, results, top 5 on the left, analysis). Errichto.rekt was at the top for the second day in a row, thanks to being one of only two solvers of the hardest problem E. Well done!

In my previous summary, I have mentioned an unusual TopCoder problem: You are given 3n sticks with lengths a, a+1, ..., a+3n-1. You need to find any way to split them into n triples in such a way that each triple forms a non-degenerate obtuse triangle, or report that there isn't one. n is up to 500, a is an integer between 1 and 10.

There are a few principal approaches to this kind of problem (did I already enumerate those on the blog? Please share a link, and also please add ones that I missed):

  • Just solve the problem on paper, in other words come up with a direct explicit construction.
  • Solve the problem on paper in two steps a-la induction: come up with a way to solve the problem for small instances of the problem, and also come up with a way to change a solution for n to a solution for n+5 (for some value of 5).
  • Only do the second inductive part on paper, and use brute force to find solutions to small instances.
  • Also replace the inductive part with something less formal: do some kind of greedy for most of the solution, and use brute force when the remaining problem is small enough.
The official analysis suggests to use the third approach, while I went with the last one since it requires the least amount of thinking :)

I like to code such solutions as a brute force that runs even for large values of n, with the greedy part being implicit by the order the brute force tries the possibilities: since for most of the decisions, we will never have time to come back to them, the first decision we try in the brute force is effectively the greedy decision. This way I don't have to explicitly choose the boundary between the greedy and the brute force, and thus can try different ideas faster.

You can take a look at my solution from the round for more details, but in short, the ordering that worked was: as the first attempt, try to pair the smallest remaining stick with the 1/3-rd and 2/3-rd ones in sorted order, and then go from those in both directions.

Thanks for reading, and check back for more!

Sunday, July 22, 2018

An extra log week

Codeforces Round 485 got the May 28 - Jun 3 week going (problems, results, top 5 on the left, analysis). OO0OOO00O0OOO0O00OOO0OO has tried an unusual problem solving order, but it didn't really help as tourist was faster overall and got the well-deserved first place. Congratulations!

The round thread is also notable for discussions about modern problemsetting practices (search for Um_nik's replies and surrounding comments).

On Saturday, TopCoder Open 2018 Round 2A saw the top-rated participants enter the competition (problems, results, top 5 on the left, parallel round resultsanalysis, my screencast). A lot of solutions failed challenges and system test in this round, and after the dust has settled it turned out that bmerry both had the highest coding phase score, and has protected the lead very well by adding 100 challenge points. Well done!

The hardest problem in this round allowed one to get quite creative. You are given 3n sticks with lengths a, a+1, ..., a+3n-1. You need to find any way to split them into n triples in such a way that each triple forms a non-degenerate obtuse triangle, or report that there isn't one. n is up to 500, a is an integer between 1 and 10.

Finally, AtCoder Grand Contest 025 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). Only Stonefeang was able to solve all problems, and thus got a clear first place. Contestants behind him solved quite varied subsets of problems in an attempt to score most points in the limited time available, but it did not really matter in the end. Congratulations to Stonefeang!

Thanks for reading, and check back for more.