10314 - Three Pigs

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

Moderator: Board moderators

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel »

Could you PM a hard test case, i think i can give you the correct answer ;)
:D Miguel & Marina :D

lky
New poster
Posts: 21
Joined: Fri Dec 05, 2003 5:59 pm
Contact:

10314 time exceeded

Post by lky »

i use dfs to search all possible combination of the graph....any way to reduce time without coding again?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Repeat it 3 times and every time update the map, what's wrong??
Try this test case:

Code: Select all

1
8
1 0 0 1 0 0 0 1
1 2 0 2 1 2 2 0
1 2 1 2 1 2 2 0
1 2 0 0 1 1 1 1
1 2 0 2 2 2 2 1
1 2 1 0 0 0 0 1
1 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1
I think your program would output 27.
But correct solution is 28.
First step:

Code: Select all

x 0 0 1 0 0 0 1
x 2 0 2 1 2 2 0
x 2 1 2 1 2 2 0
x 2 0 0 1 1 1 1
x 2 0 2 2 2 2 1
x 2 1 0 0 0 0 1
x 2 2 2 2 2 2 1
x x x x x x x x
you get 15 acorns
Second step:

Code: Select all

x x x x x x x x
0 2 0 2 1 2 2 x
0 2 1 2 1 2 2 x
0 2 x x x x x x
0 2 x 2 2 2 2 1
0 2 x x x x x x
0 2 2 2 2 2 2 x
0 0 0 0 0 0 0 x
you get 9 acorns (note, there is a way to reach 10 acorns, but you should not use it).
Third step:

Code: Select all

x x x 0 x x x x
0 2 x 2 x 2 2 x
0 2 x 2 x 2 2 x
0 2 x x x 0 0 x
0 2 0 2 2 2 2 x
0 2 0 0 0 0 0 x
0 2 2 2 2 2 2 x
0 0 0 0 0 0 0 x
you get 4 acorns
15 + 9 + 4 = 28

HYri
New poster
Posts: 5
Joined: Thu Oct 21, 2004 6:00 pm

how?

Post by HYri »

To Revenger
5
1 1 1 1 1
2 1 2 2 1
2 1 1 2 1
2 1 1 2 1
2 2 2 2 1
how could it be 9?

isn't it -1? there's no ways for "Three" pig..?

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone »

Three pigs is not claimed that they should use different ways

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 10314 - Three Pigs

Post by RC's »

I got TLE using DFS and backtracking.. I don't know how to optimize my code. How can I know if one path has been taken and so that another pigs will not follow the exactly same path ? some say using DP.. but I don't know how because I am bad at DP.. Can anyone give me hint ?

Post Reply

Return to “Volume 103 (10300-10399)”