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

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

Post by Carlos »

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.
Top
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Contact emotional blind

Post by emotional blind »

Welcome Carlos,
It should be.
Top
Malkava
New poster
Posts: 2
Joined: Wed Oct 25, 2006 6:28 pm

563 - Runtime Error

Post by Malkava »

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]
Top
rimu
New poster
Posts: 9
Joined: Sat Feb 26, 2005 4:41 pm

MaxFlow Algorithm and Problem 563-CrimeWave

Post by rimu »

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
Top
ajaysomani
New poster
Posts: 5
Joined: Sat Dec 30, 2006 2:16 pm
Location: Hyderabad
Contact:
Contact ajaysomani

Post by ajaysomani »

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.
Top
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol »

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
Top
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Contact sclo

Post by sclo »

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().
Top
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol »

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
Top
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
Contact Jan

Post by Jan »

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
Top
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol »

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
Top
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Contact emotional blind

Post by emotional blind »

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.
Top
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Contact mf

Post by mf »

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.
Top
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Contact emotional blind

Post by emotional blind »

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)
Top
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Contact mf

Post by mf »

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
Top
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Contact emotional blind

Post by emotional blind »

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

Return to “Volume 5 (500-599)”