Page 1 of 1
10874
Posted: Tue Jun 28, 2005 8:59 am
by 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:
Could anyone look at at it and find my mistake? I have no idea. Thanks.
Re: 10874
Posted: Tue Jun 28, 2005 9:47 am
by little joey
You must have been dreaming ...
Posted: Wed Jun 29, 2005 5:32 am
by 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? :-)
Posted: Wed Jun 29, 2005 7:39 am
by 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.
Posted: Wed Jun 29, 2005 8:37 am
by 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. :-)
10874 - Segments
Posted: Fri Aug 19, 2005 4:54 pm
by helloneo
i don't know what's wrong..
please give me some inputs.. Y.Y
Posted: Fri Aug 19, 2005 6:16 pm
by 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:
hmm..
Posted: Fri Aug 19, 2005 8:44 pm
by helloneo
thank you for your advice..
i chaged my code.. and i'm still getting WA..
what's wrong with my code..!!
Re: hmm..
Posted: Fri Aug 19, 2005 10:35 pm
by 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:
Posted: Sun Apr 22, 2007 5:59 pm
by 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 ..?!
Re: 10874 - Segments
Posted: Sun Jan 11, 2015 4:55 am
by 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.