## 10206 - Stars

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

### 10206 - Stars

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?
Wenyuan Dai, Shanghai Jiaotong University.

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

### 10206 Stars, How to deal with the symmetrical constellations

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.
I stay home. Don't call me out.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Every constellation only occurs once for every subset of stars that it can be made of. So be careful with symmetric constellations.
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.
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?
I stay home. Don't call me out.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.
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
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.
I stay home. Don't call me out.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.
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 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.
I stay home. Don't call me out.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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.
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 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 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.
I stay home. Don't call me out.

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

### Re: 10206 - 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;
}
``````