663 - Sorting Slides

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

663 - Sorting Slides

Post 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]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post 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.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post 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 ?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post 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.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post 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]

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

663 sorting slides

Post 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]
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

never mind... i didnt read the thread before, now i found where my mistakes are.
Kalo mau kaya, buat apa sekolah?

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post 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.
Last edited by sohel on Wed Jun 20, 2007 10:19 am, edited 1 time in total.

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)

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

ulin
New poster
Posts: 15
Joined: Wed Jun 30, 2004 11:24 am
Location: POLAND (Plock)

Post 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.
8)
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
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Post 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?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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
Output:

Code: Select all

Heap 1
(C,3) (D,4) (E,5)
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

ral
New poster
Posts: 5
Joined: Tue Jan 09, 2007 12:06 am

Post 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);
}
Rodrigo Alves Lima
Brazil

Post Reply

Return to “Volume 6 (600-699)”