Page 1 of 2

11101 - Mall Mania

Posted: Fri Sep 29, 2006 2:59 am
by vinay
how to solve this problem...

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

Posted: Fri Sep 29, 2006 9:32 am
by little joey
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?

Posted: Fri Sep 29, 2006 10:05 am
by vinay
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... :D

Posted: Fri Sep 29, 2006 11:29 am
by vinay
when i move like this its tle... :cry:

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..
:oops:

Posted: Fri Sep 29, 2006 11:58 am
by little joey
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

Posted: Fri Sep 29, 2006 1:41 pm
by gvcormac
vinay wrote:how to solve this problem...

O(n^2) should clearl time limit i.e. checking all pair of points....... :cry:
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.

Posted: Fri Sep 29, 2006 6:58 pm
by miras
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: Fri Sep 29, 2006 7:02 pm
by gvcormac
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.

Posted: Sat Sep 30, 2006 1:39 am
by vinay
@little joey

thanks for ur help its accepted :D

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

WA

Posted: Thu Aug 09, 2007 11:16 am
by TripShock
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;
}

Same Problem of TripShock

Posted: Fri Mar 14, 2008 9:51 pm
by merothehero
Hey Guys !

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

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

Re: 11101 - Mall Mania

Posted: Sun Feb 22, 2009 9:44 am
by vahid sanei

Code: Select all

Accepted 
Spoiler :[BFS && Multi Source] 

Re: 11101 - Mall Mania

Posted: Thu Nov 04, 2010 2:20 pm
by Angeh
I used multi source bidirectional BFS as it would be very very much faster....

Re: 11101 - Mall Mania

Posted: Thu Jun 07, 2012 6:28 pm
by SyFyKid
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;

            // 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();
    }
}
Thanks!

Re: 11101 - Mall Mania

Posted: Fri Jun 08, 2012 1:13 am
by brianfry713
My AC output for the input you posted is:

Code: Select all

2
1
1