10206 - Stars

[dwyak]

The problem says, "If there are several equally bright solutions, output only one of them. ".
I think it means there are multiple answers, and we can output any one.
But, it's a red problem, without special judge.
Does all the testcase have a unique answer?

[ImLazy]

For example, in this test data:

Code: Select all

4
0 0
1 0
1 1
0 1
1
4 Rect
0 0
1 0
1 1
0 1

How many times does the constellation occurs? Is it 1 or 4? I think it should be 4, because they are not identical, they have different rotation.

[little joey]

The answer is 1.
Every constellation only occurs once for every subset of stars that it can be made of. So be careful with symmetric constellations.

[ImLazy]

Thank you.
But this problem is still very difficult for me.
My algorithm is: for every pair of points in the map, regard they as the first and the second point in the constellation. And for each other point in the constellation, calculate its coordinate in the map, if it is not integer or it doesn't exist in the map, then break the loop and go to another pair of points in the map.
But this method seems to be too slow.
What's you algorithm?

[little joey]

Yes, I use the same algorithm.
Once you confirmed that a candidate position for the third, fourth, etc. star in the constellation has (almost) integer coordinates, you have to determine if that position actually contains a star, and if so, identify that star (to determine its brightness). You will have to find a constant time method to do that; looping through all possible stars is too slow.

[ImLazy]

Do you mean you can identify whether there is a star at one position in constant time?
But I think it's very difficult, because the problem doesn't tell the max value of coordinate, I can not use a 2-dimension array to describe stars.
I think this takes at least O(log n) time, if I use a Bianry Search Tree.

[little joey]

Hmm. Yes, you're right, the boundaries for the coordinates are not given. I looked at my code and not at the description, and in my code I use the fact that -128 <= x,y <= +127. I realy can't recall where I got that information (probably some asserts in a previous version or a posting on the board). But you can use that it to build a starmap of reasonable size.

On second thought: If you want to be safe, you can store the star positions in a hash table for near-constant lookup time.

[ImLazy]

Thank you very much.
I agree with you that the test data of this problem is very weak, because I saw the ranklist, and all of the solvers use 0:00.000 CPU time.

[little joey]

Indeed, it is. But this problem is exactly the same as 316 which has a much bigger testset. So when you get this one accepted, you can try 316 with the same code to compare your runtime with other solvers.

[ImLazy]

Thank you.

[ImLazy]

Now I get AC in 10206, but Runtime Error in 316.
I'm sure the size of the array is big enough. I'm afraid I shall take long time to debug my code because it is very long.

[metaphysis]

Test data generator.

Code: Select all

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <set>
#include <string>

using namespace std;

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

    int cases = 5;
    set<long long int> produced;
    
    for (int c = 1; c <= cases; c++)
    {
        int n = rand() % 100 + 1;
        cout << n << '\n';

        produced.clear();
        int counter = 0;
        while (counter < n)
        {
            long long int x = rand() % 1000;
            long long int y = rand() % 1000;
            int brightness = rand() % 1000;
            long long int hash = x * 10000 + y;
            if (produced.find(hash) == produced.end())
            {
                cout << x << ' ' << y << ' ' << brightness << '\n';
                produced.insert(hash);
                counter++;
            }
        }
        
        int m = rand() % 20 + 1;
        cout << m << '\n';
        
        for (int i = 1; i <= m; i++)
        {
            int si = rand() % 6 + 1;
            string name = to_string(c) + "-" + to_string(i);
            cout << si << ' ' << name << '\n';
            
            produced.clear();
            counter = 0;
            while (counter < si)
            {
                long long int x = rand() % 1000;
                long long int y = rand() % 1000;
                long long int hash = x * 10000 + y;
                if (produced.find(hash) == produced.end())
                {
                    cout << x << ' ' << y << '\n';
                    produced.insert(hash);
                    counter++;
                }
            }
        }
    }
    cout << 0 << endl;

    return 0;
}