11006 - Wheel Good

tobby · Post by **tobby** » Fri Mar 10, 2006 8:24 pm

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 · Post by **tobby** » Sat Mar 11, 2006 5:46 am

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

tobby · Post by **tobby** » Sat Mar 11, 2006 6:25 am

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

aminallam · Post by **aminallam** » Thu Mar 23, 2006 6:14 pm

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

aminallam · Post by **aminallam** » Fri Mar 24, 2006 11:13 am

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

misof · Post by **misof** » Fri Mar 24, 2006 12:03 pm

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

tobby · Post by **tobby** » Fri Mar 24, 2006 12:38 pm

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

Hint: greedy.

aminallam · Post by **aminallam** » Fri Mar 24, 2006 5:25 pm

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

aminallam · Post by **aminallam** » Thu Mar 30, 2006 6:44 am

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

tobby · Post by **tobby** » Sat Apr 01, 2006 8:12 pm

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 · Post by **sohel** » Sun Apr 02, 2006 4:26 pm

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

windows2k · Post by **windows2k** » Thu Jun 01, 2006 3:44 am

tobby wrote: Hint: greedy.

I don't have any thought how to greedy.
Could you give more hints?

tobby · Post by **tobby** » Fri Dec 15, 2006 5:08 am

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 = ?