316 - Stars

[stefan_buettcher]

Can anybody who has solved the problem offer a few
testcases to me so that I can check my program? I am
getting WA and have absolutely no idea where the bug is.

[Moha]

first- you should handle for 1 and 2 star in constellation.
and when number of star in sky is less than constellation.
second - you should handle isomorhism situation for example this one:
4
1 1 1
1 2 1
2 1 1
2 2 1
1
4 Square
1 1
1 2
2 1
2 2
answer should be 1 occurance.
Goodlock!

[stubbscroll]

I'm totally stuck on problem 316. After 36 WA/RTE and lots of hours spent I'm posting here...

(POSSIBLE SPOILERS FOR THOSE WHO HAVEN'T SOLVED THIS PROBLEM YET:)

My algorithm is as follows:

I first check how many times each constellation appear within itself, to handle squares and other shapes that can occur more times with a different rotation.

Then I check the constellation against the map. For each two points in the map, I adjust the two first points in the constellation against them and I scale/rotate/translate all points in the constellation. I find the angle of rotation with atan2, and I do the rotation using sin/cos. Constellations with 1 and 2 stars use special case code. The number of occurrences are divided by the the number of occurences the constellation appeared in itself. In the test case above, the number of occurences (4) would be divided by 4 to return 1 occurrence.

However, I get run-time error (divide by zero), even though my program gets accepted at Peking University online judge where it's also possible to submit this problem. Via assert I've found out that in one test case with a constellation of 3 stars, my program finds that the constellation appears 0 times within itself, and that the absolute value of the coordinates in the constellation is not larger than 4, which leaves a range of [-4..4]. I generated all possible inputs of 3-star constellations (all 511920 of them), my program manages to process them without RTE on my computer. I've compared the output of the official solution (btw, I submitted it in desperation and it gets RTE) against mine on a few hundred thousand random generated inputs, and the outputs are identical.

Now, I ask you people who have AC on this problem... Could you give me a hint of what the trick is? I'm 95% sure that my program handles all normal inputs, so there must be a trick in the input files...

[little joey]

Are you somehow (implicitly) assuming that the stars, both within the starmap as within one constellation, should be distinct? I realy can't tell you if the judge input contains cases where two stars coincide, but that looks like a possible cause for a program to fail with the type of error you describe.
Again: I have no idea if there is such data, but looking at my own code, I see that it (unintentionally) handles these cases correctly.

[stubbscroll]

I have checked for equal coordinates earlier, and I checked it again just to be sure. I just submitted a program that only reads the input with assert on equal coordinates. It reported WA, so there can't be equal coordinates. Thanks for the help anyway. Maybe I'll get some more ideas later...

[ImLazy]

Some subset may occur more than one time because some constellations are symmetrical. So how do you rule out the repeating occurences?
I used to store all the occurences in an array and check the repeating ones. But that causes MLE.

[ImLazy]

Now I have conquered this error. But still I get WA.
Do you have any special test data?
By the way, I have get AC in #10206 (the same problem as #316), but WA in this problem.

[ImLazy]

I keep getting WA in this problem . So please help me to check your output for this test data with mine.
The input data is here: http://baidiheizi.diy.myrice.com/acm/316in.txt
It is very big and may take you minutes of time to run it. But please help me.
My output is here: http://baidiheizi.diy.myrice.com/acm/316out.txt
Is it the same as yours? Thanks.

[little joey]

Hi ImLazy,
I have many differences in my output compared to yours.
Your answer for the third contellation in map 5 is obviously wrong:
There are 551 stars in map 5 and the third constellation has 2 stars, this means that every pair of stars should count as an occurrance. There are (551 * 550) / 2 = 151525 pairs, but in your output you report only 105580 occurrences.
Further comparison of your output and mine reveals that your counts are always lower or equal than mine. I think that your tolerance when comparing a calculated star position (in doubles) to an actual star position (in integers) is too low.

[ImLazy]

Thank you. I will check it.

[ImLazy]

There is no problem with my precision. Because I never do real number calculating, I calculte the numerator and denominator respectively.

My problem is still the symmetrical constellations. I made some mistake to deal with them.

Now I get AC! Thank you very much!

[morris821028]

tricky input:

1
1 1 1
4
1 Point
7 8
2 Line
1 4
3 9
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5

tricky output:

Map #1

Point occurs 1 time(s) in the map.
Brightest occurrence: (1,1)

Line occurs 0 time(s) in the map.

Triangulum occurs 0 time(s) in the map.

Cancer occurs 0 time(s) in the map.
-----

[metaphysis]

Comfirmed by using assert in C++:
(1) There is no dupciliated point in star map or constellation in judge data.
(2) There is no need to handle symmetrical constellations, because all constellation are not symmetrical in judge data.

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