10599 - Robots(II)

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

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10599 - Robots(II)

Post by Red Scorpion » Sat Dec 27, 2003 2:52 pm

Hi,..

I used DP to solve this, but always got WA.
Is there any trick in this prob?
can someone who have got AC give me some test cases?

Thanks.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sat Dec 27, 2003 2:57 pm

I got accepted this problem with DP in last contest, but now it results in WA. :( What is wrong?!
JongMan @ Yonsei

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Sat Dec 27, 2003 6:03 pm

Whinii F. wrote:I got accepted this problem with DP in last contest, but now it results in WA. :( What is wrong?!
Yes I got accepted at online contest but now I get WA too.
I think problem in special correction program (sign is yellow).

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Sun Dec 28, 2003 4:45 am

I have met the same problem, accepted codes during the
contest now got wrong answer, and I noticed that no one
has passed. Administrator, plz have a look.
Retired from SJTU Accelerator 2004

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Dec 29, 2003 7:20 am

After rejudge I got AC, thanks.

hj
New poster
Posts: 5
Joined: Sun May 25, 2003 11:56 am

Post by hj » Sun Jan 04, 2004 2:44 pm

hello !
could somebody check this, thanks
input :
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
0 0
-1 -1
output:
CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 10
is it correct ??, is there any tricky input ?

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Sun Jan 04, 2004 6:13 pm

hj wrote:hello !
could somebody check this, thanks
input :
10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
5 1
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 10
6 1
6 2
6 3
6 4
6 5
6 6
6 7
6 8
6 9
6 10
7 1
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
7 10
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
0 0
-1 -1
output:
CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 10
is it correct ??, is there any tricky input ?
Last number is 100.

CASE#1: 19 48620 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100

And don't forget about avoiding trailing space, i.e. no space at the end of line.

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Sat Jan 10, 2004 12:55 pm

Hi

I also use Dynamic Programming to solve this problem , but I never can get AC. I ckecked my program on your test case with garbage on each field and it wrote that the number of ways to collect 19 garbages is 19! (factorial) I realised that I have made a mistake in counting the ways ... can somebody give me a hint ? I has been working on this problem for 3 hours during the cotest , but of course I got WA :<
This is the only thing I can't do about this problem - my program [in Pascal] correctly outputs the maximum amount of garbage that can be collected , corretly writes the sample path , but I can't invent how to count the ways. Please help

Kiha (tm)

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Jan 11, 2004 6:37 pm

Is this a valid output for the test case given above?

CASE#1: 19 48620 1 11 21 31 41 51 61 71 81 91 92 93 94 95 96 97 98 99 100

Someone please give a few more test cases. I can't remember when was the last time I got so many WA-s :(

Thanks in advance

Dreamer.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Jan 11, 2004 8:06 pm

Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle. :)
JongMan @ Yonsei

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Jan 12, 2004 5:01 am

Whinii F. wrote:Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle. :)
No. Resulting number fit into 64-signed integer.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Jan 12, 2004 7:53 am

Hi, I used 'long long' to solved this problem.
But maybe the judge data fit into 64-signed integer.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Jan 12, 2004 8:06 am

Oops. :( Is it true?? For test cases like 100 100 (and 10000 garbages, one in each grid square), the resulting number should easily overtake 2^64, where my program outputs

22750883079422934966181954039568885395604168260154104734000

..

I got WA using int during the contest and noticed this to get AC. Of course this problem's core is not bigint, but they should have commented about upper limit of the resulting number. :(
JongMan @ Yonsei

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Mon Jan 12, 2004 8:25 am

Whinii F. wrote:Oops. :( Is it true?? For test cases like 100 100 (and 10000 garbages, one in each grid square), the resulting number should easily overtake 2^64, where my program outputs

22750883079422934966181954039568885395604168260154104734000

..

I got WA using int during the contest and noticed this to get AC. Of course this problem's core is not bigint, but they should have commented about upper limit of the resulting number. :(
I use long long during contest and my program got AC.
I think problemsetter don't want contestant to use long arithmetic,
because problem is enough difficult.
Though, I agree with Whinii that problemsetter had to comment it in problem description.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Mon Jan 12, 2004 6:56 pm

Whinii F. wrote:Just like a lot of combinatorial problems, it is likely that the resulting number can be too large for a 64bit integer to handle. :)
Hello, Whimi F.
Could you say how to calculate the ways that the maximum garbage ?
Thx :D

Post Reply

Return to “Volume 105 (10500-10599)”