663 - Sorting Slides

Revenger · Post by **Revenger** » Sun Jul 28, 2002 7:20 pm

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]

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Jul 29, 2002 1:58 am

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.

Revenger · Post by **Revenger** » Mon Jul 29, 2002 8:29 am

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 ?

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Jul 29, 2002 11:23 am

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.

Revenger · Post by **Revenger** » Wed Jul 31, 2002 2:40 pm

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]

Abednego · Post by **Abednego** » Sun Apr 27, 2003 2:47 am

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... ;-)

titid_gede · Post by **titid_gede** » Tue Jul 29, 2003 8:42 am

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]

titid_gede · Post by **titid_gede** » Wed Jul 30, 2003 12:04 pm

never mind... i didnt read the thread before, now i found where my mistakes are.

ulin · Post by **ulin** » Sat Aug 14, 2004 11:04 pm

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

sohel · Post by **sohel** » Mon Aug 16, 2004 12:19 pm

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.

ulin · Post by **ulin** » Mon Aug 16, 2004 4:27 pm

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

ulin · Post by **ulin** » Thu Aug 19, 2004 5:28 pm

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!

Khaled_912 · Post by **Khaled_912** » Wed Apr 11, 2007 6:09 pm

Here's the test case that Andrian has mentioned:

Code: Select all

My program outputs (C, 3) and I keep getting WA.
Any more test cases plz?

Jan · Post by **Jan** » Wed Apr 11, 2007 10:34 pm

Slightly updated one...

Input:

Code: Select all

Output:

Code: Select all

Heap 1
(C,3) (D,4) (E,5)

Hope it helps.

ral · Post by **ral** » Mon Jun 11, 2007 7:44 pm

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);
}

OJ Board

663 - Sorting Slides

663 - Sorting Slides

663 sorting slides