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.