Heroes of Magical Might

"If the hero choose to enter the gate at (2,2), he may end up at (1,2) or (2,3) with equal probability 1/2."

Should'nt this line be:

"If the hero choose to enter the gate at (2,1), he may end up at (1,2) or (2,3) with equal probability 1/2."

@hardcode It really should be “chooses”, but the change you suggested is the important one.

can anyone tell how the output to third case becomes 3.5

" You are guaranteed that the hero can always collect at least one treasure with probability greater than 0. "

But I see that in the second test case, the value is given as zero.

Can somebody please tell what is the correct value of probablity there ?

@Kunal Jain: The 2 probabilities are different. Read the problem statement carefully!!!

Problems with the problem statement:

1. "In addition, if your hero's current square is a gate, your hero could choose to enter the gate."

Not clear whether that counts as a separate move or is an additional part of the a move (although it can be figured out from examples).

2. "suppose your hero's starting position is at (1,1)"

It is not clear what (1,1) represents. Is the corner at (0,0) or (1,1), and which corner is it (top-left or bottom-left)?

3. The input specification forgets to mention P (and optimally, also its formatting - can it say "1e-100", up to how many digits?)

4. "rounded to two decimal places". Again, not clear what "rounded" means (is round(1.235)=1.23 or 1.24?). In the future problems, a better approach could be "output up to X decimal places, errors up to epsilon are OK", because that seems to be the intention, while the current wording doesn't allow for any error, strictly speaking.

I guess my point 2 can be figured out from context.  So points 1,2,3 can be considered nit-picking, since they all can be figured out from context, examples, or by trial-and-error :)

can anybody tell me how 6.41 iscoming in the last output

as though i fell 6.66 is the mnimal possible move to get the first treasure

How in second case can i goto treasure as probability is 0 ??

@admin where is input for P given ???

@suhash What do you mean by reading carefully.

I tried amny times.

Can you point to which line you are reffering to.

'He may go in the remaining 3 directions with equal probability (1-P)/3.'

P=0 doesn't mean he doesn't move at all. Just not in the one he chose.

@stephen Ya, so in case 2 the prob is zero, so if he try to move to (0,1) he will remain at (0,0).

And he can not do any thing other as there are no more cells

So every turn, he must try to move to (0,1), and due to prob=0 he will always remian at (0,0).

@stephen and second thing is that even then how comes he reach (0,1) in expected 3 steps in example 2

"In each turn, you can:

Choose one of the four possible directions,"

You seem to think you can only choose one.

@piyush: I think stephen answered your question!!

@uday jalan: The sample output(6.41) is right. You could write a brute force program to check that. If you are'nt getting 6.41, then you are definitely missing something in the problem statement!!

A question:

"In addition, if your hero's current square is a gate, your hero could choose to enter the gate. "

Is that means I must get a move to the adjacent square and then can use the gate?

(if so , can i use it after move to an obstacle and go back?)

or I can use it without move to the adjacent square?

There is a input for this question:

5 2

S@

##

@#

##

@*

0.25

Can anybody answer my question or add this data to examples?

'In addition' means in addition to your first four options. If your current square is a gate, you can either enter the gate or move in the next turn; not both.

Thank you!

And I got Accepted. :)

AAAAAAAAH TAKE THAT YOU STUPID PROBLEM HA!

Sorry. After 96 failed submissions before accepted I couldn't help it.

@Stephen: 96 failed submissions?  Better give back your title :P

Hey, there's nothing wrong with persistence ;)

(Most of my submissions were silly attempts at getting a bad solution to run in time, anyway. I'll be interested in seeing which other solutions can handle some tricky test cases that didn't seem to be included, though.)

@admin: I can't make any further submissions to the problems in this month's contest. The submit button for this one just links to http://www.codechef.com/MARCH10/problems/N2/#.

@admin: This is fixed, thanks, but now I've disappeared from the rank list on the main page. And I was so proud to see my name up there in first place, along with everyone else's. ;)

@Michael

The rank-list does not seem to like having more than 11 people in it. I assume the ranking(among the ones with a common rank) is shuffled from time to time. You can see this by comparing the 2 rank-lists(global and Non-Indian). Other than the unlikely case of both being the same, you can pinpoint the two people who are missing in atleast one of the two lists.   For example, yesterday(around 8:00 pm EST), I was missing from the global list and Josh Metzler was missing from the Non-Indian rank-list.

Also, there are some other bugs. My name seems to appear in both first and the second page from time to time. Names disappearing from the rank-list might be a consequence of this.

@Balakrishnan: Ah, ok. So long as the chef isn't picking on me. Thanks for the reply.

can any body explain how output for testcase 4 is 6.41.

i don't get it.

Can anybody give the hint as to how to proceed to solve this problem ?

I have no idea on how to get even the 4th sample output.

Let D[i][j] = Expected no. of steps to reach from location x,y to any one of the treasure.

So, the problem asks you to compute D[S(x)][S(y)]

