## 10314 - Three Pigs

Moderator: Board moderators

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico
Could you PM a hard test case, i think i can give you the correct answer
Miguel & Marina

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

### 10314 time exceeded

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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?

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

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 ?