Monday, January 4, 2021

A Samara week

"Good Bye 2020" was the last round of the year on Codeforces (problems, results, top 5 on the left, analysis). The round has left me with mixed feelings, as I've spent almost the whole 3 hours solving relatively standard problems, and did not have enough time to solve the very exciting problem I. The main reason for that was that I forgot how to count DAGs, and tried to reinvent the wheel in problem H for a very long time. tourist, on the other hand, did not struggle so much with H, and won the round. Well done! Also well done to scott_wu, fivedemands, mnbvmar and qwerty787788 who were able to solve the last problem.

Here's that exciting problem: there is a hidden array of n b-bit integers (in other words, each element is between 0 and 2b-1). You do not know the elements of the array, but you can ask questions about them: in one question, you can ask "is it true that the i-th element of the array is greater than j?" for some value of i between 1 and n and j between 0 and 2b-1. Your goal is to find the value of the maximum element in the array, and you need to do it in O(n+b) queries. The problem actually asked to do it in at most 3*(n+b) queries, but I think just doing it in a linear number of queries is the most interesting part.

Note that simply finding each element with binary search would lead to n*b queries, and it's not clear initially how we can do any better as each query only asks about one element, and the elements are somewhat independent. Can you see the way? n and b are up to 200, and the interactor is adaptive (so your solution most likely needs to be deterministic).

The new year pause was not long, and Open Cup 2020-21 Grand Prix of Samara took place on Sunday (results, top 5 on the left, analysis, overall Open Cup standings). Unlike last year, which saw a fierce competition at the top of the overall Open Cup scoreboard between three teams, this year team USA1 really dominates the proceedings, and they won their 7th Grand Prix out of 8 this time, finishing all problems in 3.5 hours. Congratulations!

The Prime New Year Contest is another staple of the holidays. It is running until the end of this week, and features the problems from 2020 which were not solved by anybody during respective contests. Good luck getting something accepted there, and huge respect to those who already did!

In my previous summary, I have mentioned an AtCoder problem: you are given an undirected graph with four vertices and four edges that looks like a square (the picture from the statement on the right). You know that a walk started from vertex S, finished at vertex S, has passed the ST edge (in any direction) a times, the TU edge b times, the VU edge c times, and the SV edge d times. How many different walks fit that description? a, b, c and d are up to 500000, and you need to compute the answer modulo 998244353.

If we replace the ST edge with a parallel edges, the TU edge with b parallel edges, and so on, then we're looking for the number of Euler tours in the resulting graph modulo dividing by some factorials to account for the fact that all parallel edges are equivalent. However, counting Euler tours in undirected graphs is hard.

But given the simple structure of our graph, we can actually reduce our problem to counting Euler tours in directed graphs, which can be done using the BEST theorem! We can iterate over the number of times we pass the ST edge in the direction from S to T, in other words over how many ST arcs would our directed graph have. This determines the number of TS arcs by subtracting from a, then the number of SV and VS arcs from the constraint that the in-degree and out-degree of S must be the same, and so on until we know the number of times we pass each edge in each direction, and we can then count the Euler tours in the resulting graph in constant time (because the graph has 4 vertices and 8 "arc types", and the actual number of parallel arcs does not affect the running time of the BEST theorem). Since a is up to 500000, we have to do this constant time computation 500000 times, which is fast enough.

Thanks for reading, and check back next week!

Tuesday, December 29, 2020

A rng_58 week

Last week wrapped up the year for two major contest platforms — TopCoder and AtCoder — and with it the races to qualify to the corresponding onsites.

TopCoder SRM 796 was the first round of the week (problems, results, top 5 on the left, analysis). maroon_kuri was leading after the coding phase but failed the system tests; none of myself, tourist and Egor could find a challenge opportunity even though there were lots of them available, including in the 500-pointer which screamed "look for challenges here!" as it had just one sample case.

