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.

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

Topcoder SRM 555; Implementation Subtelties

This was my first non TCO div1 SRM, as last SRM advanced me to division 1. With this extra joy, came the nervousness of competing in a room where almost everyone else was supposed to be much better then me. Anyway, I had decided to focus on just the easy problem, as solving it alone would have raised my probability of gaining in rating. After struggling with it initially, I came up with the right approach to solve it. Unfortunately, I couldn’t get the implementation subtleties correct till the end, and ended up with non positive score. After the SRM, I entered practice room to validate that my DP was right, and also tried a simpler recursive method that worked as well.
Continue reading

Topcoder SRM 543; A lesson in initializing your variables

Topcoder SRM 543 could have been my best performing SRM, and I was pretty sure before the systests update for me, that it is going to be so. I was bound to end up in the top 10, what with my quick submission to easy problem, reasonably quick submission to medium, and three successful challenges. But there were surprises in the wait for me, and not happy ones.
Continue reading

Topcoder SRM 533; A disappointment

Just as the title suggests, this SRM was a bitter disappointment for me. The easy problem was easy, but it took me some time to come up with a simplified solution. I made up for this delay with a successful challenge in the challenge phase. But the sad part was the medium problem. By reading the problem statement, I instantly knew it was a DP, and that the greedy solution won’t work. Part of my jumping straight to a DP solution was because of my current love for DP problems and thus being always preoccupied with a solution containing DP. But alas, things didn’t work as planned…
Continue reading