Then trivially, D[x][y]=0 where x,y is location of each treasure (you don't need to move at all if you are present there).

From the problem it follows that for all other valid i,j:

Try for each of 4 the directions:

D[i][j]=min over all 4 directions(p*(1+D[x][y]) + sum over other 3 directions ((1-p)/3 *(1+ D[r][s]))) where x,y is the neighbour in direction you moved and r,s are the 3 neighbours in the direction you didn't move. If you can't move to either one of the directions due to it being blocked or out of boundary, then substitute D[i][j] in place of D[r][s] or D[x][y].

Now coming to the gates:

In addition, one may use the gate if the current location is a gate, so,

for each gate i,j:

D[i][j]=min(D[i][j],1+sum(D[x][y])/(no. of gates -1)) summing over all gates x,y other than i,j

That is if you are at a gate, you can either not use it (first argument of min), or if you use it then expected no. of steps = 1 + average over expected values from all other gates.

This is easy so far. To get the final answer you can iteratively get there.

1. Initialize D[0][i][j]=0 for all i,j

2. Then using the equations derived above, for each k>0:

Intialize D[k][i][j] to infinity.

D[k][i][j]=min(D[k][i][j], p*(1+D[k-1][x][y]) + sum ((1-p)/3 *(1+ D[k-1][r][s]))) for all valid i,j

In addition, for each gate i,j:

D[k][i][j]=min(D[k][i][j],1+sum(D[k-1][x][y])/(no. of gates -1)) for all other gates x,y

This coverges fast, and you don't need to go beyond k from 0 to 100 or so for given test cases

So, total complexity = M*N*K where K = max iterations one needs to loop through.

Are you serious? That approach shouldn't work at all; for example, a simple 20x20 case with no walls going from top left to bottom right takes about 20000 steps to converge to 2dp when P=0.25. A more complex case where every second row is nearly all walls (ie the path takes a zigzag approach to get from top to bottom) takes about 800000 steps to converge when P=0.25.

If that managed to pass the test cases must have been very weak.

The real problem is a bit harder than that.

That one actually worked. I was also surprised when my solution passed with that approach.

While testing locally, I also tried your case#1 but with P=0, 1 and 0.5 It converged pretty fast for these values. But you are right, I see that the convergence becomes slow for P=0.25

For your case#2 (alternate walls in 20x20 grid), here are some results for 7dp convergence:

P=1 -> 131 iterations

P=0.5 -> 739 iterations

P=0.25 -> 791966 iterations (dadgum!)

P=0 -> 658 iterations

It did pass the test cases though, so I guess there weren't any with P ~ 0.25

Since test cases tend to be weak (i.e. apparently just randomly generated), value iteration was worth a shot, before going to more trouble. Of course, I shouldn't have got away with it, and I don't like it either. We should be forced to solve the problems, not have the option of weak algorithms that are likely to work.

I was pretty surprised when my iterative approach passed, too, since I had found the zigzag case.  I was planning to solve a couple sets of equations.  They would be of the form Cij = Cxy*p + (Cab + Cad + Ccb)*(p-1) + 1.  The problem is that I need to find the best direction to try to go from each cell before I have the equations right.  Finally I would need to take the gate on gate cells if the expected value from all other gate cells + 1 was less that the expected value from this gate cell.

was this an expected approach ?

I remembered there was a similar problem in Topcoder Div 1 500 with additional constraint that it will represent a tree, so I assumed maybe there's no complete solution exists for this problem or probably it's very complex.

By the way i tried iteration based approach lots of time but kept getting WA :(

This has to be a joke?! Disappointments here at CodeChef just keep on coming. Despite all the nice words about how you value our feedback, there doesn't seem to be much you're actually doing about it. "Since test cases tend to be weak" - I think this says it all about the reputation you've established.

It's obvious iterative solution shouldn't stand a chance and I was really looking forward to some "wow"-factor of the intended solution. Here's how I've spent a week trying to solve this problem:

You can formulate the equations X=min(A,B,C,D) as a linear program with constraints X<=A, B, C, D and then maximize for X. You end up with close to 2000 constraints and 400 variables. I've failed trying to implement my own simplex tableau method because of some degenerate cases and precision problems. In the end I've borrowed an implementation from Numerical Recipes which solves a single test case under a second. It timed out and the only improvement I could see was to implement some interior point method, about which I know pretty close to nothing. That's where I gave up.

I used an iterative approach, but instead of replacing the old calculation with the new calculation, replace it with new+.97*max(0,new-old).  This leads to much faster convergence (althogh theoretically I think could lead to WA).  I solve the zig-zag case in about 8000 iterations.  I got TLE several times due to cases where certain squares were inaccessible.

I did the following:

1) Run BFS to determine an initial strategy, as well as remove squares unaccessible from treasures.

2) Given the current strategy we are using, solve the matrix equation to get the expected number of turns to reach a treasure from every accessible square.

3) Rechoose the strategy so that we try to head towards a square with less expected number of turns.

4) Repeat 2) and 3) until the strategy does not change.

This seemed to work as well with the "tricky" test cases mentioned above.

I also find it very disappointing that the iteration approach passes. CodeChef definitely needs to have some testers on the problems before using them. I would also be interested in hearing if there is any clever (and fast) solution to this problem that doesn't exploit the weak test cases.

