10314  Three Pigs
Moderator: Board moderators
10314  Three Pigs
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.
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....
I don't know how to solve this poblem. It seems to be so tricky !!!.
Anyone would like to help me ???[pascal] [/pascal]
Anyone would like to help me ???[pascal] [/pascal]
try using minimal cost stream
i think it is the same as an IOI97 problem
try to construct a net and use minimal cost stream
try to construct a net and use minimal cost stream

 New poster
 Posts: 15
 Joined: Tue Sep 10, 2002 1:56 am
 Location: Brasil
 Contact:
Three pigs reduction
Are you sure it's a NPProblem? 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!
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!
Interested
Pedrinho UFPE wrote:
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.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?
10314 more inputs please!
Hi!
Cloud someone give me some inputs for 10314?
Cloud someone give me some inputs for 10314?

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
What's wrong??
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==n1 && c==n1)
{
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??
[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==n1 && c==n1)
{
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??
Miguel & Marina
Tests
Try this test
Output should be
I think I give you too much test cases to solve the problem. Good luck!
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
Code: Select all
9
17
23
33

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
Yeap
My program solves all test cases you give here in short time. I don't know what's wrong.
Miguel & Marina

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