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


With this SRM, I advance to division 1, and I hope to stay their for the time to come.

Be Sociable, Share!

Leave a Reply