SKHeap; A quick MaxHeap and HeapSort implementation

Heap is an interesting data structure. It is a binary tree, that keeps the maximum (in case of MaxHeap) element at the root, thus providing access to it in O(1) i.e. constant time. You can pop the root element in O(lgN) time, and insert new elements into the heap in O(lgN) time as well. Initial buildup of the heap takes linear time. You can sort a sequence of elements using heap, by first building the heap out of all the elements, and then retrieve the elements back. Since initial build up is linear time, each retrieval of the maximum element is O(lgN) time, and you do N such retrievals, the resulting sorting algorithm is of O(NlgN) complexity and called HeapSort.

It is fun to implement these well known data structures and algorithms. So while I was bored and free for half an hour, I quickly wrote a basic implementation of a Heap and HeapSort in Objective-C and pushed it to Github. Check it out and let me know if you like it or find any issues with it.

Topcoder SRM 584; A late correct solution is better than a quick but wrong one

This was an interesting SRM. I solved both easy and medium lightening fast, and moved on to solve the hard one. I understood the hard problem, but just couldn’t come up with a generic solution. So mid way into the problem, I decided to look back at the medium problem to confirm I didn’t miss any corner case. I tested it with a tricky case that I came up with while I was devising the algorithm, but hadn’t tested my solution on after I passed example test cases. Guess what!? It failed!! Bummer. I quickly looked through my solution to cater for this tricky case and resubmitted. That reduced my score for the problem to half of my first submission. But it did save me from a completely failed solution. ;)

DIV2 Medium; Egalitarianism:

If there are any two people in the kingdom that aren’t connected either directly or through some friends, answer is -1. Reason is, there aren’t any limitations imposed between the difference of these two people, and their difference can be arbitrarily large or small.

In the other case, every citizen is connected to every other citizen either directly or through other friends. In such a case, we need to find the maximum friendship distance between any two people, and multiply that with “d”, as that will be the maximum possible difference between their wealth.

We can use Floyd-Warshall algorithm for finding out minimum distance between any two citizens, and then chose the maximum out of these minimum. If maximum is equal to infinity, it means there are two people not connected, so return -1. Otherwise return maximum*d.

A corner case to check for though is that we must not consider a connection to self. If there is a loop in the graph, this loop can have the maximum distance, but we are looking for maximum wealth difference between two different people. This is the case my first implementation missed. Though I did use it in the challenge phase to get +75 points. :)

DIV2 Easy; TopFox:

We can easily generate all possible handles as the constraints are low, and figure out the count of unique ones.

Conclusion:

I am back to division 1. Cool!

Topcoder SRM 583; Depressing

I can safely say I knew correct solutions to all of the three problems in this SRM. I solved easy problem lightening fast. Medium was an implementation problem, with quite a few corner cases, but nothing too tricky. It took me a good amount of time, so that I had little time for hard problem. I knew hard problem was finding maximum cost from each point, to any other point, and returning minimum of it. But I couldn’t implement it in time.

That’s not it though. My medium failed. With one of the most stupidest mistakes ever. I was indexing an array of mine with an input that was 1-indexed, while my array was 0-indexed. All I had to do was to subtract 1 from the input before passing it to array as an index, and my solution passes. :(

DIV2-Easy; SwappingDigits:

All we need to do is swap digits at each pair of indices into the string, and see if it produces minimum integer with no leading 0.

DIV2-Medium; IDNumberVerification:

An implementation problem. Check that each part of the ID is valid, and then return gender of the person.

Conclusion

Sad SRM. But meh! Happens.

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.

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’.