10874 - Segments

[Abednego]

The contest started at 2am my time, so I was not thinking clearly during it. :-) I could not figure out why my code for this problem was wrong. But even a few days after that, I still have no idea. It looks to me like a very simple DP problem.
1. You scan row by row from top to bottom.
2. At each row, you will either go down at the left end of the segment or at the right end.
3. You try both possibilities and get 2 sub-problems, which you solve recursively.
4. You keep a memoization table to avoid recursing too many times on the same sub-problems.
I did this iteratively:

Code: Select all

erased. works now

Could anyone look at at it and find my mistake? I have no idea. Thanks.

[little joey]

Code: Select all

   ...
        t[n - 1][1] = n * n;
   ...

You must have been dreaming ...

[Abednego]

I must still be dreaming! Of course, if the last segment has length 0, this doesn't work. But when I switch these two lines:

Code: Select all

        t[n - 1][0] = n - L[n - 1];
        t[n - 1][1] = n * n;

I still get WA.

I even changed them to

Code: Select all

        t[n - 1][1] = R[n - 1] - L[n - 1] + n - L[n - 1];
        t[n - 1][0] = n - L[n - 1];

I'm going to look very stupid when somebody tells me what's wrong, won't I? :-)

[little joey]

Now, maybe I am dreaming, but I interpreted these two lines as being the number of steps along the bottom line to reach the goal square from resp. L[n-1] and R[n-1], and changed them to:

Code: Select all

        t[n - 1][0] = n - L[n - 1];
        t[n - 1][1] = n - R[n - 1];

This got me AC, without any other changes.

The number of steps you need to visit all the squares is either n*n-1, if n is odd, or n*n+n-1, if n is even, so n*n struck me as a too high number.

[Abednego]

Ahhh! My t[j] means "number of steps from row i, end j, if segment number i has already been covered". It's an off-by-one error. Thank you very much. I can't believe it took me 4 days and a lot of help to figure this out. :-)

[helloneo]

Code: Select all

code removed

i don't know what's wrong..
please give me some inputs.. Y.Y

[Cho]

Your code fails with this input:

Code: Select all

5
4 4
3 5
1 1
2 3
2 2
9
6 6
2 7
4 8
3 4
5 8
3 5
6 7
1 2
5 6
0

My output:

Code: Select all

18
56

[helloneo]

thank you for your advice..
i chaged my code.. and i'm still getting WA..
what's wrong with my code..!!

Code: Select all

code removed

[Martin Macko]

It fails on this input:

Code: Select all

10
2 8
3 7
5 8
2 6
5 7
6 9
5 10
4 4
7 8
2 7
0

My AC's output:

Code: Select all

66

[helloneo]

Finally got AC..~!
My greedy was wrong and I solved it with DP..
Hmm.. it took me about 20 months to solve this problem though ..?!

[gaurav2289]

I am getting TLE for the below code even though I am using DP Can someone help me ?

Code: Select all

Removed after AC. I was using std::vector< std::vector<int> > for memoization table construction and destruction of which is too slow and results in TLE.