11101  Mall Mania
Moderator: Board moderators
11101  Mall Mania
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.......
If I will myself do hashing, then who will do coding !!!

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 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).
Re: 11101 Mall Mania
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.
Hi,
I solved this problem by BruteForce, 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 BruteForce, 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
Regrads
Miras
Regrads
Miras
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 BruteForce, 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
@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???
If I will myself do hashing, then who will do coding !!!
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;
}

 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]
Seem uv Got the same problem of Trip Shock ...
if Anyone would help .....it'll be appreciated ![/quote]
MeroTheHero

 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
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;)
Beliefs are not facts, believe what you need to believe;)
Re: 11101  Mall Mania
Can someone help me with this problem?
I am always getting WAs...
is this outputinput data is correct?
INPUT
OUTPUT:
Here is my code: http://paste.ubuntu.com/1028665/
Thanks!
I am always getting WAs...
is this outputinput 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();
}
}

 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!