## 10874 - Segments

Moderator: Board moderators

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

### 10874

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.
Last edited by Abednego on Wed Jun 29, 2005 8:37 am, edited 1 time in total.
If only I had as much free time as I did in college...

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### Re: 10874

Abednego wrote:

Code: Select all

``````   ...
t[n - 1][1] = n * n;
...
``````
You must have been dreaming ...

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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? :-)
If only I had as much free time as I did in college...

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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. :-)
If only I had as much free time as I did in college...

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 10874 - Segments

Code: Select all

``````code removed
``````
i don't know what's wrong..
please give me some inputs.. Y.Y
Last edited by helloneo on Sun Apr 22, 2007 5:56 pm, edited 2 times in total.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### hmm..

i chaged my code.. and i'm still getting WA..
what's wrong with my code..!!

Code: Select all

``````code removed
``````
Last edited by helloneo on Sun Apr 22, 2007 5:54 pm, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: hmm..

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

### Re: 10874 - Segments

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.
``````