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.

SPOJ; The Next Palindrome

This problem asks for next integer that is also a palindrome, after a given integer. A naive approach would be to start iterating over integers after the given one, and see if you hit a palindrome. Whenever you do, that is your answer. But the problem is that given input can have 1000000 digits. Iterating over integers that big to find a palindrome is going to take eons, besides the fact that you can’t even represent that big a number with a primitive type.

Solution:

We are going to use string operations to generate next palindrome. Notice that a palindrome is identified by its left half digits. If you know the first half of the integer, the second half is just a mirror of the first half.

We start by first generating a palindrome out of the given input, by mirroring first half portion over to the second half, around the center. This will give us a palindrome that is closest to the input number. Any palindrome which changes any digit of the first half of the given input, will take us farther away from our given integer in either directions.

E.g. if input is 39474657, we change it to 39477493.

Now that we have a palindrome which is closest to given input, we just incrementally generate higher palindromes, till we have a number that is higher than our input. In order to do this, we increment the center digit. If it is an even sized integer, there are two digits in the center. Remember that as soon as we increment the center digit, we will have a palindrome that is next higher than our existing one. Only caveat is that if the center digit is a ‘9’. In which case we change it to ‘0’, and increment the next digit to the left (also incrementing its mirror digit to the right). If next digit is ‘9’ too, we keep on performing this operation till we hit a digit that isn’t a ‘9’. It is possible that we encounter all digits as ‘9’, in which case, we add a ‘1’ to left of our input, while incrementing the right most ‘0’ as generated by previous operations, to a ‘1’.

Google Codejam 2013 Qualification Round

Google Codejam 2013’s qualification round is in progress as I write these words. I have solved enough problems to be confident that I will qualify. While I am eyeing the last remaining one, I am not going to try too hard to crack it. In this post I am going to briefly discuss problems in the round, without hinting on any solution.

Problem A. Tic-Tac-Toe-Tomek:

This is an implementation problem. You have to check whether game in current state is a win for ‘X’, ‘O’, a “Draw”, or  “Game has not completed”.

Problem B. Lawnmower:

You have a NxM meters of lawn, and you want to cut grass in each 1×1 meter of it to a certain length as given in problem input. The only way you can use your lawnmower is to set its setting to cut grass above a certain length, before it enters the lawn, and then let lawnmower enter lawn from any direction perpendicular to edge of lawn, cutting grass as it crosses the lawn in a straight line till it exits on the other side. You can use your lawnmower as many times as you want, and can not change its settings once it is inside the lawn.

You are required to validate whether it is possible to use your lawnmower to cut grass of your lawn according to the pattern given as input.

Problem C. Fair and Square:

You have to find the number of Fair and Square integers in a range A to B inclusive. A fair and square integer is an integer which is a palindrome and also a square of a palindrome. This problem has three input sets. One small, and two large ones. You won’t go very far with a naive solution with the large inputs. Specially the second large.

Problem D. Treasure:

I haven’t yet solved this problem. You have N chests, and you start with a set of keys. Each chest opens with a certain type of key, and a key once used can not be used again. Each chest has additional keys that you can pick up and use. You have to determine the lexicographically smallest sequence to open the chests in. It is possible that not all chests can be opened no matter what sequence is followed, in which case solution is IMPOSSIBLE.

Conclusion:

I have solved problems A and B, and small and first large set of C with a great deal of confidence in my solutions. I am pretty sure my solution to second large set of C is wrong. And I haven’t attempted D yet.

Topcoder SRM 575

This was one exciting SRM. I started off very badly. It took me long while to figure out the easy problem. I was the second last to submit it in my room, getting a very low score. Fortunately, medium was an easy game theory problem, and I was able to submit it fast. At the end of coding session, I was somewhere in the middle of the room, score wise. In challenge phase, I was able to get two successful challenges, while lots of other players tried failed challenges. I ended up being at the top of the room after challenge phase, which was very surprising given my totally disastrous start to the match. Both of my problems passed system tests, and I got a +64 in rating. Yay!
Continue reading

Making all integers in an array same using minimum steps

In past rounds of both topcoder and codeforces, same problem showed up with slight variations. In generic terms, we had to make all integers in an array same, using minimum number of steps, where a single step is incrementing or decrementing a single element of the array by a constant integer, say ‘d’.

Solution:

We need to figure out median of the sorted array, set that as the target, and make all elements equal to this target. This will ensure minimum increments/decrements. When the number of elements in array “N” are odd, median is (N/2)th element of the array. If N is even, we have two medians, (N/2)th and (N/2)+1th element. We can choose any integer between these two medians (inclusive) as the target (given that selected integer is equal to other elements modulo ‘d’).

Remember that in order for a solution to exist, all elements in the array need to be equal modulo “d”. Because otherwise, no matter what number of increments/decrements your perform, integers can’t be equalized.

Explanation:

Why select median element as the target to make all other elements equal to?

Lets take an example: A = [2, 4, 5, 8, 9, 15, 35], d = 1

Here, median element is N/2 = 7/2 = 3rd element = 8 (0 indexed).

Lets start by deciding not to use median element as the target. Lets select another integer, ‘x’, as the target, which is not the median. It can be in either direction of the median, left, or right. In our example, let x = 4. Now lets say that the number of increments/decrements we had to perform to make all elements in given array equal to x, is ‘c’, the cost. Lets move our chosen target x closer to median by an element by incrementing by d, so that we now have one more element to the left, and one less on the other side. In our example case, let our new x = ‘5’. Now we have one more element to the left of our target, and one less to the right. Now in order to equalize all elements in our new array, which was equalized to our previous target of ‘4’, notice that we will have to add ‘d’ to all the elements to left of our target, and reduce ‘d’ from all elements to the right. Since number of elements to the left is 2, and there are 4 elements to the right. our cost ‘c’ is reduced. We can keep on going like this, till we reach the median as our target ‘x’. Once we have chosen median as our target ‘x’, we obtain an optimal cost ‘c’. Going either to left or right of it, only increases our cost.