## 11101 - Mall Mania

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

Moderator: Board moderators

### Re: 11101 - Mall Mania

Thank you for replying!

But why its 1 instead of 0 or 2 on this test case:
Code: Select all
`40 00 11 11 063 23 12 11 11 22 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 ?

brianfry713 wrote:My AC output for the input you posted is:
Code: Select all
`211`
SyFyKid
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

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

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

### Re: 11101 - Mall Mania

brianfry713 wrote: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
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

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());    }        }`
Last edited by SyFyKid on Tue Jun 12, 2012 10:32 am, edited 1 time in total.
SyFyKid
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

Why are you using 1997?
brianfry713
Guru

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

### Re: 11101 - Mall Mania

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;

brianfry713 wrote:Why are you using 1997?
SyFyKid
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

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

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

### Re: 11101 - Mall Mania

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

brianfry713 wrote:My C++ code that got AC in 0.752 sec I rewrote in JAVA and got TLE.
SyFyKid
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

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:

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.
brianfry713
Guru

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

### Re: 11101 - Mall Mania

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

brianfry713 wrote: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:

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
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

### Re: 11101 - Mall Mania

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());    }        }`

brianfry713 wrote: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:

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
New poster

Posts: 26
Joined: Tue May 08, 2012 9:47 am

Previous