Sunday, February 25, 2018

An infinite ratio week

This week had a round from each of the platforms I usually cover. First off, TopCoder held SRM 730 on Tuesday (problems, results, top 5 on the left, analysis). The competition was ultimately decided during the challenge phase where I was basically very lucky: my room had 8 incorrect solutions for the 250, and I've managed to bring down 4 of those; ACRush had only 4 incorrect solutions in his room, one of those was challenged by somebody else, and he got the other 3. Nevertheless, amazing comeback after an almost half-year break for ACRush!

Quite unusually, the hard problem was solved by ksun48 in less than 5 minutes. The problem asked to find the sum of 2x1 (two to the power of the minimum number) over all possible ways to choose k distinct positive integers up to n: 1<=x1<x2<...<xk<=n, where n is up to a billion, and k is up to a million.

Next up was AtCoder Grand Contest 021 on Saturday (problems, results, top 5 on the left, analysismy screencast). tourist was nearly unstoppable this time, earning his first place with about 25 minutes left in the contest. Egor in 3rd place had the most realistic chance to overtake him thanks to a creative strategy, as he decided to avoid spending more time to earn the fairly technical final 300 points in the partial-scoring problem F, and instead focused on problem E which would give 1200 points if solved. Unfortunately 25 minutes were still not enough for that. Nevertheless, congratulations to both!

Problem B was quite cute. You are given 100 points on the plane. For each given point, consider the part of the plane where it is the closest of the given points (a Voronoi diagram). Some of the parts will be finite, and some will be infinite. What are the relative areas of the infinite parts (see the problem statement for the formal description)?

Sunday started with the Open Cup Grand Prix of Saratov (problemsresults, top 5 on the left). Six teams were able to solve 11 this time, but team Past Glory has managed to do that without a single incorrect attempt — amazing!

After a short break, Codeforces Round 467 wrapped up the week (problems, results, top 5 on the left, my screencast). mnbvmar has earned his first place by solving 4 problems in just over an hour, 15 minutes faster than anybody else — and then protected his lead from Syloviaely's surge by finding 5 successful challenges. Very well done!

Problem C provided a level playing field for experienced and inexperienced competitors, as it had nothing to do with standard algorithms or even standard ideas. You are given a string s of length 2000, and need to transform it into a string t of the same length using at most 6100 operations, or report that it's impossible. In one operation, you can split the current string into two, reverse the second part, and then put the first part after the reversed second part: for example, you can obtain the string fedcab from the string abcdef in one operation. Either part is allowed to be empty. Can you see a way to do the transformation of length n in at most 3n operations? Somewhat surprisingly, there are many working approaches in this problem.

Thanks for reading, and check back next week!

No comments:

Post a Comment