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

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

Post by mf » Fri Feb 22, 2008 12:35 pm

It isn't easy for me to modify my program to print flow value for all tests. (It has some optimizations, and I'm afraid I could break things if I try to patch it now.)
Better you just post 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 » Fri Feb 22, 2008 1:42 pm

Thanks. Here is my code. I guess it will be understandable for you. otherwise ask me, I will try my best to describe my algorithm.

Code: Select all

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define S 60
enum {LEFT=0,RIGHT,UP,DOWN, VER};
int move[5][2]={	{0,-1},{0,1},{-1,0},{1,0},{0,0} };
int rev[5]={RIGHT,LEFT,DOWN,UP,VER};
bool fnet[S][S][5], vis[S][S][2];
int pre[S][S][2], s, a;

bool in(int x, int y){
	return (x>=1 && x<=s && y>=1 && y<=a);
}

bool bfs(int x, int y){
	queue<int> Q;
	memset(pre,-1,sizeof(pre));
	memset(vis,0,sizeof(vis));
	int u1, v1, w1;
	Q.push(x);
	Q.push(y);
	Q.push(0);
	vis[x][y][0]=true;

	while(!Q.empty()){
		int u=Q.front();Q.pop();
		int v=Q.front();Q.pop();
		int w=Q.front();Q.pop();

		if(w==1 && (u==1 || u==s || v==1 || v==a) ){
			while(pre[u][v][w]!=-1){
				int pr = pre[u][v][w];
				if(w==1)fnet[u][v][pr]=(pr==4);
				else fnet[u+ move[pr][0]][v + move[pr][1]][rev[pr]]=(pr!=4);

				u = u + move[pr][0];
				v = v + move[pr][1];
				w = 1 - w;
			}
			return true;
		}

		for(int i=0;i<5;++i){
			u1 = u + move[i][0];
			v1 = v + move[i][1];
			w1 = 1 - w;

			if( in(u1,v1) && vis[u1][v1][w1]==false ){
				if( (w==0 && fnet[u1][v1][rev[i]]==(i<4) ) || (w==1 && fnet[u][v][i]==(i==4) ) ){
					Q.push(u1);
					Q.push(v1);
					Q.push(w1);
					vis[u1][v1][w1]=true;
					pre[u1][v1][w1]=rev[i];
				}
			}
		}
	}	
	return false;
}

int main (void){
	int T, b;
	int i, j, k;
	int x[S], y[S];
	freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&s,&a,&b);
		for(i=0;i<b;++i)
			scanf("%d%d",&x[i],&y[i]);

		memset( fnet, 0, sizeof( fnet ) );
		
		for(i=0;i<b;++i){
			for(j=0;j<b;++j)
			if(bfs(x[j],y[j])==true)
				break;
			if(j==b)break;
		}
		
		//printf("(flow: %d) ",i);
		if(i<b)printf("not possible\n");
		else printf("possible\n");
	}
	return 0;
}

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

Post by mf » Fri Feb 22, 2008 2:02 pm

I think that your graph can be wrong.

There should be just these edges (each of capacity 1):
(x,y,0) -> (x,y,1)
(x,y,1) -> (x',y',0), for all 4 grid points (x',y') adjacent to (x,y)

There shouldn't be allowed any moves from (x,y,0) to (x',y',1), except when (x',y') = (x,y).

And another thing, I think that it'll be a lot easier to debug max flow code, if you explicitly build the graph in this problem.

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 2:15 pm

If first flow contains edge from (x,y,1) to (x',y',0), where (x,y) != (x',y'),
I think it is possible to flow containing edge (x',y',0) to (x,y,1) in next unit flow.
----------- that is how I understand. isnt it?

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

Post by mf » Fri Feb 22, 2008 2:37 pm

Try to explicitly create the graph and all its edges, and write a max-flow algorithm to work on this explicit graph. It will be a lot simpler for both of us to debug and see what's going on in such a graph.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: some question

Post by f74956227 » Sun Nov 16, 2008 2:08 am

