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]

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 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!
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==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??
[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
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.


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