Hello, I am one of the participants of APIO 2025 (you can check at rank 44). The problems are really hard and tricky, and one of them is the 3rd problem — rotate. You guys can check the statements of APIO2025 in here: https://github.com/apio2025/apio2025_tasks.
I won't talk about the statement of the 3rd problem here since it's already in github; you guys should check that before reading my solution.
So, I don't know if this is the intended solution, but I think I am really lucky when I got accepted at 4h45. And that solution is really simple. Here's my solution:
Solution
Code
I can't prove my solution, so can you guys check this and prove it for me, or is this solution wrong?
Thank you for reading this blog.
Auto comment: topic has been updated by i_love_huyhau6a2 (previous revision, new revision, compare).
orz danghuyhau
Oh wow
orz danghuyhau
Orz danghuyhau
danghuyhau orz
as his friend, i_love_huyhau6a2 OTL
as a penguin, i_love_huyhau6a2 orz
as his friend, i_love_huyhau6a2 orz
orz danghuyhau
How does the energy not decrease at all when you do this. This is the second subtasks solution so how does it work for full points?
I don't know but somehow it worked.
After I got accepted, I used the grader to check my code, but somehow it worked perfectly (random tests).
wtf you are right I just coded it and it got the 100 with 13 lines of code
Your solution are actually correct.
Because when you rotate $$$v_{\lfloor\frac n2\rfloor}$$$ to be perpendicular to $$$v_0$$$, consider the acute angle between them. There are at least $$$\lfloor\frac n2\rfloor-1$$$ lines in this angle (specifically, $$$v_1,v_2,\ldots,v_{\lfloor\frac n2\rfloor-1}$$$ or $$$v_{\lfloor\frac n2\rfloor+1},v_{\lfloor\frac n2\rfloor+2},\ldots,v_{n-1}$$$). Obviously they, as well as $$$v_0$$$, will be always getting further from $$$v_{\lfloor\frac n2\rfloor}$$$ during the first rotation. That are at least $$$\lfloor\frac n2\rfloor$$$ lines, so the efficiency always increases during the first rotation.
Now $$$v_0$$$ and $$$v_{\lfloor\frac n2\rfloor}$$$ are already perpendicular. Obviously, the sum of distance to the two lines of any other line is $$$25000$$$, which is a constant. So we can just "delete" the two lines, remaining a subproblem of $$$n-2$$$ lines.
By induction, the correctness of the solution can be shown.
Thank you, it's really surprising that this problem has a very simple solution.
orz danghuyhau
Before the model solution was released, I thought that this was actually the intended solution. I was shocked when I saw that the model solution was much more complicated!
Where can i find the model solution?
It's in the GitHub repo: https://github.com/apio2025/apio2025_tasks/tree/main/rotate/solutions/model_solution
And any code will get to 74 points, even local search. Maybe this was intended to be an easy problems, but somehow 90% of people haven't got a single idea on this problem.
Can't really blame them, it's geometry + constructive (the two things people hate most). Personally, one of my friends (who's pretty good at math olympiads) didn't even try it during contest, and then solved in 20 minutes afterwards. So, yeah. I think people just got intimidated by the problem.
Personally: I got a 54 (yeah I am cursing myself afterwards), after using ternary search and some optimizations (I didn't local search, my method was just "take the thing which increase you efficiency most at the current moment").