Page 1 of 1
11006 - Wheel Good
Posted: Fri Mar 10, 2006 8:24 pm
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.
Posted: Sat Mar 11, 2006 5:46 am
by tobby
Oops. I see some flaws in my idea. I shall post more after I have fixed that.
Posted: Sat Mar 11, 2006 6:25 am
by tobby
Accepted. The number above should be correct. Also, for N = 13, you should get a 20-gon.
Posted: Thu Mar 23, 2006 6:14 pm
by aminallam
Please help me to solve this problem. I have made wrong algorithms. What should I do to solve it?
Posted: Fri Mar 24, 2006 11:13 am
by aminallam
Can you give me a hint or small input/output for this problem?
Posted: Fri Mar 24, 2006 12:03 pm
by misof
a similar TopCoder problem:
http://www.topcoder.com/stat?c=problem_ ... 87&rd=8068
(read the corresponding editorial there)
Posted: Fri Mar 24, 2006 12:38 pm
by tobby
aminallam wrote:Can you give me a hint or small input/output for this problem?
Hint: greedy.
Posted: Fri Mar 24, 2006 5:25 pm
by aminallam
Thank you very much Mr. Misof. It is nice to see you here. Thanks Mr. tobby.
Posted: Thu Mar 30, 2006 6:44 am
by aminallam
For Mr. tobby, if you have time, please describe the greedy approach.
Posted: Sat Apr 01, 2006 8:12 pm
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.
Posted: Sun Apr 02, 2006 4:26 pm
by sohel
Why is the problem statement written in that style..
.. isn't it kind of confusing.
Posted: Thu Jun 01, 2006 3:44 am
by windows2k
tobby wrote:
Hint: greedy.
I don't have any thought how to greedy.
Could you give more hints?
Posted: Fri Dec 15, 2006 5:08 am
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 = ?