563 - Crimewave

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

Moderator: Board moderators

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos » Mon Jun 26, 2006 11:37 pm

I've re-rejudged every submission, so the submissions above 10 seconds will dissapear. Process will take 3-4 days, since I can't rejudge right now.
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Jun 27, 2006 11:08 am

Welcome Carlos,
It should be.

Malkava
New poster
Posts: 2
Joined: Wed Oct 25, 2006 6:28 pm

563 - Runtime Error

Post by Malkava » Wed Oct 25, 2006 6:33 pm

Hi. I'm receiving Runtime Error (Inavlid Memory Reference) for about 2 days and can't find where this invalid memory reference can be happening.

Thanks for your help =)

Here's my code (I tried an algorithm that looks like max bipartite matching)

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

int vis[55][55];
int antx[55][55];
int anty[55][55];
int bank[55][55];

int nvis;

int dirx[] = {1,0,-1,0};
int diry[] = {0,1,0,-1};

int nx, ny;

#define f(i,j,k) for(int i = j; i < k; i++)
#define sz size
#define pb push_back

int dfs(int x, int y){
	vis[x][y] = nvis;
	int xx, yy;

	if(x == 0 || y == 0 || x > nx || y > ny) return 1;
	
	f(i,0,4){
		xx = x + dirx[i];
		yy = y + diry[i];

		if(bank[xx][yy]) continue;		
		if(vis[xx][yy] >= nvis) continue;

		if(antx[xx][yy] == x && anty[xx][yy] == y) continue;

		if(anty[xx][yy] == -1 && antx[xx][yy] == -1){
			if(dfs(xx,yy)){
				antx[xx][yy] = x;
				anty[xx][yy] = y;
				return 1;
			}
			else continue;
		}
		if(dfs(antx[xx][yy],anty[xx][yy])){
			antx[xx][yy] = x;
			anty[xx][yy] = y;
			return 1;
		}
	}

	return 0;


	
}

vector<int> bx, by;

int main(void){
	int n;

	scanf("%d",&n);
	while(n--){
		int b;
		scanf("%d %d %d",&nx,&ny,&b);
		f(i,0,55) f(j,0,55) bank[i][j]=0;
		bx.clear(); by.clear();
		int is = 1;
		f(i,0,b){
			int a,c;
			scanf("%d %d",&a,&c);
			bx.pb(a); by.pb(c);
			if(bank[a][c]){
				is = 0;
				goto end;
			}
			bank[a][c]=1;
		}
		f(i,0,55) f(j,0,55) { vis[i][j] = 0; anty[i][j]=antx[i][j]=-1; }
		nvis = 0;
		f(i,0,b){ 
			nvis++; 
			if(!dfs(bx[i],by[i])){
				is=0; 
				break;
			}
		}
				
		end:;
		if(is) printf("possible\n");
		else printf("not possible\n");

	}

	return 0;

}
[/code]

rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

MaxFlow Algorithm and Problem 563-CrimeWave

Post by rimu » Tue Dec 12, 2006 4:37 pm

The problem 563-CrimeWave is a maximum
flow problem. The funny thing is i've AC
for this problem although i think my solution
is wrong in the way it implements ford-fulkerson
algorithm!!!

Since vertices also have capacities in this
problem, i had the usual idea of splitting
the vertices into two and have the newly
created edge the vertex capacity. But i just
couldn't find a way to split the vertices.
I know it sounds funny, but given the grid like
graph structure it seem very complicated to
split the vertices, and to add pain, this is
an undirected graph.

Finding no other way and since the capacity of
all the vertices is exactly 1, i thought of
using a 'visited' array just to mark an already
visited vertex and never to use it while finding
a new augmenting path. However the way ford-fulkerson
algorithm works i thougth it was incorrect to
do this. BUT it was AC!!

now i've two questions.

(1) is my approach correct or incorrect? why?

(2) how can i split the vertices of an undirected
graph like the one below to accomodate vertex capacities?

