In regards to the DIVIDEN problem, I realized that the subtasks in the report are mislabeled. e.g. I completely solved what was labeled as subtask 2 and only received 25 pts instead of 75. Asking the judges this question wasn’t very fruitful, so I thought I’d leave this as a heads up here for others.
Also, are there any restrictions on the output points D_1, …, D_N that isn’t listed in the problem description? Cause I don’t believe I’m closer to getting any of the nontrivial ‘subtask 1’ (i.e. the actual subtask 2) testcases right regardless of changes I make. For example the GOOD GALAXY problem has extremely weak test cases (i.e. many bad galaxies were classified as good in my program but it still receives AC), and I just wanted to make sure that this problem’s test cases weren’t similar
Yes, I noticed this as well. I don’t think there are any explicit conditions on the coordinates of the output points. At least, I did not have to constrain them in anyway to get AC.
Hmm, ok. Its weird, the last many submissions of mine did little to alter the correct testcases I get from the harder subtask. Perhaps there was some formatting issue in larger cases unaccounted for? Was there anything not given in the problem statement that you had to account for?
I like this problem, but honestly I think this is not (in current shape) a good problem for a programming contest.
The expected value for N = 0 (mod 3) is “NO”, which is correct from “compass-and-straightedge construction” point of view, but should be “YES” (read more).
We can construct 60° angle easily. Using angle bisection we can get 30°, 15° immediately. But why to stop here? Using binary search approach, we can find (using bisection) the point P, which is closer than required eps = 10^-5 for 1° degree, later we can use this point to split 15° angle and repeat the procedure for all possible degrees N.
Or am I wrong and both solution “NO” and “YES” were accepted for N = 3 for example? I didn’t try, because I think chance for this to happen is quite small.
Now that the contest is over, I can tell you the corner case. An angle of degree three is always constructible, so the only impossible cases are when the angle divides three. The cases you are getting correct are only the no cases. You can verify that your no cases are correct during the contest by throwing an error when you are returning no. I noticed my original solution was throwing an error for everything, so just checking if it is a power of 2 is not sufficient
I was under the impression that an angle can be split in the given way iff it was a power of 2. I recall it being provably impossible to trisect an angle. How is an angle of degree 3 constructible?
Actually further looking at others’ solutions I understand it now…wow that was pretty hard to think of
On wiki, there was a link, that it is possible to construct 72° angle, then 72 - 60 = 12 => 6 => 3 I§m not sure how clear is this from code, the construction was not so simple - File:Pentagon construct.gif - Wikimedia Commons
I just spotted there is:
The first line of the output should contain a single word: YES or NO - whether it is theoretically possible to perform the construction described above with a straightedge and compass only.
in problem statement text, so I’m wrong…