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

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

11101 - Mall Mania

Post by vinay » 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....... :cry:
If I will myself do hashing, then who will do coding !!!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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?

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

Post by vinay » 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... :D
If I will myself do hashing, then who will do coding !!!

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

Post by vinay » Fri Sep 29, 2006 11:29 am

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:
If I will myself do hashing, then who will do coding !!!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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).

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

Re: 11101 Mall Mania

Post by gvcormac » Fri Sep 29, 2006 1:41 pm

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.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » 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 ;-)
Remember Never Give Up
Regrads
Miras

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

Post by gvcormac » Fri Sep 29, 2006 7:02 pm

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.

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

Post by vinay » Sat Sep 30, 2006 1:39 am

@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???
If I will myself do hashing, then who will do coding !!!

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

WA

Post by TripShock » 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;
}

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

Same Problem of TripShock

Post by merothehero » 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]
MeroTheHero

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

Re: 11101 - Mall Mania

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

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

Post by Angeh » Thu Nov 04, 2010 2:20 pm

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

Post by SyFyKid » 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

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11101 - Mall Mania

Post by brianfry713 » Fri Jun 08, 2012 1:13 am

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!

Post Reply

Return to “Volume 111 (11100-11199)”