Code: Select all

	0---0---0
	|   |   |
	0---0---0
	|   |   |
	0---0---0
Thanks.
i'll be back

ajaysomani
New poster
Posts: 5
Joined: Sat Dec 30, 2006 2:16 pm
Location: Hyderabad
Contact:

Post by ajaysomani » Sat Dec 30, 2006 8:01 pm

Hi,
I don't understand the fact that a bank can be robbed more than once ... I did exactly same as ImLazy has written above but I always get WA :cry::cry:. My programs output matches with the above output on all the 50 cases [ I suppose the output shown above is correct ]. Can somebody help me out about it. Here is the code for you to have a look =>

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<stack>
#include<algorithm>
#include<queue>
#include<list>
#include<map>
#include<cassert>
using namespace std;
/* maximum Flow using Ford Fulkerson method */
#define INF 10000000
int n,source,destination;
list<pair<int,int> > graph[5002];
int calCapacity(int a,int b){
	for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
		if((*i).first == b){
			return (*i).second;
		}
	}
	return 0;
}
void updateCapacity(int a,int b,int c){
	bool state = false;
	for(list<pair<int,int> >::iterator i=graph[a].begin();i!=graph[a].end();i++){
		if((*i).first == b){
			(*i).second += c;
			if((*i).second == 0){
				graph[a].erase(i);
				return;
			}
			state = true;
			break;
		}
	}
	if(!state){
		graph[a].push_front(pair<int,int> (b,c));
	}
	return;
}
int bfsCapacity(){
	queue<int> q;
	bool visited[n],done=false;
	int from[n],cur,where,pathCapacity,prev;
	memset(visited,false,sizeof(visited));
	from[destination] = from[source] = -1;
	q.push(source);
	visited[source] = true;

	while(!q.empty() && !done){
		cur = q.front();q.pop();
		for(list<pair<int,int> >::iterator i=graph[cur].begin();i!=graph[cur].end();i++){
			if(!visited[(*i).first] && (*i).second > 0){
				visited[(*i).first] = true;
				q.push((*i).first);
				from[(*i).first] = cur;
				if((*i).first == destination){
					done = true;
				}
			}
		}
	}
	if(!visited[destination]){
		return 0;
	}
	where = destination;
	pathCapacity = INF;
	while(from[where] > -1){
		pathCapacity = min(pathCapacity,calCapacity(from[where],where));
		where = from[where];
	}
	where = destination;
	while(from[where] > -1){
		prev = from[where];
		updateCapacity(from[where],where,-pathCapacity);
		updateCapacity(where,from[where],pathCapacity);
		where = from[where];
	}
	assert(pathCapacity == 1);
	return pathCapacity;
}
int maxFlow(){
	int answer = 0,p;
	while(1){
		p = bfsCapacity();
		if(!p){
			break;
		}
		answer += p;
	}
	return answer;
}
int main(){
	int N,row,column,c,x,y;
	scanf("%d",&N);
	while(N--){
		scanf("%d%d%d",&column,&row,&c);
		source = 0;
		destination = 2 * row * column + 1;
		n = 2 * row * column + 2;
		for(int i=0;i<n;i++){
			graph[i].clear();
		}
		for(int i=0;i<c;i++){
			scanf("%d%d",&y,&x);
			x = row - x;
			graph[source].push_front(pair<int,int> ((x*column + y)*2-1,1));
		}
		for(int i=0;i<row;i++){
			for(int j=1;j<=column;j++){
				graph[(i*row+j)*2-1].push_front(pair<int,int> ((i*column+j)*2,1));
				if ( i > 0){
					graph[(i*column+j)*2].push_front(pair<int,int> (((i-1)*column+(j))*2-1,1));
				}
				if ( i < row-1 ){
					graph[(i*column+j)*2].push_front(pair<int,int> (((i+1)*column+(j))*2-1,1));
				}
				if ( j > 1){
					graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j-1))*2-1,1));
				}
				if ( j < column ){
					graph[(i*column+j)*2].push_front(pair<int,int> (((i)*column+(j+1))*2-1,1));
				}
				if(i == 0 || i == row - 1 || j == 1 || j == column){
					graph[(i*column+j)*2].push_front(pair<int,int> (destination,1));
				}
			}
		}
		if(maxFlow() == c){
			puts("possible");
		}
		else {
			puts("not possible");
		}
	}
	return 0;
}
Thanks a lot in advance.
People die young because god loves them so much, I am still on earth because there is a godess here who loves me even more.

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Aug 23, 2007 12:20 pm

