11101 - Mall Mania

[vinay]

how to solve this problem...

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

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

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

[vinay]

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

[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).

[gvcormac]

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]

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

[gvcormac]

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]

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

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

[merothehero]

Hey Guys !

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

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

[vahid sanei]

Code: Select all

Accepted 
Spoiler :[BFS && Multi Source] 

[Angeh]

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

[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!

[brianfry713]

My AC output for the input you posted is:

Code: Select all

2
1
1