Saturday, February 23, 2013

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.


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


vexorian said...

I failed system tests in 500. But writer says that the logic that at least one leap should end in an R[i] is correct. Also, according to coder history the test case I fail is because of time out.

edufgf said...

Is there any official editorial for 500problem?

vexorian said...

I will write and release it within some hours.

But yeah, it is all about trying all the ways in which the leap falls at R[i]

vexorian said...

Ok, fixed my 500.

Yes, using fractions was overkill, and actually the reason I timed out.

But it was definitely a good thing to only use integers, when I replaced fractions with doubles, I fail a test case for precision.

Here's the modification of my solution it is basically the same as what I submitted, except that it does not call fix() (and thus does not call gcd):

hss said...

Nice logic for Div 500. Difficult to come up with the idea for div 500. The proof for the greedy approach could be by contradiction which : if there exists a gap between all R[i]s and next landing, it can be safely shifted by the minimum possible gap so that you do not fall in the pit. Hence the minimum possible gap between R[j] and next landing should be 0 over all possible values of j.
Using your idea,