11101 - Mall Mania

[SyFyKid]

Thank you for replying!

But why its 1 instead of 0 or 2 on this test case:

Code: Select all

4
0 0
0 1
1 1
1 0
6
3 2
3 1
2 1
1 1
1 2
2 2

we have 2 blocks which intersect just in 1 dot, so what we should count - minimal blocks which should walk Kim or minimal crosses of streets/avenues ?

My AC output for the input you posted is:

Code: Select all

2
1
1

[brianfry713]

Your input is not valid. The malls do not intersect, even in one point. I tested the judge's input.

[SyFyKid]

Your input is not valid. The malls do not intersect, even in one point. I tested the judge's input.

thank you very much! Ill try with this ...

[SyFyKid]

Nothig... just TLE... is it possible to solve in java?
I am using BFS from all the points from the first mall and when I rich any point from second mall - output the answer and exit.
am I doing something wrong? or I have TLE 'cause the input data is so large?

Thanks.

Here is my code:
http://paste.ubuntu.com/1035851/

Code: Select all

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.Collection;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Andrew Shmig aka SyFyKid
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		MallMania solver = new MallMania();
		solver.solve(1, in, out);
		out.close();
	}
}

class MallMania {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
        final int MAX_SIZE = 2001;
        final int PRIME = 1997;
        int[] DX = {-1, 0, +1, 0}, DY = {0, -1, 0, +1};
        int p1;
        Queue<Integer> q = new LinkedList<Integer>();
        HashSet<Integer> used = new HashSet<Integer>();
        
        while((p1 = in.RI())!=0){
            // mall 1
            for(int i=0; i<p1; i++){
                int x = Integer.parseInt(in.RS()), y = Integer.parseInt(in.RS());
                int tmp = (x*PRIME + y)*PRIME;
                
                q.add(tmp);
                used.add(tmp);
            }
            
            // mall 2
            int p2 = in.RI();
            for(int i=0; i<p2; i++){
                int x = Integer.parseInt(in.RS()), y = Integer.parseInt(in.RS());
                int tmp = (x*PRIME + y)*PRIME;
                
                used.add(-tmp);
            }
                                    
            // bfsing
            exit:
            while(!q.isEmpty()) {
                int cur = q.poll();                
                int curX = cur/PRIME/PRIME, curY = cur/PRIME%PRIME, curD = cur%PRIME;
                
                for(int i=0; i<DX.length; i++){
                    Integer newX = curX + DX[i], newY = curY + DY[i], newD = curD + 1, tmp = (newX*PRIME + newY)*PRIME + newD;
                    
                    if(newX>=0 && newX<MAX_SIZE && newY>=0 && newY<MAX_SIZE){
                        if(used.contains(-(tmp - tmp%PRIME))){
                            out.println(tmp%PRIME + 1);
                            break exit;
                        }
                        
                        if(!used.contains(tmp)){
                            q.add(tmp);                       
                            used.add(tmp);
                        }
                    }
                }
            }
            
            // init
            q = new LinkedList<Integer>();
            used = new HashSet<Integer>();
        }
	}
}

class InputReader {      
    private BufferedReader reader;
    private StringTokenizer tokenizer;
        