This round concluded the three-month race for the second TCO21 spot (results, top 5 on the left). Even though six SRMs is quite a lot, the race came down to the wire and to a lot of very close calls: in SRM 792, neal_wu produced an amazing 200-point challenge phase to get a 3-point advantage and deny Um_nik the 5 race points; in SRM 793, tourist's easy was challenged but he would still win the round had ksun48 not taken his turn to earn 200 challenge points; you can see the story of SRM 796 above.

AtCoder held its two last rounds of the year on the weekend, starting with AtCoder Grand Contest 050 on Saturday (problems, results, top 5 on the left, analysis). Um_nik was the fastest on the four relatively easier problems, and protected his lead by finding the main insight and figuring out all details in the very tricky problem F. Congratulations on the win! duality and newbiedmy were also able to solve the hardest problem, and rounded up the top three. newbiedmy in particular must've had one hell of a contest: he started with this problem, and did not give up after 11 incorrect attempts. This unusual strategy was richly rewarded!

AtCoder Grand Contest 051 on Sunday was the last contest of rng_58 as AtCoder admin (problems, results, top 5 on the left, analysis). Even though the point values were different, the scoreboard looks very similar: the first four problems were solved by many, while the last two were very hard and only got accepted solutions in the last 45 minutes of the 4.5-hour contest. semiexp and yutaka1999 went for problem F which gave them more points and the first two places. Congratulations!

I'd like to highlight problem D: you are given an undirected graph with four vertices and four edges that looks like a square (the picture from the statement on the right). You know that a walk started from vertex S, finished at vertex S, has passed the ST edge (in any direction) a times, the TU edge b times, the VU edge c times, and the SV edge d times. How many different walks fit that description? a, b, c and d are up to 500000, and you need to compute the answer modulo 998244353.

Given that Makoto (rng_58) is retiring as AtCoder admin, I'd like to thank him for bringing AtCoder to the English-speaking world, and for making it the place for solving awesome problems. Extremely well done!

The two rounds have concluded the race for the 8 AtCoder World Tour Finals spots (results, top 8 on the left). Congratulations to all finalists! This is the third season of the AtCoder points system. The top 8 has quite a big intersection with those from the two previous years (2018, 2019), with tourist, Um_nik and myself qualifying all three times, and ecnerwala and mnbvmar qualifying last year. It will be the first WTF for Benq, Stonefeang and endagorion, assuming it does actually take place of course :)

Thanks for reading, and Happy New Year!

Monday, November 23, 2020

A Seattle week

Codeforces Round 684 warmed the contestants up before the remaining TCO20 rounds (problems, results, top 5 on the left, analysis). It was very close between the top 3, but ecnerwala has managed to avoid getting TLE on pretests in the last problem (and therefore having to spend more time speeding up the solution) and thus gained a very small edge. Congratulations on the first place!

The problemsetters received a lot of flak for the tight time limits. I have not solved the round myself, so I can't offer any firsthand experience. However, I found it quite impressive that three different coders were complaining about having to squeeze their solutions only to learn that the have bad asymptotic complexity (1, 2, 3 — thanks a lot to dorijanlendvaj for investigating those!). 

TCO20 Semifinal 2 followed next day (problems, results on the left, stream recordinganalysis). The problems were significantly easier compared to Semifinal 1, with a relatively standard easy, a unique but not very hard medium, and a hard which was mostly solved by printing out the nimbers for small inputs and figuring out a pattern. Solving all three problems was enough to advance without any additional concerns; Egor and uwi solved two each, and Egor got ahead thanks to uwi's resubmit and his own successful challenge.

The top 4 from this round, together with the top 5 from the first round, competed in the TCO20 Final on Saturday (results on the left, stream recording). The problems were also not too difficult, and the competition came down to speed and random bugs, with less than 50 points separating many contestants at the top. tourist was just a tiny bit faster than everybody except Um_nik, and Um_nik's hard failed the system tests paving the way for the second TCO victory in a row for tourist — congratulations!

