Topcoder Open 2013: Round 1A

As I begin to write this during the intermission phase, it appears that I did well and solved the three problems. But I am really not sure about the medium I coded. And dumb mistakes are always possible.

I forgot to mention that, since Tournament matches (unlike SRMs) are not practice, I am not going to use my suicidal strategy during these matches. But I think that I I advance to round 3, my only chance to advance at all would be to solve the hard problem, so if I get to round 3, I will open ONLY the hard problem, maybe I get lucky and advance (Yeah right).

250: The one with heights.

You are given a matrix of up to 50x50 heights , each height is from 0 to 9, you can increase or decrease each height any number of times. The objective is for the difference between maximum and minimum height to be at most 1 after you decrease/increase. Return the minimum number of steps (increase/decrease) needed.

Simple! One height of the final matrix got to be the minimum height, and this height is from 0 to 9, so just try each of these 10 values for the minimum height. Then each of the heights has to be between minimum and minimum+1, so it is easy to calculate the minimum cost to make the height fall in that interval.

500: The one with jumps.

You want to jump using leaps of width X starting at a point 0, and up until D or any point greater than it. The catch is that there are many pits, and for each pit i, the space between L[i] and R[i] are impassable (Not inclusive, so L[i] and R[i] are good to stand in), return the minimum X.

The first thing to notice is that we can do D = R[n-1] and everything will be good.

At first it seemed that as long as the last leap fell in R[n-1] it would be fine, so I solved with that assumption and I even passed examples. I passed examples long after spending a good time debugging the solution, so I forgot that I was supposed to actually make sure that the R[n-1] condition was true. I submitted it and then my brain reacted... wait. So it turns out that the case : D=6, L={0,4}, R={3,5} this would be wrong. It is not a good idea to fall in position 5, the best result is 3.

But that challenge case made me notice the real condition: At some point the leap should touch one of the values of R[i]. It makes sense but it is hard to prove. So I just tweaked the solution I already had to make it try all values of R[i] instead of the last one. Time out seemed a risk, but it seems fine.

Anyway, let us say you want a leap that falls in R[i], then you got to first verify that leaps of width R[i] will not have an issue), then you can try R[i]/2, R[i]/3, ... and so and so until R[i]/R[i] and see if any of those leaps also work. Remember the minimum.

For some odd reason, at a point during debug I decided to use fractions instead of doubles. I think it is overkill the bug I was having was not related to precision.

And to check if a leap of width X is possible, you can just try for each pit : If there is a integer r such that: r*X is between L[i] and R[i] then it is wrong.

1000: The one with arrows

You got a matrix of up to 15x15 directions (up, down, right, left). The objective is to change the contents of the matrix so that, no matter what cell you start at, you will always eventually return to the initial position, by always moving to the cell pointed by the direction of the current cell you stand at. The rows and columns are cyclic.

I am not sure why, but I noticed "this is max flow" right a way. I just didn't know how to do it until some thought work.

The trick is that , the objective is fulfilled if and only if for each cell x: There is one cell that points to cell x. Try it. Then we can solve this using min cost perfect bipartite matching: For each cell, assign a target cell to it, each cell must have only one incoming and outcoming cell. If the initial direction of a cell is LEFT, then it is free to assign the cell to the left, else the cost is 1. And so and so for each direction.

Comments?

I plan to make the editorial as quickly as possible to have a free schedule.