    public InputReader(InputStream stream)
    {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next()
    {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public String RS()
    {
        return next();
    }
    
    public int RI()
    {
        return Integer.parseInt(next());
    }
    
    }

[brianfry713]

Why are you using 1997?

[SyFyKid]

hey!
Its really impossible to solve this problem using class Pair and each time creating a new object... so I decided to encode coordinates X, Y and distance in one number (it was "long").
I took 1997 because it doesnt matter at all... I have just tested and had all the time TLE. But for sure this PRIME should be something bigger... bigger than the maximum possible distance... so its near 4001 or 4007...

I am encoding each (X, Y, DISTANECE) in this way:
long cell = (X*PRIME + Y)*PRIME + DISTANCE;

after that I can get X:
long X = cell/PRIME/PRIME;

get Y:
long Y = cell/PRIME%PRIME;

and DISTANCE:
long distance = cell%PRIME;

Why are you using 1997?

[brianfry713]

My C++ code that got AC in 0.752 sec I rewrote in JAVA and got TLE.

[SyFyKid]

Can you show your JAVA solution? maybe we can make it faster?
and the last question: my algo is ok?

My C++ code that got AC in 0.752 sec I rewrote in JAVA and got TLE.

[brianfry713]

I optimized my JAVA code and got AC in 1.084 sec. I used BufferedReader and BufferedWriter. A faster way to combine two integers is to use shift and bitwise and. I kept the distance in it's own 2-D array and placed x and y into the queue.
To add to the queue:
Q[tail++]=(x<<11)+y;

To remove from the queue:
x=Q[head]>>11;
y=Q[head++]&2047;

I also changed from a standard flood fill to a bidirectional meet in the middle approach, but didn't see much difference in the runtime.

[SyFyKid]

wow! thanks for such idea about combining two integers... I'll try !

I optimized my JAVA code and got AC in 1.084 sec. I used BufferedReader and BufferedWriter. A faster way to combine two integers is to use shift and bitwise and. I kept the distance in it's own 2-D array and placed x and y into the queue.
To add to the queue:
Q[tail++]=(x<<11)+y;

To remove from the queue:
x=Q[head]>>11;
y=Q[head++]&2047;

I also changed from a standard flood fill to a bidirectional meet in the middle approach, but didn't see much difference in the runtime.

[SyFyKid]

Finally solved it.
Used JAVA BitSet to check if we already visited point... and thanks for idea about combining 2 integers. really nice!
Got AC in 1.020

Code: Select all

import java.util.BitSet;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Andrew Shmig aka SyFyKid
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		MallMania solver = new MallMania();
		solver.solve(1, in, out);
		out.close();
	}
}

class MallMania {
    int[] q = new int[4008004];
    int[][] data = new int[2009][2009];
    int[] DX = {-1, 0, +1, 0}, DY = {0, -1, 0, +1};
    BitSet used = new BitSet(4006008), used2 = new BitSet(4006008);
    
	public void solve(int testNumber, InputReader in, PrintWriter out) {
        int p1, p2;
        int left, right;
        int MAX_SIZE = 2001;
        
        while(true){
            left = right = 0;
                        
            p1 = in.RI();
            if(p1 == 0) break;
            for(int i=0; i<p1; i++){
                int x = in.RI(), y = in.RI();
                
                q[right++] = (x<<11) + y;
                used.set(x*MAX_SIZE + y);
                data[x][y] = 0;
            }
            
            p2 = in.RI();
            for(int i=0; i<p2; i++){
                int x = in.RI(), y = in.RI();
                used2.set(x*MAX_SIZE + y);
            }
            
            exit:
            while(true){
                int cell = q[left++];
                int curX = (cell>>11), curY = (cell&2047);
                
                for(int i=0; i<DX.length; i++){
                    int newX = curX + DX[i], newY = curY + DY[i];
                    
                    if(newX>=0 && newX<=MAX_SIZE && newY>=0 && newY<=MAX_SIZE){
                        if(used2.get(newX*MAX_SIZE + newY)){
                            out.println(data[curX][curY] + 1);
                            break exit;
                        }
                        
                        if(!used.get(newX*MAX_SIZE + newY)){
                            q[right++] = (newX<<11) + newY;
                            data[newX][newY] = data[curX][curY] + 1;
                            used.set(newX*MAX_SIZE + newY);
                        }
                    }
                }
            }
            
            // clearing
            used.clear();
            used2.clear();
        }
	}
}

class InputReader {      
    private BufferedReader reader;
    private StringTokenizer tokenizer;
        
    public InputReader(InputStream stream)
    {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }
    
    public String next()
    {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    
    public int RI()
    {
        return Integer.parseInt(next());
    }
    
    }

I optimized my JAVA code and got AC in 1.084 sec. I used BufferedReader and BufferedWriter. A faster way to combine two integers is to use shift and bitwise and. I kept the distance in it's own 2-D array and placed x and y into the queue.
To add to the queue:
Q[tail++]=(x<<11)+y;

To remove from the queue:
x=Q[head]>>11;
y=Q[head++]&2047;

I also changed from a standard flood fill to a bidirectional meet in the middle approach, but didn't see much difference in the runtime.