My contest was compromised early by two things: first, I had to resubmit the easy because I forgot to apply the modulo in one of the operations and therefore got an integer overflow. I guess it is a good lesson that tells me to start using a "modint" class that everybody else is using (which might be prohibitively slow in Java, but fine in C++). Second, after opening the medium I've immediately started to implement a brute force solution that computes the losing positions for small inputs, inspired by what happened in the semifinal. This strategy has backfired in this problem, as just a tiny bit of thinking on paper could've allowed me to achieve the same insight (that the losing positions are exactly the same as in the normal Nim) much quicker. I was therefore more than 100 points behind tourist and Um_nik after the first two problems.

I have managed to recover a big part of that gap on the hard problem, using the same strategy — implementing a brute force solution to see a pattern that enables a real solution (that all interesting states are the multiples of interesting 0/1 states), so one could say that this strategy worked out about even if one looks at the medium and hard combined.

I was therefore less than 50 points behind the first place, and needed just one successful challenge to win. I could not find any incorrect solutions, though, so I went with a last-second challenge on neal_wu's medium, which used an approach that was different from the approach that I and most others have taken, and which I hypothesized could TLE. It turned out it was fast enough, but I think it was definitely worth a try.

It is also interesting that the only incorrect solution in this round — Um_nik's hard — had a bug that I considered during the coding phase: it computed differences with the previous element instead of differences with the next element on every iteration. However, I was not sure if this bug can affect the results, so I've ran both variants of my solution on the biggest testcase (26, 1018), and they indeed gave the same output. I've thought that maybe the parity of n plays a role, so I've also tried (25, 1018) and the results were also the same, which got me completely convinced that the direction does not matter :) It turns out that both (24, 1018) and (26, 1017) have different outputs for those two solutions, so I was really close to discovering this and then checking all other solutions for this bug and challenging Um_nik successfully.

It is a bit more painful to come so close to winning in multiple ways (compared to for example 2019 where I did not really have any chance). Well, better luck next time, and congratulations to tourist once again!

In my previous summary, I have mentioned an AtCoder problem: you start with a sequence of n zeros (n<=50), and can apply the following four operations any number of times:
  1. Add one to any number. This operation costs 1.
  2. Subtract one from any number. This operation costs 1.
  3. Add one to any contiguous segment of numbers. This operation costs C.
  4. Subtract one from any contiguous segment of numbers. This operation costs C.
Now, you are given k (k<=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 109. You need to find sum of the minimum costs to obtain the final state for each of kn possible final states, modulo 109+7.

Swistakk has explained my approach in this comment, so I will only clarify that reducing the problem to O(n*k) problems where each element is 0 or 1 is done by considering independent problems "how to add 1 to all numbers which must be >=1 in the end", "how to add 1 to all numbers which must be >=2 in the end" and so on.

November was quite packed with onsite finals that were in limbo given the circumstances, and ended up happening online close to the end of the year. Now most of them have passed (VK Cup, Yandex Cup, TopCoder Open), AtCoder WTF is most likely postponed further (judging from the list of upcoming contests here), so the only remaining big onsite-turned-online final (and my last chance to win something this year) is the Facebook Hacker Cup on December 5.

Thanks for reading, and check back next week!

Sunday, November 15, 2020

A clean slate week

I think it's really past time to admit that I can't keep up with the weekly schedule, and start enjoying writing the posts instead of stressing about the backlog of several months. So, here comes:  

This week's competitive programming events started with the Kotlin Heroes 5 on Codeforces (problems, results, top 5 on the left, analysis). Gone is the idea to auto-convert from Java, as everyone in top 5 seemingly writes somewhat idiomatic Kotlin directly (however I'm wondering if it looks idiomatic to Roman Elizarov :)). tourist and Benq were the only contestants to solve all problems, but Benq's chance to catch tourist was mostly gone with the incorrect attempt on problem D on the 12-th minute, which he took 9 minutes to correct and therefore fell behind so much he could not really recover. Congratulations to both on the great performance!

