Page **1** of **2**

### 10314 - Three Pigs

Posted: **Tue Jul 02, 2002 3:35 am**

by **gvcormac**

10314 is unreadable with Netscape, and even with Explorer 6 is has one very long line that doesn't wrap.

In general, the format of this new batch is mangled - even for the "borrowed" questions for which the original html was fine.

### 10314 Three Pigs....

Posted: **Sat Jul 13, 2002 6:23 pm**

by **20571KJ**

I don't know how to solve this poblem. It seems to be so tricky !!!.

Anyone would like to help me ???[pascal]

[/pascal]

Posted: **Sun Jul 14, 2002 3:03 pm**

by **Revenger**

The problem is very hard. To solve it you should use DFS + BFS + Backtracking. My program size is 7 KB!

### try using minimal cost stream

Posted: **Tue Aug 06, 2002 9:10 am**

by **dynamic**

i think it is the same as an IOI97 problem

try to construct a net and use minimal cost stream

Posted: **Tue Aug 06, 2002 10:02 am**

by **Revenger**

To dynamic: Have you solved this prob? I think that you haven't. It's NP problem and the only way to solve it is Backtracking

Posted: **Tue Aug 06, 2002 6:15 pm**

by **dynamic**

i'm terribly sorry that i made a mistake...

### Three pigs reduction

Posted: **Tue Sep 10, 2002 2:47 am**

by **Pedrinho UFPE**

Are you sure it's a NP-Problem? Why?

This problem is:

Given a graph G = (V,E), a subset S of V and 2 vertices x and y of V, find a path from x to y visiting the maximum elements of S. For each vertex v of the path xy in S, do S' = S - {v}. Return to the first problem with S'. Do this 2 times, and print #S - #Sfinal. Ok?

How did you solve this problem?!

Thanks for all!

Posted: **Tue Sep 10, 2002 5:41 am**

by **Revenger**

Pedrinho UFPE wrote:

Given a graph G = (V,E), a subset S of V and 2 vertices x and y of V, find a path from x to y visiting the maximum elements of S. For each vertex v of the path xy in S, do S' = S - {v}. Return to the first problem with S'. Do this 2 times, and print #S - #Sfinal. Ok?

This is algo is really good if pig can visit the same cell twice. But the pig can not. May be I misunderstood your algo. To prevent visiting the same cell twice we can use DP, but it use 2^|S| bytes of memory, where |S| - is the nubmer of elements in S.

Posted: **Tue Jul 01, 2003 1:13 pm**

by **windows2k**

Could you describe your thought to solve the problem?

I don't know how to do

### 10314- more inputs please!

Posted: **Mon Jul 21, 2003 3:49 pm**

by **bigbit**

Hi!

Cloud someone give me some inputs for 10314?

### What's wrong??

Posted: **Fri Aug 29, 2003 9:04 pm**

by **Miguel Angel**

Can anyone help me with my code, I don't know what is wrong, It gets WA at 0.04 s. It uses B&B, so it's impossible to fail, maybe to get TL, but WA. Main procedure here:

[java]

int dfs(int r, int c)

{

if (r<0 || r==n || c<0 || c==n) return 0;

if (used[r][c]) return 0;

if (map[r][c]==TRAP) return 0;

used[r][c] = true;

return map[r][c] + dfs(r + 1, c) + dfs(r - 1, c)

+ dfs(r, c + 1) + dfs(r, c - 1);

}

void visit(int r, int c)

{

int i, j, s, next;

boolean flag;

if (r<0 || r==n || c<0 || c==n) return;

if (used[r][c]) return;

if (map[r][c]==TRAP) return;

if (map[r][c]==CORN) prev++;

if (r==n-1 && c==n-1)

{

row[step] = r;

col[step] = c;

++step;

if (prev > max)

{

for (s=0; s<step; s++) {

brow[s] = row[s];

bcol[s] = col[s];

}

nofs = step;

max = prev;

}

--step;

if (map[r][c]==CORN) prev--;

return;

}

next = dfs(n - 1, n - 1) - map[r][c];

flag = used[r][c];

/*clearAll() = sets all as non used*/

clearAll();

for (s=0; s<step; s++)

used[row[s]][col[s]] = true;

if (flag && prev + next > max)

{

row[step] = r;

col[step] = c;

step++;

used[r][c] = true;

visit(r + 1, c);

visit(r - 1, c);

visit(r, c + 1);

visit(r, c - 1);

used[r][c] = false;

step--;

}

if (map[r][c]==CORN) prev--;

}

[/java]

Repeat it 3 times and every time update the map, what's wrong??

### Tests

Posted: **Sat Aug 30, 2003 5:44 pm**

by **Revenger**

**Try this test**
Code: Select all

```
4
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
5
1 1 1 1 1
1 2 1 1 1
1 2 1 1 1
1 2 1 1 1
1 2 1 1 1
6
1 1 1 1 1 1
1 2 1 2 2 1
1 1 1 1 2 1
1 2 1 1 2 1
1 2 2 2 2 1
1 1 1 1 1 1
7
1 1 1 1 1 1 1
1 2 1 2 1 2 1
1 1 1 2 1 1 1
1 2 2 2 2 2 1
1 1 1 2 1 1 1
1 2 1 2 1 2 1
1 1 1 1 1 1 1
```

**Output should be**
I think I give you

*too much* test cases to solve the problem. Good luck!

### Yeap

Posted: **Sat Aug 30, 2003 6:38 pm**

by **Miguel Angel**

My program solves all test cases you give here in short time. I don't know what's wrong.

### Tests 2

Posted: **Sat Aug 30, 2003 7:08 pm**

by **Revenger**

Try this

Output should be

Posted: **Sun Aug 31, 2003 1:21 am**

by **Miguel Angel**

Of course can't solve that