Monday, July 19, 2021
Sunday, April 25, 2021
The key trick to make progress in the problem is to find a less general, but still non-trivial case which we can solve. It turns out that such case is the one when the initial labeling of points forms a single cycle, for example: point 1 has label 2, point 2 has label 3, and so on, until point n which has label 1. In this case we can solve the problem using only the swaps that include point 1, and therefore their segments will not intersect: we start with labels 234...n1. We swap the labels of points 1 and 2, and we get 324...n1. We swap the labels of points 1 and 3, and we get 423...n1. We continue with swapping the labels of points 1 and 4, and so on, and eventually we get n234...(n-1)1, and finally we swap the labels of the first and last points to get the identity permutation. Note that our choice of point 1 as the "pivot" of all swaps was arbitrary, and we could do the same with any other point.
The initial permutation has some number of cycles, and whenever we swap two elements from different cycles they merge into one. While we have more than one cycle, we can find two adjacent points in the sorted order that belong to different cycles, and swap them to merge those cycles. We repeat this until we have just one cycle remaining, and then apply the single-cycle solution.
There are some additional small details to be figured out, which you can find in the official editorial. I could not solve this problem myself, in part because the space of possible approaches is so vast, and yet most of them do not seem to work. I've checked the solutions for this problem from the top finishers, and they all seem to use this approach. In fact, I'm really curious: is some fundamentally different solution possible here? If not, does there exist some intuition why?
Thanks for reading, and check back next week.
Sunday, April 18, 2021
- It did not work on the samples
- Its complexity was O(n2*log(n)) in the worst case (even though with a 7-second time limit this was not obviously bad)
Sunday, April 11, 2021
I have prepared the test data for the second problem, Prime Time, and I (humbly, of course :)) think it was a great example of how a not particularly difficult problem can still be nice. The problem went like this: you are given up to 1015 cards, each with a prime number between 2 and 499. You need to split the cards into two piles, such that the sum of the numbers in the first pile is equal to the product of the numbers in the second pile, or tell that it's impossible. Can you see how to handle such a huge amount of cards?problems, results, top 5 on the left, analysis). I have solved the first three problems in less than 50 minutes, which was great, but then I could not score any additional points in the remaining 2 hours and 10 minutes, which was a bit frustrating :) I've tried to approach all three remaining problems in the beginning, but eventually focused on the problem E, and it turns out I was really close: I did identify the two cases from the official analysis, I have correctly (I think) handled the first case and tried various formulas that looked very similar to the correct one for the second case, but I could neither figure out all details and come up with a formula on paper, nor get the correct answers for the sample cases by trying small changes to the formulas. It turns out that my problem was that I was inserting the segments in the increasing order of the starting time, instead of the decreasing order of the ending time. These two ideas look symmetric on the surface, but they actually are not equivalent because the problem asks about local maxima, and the symmetric case would be local minima. However, my idea can still handle the first case just as well (because the first case is in fact symmetric, as we have n-1 local minima there as well), which made it hard to move away from it for the second case.
Congratulations to the seven contestants who have managed to handle all details correctly and solve one of the harder problems, and especially to jiangly on the win!
Thanks for reading, and check back next week.
Monday, April 5, 2021
my previous summary, I have mentioned a Codeforces 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.
Monday, January 4, 2021
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).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!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
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.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.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.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!
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!