## 11101 - Mall Mania

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

Moderator: Board moderators

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### 11101 - Mall Mania

how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points.......
If I will myself do hashing, then who will do coding !!!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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?

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
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...
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
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..
If I will myself do hashing, then who will do coding !!!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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).

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### Re: 11101 Mall Mania

vinay wrote:how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points.......
Not sure what you mean by "n." There's no "n" in the problem.

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.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 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
Remember Never Give Up
Miras

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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
If you want to compose some more extensive test data, I bet you could convince the administrators to install it.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
@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???
If I will myself do hashing, then who will do coding !!!

TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

### WA

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

merothehero
New poster
Posts: 1
Joined: Fri Mar 14, 2008 9:46 pm

### Same Problem of TripShock

Hey Guys !

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

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

vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11101 - Mall Mania

Code: Select all

``````Accepted
Spoiler :[BFS && Multi Source]
``````
Impossible says I`m possible

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11101 - Mall Mania

I used multi source bidirectional BFS as it would be very very much faster....
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

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

### Re: 11101 - Mall Mania

Can someone help me with this problem?

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
``````
OUTPUT:

Code: Select all

``````2
2
1

``````
Here is my code: http://paste.ubuntu.com/1028665/

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;

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

}

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

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

// 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;
boolean eof = false;

public static void main(String[] args) {
}

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 {
} catch (Exception e) {
ret = "";
}
if (ret == null) {
eof = true;
return null;
}
return ret;
}

int RC() {
try {
} 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) {
out = new PrintWriter(new OutputStreamWriter(System.out));
} else {
try {
File input = new File("input.txt");
if (!input.exists()) {
input.createNewFile();
}

out = new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt")));
} catch (Exception e) {
e.printStackTrace();
System.exit(111);
}
}
}

@Override
public void run() {
solve();
out.close();
}
}
``````
Thanks!

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

### Re: 11101 - Mall Mania

My AC output for the input you posted is:

Code: Select all

``````2
1
1``````
Check input and AC output for thousands of problems on uDebug!