TopCoder Open 2020 has opened its virtual doors with Semifinal 1 (problems, results on the left, stream recording). The round was marred by an incorrect reference solution for the 500, seemingly making the problem unsolvable, at least within the time of the round, and resulting in neal_wu's challenge requests not being processed. In the end, the organizers have awarded him 50 challenge points as well (so we got +100 challenge points with just one incorrect submission :)), and advanced five competitors to the finals instead of four. Congratulations to all five! I think this is a decent solution to this situation, but I'm wondering if rerunning the round from scratch with a different set of problems would (arguably, of course) be more fair.

I have been commentating the round on the stream, and I didn't really do it well. First of all, I've had one job — to read the handles of the Russian competitors correctly — and still managed to mispronounce Um_nik's handle :( To add insult to injury, I did not name him in my list of contestants who have been doing very well recently, which was of course an obvious oversight. I'd like to take this opportunity and apologize to Alexey!

There were also serious connection issues which resulted in my voice not making it to the stream in many cases, and in us talking over each other a few times :( In addition, I have assumed that the first solution for the medium that came to our mind would run in time, while it actually did not. Streaming is hard! Please share any improvement suggestions that you have, I hope to do better next time.

AtCoder Grand Contest 049 followed on Saturday (problems, results, top 5 on the left, analysis). Um_nik breezed through the first five problems, and since the last problem was too tough to crack, his first place was not really in doubt. Well done! The race towards the 8 WTF spots is close to its conclusion (assuming there will be 1 or 2 more qualifying AGCs), with the top 4 most likely already booking their spots, mnbvmar being almost there, and maybe maroonrk as well if he keeps being a writer in the remaining rounds :)

In keeping with the meta-story of problem E, I came up with a solution that seems to have exactly zero things in common with the editorial :) Here is the problem statement: you start with a sequence of n zeros (n<=50), and can apply the following four operations any number of times:
  1. Add one to any number. This operation costs 1.
  2. Subtract one from any number. This operation costs 1.
  3. Add one to any contiguous segment of numbers. This operation costs C.
  4. Subtract one from any contiguous segment of numbers. This operation costs C.
Now, you are given k (k<=50) candidates for each value in the final state of the sequence, each candidate is between 1 and 109. You need to find sum of the minimum costs to obtain the final state for each of kn possible final states, modulo 109+7.

Right after the end of the AtCoder round, Errichto hosted the final 8 of the first open Lockout tournament organized by Geothermal (detailsstream recording, top 8 bracket on the left). pseudocoder10 has created an excellent bot that runs the matches and automatically picks Codeforces problems of appropriate difficulty that both participants have not solved yet, and the system with 6 problems and 100-200-300-400-500-600 point values provided for a big strategic variety and made the matches very exciting to watch. Well done to everyone involved, and congratulations to Um_nik on the victory!

rng_58 is running another iteration on new problems (future AtCoder Regular Contests), consider signing up if you're 2800+ on AtCoder!

Codeforces Round 683 wrapped up the week (problems, results, top 5 on the left, analysis). Um_nik has solved problem E in a seemingly normal rhythm, and went on to solve everything with almost half an hour to spare and win the round. Most of the others could not get past pretest 3 in problem E (Um_nik also had two attempts that stopped there), with ksun48 advancing as far as pretest 5. Congratulations to Um_nik on the convincing victory!

The diff between his passing solution and "wrong answer on pretest 3" attempt is small, but it does seem to be a substantial fix to the solution logic (see it on the right).

Thanks for reading, and check back (maybe) next week!

Sunday, September 20, 2020

An unexpected verdict week

Codeforces Round 658 was the first event of the Jul 20 - Jul 26 week (problems, results, top 5 on the left, my screencast, analysis). Benq has managed to finish all six problems in time, even though the first five would be enough for the first place anyway. Congratulations on the confident victory!

I have managed to dig myself out of the piecewise quadratic function world with just 8 minutes to go, which was still quite satisfying even though competing with Benq was completely out of question :)

