10874 - Segments

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10874

Post by Abednego » Tue Jun 28, 2005 8:59 am

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

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

Re: 10874

Post by little joey » Tue Jun 28, 2005 9:47 am

Abednego wrote:

Code: Select all

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

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

Post by Abednego » Wed Jun 29, 2005 5:32 am

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

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

Post by little joey » Wed Jun 29, 2005 7:39 am

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.

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

Post by Abednego » Wed Jun 29, 2005 8:37 am

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

Post by helloneo » Fri Aug 19, 2005 4:54 pm

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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Aug 19, 2005 6:16 pm

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

Post by helloneo » Fri Aug 19, 2005 8:44 pm

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
Last edited by helloneo on Sun Apr 22, 2007 5:54 pm, edited 1 time in total.

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

Re: hmm..

Post by Martin Macko » Fri Aug 19, 2005 10:35 pm

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

Post by helloneo » Sun Apr 22, 2007 5:59 pm

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

Post by gaurav2289 » Sun Jan 11, 2015 4:55 am

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.

Post Reply

Return to “Volume 108 (10800-10899)”