can somebody help with "a bank rodded more than one time"?
int my code

if(grid[j].b>1)duplicate = true;

and if duplicate is true, should i always print no possible?

but i try som case
2
3 3 2
3 1
3 1
3 4 2
3 1
3 1
my friend's AC answer give no possible, possible ! why?
in case two, 3 1 is duplicate (robbed than one time :( )

can somebody help me plz :cry:
electron

faximan
New poster
Posts: 1
Joined: Wed Sep 15, 2010 1:19 am

Re: 563 - Crimewave

Post by faximan » Wed Sep 15, 2010 1:24 am

I have written a solution that works with all inputs given earlier in this thread.
It uses Ford-Fulkeson with BFS.

However, I get TLE and I've been trying to speed up my code for many hours now, but no success.
Please can someone point me in a direction to go? I want to solve this bloody problem!

Code in Java, but tried the same in c++ as well.

Code: Select all

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	static int szx, szy, nbrBanks, nbrNodes, source, sink;
	static int[][] capacity;
	static int[] banks, parent;
	static boolean seen[];
	static Queue<Integer> q;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		int nbrTests = scanner.nextInt();
		for (int i = 0; i < nbrTests; i++) {

			szx = scanner.nextInt();
			szy = scanner.nextInt();
			nbrBanks = scanner.nextInt();

			nbrNodes = szx * szy * 2 + 2;
			source = 0;
			sink = nbrNodes - 1;

			banks = new int[nbrNodes];
			seen = new boolean[nbrNodes];
			parent = new int[nbrNodes];
			capacity = new int[nbrNodes][nbrNodes];

			for (int j = 0; j < nbrBanks; j++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				int index = getIndex(x, y, true);
				banks[index] = 1;
				capacity[0][index] = 1;
			}

			buildGraph();

			if (maxFlow() == nbrBanks)
				System.out.println("possible");
			else
				System.out.println("not possible");
		}
	}

	private static int maxFlow() {

		int maxFlow = 0;
		while (findAugmentingPath()) {
			maxFlow++;
			adjustCapacity();
		}
		return maxFlow;
	}

	private static boolean findAugmentingPath() {
		for (int i = 0; i < nbrNodes; i++) {
			seen[i] = false;
			parent[i] = -1;
		}

		q = new LinkedList<Integer>();
		q.add(source);
		seen[source] = true;

		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int i = 0; i <= sink; i++) {
				if (!seen[i] && capacity[cur][i] > 0) {
					seen[i] = true;
					parent[i] = cur;
					if (i == sink)
						return true;
					q.add(i);
				}
			}
		}
		return false;

	}

	private static void adjustCapacity() {
		int cur = sink;
		int prev = parent[sink];
		while (prev != -1) {
			capacity[prev][cur]--;
			capacity[cur][prev]++;
			cur = prev;
			prev = parent[cur];
		}

	}

	private static void buildGraph() {
		for (int i = 1; i <= szx * 2; i++)
			for (int j = 1; j <= szy; j++) {
				connectNode(i, j);
			}
	}

	private static void connectNode(int x, int y) {
		if (x > szx) {
			capacity[getIndex(x, y, false)][getIndex(x - szx, y, false)] = 1;
		} else {
			if (x == 1 || y == 1 || x == szx || y == szy)
				capacity[getIndex(x, y, false)][nbrNodes - 1] = 1;
			if (x > 1)
				capacity[getIndex(x, y, false)][getIndex(x - 1, y, true)] = 1;
			if (x < szx)
				capacity[getIndex(x, y, false)][getIndex(x + 1, y, true)] = 1;
			if (y > 1)
				capacity[getIndex(x, y, false)][getIndex(x, y - 1, true)] = 1;
			if (y < szy)
				capacity[getIndex(x, y, false)][getIndex(x, y + 1, true)] = 1;
		}
	}

	public static int getIndex(int x, int y, boolean entry) {
		if (entry)
			return szx * szy + (y - 1) * szx + x;
		else if (x > szx)
			return szx * szy + (y - 1) * szx + (x - szx);
		else
			return (y - 1) * szx + x;
	}
}

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 563 - Crimewave

