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.

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.