11378 - Bey Battle

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

Moderator: Board moderators

Post Reply
sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

11378 - Bey Battle

Post by sonyckson » Sat Jan 05, 2008 9:48 pm

Hello!, are there tricky cases in this problem?? ( as for in problem A ?? ).... I understand intersection of squares as intersection of their areas... is that right?....

My algorithm runs in O( n log(n)^2 ), and do a binary search in the square size. I have a function that tells me if for all squares of size K ( K even natural ) is there any intersection. Thanks! Eric.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11378 - Bey Battle

Post by rio » Sat Jan 05, 2008 10:13 pm

sonyckson wrote:Hello!, are there tricky cases in this problem?? ( as for in problem A ?? )
I don't think there is any tricky case.
I understand intersection of squares as intersection of their areas... is that right?....
Yes. Touching is OK.
My algorithm runs in O( n log(n)^2 ), and do a binary search in the square size. I have a function that tells me if for all squares of size K ( K even natural ) is there any intersection. Thanks! Eric.
Are you sure your function works?
This problem is a variety of Closest Pair Problem, so you could just modify the algorithm for Closest Pair Problem to solve this problem.
-----
Rio

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sat Jan 05, 2008 10:41 pm

Well, my idea is the next:

Just when i get all the points, i sort them by their x value. then I do binary search to get the square size. My function has 2 sets one has pairs of points beggining with the x-value, and the other pairs of points begining with the y-value ( lets call them conjx and conjy ) , i iterate for every point (in the sorted by the x-value order) and in each iteration i do the next:

1- eliminate all the points of my conjx set which x-value differ from my actual point x-value by more or just K ( K = length of square in the function ).
2- i make the point P = (y-K+1, -1000001), where y is the y-value of my actual point ( of the actual iteration i mean ), then i find the lower point, greater than P, and if this point y-value has a difference with my actual y-value of less than K ... then that point and my actual point must have intersecting squares and the function finish.
(this because their x's and y's difference both differ in less than K )
3- I insert my actual point in the conjx and in the cony ( after swaping y and x ).

Here is the code...
( i used long long because i dont know which is the bug, but i know it is not neccesary )

Edited.

Thanks!. Eric.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sun Jan 06, 2008 12:13 am

Actually, there was a tricky thing for me in the problem statement, i didnt realize that the square sides might not have integer coordinates. My approach is ok, and i also did the closest point idea, which showed to be easier to implement :).Thanks! gl! Eric.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal » Sun Jan 06, 2008 11:24 am

sonyckson wrote:Actually, there was a tricky thing for me in the problem statement, i didnt realize that the square sides might not have integer coordinates. My approach is ok, and i also did the closest point idea, which showed to be easier to implement :).Thanks! gl! Eric.
For this problem, would the approach:
"
Find the _points_ that correspond to the closest pair of points on the plane. And then, see what square can fit between these two points
"
work? I have a feeling that it would. Since there is no different orientation of the square possible.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Sun Jan 06, 2008 8:48 pm

mmmm.. suppose you have points (0,0)....(0,4).... and (3,7).... the closest points are (0,0) and (0,4) ( if i am not so sleep :P ).... then your answer would be 4... but the correct answer is 3.

Suppose you have two points on the plane, how do you get the greatest size of the squares? When you get that you can see how to use the closest point algorithm. gl! , Eric.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jan 07, 2008 4:34 am

Well when i set this problem i was looking for an O(N) algorithm. But i could not find. After that i implemented an NlgN version which used BST which is quite hard to code. I completely overlooked modified closest pair solution. So i though it was going to be one of the hardest. But now i can see how easy it was! :) Hope you people liked it!
Self judging is the best judging!

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal » Mon Jan 07, 2008 4:46 am

sonyckson wrote:mmmm.. suppose you have points (0,0)....(0,4).... and (3,7).... the closest points are (0,0) and (0,4) ( if i am not so sleep :P ).... then your answer would be 4... but the correct answer is 3.

Suppose you have two points on the plane, how do you get the greatest size of the squares? When you get that you can see how to use the closest point algorithm. gl! , Eric.
Hi,
When there are two points, redefine the dist between then as max(diffx/2, diffy/2). This is the size of the largest square.

This is the L-Inf metric. This can be transformed to L-1 metric by
(x,y)->(x-y, x+y).

but, I am unable to code this problem :'( Any hints on how to _code_ ? :) I got the theory part!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

Post by sonyckson » Mon Jan 21, 2008 4:23 am

jvimal wrote: When there are two points, redefine the dist between then as max(diffx/2, diffy/2). This is the size of the largest square.
Very near, the redefined distance ( the one should give us the size of the largest square ) betwen two points p1 = (x1,y1) and p2 = (x2,y2) is dist(p1,p2) = max(abs(x1-x2), abs(y1-y2) ).... now, use the closest point algorithm, think a little about the result. gl! Eric.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11378 - Bey Battle

Post by newkid » Thu Oct 13, 2011 7:55 am

It would've been nice if the lower value of N was defined. I don't think there were case with N == 1 (haven't tested though, I just printed 0 for that case)
hmm..

metaphysis
Experienced poster
Posts: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 11378 - Bey Battle

Post by metaphysis » Sun Feb 11, 2018 4:01 am

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));

    cout << "100000\n";
    for (int c = 1; c <= 100000; c++)
    {
        int n = rand() % 1000000;
        if (rand() % 2 == 0)
            cout << n;
        else
            cout << -n;
        cout << ' ';
        n = rand() % 1000000;
        if (rand() % 2 == 0)
            cout << n;
        else
            cout << -n;
        cout << '\n';
    }
}

Post Reply

Return to “Volume 113 (11300-11399)”