## 563 - Crimewave

Moderator: Board moderators

Carlos
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Contact:
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.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Welcome Carlos,
It should be.

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

### 563 - Runtime Error

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.

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;
int antx;
int anty;
int bank;

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

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
Contact:
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  . 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;
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(){
while(1){
p = bfsCapacity();
if(!p){
break;
}
}
}
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;
}``````
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.

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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().

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

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

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

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

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

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