Page 1 of 2
663 - Sorting Slides
Posted: Sun Jul 28, 2002 7:20 pm
by Revenger
Why this code gets WA? I have no idea
My algorithm is such:
- if there is a slide on which lie only one number then I consider that this slide have this number
- if there is a number which lie on only one slide then I consider that this slide have this number
- if there is no such slides and numbers I terminate my algo
[pascal]Program p663;
Type Rect = Record Xmin,Ymin,Xmax,Ymax : Integer End;
Point = Record X,Y : Integer End;
Var Tr : Array['A'..'Z']of Record
D : Rect;
N : Integer;
End;
Pnt : Array[1..26]of Record
D : Point;
N : Char;
End;
T,N : Integer;
i,j,k : Integer;
Ch : Char;
ExitRepeat : Boolean;
Function InSide(A : Point; B : Rect) : Boolean;
begin
InSide:= (B.Xmin<=A.X) And (A.X<=B.Xmax) And (B.Ymin<=A.Y) And (A.Y<=B.Ymax);
end;
begin
T:=0;
While True do begin
Read(N);
if N=0 then Break;
for i:=1 to N do begin
Ch:=Chr(Ord('A')+i-1);
Read(Tr[Ch].D.Xmin,Tr[Ch].D.Xmax,Tr[Ch].D.Ymin,Tr[Ch].D.Ymax);
Tr[Ch].N:=0;
end;
for i:=1 to N do begin
Read(Pnt
.D.X,Pnt.D.Y);
Pnt.N:=' ';
end;
Repeat
ExitRepeat:=True;
for i:=1 to N do
if Pnt.N=' ' then begin
k:=0;
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N=0 then
if InSide(Pnt.D,Tr[Ch].D) then begin
if k=0 then k:=j else k:=-1;
end;
end;
if k>0 then begin
Ch:=Chr(Ord('A')+k-1);
Pnt.N:=Ch;
Tr[Ch].N:=i;
ExitRepeat:=False;
end;
end;
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N=0 then begin
k:=0;
for i:=1 to N do
if Pnt.N=' ' then
if InSide(Pnt.D,Tr[Ch].D) then begin
if k=0 then k:=i else k:=-1;
end;
if k>0 then begin
Pnt[k].N:=Ch;
Tr[Ch].N:=k;
ExitRepeat:=False;
end;
end;
end;
Until ExitRepeat;
T:=T+1;
Writeln('Heap ',T);
k:=-1;
for i:=1 to N do
if Pnt.N<>' ' then k:=0;
if k=-1 then Writeln('none') else begin
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N>0 then
Write('(',Ch,',',Tr[Ch].N,') ');
end;
Writeln;
end;
Writeln;
end;
end.[/pascal]
Posted: Mon Jul 29, 2002 1:58 am
by Adrian Kuegel
Consider this case:
You have 5 points and slides:
point 1 and 2 are in slides 1 and 2, point 3 lies in slides 1, 2 and 3, points 4 and 5 are in all 5 slides. Then points 1 and 2 must be the numbers of the first two slides, but which number is on slide 1 cannot be determined. But after you remove the two slides and the two numbers, you can see that point 3 is only contained in slide 3.
Posted: Mon Jul 29, 2002 8:29 am
by Revenger
I wrote
- if there is a slide on which lie only one number then I consider that this slide have this number
So, on 3rd slide lie only one number - 3, and I consider that number 3 on 3rd slide.
May be you understand my algo not clear enough ?
Posted: Mon Jul 29, 2002 11:23 am
by Adrian Kuegel
Perhaps you didn't read my changed text, but now I said that points 4 and 5 are contained in all slides, that means also in slide 3. And I did understand your algorithm, I used the same, but it is not enough, you have to add a check.
Posted: Wed Jul 31, 2002 2:40 pm
by Revenger
I have add a check but I still get WA
Why???
[pascal]Program p663;
Type Rect = Record Xmin,Ymin,Xmax,Ymax : Integer End;
Point = Record X,Y : Integer End;
Var Tr : Array['A'..'Z']of Record
D : Rect;
N : Integer;
End;
Pnt : Array[1..26]of Record
D : Point;
N : Char;
End;
T,N : Integer;
i,j,k : Integer;
Ch : Char;
ExitRepeat : Boolean;
Function InSide(A : Point; B : Rect) : Boolean;
begin
InSide:= (B.Xmin<=A.X) And (A.X<=B.Xmax) And (B.Ymin<=A.Y) And (A.Y<=B.Ymax);
end;
Function Check : Boolean;
Type TCh = Array[1..26]of Byte;
TU = Array['A'..'Z']of Byte;
Var Ch : TCh;
U : TU;
Lim : Char;
Procedure Rec(Step : Integer; Ch : TCh; U : TU);
Var i,c : Integer;
j : Char;
NCh : TCh;
NU : TU;
begin
if Step=N+1 then begin
c:=0;
for i:=1 to n do
if Ch
=1 then c:=c+1;
if c=0 then Exit;
for j:='A' to Lim do
if U[j]=1 then c:=c-1;
if c=0 then begin
Check:=True;
for i:=1 to N do
if Ch=1 then
Pnt.N:='#';
for j:='A' to Lim do
if U[j]=1 then
Tr[j].N:=-1;
end;
exit;
end;
if Pnt[Step].N<>' ' then begin
NU:=U;
NCh:=Ch;
NCh[Step]:=0;
Rec(Step+1,NCh,NU);
end else begin
c:=0;
for i:=1 to Step-1 do
if Ch=1 then c:=1;
if c=0 then begin
NU:=U;
NCh:=Ch;
NCh[Step]:=0;
Rec(Step+1,NCh,NU);
NCh[Step]:=1;
for j:='A' to Lim do
if (NU[j]=0)and(Tr[j].N=0) then
if InSide(Pnt[Step].D,Tr[j].D) then NU[j]:=1;
for i:=1 to Step-1 do if Pnt.N=' ' then
for j:='A' to Lim do
if (NU[j]=1)and(Tr[j].N=0) then
if InSide(Pnt.D,Tr[j].D) then c:=1;
if c=0 then Rec(Step+1,NCh,NU);
end else begin
NU:=U;
NCh:=Ch;
c:=0;
for j:='A' to Lim do
if (NU[j]=1)and(Tr[j].N=0) then
if InSide(Pnt[Step].D,Tr[j].D) then begin
c:=1;
Break;
end;
if c=0 then begin
NCh[Step]:=0;
NU:=U;
Rec(Step+1,NCh,NU);
end else begin
NCh[Step]:=1;
for j:='A' to Lim do
if (NU[j]=0)and(Tr[j].N=0) then
if InSide(Pnt[Step].D,Tr[j].D) then NU[j]:=1;
Rec(Step+1,NCh,NU);
end;
end;
end;
end;
begin
Check:=False;
FillChar(Ch,SizeOf(Ch),0);
FillChar(U,SizeOf(U),0);
Lim:=Chr(Ord('A')+N-1);
Rec(1,Ch,U);
end;
begin
T:=0;
While True do begin
Read(N);
if N=0 then Break;
for i:=1 to N do begin
Ch:=Chr(Ord('A')+i-1);
Read(Tr[Ch].D.Xmin,Tr[Ch].D.Xmax,Tr[Ch].D.Ymin,Tr[Ch].D.Ymax);
Tr[Ch].N:=0;
end;
for i:=1 to N do begin
Read(Pnt.D.X,Pnt.D.Y);
Pnt.N:=' ';
end;
Repeat
ExitRepeat:=True;
for i:=1 to N do
if Pnt.N=' ' then begin
k:=0;
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N=0 then
if InSide(Pnt[i].D,Tr[Ch].D) then begin
if k=0 then k:=j else k:=-1;
end;
end;
if k>0 then begin
Ch:=Chr(Ord('A')+k-1);
Pnt[i].N:=Ch;
Tr[Ch].N:=i;
ExitRepeat:=False;
end;
end;
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N=0 then begin
k:=0;
for i:=1 to N do
if Pnt[i].N=' ' then
if InSide(Pnt[i].D,Tr[Ch].D) then begin
if k=0 then k:=i else k:=-1;
end;
if k>0 then begin
Pnt[k].N:=Ch;
Tr[Ch].N:=k;
ExitRepeat:=False;
end;
end;
end;
if ExitRepeat then
if Check then
ExitRepeat:=False;
Until ExitRepeat;
T:=T+1;
Writeln('Heap ',T);
k:=-1;
for i:=1 to N do
if Pnt[i].N in ['A'..'Z'] then k:=0;
if k=-1 then Writeln('none') else begin
for j:=1 to N do begin
Ch:=Chr(Ord('A')+j-1);
if Tr[Ch].N>0 then
Write('(',Ch,',',Tr[Ch].N,') ');
end;
Writeln;
end;
Writeln;
end;
end.[/pascal]
Posted: Sun Apr 27, 2003 2:47 am
by Abednego
Adrian, thanks for the example. I knew it must have been my algorithm (I was doing the same greedy picking), but I couldn't think of a counter-example. Hmmm, now there must be a way to fix this without going to Ford-Fulkerson... ;-)
663 sorting slides
Posted: Tue Jul 29, 2003 8:42 am
by titid_gede
can anyone give me sample inputs ? what's wrong with my code? thanks before..
[c]#include <stdio.h>
#include <string.h>
#define MAX 30
typedef struct {
int xmin, xmax, ymin, ymax;
} tslide;
typedef struct {
int x, y;
} tpoint;
tslide slide[MAX];
tpoint point[MAX];
int jpoint, result[MAX];
char matrix[MAX][MAX];
/*check whether point X inside slide Y*/
int isin (int x, int y) {
return (point[x].x > slide[y].xmin && point[x].x < slide[y].xmax
&& point[x].y > slide[y].ymin && point[x].y < slide[y].ymax);
}
int main() {
int i, j, k, jum, jcase = 1, last;
char found;
while (1) {
scanf ("%d", &jpoint);
if (jpoint == 0) break;
for (i = 0; i < jpoint; i++)
scanf ("%d %d %d %d", &slide.xmin, &slide.xmax, &slide.ymin, &slide.ymax);
for (i = 1; i <= jpoint; i++)
scanf ("%d %d", &point.x, &point.y);
memset (matrix, 0, sizeof(char)*MAX*MAX);
for (i = 1; i <= jpoint; i++)
for (j = 0; j < jpoint; j++)
if (isin (i, j))
matrix[j] = 1;
memset (result, 0, sizeof(int)*MAX);
for (k = 0; k < jpoint; k++) {
for (i = 0; i < jpoint; i++) {
jum = 0;
for (j = 1; j <= jpoint; j++)
if (matrix[j] == 1) {
jum++;
last = j;
}
if (jum == 1) {
result = last;
for (j = 0; j < jpoint; j++)
matrix[result][j] = 0;
break;
}
}
}
printf ("Heap %d\n", jcase++);
found = 0;
for (i = 0; i < jpoint; i++)
if (result[i] != 0) {
printf ("(%c,%d) ", i+'A', result[i]);
found = 1;
}
if (!found)
puts ("none");
else
printf ("\n");
printf ("\n");
}
return 0;
}
[/c]
Posted: Wed Jul 30, 2003 12:04 pm
by titid_gede
never mind... i didnt read the thread before, now i found where my mistakes are.
Posted: Sat Aug 14, 2004 11:04 pm
by ulin
Adrian Kuegel wrote:Consider this case:
You have 5 points and slides:
point 1 and 2 are in slides 1 and 2, point 3 lies in slides 1, 2 and 3, points 4 and 5 are in all 5 slides. Then points 1 and 2 must be the numbers of the first two slides, but which number is on slide 1 cannot be determined. But after you remove the two slides and the two numbers, you can see that point 3 is only contained in slide 3.
Hi,
Is it a counter-example for greedy algorithm? In my opinion answer for this is "none", but I'm probably wrong... What is the answer for this testcase?
Could you explain me, how greedy method don't work?
Best regards!!!
Posted: Mon Aug 16, 2004 12:19 pm
by sohel
ulin wrote:
Hi,
Is it a counter-example for greedy algorithm? In my opinion answer for this is "none", but I'm probably wrong... What is the answer for this testcase?
Could you explain me, how greedy method don't work?
That's right.. greedy won't work over here. The answer for this test case is not "none" cos you can confirm the identity of slide 3.
The question asks us to find out those slides that can be uniquely determined. And if none of them can be figured out then output should be 'none'.
I solved this problem by applying repeated Bipartite-Match algorithm. (N+1) of them to be precise.. where N indicates the number of slides.
Posted: Mon Aug 16, 2004 4:27 pm
by ulin
Thanks Sohel!
I thought, that all slides must be uniquely determined or in other case answer is "none". Thank you for help with understand.
Best regards!!!
Posted: Thu Aug 19, 2004 5:28 pm
by ulin
sohel wrote:I solved this problem by applying repeated Bipartite-Match algorithm. (N+1) of them to be precise.. where N indicates the number of slides.
I have got AC, but my time is not very well - 0.447 s - I do M Bipartite Match algorithm, where M is number of egdes in graph. It can be much more than N+1, so it is probably reason of my poor time.
I remove single edghes and check is it cause that there not exist perfect match.
What is the better way to solve this problem?
Best Regards!
Posted: Wed Apr 11, 2007 6:09 pm
by Khaled_912
Here's the test case that Andrian has mentioned:
Code: Select all
5
0 10 0 10
0 10 0 10
0 8 0 8
0 5 0 5
0 4 0 4
9 9
9 9
7 7
1 1
1 1
My program outputs (C, 3) and I keep getting WA.
Any more test cases plz?
Posted: Wed Apr 11, 2007 10:34 pm
by Jan
Slightly updated one...
Input:
Code: Select all
5
0 10 0 10
0 10 0 10
0 8 0 8
0 5 0 5
0 4 0 4
9 9
9 9
6 7
1 5
1 1
0
Hope it helps.
Posted: Mon Jun 11, 2007 7:44 pm
by ral
Hi,
I don't know what I'm doing wrong. Can anyone help me?
My algorithm:
- Ford-Fulkerson method to get the maximum matching in the bipartite graph.
- Reverse all match edges.
- DFS for each slide "x": if find a cycle with "x", don't print the match.
Code: Select all
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define DBG(x...) x //To Deactivate DBG erase 'x'
#define VAR(x...) DBG( cout << #x " = " << x << "\n" ) //Print variable
#define PRINT(x...) DBG( printf(x) ) //Print like printf
#define MAX 1500
#define INF 0x3F3F3F3F
int n; //number of slides
int cap[MAX][MAX]; //capacity
int fl[MAX][MAX]; //flow
int G[MAX][MAX]; //Graph
int source, sink; //auxiliar vertex
int orig; //original vertex
bool vis[MAX]; //visited
typedef struct Slide {
int x1, x2, y1, y2;
Slide() {}
Slide(int _x1, int _x2, int _y1, int _y2) : x1(_x1), x2(_x2), y1(_y1), y2(_y2) {};
} Slide;
typedef struct Point {
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {};
} Point;
bool path () {
int queue[MAX]; //bfs
int f[MAX]; //father
int start, end; //queue iterators
int v; //auxiliar vertex
int fmax; //max flow in path
int i; //iterator
bool marc[MAX]; //visited
memset(marc, false, sizeof(marc));
start = end = 0;
marc[source] = true;
f[source] = source;
queue[end++] = source;
while (start != end) {
v = queue[start++];
if (v == sink)
break;
for (i = 0; i < sink + 1; ++i)
if (cap[v][i] > 0 && !marc[i]) {
queue[end++] = i;
marc[i] = true;
f[i] = v;
}
}
if (!marc[sink])
return (false);
fmax = INF + INF;
v = sink;
while (f[v] != v) {
fmax = min(fmax, cap[f[v]][v]);
v = f[v];
}
v = sink;
while (f[v] != v) {
fl[f[v]][v] += fmax;
fl[v][f[v]] = -fl[f[v]][v];
cap[f[v]][v] -= fl[f[v]][v];
cap[v][f[v]] -= fl[v][f[v]];
v = f[v];
}
return (true);
}
bool cycle (int v) {
int i; //iterator
vis[v] = true;
for (i = 0; i < 2 * n; ++i) {
if (G[v][i] && !vis[i]) {
if (cycle(i))
return (true);
}
else if (G[v][i] && vis[i] && i == orig) {
return (true);
}
}
return (false);
}
int main () {
int i, j; //iterator
int xmin, xmax, ymin, ymax; //input
int ret; //max flow
int m[MAX]; //matching
int cases = 1;
int count; //number of correct match
Slide s[MAX]; //slides
Point p[MAX]; //points
while (scanf ("%d", &n) == 1 && n) {
if (cases > 1)
printf ("\n");
memset(fl, 0, sizeof(fl));
memset(cap, 0, sizeof(cap));
memset(G, 0, sizeof(G));
memset(m, 0, sizeof(m));
for (i = 0; i < n; ++i) {
scanf ("%d %d %d %d", &xmin, &xmax, &ymin, &ymax);
s[i] = Slide(xmin, xmax, ymin, ymax);
}
for (i = 0; i < n; ++i) {
scanf ("%d %d", &xmin, &ymin);
p[i] = Point(xmin, ymin);
}
for (i = 0; i < n; ++i)
for (j = n; j < 2 * n; ++j)
if (s[i].x1 < p[j - n].x && s[i].x2 > p[j - n].x && s[i].y1 < p[j - n].y && s[i].y2 > p[j - n].y)
cap[i][j] = G[i][j] = 1;
source = 2 * n;
sink = source + 1;
for (i = 0; i < n; ++i) {
cap[source][i] = 1;
G[source][i] = 1;
}
for (i = n; i < 2 * n; ++i) {
cap[i][sink] = 1;
G[i][sink] = 1;
}
while (path()) {}
ret = 0;
for (i = 0; i < n; ++i)
ret += fl[source][i];
VAR(ret);
for (i = 0; i < n; ++i) {
if (fl[source][i] == 1) {
G[i][source] = 1;
G[source][i] = 0;
}
for (j = n; j < 2 * n; ++j) {
if (fl[j][sink] == 1) {
G[sink][j] = 1;
G[j][sink] = 0;
}
if (fl[i][j] == 1) {
G[j][i] = 1;
G[i][j] = 0;
m[i] = j - n + 1;
PRINT("m[%d] = %d\n", i, m[i]);
}
}
}
printf ("Heap %d\n", cases++);
count = 0;
for (i = 0; i < n; ++i) {
memset(vis, false, sizeof(vis));
orig = i;
if (m[i] && !cycle(i)) {
if (count)
printf (" ");
printf ("(%c,%d)", char(i + 'A'), m[i]);
count++;
}
}
if (!count)
printf ("none");
printf ("\n");
VAR(ret);
}
return (0);
}