SRM 459

It's been almost a year since my first and almost half a year since my last SRM, and I felt like making another one. So somewhen before the New Year I processed the ideas whirling in my head, wrote several problems and was offered the 459-th Single Round Match.

Div2 Easy - RecursiveFigures. The problem featured some eighth-grade level geometry, which, even with all the formulas in the statement, appeared to be not too easy (I guess there is nothing too easy for D2-250). The most interesting thing about it are the pictures by Lela Latsoshvili, who will be saving all of you from my mspaint-made illustrations from now on (I hope :D).

Div2 Medium / Div1 Easy - Inequalities. This problem can be solved in a number of ways, the most general of which has performance complexity of O(NlogN), where N is the number of inequalities, and can even produce the whole optimal intervals of values. However, since this is D1-Easy, the common solution to seek for is some neat brute force. With constraints as low as 1000, one could iterate over all possible values from -1 to 1001 with step 0.5 and check the answer for each of them - which is quite easy if you parse the input properly.

Div2 Hard - ParkAmusement. At first, the problem was deemed as too hard for Division 2, since it involved conditional probability - quite an uncommon topic for the second division. Even after the addition of thorough annotations, the tester still suggested to remove the conditional probability part - but I believed in Division 2, and Division 2 did not let me down. 24 successful submissions even made this my easiest D2-Hard yet. Not that I complain about it :) The key idea of the solution is that the probability of landing X being the starting landing is the ratio of (the probability of reaching an exit from X in K pipes) and (the probability of reaching an exit from any landing i in K pipes). Computing this probabilities is performed with dynamic programming, where the state is pair(landing, pipes left).

Div1 Medium - NumberPyramids. So, we have another problem featuring Lela's illustrations in place of my crooked landscapes. Though this time the problem itself can at least compete with its corresponding pictures. I was a little surprised with the high number of successful submissions for this problem, since its solution took me more efforts than, say, the SRM443's BinaryFlips. When I am not as sleepy as now at 3:30AM, I'll put the idea of the solution here.

Div1 Hard - TheContest. Actually, at first I proposed another problem for this slot. However, it finally turned out to be way too hard, so I have modified my easiest problem from Vekua Cup Individual Contest's problemset - problem G, and suggested to use it. Unfortunately, eventually nobody solved it (though we were a lot more optimistic before the match).
The solution for the problem is as follows. First, let us consider N<=M. It's provable that if we have several rows already filled, then we always can fill the rest in spite of exactly how we've filled the previous rows. Therefore, the problem reduces to filling a row in a way not to conflict with already filled rows. For each position, let us try every number (which was not used in this column before) in ascending order. If it is possible to arrange the rest of the numbers in the columns to the right, then we take this number. And this possibility can be checked with the help of matching techniques: if we build a bipartite graph with the left-side nodes corresponding to columns and right-sides corresponding to numbers left, and the edge between left-side i and right-side j denoting that j was not used in i-th column, there must exist a maximum matching in this graph for the number to be feasible.
When N>M, we encounter a little problem. It is no longer true that we can fill the rows not thinking about the next ones. For example, for N=3 and M=2, filling the rows in this manner will give us {"12","21"} and the third row will be no longer fillable. It's easy to notice that every value must be used in the whole matrix a total of MIN(N,M)=M times. Therefore, an obvious restriction on the numbers to use is: if there is a number X such that if you don't use it in this row, then you won't have enough rows to use it a total of M times, you should use X in this row. A much less obvious thing is that this is also sufficient to fill the whole matrix row-by-row. So, for each row we should first identify all the values which have to be used in it and then fill this row, making sure that these values are used. But how to deal with this in the matchings we use to determine feasibility? Since augmenting paths in matchings never change the nodes matched (just edges), it's enough to perform all the augmentations for those must-use values and then match the rest of the columns to some of the values.
So, this is it. I still believe the targets just had a bad day, or the problem wouldn't stay virgin.

Alright, here is the round overview and that's all for now.

The red-colored New Year

So, the year 2009 is over. First of all, let me wish you all a happy and successful year 2010.

The previous year saw by far the greatest results of Georgian programming olympiads movement in whole and me in particular, the quintessence of which were the Bronze Medals at ACM ICPC 2009. But let me recollect them all in chronological order.

So, January began with two Topcoder SRMs prepared by Georgian writers - first of them by nika and the second by my very self. These were the first (at least as far as I know) international-level competitions with problemsets written by Georgians.

Our problemsetting experiment continued soon after at Winter Programming School in Kharkiv in February. The sixth day of the School was fully prepared by our team Tbilisi SU Triumvirate (Bogdanov, Jimsheleishvili, Lekveishvili) and its coach Temuri Zarkua. Also, we finished second in the overall raiting of the School.

Then, April came and we went to Stockholm in our quest for Georgia's first medals at ACM ICPC Finals. And the debut was really successful :)


Soon after the Finals, George also conducted his first SRM, and I had another two (440, 443).

Well, what else was there? In the end of June, George and me took the third place at KPI Open 2009. In September, I wrote the problemset for Vekua Cup 2009 Individual Competition. In November, Eduard and me took the second place at Open South Caucasian Championship 2009, the team Tbilisi SANGU 1 (Benidze, Rachvelishvili, Rukhadze) won the title of Champion of Georgia for the first time, and Nika took the sixth place at Google Code Jam Finals.

And now, for those of you who think 'What the hell is that red thing in the title', let's get to the final part of this post and my olympic year - my Topcoder rating. I firmly announced somewhen in Autumn that I would meet the New Year with red color at Topcoder, which means getting one's rating over 2200. I changed my handle from eyler to gojira_tc (simply gojira was already taken :|) and kept repeating that the new handle would only look good in red color. In the meanwhile, my rating graph kept falling and climbing, and finally December came with me still hanging close to the cherished line. I took the 11th place at the next-to-last SRM of the year and came closer to red than ever and was looking forward to the last SRM.

The last match of the year was on 6:00AM by Georgian time. Moreover, I had been celebrating the coming holidays on the evening of the previous day. So nothing really assumed that I would manage to keep my word, but still I decided to try. After performing decently in the coding phase, I was around the 50th place, which would guarantee a sufficient rating increase. However, I've made a couple of successful challenges, and looking at the division summary again, was utterly surpirsed, seeing my handle at the 5th place. The thing that surprised me even more was my score - 666 points. I decided to stop any challenge activity and keep the score. I found a code which was failing - at least I was sure I had the proper testcase. But I forced myself to leave it alone. After the testing, my position changed to #3, making it my best performance ever and giving me an unconditional red color. I saw that the code I thought was wrong actually passed the system test, which means I would spoil my great result if I tried to challenge it. Therefore, 666 points saved me.

So, now you can see my red-colored handle and complacent mug. As for me, I am going to take my friends to khinkali as a tribute to the forces which assisted me with their 666 points.