I am a bit confused with the problem statement . Can a bank be robbed more than once ?? If a bank is being robbed for the second time , doest it men that the second robbers are crossing the first robbers' path ??

I am getting WA . I used backtracking to match the paths . I got correct answer for the 50 inputs given in this thread. Can anyone hep me with some more tricky input ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Aug 24, 2007 5:21 am

What they meant was that in the judge input, there may be cases where the same bank is listed twice. In those cases, always output not possible.
I've verified it using assert().

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Aug 24, 2007 7:00 pm

Is there anyone who can explain the algorithm for this problem ?? I think , I have to calculate repeatedly changing source and sink and then pick the smallest flow. but I am a bit confused how to construct the graph and how to select the source and the sink . Can anyone help me ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

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

Post by Jan » Fri Aug 24, 2007 8:04 pm

Use two artificial nodes, source and sink. capacity of source to banks are all 1, and capacity of the corner points to sink are 1. Then run flow from source to sink. Hope it helps.
Ami ekhono shopno dekhi...
HomePage

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Sep 03, 2007 5:48 am

should I split every node into two nodes with capacity 1 between them to avoid the collision ???

if YES , then the number of nodex get doubled and I am afraid , I will face a TLE . :-?
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue Feb 19, 2008 9:09 am

for ImLazy's input my solution gives exactly same output as mf's output. But I am getting Wrong Answer. Can anyone give some more tricky inputs.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Feb 19, 2008 3:18 pm

I don't have any input cases. But if you make and post some inputs, I'll be happy to give you output of my accepted program.

If your algorithm is like the one described by ImLazy, then it basically should be correct, look for minor bugs in your code.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Feb 20, 2008 8:38 am

Thanks mf.
Now I am providing my max-flow values of ImLazy's inputs, Please verify these.

Code: Select all

(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 9) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible
(I am not very good at maximum flow, If you want i can paste my code here)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Feb 21, 2008 5:44 am

For this case my program found a flow of value 10, while your program says 9.

Code: Select all

1

5 5 13
4 5
1 5
3 3
1 3
4 2
3 1
4 2
4 4
1 4
2 3
1 3
4 5
2 4

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Fri Feb 22, 2008 11:41 am

Thanks again mf,
After fixing some bug, i got these output for same input.

Code: Select all

(flow: 12) not possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 12) not possible
(flow: 4) not possible
(flow: 11) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 10) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 4) possible
(flow: 14) not possible
(flow: 14) not possible
(flow: 9) not possible
(flow: 11) not possible
(flow: 15) not possible
(flow: 9) not possible
(flow: 13) not possible
(flow: 8) not possible
(flow: 6) possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 7) not possible
(flow: 12) not possible
(flow: 13) not possible
(flow: 14) not possible
(flow: 11) not possible
(flow: 4) possible
(flow: 4) possible
(flow: 9) possible
(flow: 9) not possible
(flow: 6) possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 9) not possible
(flow: 12) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 14) not possible
(flow: 15) not possible
(flow: 11) not possible
(flow: 10) not possible
(flow: 10) not possible
(flow: 3) not possible
(flow: 7) not possible
(flow: 13) not possible
(flow: 12) not possible
(flow: 3) possible
But I am still getting Wrong Answer. Are above outputs are correct?

Post Reply

Return to “Volume 5 (500-599)”