TopCoder SRM 788 started the race for the first TCO21 spot (problems, results, top 5 on the left, my screencast, analysis). My easy-hard-medium strategy has hurt me this time, as after submitting the hard I saw others get 500+ points for the medium and submitted it without enough thinking, leading to a resubmit later. On the other hand, I could submit, stress-test, debug, fix and resubmit it without the pressure of "should I switch to the hard instead?" :) It was hard to fight for the top places with the resubmission. Even though the medium problem was much harder than the other two for lyrically as well, she got it right from the first attempt and earned 5 TCO21 points. Congratulations!

Here is the problem that caused all this mess: you are given an H times W grid (H*W<=500), with some of the boundaries between cells being passable, and some being walls. All outside boundaries are walls. Your goal is to remove some more non-outside walls in such a way that the remaining walls split the entire grid into rectangular areas without internal walls. What is the maximum number of such rectangles one can get?

Codeforces Round 659 then revealed the origin of "Polish Mafia" team name (problems, results, top 5 on the left, analysis). I could not solve problem C (neither could I solve problem F, but I did not spend much time on it), and I was not alone. That makes the performance of tourist, Benq and Radewoosh who solved all six problems even more impressive, well done! Even they have solved problem C as their last or next-to-last problem, suggesting it was also quite tricky for them.

Here is that problem: you are given a string of length up to 105, consisting of the first 20 lowercase English letters. In one step, you can pick any set of characters in this string that are all equal (not necessarily all occurrences of that character), and change all of them to some other character (the same for all replacements in this step). What is the smallest number of steps needed to obtain the other given string of the same length?

I would also like to highlight the excellent investigation by maroonrk on the practical performance of modern flow algorithms :)

Thanks for reading, and check back for more!

Sunday, September 13, 2020

An Eggheads week

The Jul 13 - Jul 19 week was the second TopCoder-only week in a row, with TopCoder Open 2020 Round 2B (problems, results, top 5 on the left, parallel round results, my screencast, analysis). 203 more contestants advanced to Round 3, and DmitryGrigorev was on the first place thanks to going for easy+hard. Congratulations! Nobody was able to solve all three problems, and the score from easy+medium was only good enough for the 5th place.

Check back for more :)

A stable bubble week

TopCoder Open 2020 Round 2A was the main event of Jul 6 - Jul 12 week (problems, results, top 5 on the left, parallel round results, analysis). Four contestants solved all three problems in the main round, which is even more impressive given that nobody managed to do that in the parallel round, despite that fact that the strongest contestants who qualified directly to Round 4 were competing there. Congratulations to all four, and especially to Kriii on the win!

In my previous summary, I have mentioned a Codeforces problem: you are given an array a with at most 1000 elements. Then we write down all pairs of positions that form an inversion: pairs (u,v) such that u<v and au>av, getting a long list of all those pairs. Now we want to treat this list as a sorting program: for every pair in the list, we will swap the elements on the corresponding positions. Our goal is to make this program actually sort our array. We are allowed to put the elements of the list in arbitrary order (but we must have all pairs that form an inversion in the starting array exactly once).

If we were allowed to swap any pair that forms an inversion in the current state of the array, then the bubble sort algorithm would work, as it only swaps adjacent elements that form an inversion. However, we can only use the inversions from the initial array (and must use them all).

In order to achieve this, we need to find an algorithm that tries to keep most existing inversions unchanged. Let's do the following: first, we find the maximum number. Then, we find the second highest number, and sort them (within their places). Then, we add the third highest number and sort the three numbers within their places, using up all their inversions, and so on. This way, whenever we process a new number, the only thing that happened to the array is that the higher numbers got reordered, so the inversions involving the new number stay unchanged!

The only remaining step is to learn how to put the new number into its correct place using all its inversions. This is equivalent to putting 1 into the correct place given the array 2 3 4 ... k 1 (k+1) ... n. The following sequence of swaps does the job: swap 2 and 1, then swap 3 and 2 (which is in the original position of 1 now), then swap 4 and 3, and so on until swapping k and k-1.

Thanks for reading, and check back for more!