### 11101 - Mall Mania

Posted:

**Fri Sep 29, 2006 2:59 am**how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points.......

O(n^2) should clearl time limit i.e. checking all pair of points.......

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=37&t=12225

Page **1** of **2**

Posted: **Fri Sep 29, 2006 2:59 am**

how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points.......

O(n^2) should clearl time limit i.e. checking all pair of points.......

Posted: **Fri Sep 29, 2006 9:32 am**

Given the list of all gridpoints that lie on the perimeter of the first mall, can you identify all gridpoints that are at distance 1 from the perimeter?

And given that list, can you identify all gridpoints at distance 2?

And from that, for distance 3?

When do you stop?

And given that list, can you identify all gridpoints at distance 2?

And from that, for distance 3?

When do you stop?

Posted: **Fri Sep 29, 2006 10:05 am**

so the complexity of the algo ishud be O(nk) whrer k is the minimum distance or our answer.

thanks lwt me give a try...

thanks lwt me give a try...

Posted: **Fri Sep 29, 2006 11:29 am**

when i move like this its tle...

how can i decide in which direction to move b'coz at present i move inwards as well as outwards from the perimeter of one mall to another..

how can i decide in which direction to move b'coz at present i move inwards as well as outwards from the perimeter of one mall to another..

Posted: **Fri Sep 29, 2006 11:58 am**

In principle you could do that, but I don't think it's worthwhile. More important is that you don't move to a gridpoint for which you already know the distance, ensuring that every gridpoint is explored at most once. So you'll need a datastructure that stores that fact for every gridpoint. (SPOILER: think of floodfill).

Posted: **Fri Sep 29, 2006 1:41 pm**

Not sure what you mean by "n." There's no "n" in the problem.vinay wrote:how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points.......

I think you mean p1*p2 (the product of the perimeters)

that's too long.

There's a solution with n^2 operations where n is the

dimension of the bounding box.

Posted: **Fri Sep 29, 2006 6:58 pm**

Hi,

I solved this problem by Brute-Force, and got AC in less that 1s

How did I get it?

well The answer is simple, I randomly picked some pairs of points and couted distance between them. And that is all. I was picking those pairs 100000 times. But It shouldn't work at all

I solved this problem by Brute-Force, and got AC in less that 1s

How did I get it?

well The answer is simple, I randomly picked some pairs of points and couted distance between them. And that is all. I was picking those pairs 100000 times. But It shouldn't work at all

Posted: **Fri Sep 29, 2006 7:02 pm**

If you want to compose some more extensive test data, I bet you could convince the administrators to install it.miras wrote:Hi,

I solved this problem by Brute-Force, and got AC in less that 1s

How did I get it?

well The answer is simple, I randomly picked some pairs of points and couted distance between them. And that is all. I was picking those pairs 100000 times. But It shouldn't work at all

Posted: **Sat Sep 30, 2006 1:39 am**

@little joey

thanks for ur help its accepted

it now takes 3.143 seconds ....

yeah i was implementing floodfill , but what was the real bottleneck was the

use of vector erase which is really time consuming...

what was the time limit during the contest by the way???

thanks for ur help its accepted

it now takes 3.143 seconds ....

yeah i was implementing floodfill , but what was the real bottleneck was the

use of vector erase which is really time consuming...

what was the time limit during the contest by the way???

Posted: **Thu Aug 09, 2007 11:16 am**

I'm getting WA for my code. Can someone please spot the error...

Code: Select all

```
#include <iostream>
using namespace std;
const int MAX = 10000;
int MallA[MAX][2] = { 0 };
int APoints = 0;
int MallB[MAX][2] = { 0 };
int BPoints = 0;
int GetDist(int X1, int Y1, int X2, int Y2)
{
int Horizontal = Y1 - Y2;
if (Horizontal < 0)
Horizontal *= -1;
int Vertical = X1 - X2;
if (Vertical < 0)
Vertical *= -1;
return (Vertical + Horizontal);
}
int main()
{
int Perimeter = 0;
while (true)
{
cin >> Perimeter;
if (!Perimeter)
break;
APoints = 0;
for (int i = 0; i < Perimeter; i++)
{
cin >> MallA[APoints][0] >> MallA[APoints][1];
APoints++;
}
cin >> Perimeter;
BPoints = 0;
for (int i = 0; i < Perimeter; i++)
{
cin >> MallB[BPoints][0] >> MallB[BPoints][1];
BPoints++;
}
int ShortestDist = 9999999;
for (int i = 0; i < APoints; i++)
{
for (int j = 0; j < BPoints; j++)
{
int Distance = GetDist(MallA[i][0], MallA[i][1], MallB[j][0], MallB[j][1]);
if (Distance < ShortestDist)
ShortestDist = Distance;
}
}
cout << ShortestDist << endl;
}
return 0;
}
```

Posted: **Fri Mar 14, 2008 9:51 pm**

Hey Guys !

Seem uv Got the same problem of Trip Shock ...

if Anyone would help .....it'll be appreciated ![/quote]

Seem uv Got the same problem of Trip Shock ...

if Anyone would help .....it'll be appreciated ![/quote]