Post by Imti » Fri Sep 16, 2011 12:22 pm

I don't know whether you got accepted it..However you could reduce number of iterations in following portion.
You don't need to look over all the node's possible to find adjacent of current node rather you should look up only four node up,
down,left ,right of current node..this should avoid TLE...:)

Code: Select all

         for (int i = 0; i <= sink; i++) {
            if (!seen[i] && capacity[cur][i] > 0) {
               seen[i] = true;
               parent[i] = cur;
               if (i == sink)
                  return true;
               q.add(i);
            }


@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 563 - Crimewave

Post by @li_kuet » Fri Dec 21, 2012 11:11 am

Who are getting WA should be aware of this case

Code: Select all

2
1 1 1
1 1
5 5 2
2 3
2 3
Output :

Code: Select all

possible
not possible

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

Re: 563 - Crimewave

Post by ackoroa » Mon Mar 18, 2013 8:30 am

I also have a code which solves the sample inputs above but am still getting WA :( Can somebody help see what might be the problem?

Code: Select all

AC
Last edited by ackoroa on Tue Apr 16, 2013 6:23 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 563 - Crimewave

Post by brianfry713 » Thu Mar 21, 2013 1:30 am

Input:

Code: Select all

10
6 11 28
1 1
1 3
1 4
1 5
1 7
1 9
1 10
1 11
2 1
2 7
2 10
2 11
3 5
3 6
3 9
3 10
4 1
4 4
4 5
4 9
5 5
5 8
5 11
6 4
6 7
6 8
6 9
6 11
16 20 158
1 2
1 5
1 8
1 10
1 11
1 13
1 15
1 16
1 19
1 20
2 1
2 2
2 3
2 4
2 6
2 10
2 11
2 12
2 13
2 14
2 15
2 17
2 19
3 1
3 6
3 8
3 9
3 10
3 14
3 20
4 4
4 5
4 6
4 7
4 8
4 9
4 11
4 14
4 15
4 16
4 18
4 20
5 4
5 5
5 7
5 11
5 14
5 15
5 16
6 2
6 4
6 6
6 12
6 16
6 18
6 19
7 1
7 3
7 4
7 5
7 7
7 9
7 10
7 12
7 13
7 16
8 3
8 6
8 9
8 10
8 14
8 16
8 18
8 19
8 20
9 2
9 4
9 6
9 7
9 9
9 10
9 13
9 16
9 17
9 19
10 2
10 3
10 5
10 6
10 7
10 8
10 10
10 17
10 18
10 20
11 2
11 3
11 4
11 5
11 6
11 10
11 11
11 16
11 17
11 18
11 20
12 3
12 4
12 5
12 6
12 7
12 11
12 13
12 15
12 18
13 2
13 4
13 5
13 9
13 10
13 11
13 13
13 14
13 15
13 19
13 20
14 3
14 4
14 5
14 6
14 7
14 8
14 11
14 12
14 13
14 14
14 16
14 17
14 19
15 1
15 2
15 4
15 6
15 7
15 11
15 13
15 14
15 18
15 19
16 1
16 3
16 4
16 5
16 6
16 10
16 12
16 14
16 19
1 11 6
1 1
1 2
1 3
1 4
1 5
1 6
12 10 72
1 1
1 2
1 3
1 4
1 5
1 9
1 10
2 1
2 2
2 3
2 4
2 7
2 8
2 9
2 10
3 6
3 9
3 10
4 1
4 2
4 6
4 7
5 1
5 2
5 3
5 4
5 7
5 8
5 9
6 2
6 4
6 5
6 8
6 9
6 10
7 1
7 4
7 5
7 6
7 7
7 9
7 10
8 2
8 4
8 7
8 8
8 9
9 1
9 4
9 5
9 6
9 7
9 8
9 9
10 3
10 4
10 5
10 10
11 1
11 4
11 5
11 7
11 8
11 9
11 10
12 1
12 3
12 4
12 5
12 7
12 8
12 9
8 14 53
1 4
1 10
1 13
2 1
2 3
2 5
2 7
2 12
2 13
2 14
3 1
3 2
3 3
3 4
3 5
3 6
3 14
4 2
4 3
4 4
4 5
4 8
4 10
4 11
4 13
5 1
5 2
5 3
5 7
5 8
5 11
6 3
6 5
6 8
6 13
6 14
7 1
7 3
7 5
7 6
7 7
7 8
7 9
7 11
7 12
8 1
8 2
8 4
8 5
8 6
8 8
8 9
8 12
17 16 135
1 1
1 2
1 3
1 4
1 5
1 6
1 10
1 11
1 12
1 13
1 14
2 7
2 8
2 10
2 11
2 13
2 14
2 15
3 3
3 4
3 5
3 6
3 9
3 10
3 11
3 14
3 16
4 3
4 7
4 9
4 13
4 14
4 16
5 3
5 4
5 5
5 6
5 7
5 10
5 14
5 15
6 1
6 8
6 10
6 11
6 15
7 4
7 5
7 6
7 8
7 12
7 13
7 14
7 15
7 16
8 3
8 6
8 10
8 12
8 13
8 15
8 16
9 2
9 3
9 5
9 6
9 7
9 8
9 9
9 10
9 12
9 13
9 16
10 2
10 3
10 6
10 8
10 9
10 10
10 13
10 14
10 16
11 1
11 2
11 3
11 6
11 7
11 8
11 12
12 1
12 5
12 7
12 9
12 10
12 11
12 14
12 16
13 2
13 3
13 6
13 7
13 8
13 9
13 12
13 14
13 15
14 1
14 2
14 5
14 6
14 7
14 8
14 11
14 13
14 14
14 16
15 1
15 2
15 3
15 4
15 8
15 10
15 12
15 14
15 15
15 16
16 2
16 3
16 7
16 12
16 16
17 2
17 6
17 11
17 15
10 13 64
1 2
1 3
1 4
1 5
1 6
1 9
1 12
1 13
2 2
2 3
2 4
2 5
2 7
2 8
2 10
2 11
2 13
3 1
3 2
3 4
3 8
4 1
4 4
4 5
4 6
4 10
4 11
4 12
5 1
5 3
5 6
5 7
5 10
6 3
6 8
6 9
6 10
6 12
7 3
7 4
7 5
7 7
7 10
7 11
7 13
8 1
8 2
8 8
8 9
8 10
8 11
8 12
9 1
9 2
9 5
9 7
9 9
10 1
10 4
10 5
10 6
10 8
10 9
10 13
6 8 24
1 1
1 3
1 5
1 6
2 1
2 2
2 5
2 6
3 4
3 6
3 7
3 8
4 1
4 3
4 4
4 5
5 1
5 2
5 6
5 7
5 8
6 2
6 3
6 6
11 1 8
1 1
3 1
4 1
5 1
7 1
8 1
9 1
11 1
8 8 34
1 3
1 4
1 8
2 1
2 2
2 4
2 7
3 2
3 6
3 7
3 8
4 7
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 7
6 8
7 1
7 2
7 3
7 7
8 1
8 2
8 3
8 4
8 5
8 7
AC output:

Code: Select all

not possible
not possible
possible
not possible
not possible
not possible
not possible
not possible
possible
not possible
Check input and AC output for thousands of problems on uDebug!

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

Re: 563 - Crimewave

Post by ackoroa » Tue Apr 16, 2013 6:22 pm

I found that I mixed up one of the widths/heights in one of the formulas. Thanks so much!

int2char
New poster
Posts: 1
Joined: Fri Jan 29, 2016 9:51 am

Re: 563 - Crimewave

Post by int2char » Fri Jan 29, 2016 10:02 am

I saw someone solved it in 0.000 seconds,I use the Edmonds-Karp algorithm,but it takes 0.3 seconds. anyone know how to save time?

Post Reply

Return to “Volume 5 (500-599)”