Monday, January 22, 2018

A mean median week

This week Codeforces hosted its Round 458, also known as CodeCraft-18 (problems, results, top 5 on the left, analysis). Syloviaely has made a solid claim to the first place by submitting the 3000-point problem F just 13 minutes after the contest started (was it a previously known problem, or was it really fast solving?..), but SkyDec has gathered a whopping 800 points from challenges on two different problems, 450 on B and 350 on C, and thus finished first with quite a margin. Congratulations!

This round also had a great side story — the top-rated contestant, Um_nik, decided to go for the hardest problem H, and that bet did not play out well as he spent too much time on it and as I understood also discovered an incorrect output in one of the samples (which means an incorrect reference solution?..). The admins have decided to make the round unrated for him because of the incorrect sample issue, but he asked them to reverse that decision (and thus make him lose rating) because he deemed the issue did not impact him significantly. Kudos to Um_nik for the admirable honesty!

Last week, I have mentioned an AtCoder problem: you are given n<=2000 positive integers, each up to a<=2000. Consider all 2n-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2n-1-th in the sorted order. You need to output this median sum. Time limit is 2 seconds.

At first sight, the problem appears somewhat standard: we can run the knapsack dynamic programming that computes the number of ways to get each possible sum, and then go from lower sums to higher sums until we get 2n-1 in total.

This has two issues, though: first, the maximum sum is n*a, so the dynamic programming runs in O(n2*a). Second, the number ways to get each sum can be on the order of 2n, so we need big integers, and the running time after accounting for that is more like O(n3*a). Even O(n2*a) is too slow.

Here comes the insight: notice that all sums can be split in pairs. If the sum of all numbers is s, then for each subset with sum x we'll have the complementary subset with sum s-x (let's also include the empty subset). One of those sums is <=s/2, and the other is >=s/2, so the median is roughly equal to s/2. More precisely, the median will always be the smallest sum that is >=s/2.

This allows us to get rid of the big integers, as now we merely need to know which sums are possible, and don't care about the number of ways anymore. Moreover, we can use bitmasks to speed up this O(n2*a) solution ~32-64 times which makes it fast enough.

Thanks for reading, and check back next week!

Monday, January 15, 2018

An Um_nik week

This week's contests shared one of the problemsetters — and the winner. On Monday, Codeforces hosted its Hello 2018 round (problems, results, top 5 on the left, analysis). With the hardest problem having too much piecewise polynomial integration, the competition focused on the remaining seven. Only Um_nik could get them all, and even with 24 minutes to spare — congratulations!

On Sunday, AtCoder Grand Contest 020 started the race to Japan (problems, results, top 5 on the left, my screencast, analysis). Once again the hardest problem by tourist was a tiny bit too hard (and I even solved it after the contest by integrating polynomials, probably inspired by the analysis of the previous contest), and once again Um_nik was way faster than everybody else on the remaining problems — big congratulations again!

I found problem C quite cute. You are given n<=2000 positive integers, each up to 2000. Consider all 2n-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2n-1-th in the sorted order. You need to output this median sum. Time limit is 2 seconds.

In my last post I've discussed what was arguably the hardest contest problem of 2017: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:
  • The subgraph formed by groups A+B is connected and has at least 2 vertices.
  • The subgraph formed by groups C+D is connected and has at least 2 vertices.
  • Each vertex in A has an edge to each vertex in C.
  • There are no other edges between subgraphs A+B and C+D.
If there are many possible solutions, you need to output any one of them.

Thanks to great ideas and pointers by Swistakk, mnbvmar and lewin, we were able to put together a O(n*logn) solution — you can check it out in this comment thread.

Thanks for reading, and check back next week!

Monday, January 8, 2018

An Otherland week

The first week of 2018 was quite calm, with the most devoted taking stabs at the still-ongoing Prime New Year contest by snarknews. Only one problem remains unsolved there, and it looks like it might take some team effort to crack it. I think it's within the spirit of the contest to discuss its problems publicly (after all, many even have analysis posted online), so I propose to do just that. Please skip the following paragraphs if you don't want spoilers!

The problem goes like this: you are given an undirected graph with at most 200000 vertices and edges. Your goal is to split its vertices into four disjoint groups A, B, C, D in such a way that:
  • The subgraph formed by groups A+B is connected and has at least 2 vertices.
  • The subgraph formed by groups C+D is connected and has at least 2 vertices.
  • Each vertex in A has an edge to each vertex in C.
  • There are no other edges between subgraphs A+B and C+D.
If there are many possible solutions, you need to output any one of them.

I have been thinking about the problem for some time, but only have the following not very helpful observations:
  • If the graph has an articulation point, then we can take this point as set A, any of the components it separates as set B, and the rest as C+D. So we can assume the graph is vertex-biconnected.
  • The answer is not always "Yes" - the smallest counterexample is the graph with 4 vertices and 5 edges. This example also shows that if a biconnected graph has a vertex of degree 2, then this vertex and both adjacent vertices must be in the same half of our splitting, since both ends of a splitting edge must have degree of at least 3 (two splitting edges plus one inside the half).
  • There are also counterexamples without vertices of degree 2.
  • There might be some hashing trick involved. I.e., for example suppose we assign a random number ai to each vertex, and compute for each vertex the value sum(ai-aj), where the summation goes over all adjacent vertices j. Then if we add up those values within one half of the graph (A+B in the above terminology), then almost everything will cancel out, leaving us |C|*aA-|A|*aC, where aA is the sum of ain A. But where to go from here?..
Please share your ideas!

In my last post, I have held a vote for the best problem of 2017. And the winner is this AtCoder problem by maroonrk: you are given two rooted trees on the same set of 105 vertices. You need to assign integer weights to all vertices in such a way that for each subtree of each of the trees the sum of weights is either 1 or -1, or report that it's impossible. The solution is explained in this post. Congratulations to the problemsetter and to AtCoder, and thanks to all problemsetters of 2017!

Thanks for reading, and check back next week.