10206 - Stars

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10206 - Stars

Post by dwyak » Sun Mar 07, 2004 8:14 pm

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.

User avatar
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

Post by ImLazy » Thu Feb 02, 2006 10:18 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Feb 02, 2006 1:51 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

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

Post by ImLazy » Thu Feb 02, 2006 4:19 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?
I stay home. Don't call me out.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Feb 02, 2006 5:03 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.

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

Post by ImLazy » Thu Feb 02, 2006 5:46 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Feb 02, 2006 6:43 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.

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

Post by ImLazy » Thu Feb 02, 2006 6:55 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Feb 02, 2006 7:01 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.

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

Post by ImLazy » Fri Feb 03, 2006 6:52 am

Thank you. :D
I stay home. Don't call me out.

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

Post by ImLazy » Fri Feb 03, 2006 6:54 pm

Now I get AC in 10206, but Runtime Error in 316. :cry:
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: 128
Joined: Wed May 18, 2011 3:04 pm

Re: 10206 - Stars

Post by metaphysis » Sun Feb 11, 2018 4:07 am

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

muazuicom22
New poster
Posts: 25
Joined: Tue Sep 11, 2018 10:32 pm

Post by muazuicom22 » Sat Sep 29, 2018 6:03 pm

CTY TDL CHUYÊN NHẬN LÀM GIẤY TỜ :

Kính gửi Quý khách hàng , Cty TDL chúng tôi

Nhận làm tất cả các loại giấy tờ liên quan đến BĐS , từ dễ đến khó , khu vực Thành Phố HCM Và Bình Dương.
* Vẽ thiết kế xây dựng, xin giấy phép xây dựng.
* Vẽ hiện trạng đo đạc nhà đất, nhà máy, nhà xưởng.
*Dịch vụ thiết kế Phòng cháy, chữa cháy và Thẩm duyệt.
* Dịch vụ xin chuyển mục đích sử dụng đất.
* Dịch vụ hoàn công nhà xưởng, công trình trên đất.
* Dịch vụ tách thửa sổ đỏ, nhà đất, nhà xưởng, nhà máy.
* Dịch vụ xin cấp mới sổ đỏ, sổ hồng hoặc xin cấp Giấy chứng nhận Quyền sử dụng đất, quyền sở hữu nhà ở và tài sản khác gắn liền với đất.
* Dịch vụ xác định lại ranh giới, thực trạng nhà đất, cấp sổ mới.
* Dịch vụ xem xét lại quy hoạch xây dựng.
* Dịch vụ hợp thức hóa nhà đất.
* Dịch vụ sang tên , đăng bạ sang tên chủ quyền, thừa kế di chúc.


Ai có nhu cầu liên hệ 0938.242.835 c.Hong.
Quý khách Lưu lại khi cần . Trân trọng cảm ơn. Uy Tin_ chinh chuan.
Chúc Anh chị một ngày tốt lành

Post Reply

Return to “Volume 102 (10200-10299)”