Codeforces round 186; The one that got rated

We finally had a codeforces round that went smooth and rated. :) Past two rounds that I participated in, both had something going wrong with it, and ended up unrated.

DIV-2 Problem A; Ilya and Bank Account:

You are given an integer N, and you are allowed to drop its last digit, or second last digit, to create an integer with greater value. If N is greater then 0, dropping allowed digits can not increase its value. If it is smaller then 0, dropping one of the allowed digit will give you the largest possible integer.

DIV2 Problem B; Ilya and Queries:

First, iterate over the array, calculating positions where s[i]==s[i+1]. Lets call this new array dp. Then dp[0] = 0. For i=1 to s.size()-1, dp[i] = dp[i-1] if s[i]!=s[i-1], or else dp[i] = dp[i-1]+1. Now to find out count of all the integers ‘i’ between [l, r), such that s[i] = s[i+1], we can simply use dp[r]-d[l].

DIV2 Problem C; Ilya and Matrix:

We want to place all of the 4^n integers in the matrix in such a way, that the beauty of matrix is maximised. Beauty of matrix depends on the highest integer within it, plus the beauty of matrices that we get once we divide given matrix into four square matrices. One of these matrices will get our original highest integer that existed in the bigger matrix this smaller matrix is part of. In order to maximise beauty of the remaining three, it makes sense to place the next three highest integers out of our original 4^n integers in them. In the next step, we will have 16 sub matrices, and in order to maximise beauty of each, it would make sense that all of those 16 have the 16 highest integers from within the 4^n integers. And so on. Thus we iterate over sorted array of our 4^n integers, n times, each time adding first  4^i (where i is iteration number) integers from the array into our result.

DIV2 Problem D; Ilya and Roads:

This was a nice dynamic programming problem. Though I couldn’t figure correct recurrence for it. If someone has a simple explanation for it, please comment.

Conclusion:

I got a +140 in rating. Yay!

Topcoder SRM 580; The one that made me feel stupid

So my second SRM with me being in DIV-1. And yet again I dropped to DIV-2. I focused on just the easy problem, and it *was* easy, but needed a bit clarity in thought. Alas I couldn’t solve it. Though my thought process was on the right lines, but not good enough.

DIV-1 Easy; EelAndRabbit:

You can choose any two time instants, on which your rabbit can capture all fish right infront of him (having any part coincide with the “x” position on which rabbit is standing). All fish move with same speed. Thus their formation will be same at any given moment in time. Thus you can easily transform the problem into choosing two positions over the X-axis for your rabbit, instead of two time instants.

But problem is, X-axis is comprised of real numbers. How can you choose two positions in this interval of real numbers? Let one of the two positions which will give us an optimal answer, to be ‘x’. While standing over ‘x’, lets say our rabbit can capture ‘y’ number of fish, that all intersect the vertical line that crosses the stream starting from position ‘x’. How far to the left, or right, can you move this vertical line, such that it still intersects with ‘y’ number of fish? If you drag it to the left, you can move till you touch the tail of any one of the ‘y’ fish. If you move any further, you will not hit this fish anymore, and thus your solution won’t be optimal. Same is the case if you move it to the right (you can go as long as the first fish whose head you hit).

Thus all you need to do is iterate over either all the tails, or heads, and select two of them which give you highest hits over the fish. There are at most 50 fish. Thus you can search over all possible pairs of tails (or heads), and select the pair that gives you highest fish.

Conclusion:

I liked this problem. And I hope to be back to DIV-1 soon.

Topcoder SRM 579; Not that tough

And one more time I enter the DIV-1 class with a good performance in this SRM. I was able to very quickly solve the easy one, implement a clear solution for the medium, and devised a correct solution to hard problem, though I couldn’t finish implementing it in time during the contest. Later in practice I confirmed that my solution was correct.

DIV-2 Easy; PrimalUnlicensedCreatures:

In order to defeat a Grez, it helps to have maximum level possible to achieve before fighting this new Grez. In order to do so, it is intuitive that one should fight all creatures with power less then the next Grez you are about to fight. Thus solution is to sort creatures by increasing level of power, and incrementally beat creatures, till you can’t beat anymore of them.

DIV-2 Medium; UndoHistory:

This is an implementation problem. One needs to be careful and make sure to understand what the problem is actually asking for. Only tricky case is when you have to decide between replacing your existing buffer with a string from undo history vs typing a few more characters to complete what you could restore from undo history.

DIV-2 Hard; MarblePositioning:

You have to place marbles in such a way that they do not overlap, yet they are closely packed such that distance between first and last marble is the minimum. Since number of marbles can be at most 8, we can iterate over all possible permutations, and figure out what is the least possible distance between first and last marble in this arrangement. Minimum of all arrangements is your answer. In order to ensure minimum distance between first and last marble for a specific arrangement, we need to place each new marble at a position that is closest to already placed marbles yet do not overlap any one of them. To do this, check what position you will have to place this new marble against each existing marble, such that it only touches it. The maximum position of all of these is the one you should place this new marble at.

In order to figure at which position you should place a marble while comparing it to an already placed marble, notice that the new marble will have to touch existing marble at one point, such that the direct distance between their centers will be r1+r2 (radius of first, plus radius of second marble), while the distance between their points touching the ground will be sqrt((r1+r2)^2 – (abs(r1-r2))^2)). Reducing this equation gives you 2*sqrt(r1*r2).

Conclusion:

With this SRM, I advance to division 1, and I hope to stay their for the time to come.