## 316 - Stars

Moderator: Board moderators

stefan_buettcher
New poster
Posts: 2
Joined: Fri Feb 14, 2003 11:20 pm

### 316 - Stars

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

### somthing to consider..

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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

### Stuck on problem 316 without knowing why

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
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
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 316 Star. keep WA

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.
Last edited by ImLazy on Sun Feb 05, 2006 5:22 am, edited 1 time in total.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 316 Star. If you get AC, please check your output 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.
I stay home. Don't call me out.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Thank you. I will check it.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
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!
I stay home. Don't call me out.

morris821028
New poster
Posts: 13
Joined: Thu Dec 06, 2012 4:07 pm

### Re: 316 Star. keep WA

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.
-----
?? Taiwan ! ??????????

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

### Re: 316 - Stars

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
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 316 - Stars

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