Posted: **Sun Feb 22, 2009 9:44 am**

Code: Select all

```
Accepted
Spoiler :[BFS && Multi Source]
```

Posted: **Thu Nov 04, 2010 2:20 pm**

I used multi source bidirectional BFS as it would be very very much faster....

Posted: **Thu Jun 07, 2012 6:28 pm**

Can someone help me with this problem?

I am always getting WAs...

is this output|input data is correct?

INPUT
OUTPUT:
Here is my code: http://paste.ubuntu.com/1028665/
Thanks!

I am always getting WAs...

is this output|input data is correct?

INPUT

Code: Select all

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

Code: Select all

```
2
2
1
```

Code: Select all

```
import java.io.*;
import java.util.*;
import java.util.StringTokenizer;
public class Main implements Runnable {
void solve(){
console(true);
Queue<Integer> q;
HashSet<Integer> secondMall, used;
int UPPER_X, LOWER_X, UPPER_Y, LOWER_Y;
int inters;
while(true)
{
// init
q = new LinkedList<Integer>();
secondMall = new HashSet<Integer>();
used = new HashSet<Integer>();
UPPER_X = UPPER_Y = Integer.MIN_VALUE;
LOWER_X = LOWER_Y = Integer.MAX_VALUE;
inters = 0;
// input reading
int p1 = RI();
if (p1 == 0) break;
for(int i=0; i<p1; i++)
{
int x = RI(), y = RI();
UPPER_X = Math.max(UPPER_X, x);
UPPER_Y = Math.max(UPPER_Y, y);
LOWER_X = Math.min(LOWER_X, x);
LOWER_Y = Math.min(LOWER_Y, y);
q.add(encode(x, y, 0));
used.add(encode(x, y));
}
int p2 = RI();
for(int i=0; i<p2; i++)
{
int x = RI(), y = RI();
UPPER_X = Math.max(UPPER_X, x);
UPPER_Y = Math.max(UPPER_Y, y);
LOWER_X = Math.min(LOWER_X, x);
LOWER_Y = Math.min(LOWER_Y, y);
secondMall.add(encode(x, y));
if(used.contains(encode(x, y))) inters++;
}
// bfsing
int ans = Integer.MAX_VALUE;
while(!q.isEmpty())
{
int cell = q.poll();
int x = getX(cell), y = getY(cell), d = getD(cell);
if(secondMall.contains(encode(x, y)))
{
ans = Math.min(ans, d);
}
for(int i=0; i<DX4.length; i++)
{
int newX = x + DX4[i], newY = y + DY4[i], newD = d + 1;
int newCell = encode(newX, newY), encCellD = encode(newX, newY, newD);
if(newX>=LOWER_X && newX<=UPPER_X && newY>=LOWER_Y && newY<=UPPER_Y && !used.contains(newCell))
{
used.add(newCell);
q.add(encCellD);
}
}
}
// output
if(inters == 0) out.println(ans);
else if(inters == 1) out.println(2);
else if(inters > 1) out.println(1);
}
}
int getD(int c)
{
return c%PRIME;
}
int getY(int c)
{
return (c/PRIME)%PRIME;
}
int getX(int c)
{
return (c/PRIME)/PRIME;
}
int encode(int a, int b)
{
return encode(a, b, 0);
}
int encode(int a, int b, int c)
{
return a*PRIME*PRIME + b*PRIME + c;
}
// ---------------------------------------------------------- TEMPLATE ----------------------------------------------
final int PRIME = 9997;
final int[] DX4 = new int[]{-1, 0, +1, 0}, DY4 = new int[]{0, +1, 0, -1}; // 2D - 4
final int[] DX6 = new int[]{0, +1, 0, -1, 0, 0}, DY6 = new int[]{+1, 0, -1, 0, 0, 0}, DZ6 = new int[]{0, 0, 0, 0, +1, -1}; // 3D - 6
final int[] DX8 = new int[]{-1, -1, -1, 0, +1, +1, +1, 0}, DY8 = new int[]{-1, 0, +1, +1, +1, 0, -1, -1}; // 2D - 8
StringTokenizer st;
PrintWriter out;
BufferedReader br;
boolean eof = false;
public static void main(String[] args) {
new Thread(new Main()).start();
}
String nextToken(){
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String RLine() {
String ret;
try {
ret = br.readLine();
} catch (Exception e) {
ret = "";
}
if (ret == null) {
eof = true;
return null;
}
return ret;
}
int RC() {
try {
return br.read();
} catch (Exception e) {
return -1;
}
}
String RS() {
return nextToken();
}
int RI() {
return Integer.parseInt(nextToken());
}
long RL() {
return Long.parseLong(nextToken());
}
double RD() {
return Double.parseDouble(nextToken());
}
void console(boolean f) {
if (f) {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
} else {
try {
File input = new File("input.txt");
if (!input.exists()) {
input.createNewFile();
}
br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));
} catch (Exception e) {
e.printStackTrace();
System.exit(111);
}
}
}
@Override
public void run() {
solve();
out.close();
}
}
```

Posted: **Fri Jun 08, 2012 1:13 am**

My AC output for the input you posted is:

Code: Select all

```
2
1
1
```