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

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:

Thanks to great ideas and pointers by Swistakk, mnbvmar and lewin, we were able to put together a O(

Thanks for reading, and check back next week!

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 2^{n}-1 nonempty subsets, and compute the sum of the numbers in each subset. Now sort those sums, and find the median sum — the 2^{n-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.

Thanks to great ideas and pointers by Swistakk, mnbvmar and lewin, we were able to put together a O(

*n**log*n*) solution — you can check it out in this comment thread.Thanks for reading, and check back next week!