Since I didn't really have any idea as to how to solve this except for using iteration, I initially tried using iteration but with little hope that it should work. After playing around with some test cases I found the zig-zag case with P=0.25 that took around 800000 iterations to converge, which destroyed my small hope for this approach. I then used the iterative approach for about 1000 iterations, and used the best strategy found for each square to write up a set of simultaneous linear equations for the squares. I solved these equations using Gaussian elimination. This approach should pass if the iterative solution fairly quickly finds the correct strategy for each square. However I suspect that this could take a lot of iterations, but I haven't really looked into it.

My approach is very similar to that mentioned by Mark.

I used Gaussian elimination after running the iterations for a couple of times. Then again run Gaussian elimination to get the exact value of expectations given the current strategy.    I got AC when the frequency of running Gaussian elimination  was around 1 in every 30 iterations. In-fact using this strategy, the number of iterations on an average is much lower than the iterative approach.I was thinking I would need to code up the Gaussian elimination applied to sparse matrices, but I never ran into the need for doing that. Ironically, I never tried the iterative scheme mentioned by Gagandeep (I had coded it as a ground truth and was under the impression that it would never get accepted).

I am extremely disappointed. Yet another problem that it appears the problem author can't even solve themselves. I spent a long time working on my solution to this problem knowing the iterative approach had no hope.

I eventually came up with exactly the same approach as Cedric above, which converges extremely fast - ie, not talking hundreds of iterations, perhaps less than 10 even for hard cases.

The problem is that you would think solving a 400x400 matrix of equations would take 400^3 time, and thus be too slow. However, the matrix is very sparse. If there were no gates at all, then since each row can be expressed fully in terms of the previous row, you can solve this in 20^4 time.

And how do you deal with gates? Gates could throw in a big problem, since a single gate could use values from absolutely anywhere else in the grid. The trick is to introduce a new variable - the sum of the values of all gates. Now each gate can simply be expressed in terms of this sum and a constant, so we get back to the simple 20^4 case (where the last two columns of the matrix are this sum and a constant).

Thus we can solve the matrix equations in 20^4 time, and this easily runs fast enough.

What a waste of a nice problem. Thanks, Codechef.

This must have come up before, but why not let contestants submit test cases? It can work like this:

1) If your test case defeats some currently accepted solution, it is added to the test cases, otherwise it is rejected. (You can submit it again later.)

2) Your own submissions don't have to pass your own test cases. Why? You know the answers to your own cases, so there's no point. On the other hand, if you're the only one who knows why a problem is impossible, you deserve the point.

3) User submitted test cases shouldn't count towards total running time, because of (2).

It's not ideal, but it would have worked perfectly for this problem, and some others I can think of.

It would probably be a good idea to have a deadline for submitting test cases, say halfway through the contest. It shouldn't become something to use as a contest-winning strategy. The idea is just to sort out the weak test cases problem.

@Stephen: Nice job. I wasn't sure there is a solution, since the problem with solving equations is that it's so slow, but that trick should do it. It would be interesting, but probably difficult, to prove that it can handle all cases.

I think user submitted test cases (say for the first two days or so) would be great.  I disagree with your points #2 and #3, though.  Your own code should definitely be able to solve it within the time limit, and if it doesn't count towards the run time, then people could just brute force the hard cases.  I don't see why submitting a test case means you necessarily know the answer - I would hope the judge is used to come up with the correct answer.

If the judge can't solve the user submitted case in time, the time limit can be extended, the judge rewritten, or the problem thrown out.

I didn't mean you shouldn't have to pass user cases within the time limit. Obviously that is very important. The idea is that running time on user-submitted cases won't be used to determine rankings, otherwise it could be abused. You submit a hard case that takes long to solve, while your solution includes code for recognizing the case and printing out the pre-computed answer, giving you a better total running time than those who don't do the same. Not a big issue, really. Just trying to cover all the angles.

Submitting a test case doesn't necessarily mean you know the answer, but what stops you from computing it? (Assuming you have solved the problem.)

That's a good point about being able to recognize and print out a precomputed answer for the test case you submit.  Fortunately the runtime isn't actually used for ranking in the competition - just on the problem page, so that isn't a big deal.  I did want to add, though, that for obvious reasons we shouldn't allow user submitted cases to the tie breaker problems.

@Josh: it depends on the problem.  Marathon Match 56 allowed user submitted test cases (during the first week only) and it seemed to receive generally positive feedback.

Some analysis here: http://discussed.codechef.com/showthread.php?t=1079

@Stephen Merriman

Good job!

It's amazing that you came up with that powerful solution!

But maybe you can proof your solution can pass all test cases (by calc the complexity of time of iterations) OR find a testcase defeat your solution.

@Michael Dorfling

That's a nice idea!

But there must be a really RIGHT standard solution for each solition.

Or if it come out a incorrect output , maybe some player's program have the same wrong algo but pass the test.

Maybe this problem's writer doesn't have a such program.(I just guess ^o^ )

---

As for the tester,it really need such process to confirm the writer's solution.

I don't want to see the same issue as this month's N5:Traffic jam.

The writer corrected the data after so many days.

I hope CodeChef will be better and better!