## 11101 - Mall Mania

Moderator: Board moderators

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

### Re: 11101 - Mall Mania

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 ?
brianfry713 wrote:My AC output for the input you posted is:

Code: Select all

``````2
1
1``````

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

### Re: 11101 - Mall Mania

Your input is not valid. The malls do not intersect, even in one point. I tested the judge's input.
Check input and AC output for thousands of problems on uDebug!

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

### 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.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Queue;
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;
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;
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;

}

// 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;

}

// 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)){
}
}
}
}

// init
used = new HashSet<Integer>();
}
}
}

private StringTokenizer tokenizer;

{
tokenizer = null;
}

public String next()
{
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

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.

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

### Re: 11101 - Mall Mania

Why are you using 1997?
Check input and AC output for thousands of problems on uDebug!

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

### 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?

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

### Re: 11101 - Mall Mania

My C++ code that got AC in 0.752 sec I rewrote in JAVA and got TLE.
Check input and AC output for thousands of problems on uDebug!

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

### 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.

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

### 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.
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.
Check input and AC output for thousands of problems on uDebug!

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

### 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.
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.IOException;
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;
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();
}
}
}

private StringTokenizer tokenizer;

{
tokenizer = null;
}

public String next()
{
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

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.