10206 - Stars
Moderator: Board moderators
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?
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.
10206 Stars, How to deal with the symmetrical constellations
For example, in this test data:
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.
Code: Select all
4
0 0
1 0
1 1
0 1
1
4 Rect
0 0
1 0
1 1
0 1
I stay home. Don't call me out.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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?
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.
-
- 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.
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.
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.
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.
-
- 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.
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.
-
- 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.
-
- 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;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.