11006 - Wheel Good

All about problems in Volume 110. 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
tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

11006 - Wheel Good

Post by tobby »

I am getting WA for this problem. Not very surprising since I just follow my intuition to code it.

I get a 7592-gon for N = 100000. Is this correct? If not, could anyone please give any hints? Thank you.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

Oops. I see some flaws in my idea. I shall post more after I have fixed that.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

Accepted. The number above should be correct. Also, for N = 13, you should get a 20-gon.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Please help me to solve this problem. I have made wrong algorithms. What should I do to solve it?

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Can you give me a hint or small input/output for this problem?

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

a similar TopCoder problem:
http://www.topcoder.com/stat?c=problem_ ... 87&rd=8068
(read the corresponding editorial there)

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

aminallam wrote:Can you give me a hint or small input/output for this problem?
Hint: greedy. :D

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Thank you very much Mr. Misof. It is nice to see you here. Thanks Mr. tobby.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

For Mr. tobby, if you have time, please describe the greedy approach.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

Maybe you should try to construct by hand a 20-gon for N=13 to begin with. Sorry I don't have time now to explain more. Will write more later if I have time.

Note that the polygon you get need not be mirror symmetric.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Why is the problem statement written in that style..
.. isn't it kind of confusing.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k »

tobby wrote: Hint: greedy. :D
I don't have any thought how to greedy.
Could you give more hints?

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

I promised to leave some hints here, so I am back!

Think about a highly related problem: how do you construct the smallest 4k-gon (in terms of its width) satisfying the symmetry property?

Code: Select all

   k = 1      k = 2      k = 3

     _          _
    |_|        / \
              |   |        ?
               \_/
                

 width = 1  width = 3  width = ?

Post Reply

Return to “Volume 110 (11000-11099)”