We will hold UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323).
- Contest URL: https://atcoder.jp/contests/abc323
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231007T2100&p1=248
- Duration: 100 minutes
- Writer: nok0, math957963, kyopro_friends, evima
- Tester: cn449, physics0523
- Rated range: ~ 1999
- The point values: 100-200-250-425-450-525-650 We are looking forward to your participation!
Hope to solve problem A, B, C, D.
update in 2023-10-07 20:28 CST: I use just 27 minutes to solve them! What easy problems!
update in 2023-10-07 21:40 CST: Sadly, I almost solved problem F but I didn't, I almost!
Solved A-F in 70 minutes but started late ,so no positive delta for me.
Standard E + some case pondering in F.
Also there is no link to the discussion (this blog) on the AtCoder contest page, you might wanna look into that
How to solve G — Inversion of Tree?
Also, did anyone do it using Prufer code?
trash D. I TLE for 4 times.
trash F. I got WA on only one testcase!!!!
D isn't trash , don't call a problem trash just because you bricked in it
Don't use
#define int long long, or you'll get wrong answer on 11 testcases.not true , you can just stop doubling a size when it crosses 10^9
ngl, F is hot trash. Why does this problem exist? Just a lot of casework.
It's not that bad.
There are only 8 cases (which octant relative to the goal is the cargo?), most of which are similar to one another.
If you do some transformations, there is only 1 case.
I can't find Programming in middle of all this math..
It's all about modeling the task to not feel like hot trash. Honestly you wouldn't have had too many tricky cases if you had modeled it nicely.
It exists because it encourages contestants to figure out elegant ways to approach the problem that do NOT involve a lot of casework. If you were unable to do so, that's an issue with your skill and not on the problem design. The fact that it CAN be solved with heavy casework means weaker solutions can still AC with a higher penalty (coding time), which is an opportunity that is not often granted for problems beyond one's skill level.
Some tips: you can flip the axes and/or rotate them to reduce the number of possible scenarios, you can use recursion to break the journey into smaller pieces, you can use a min function to compare between multiple options (like whether to move the block horizontally first or vertically first). The only "tricky" case (which should be really apparent to most contestants, so it's not likely to be overlooked) is when you're on the same row/column as the block and want to move to the opposite side, but this can be handled by simply adding 2 to the step count.
i didn't ask for an editorial sir, I solved it but didn't enjoy it.
To be fair you could even just compress the search space and use dijkstra on it. The number of "important" coordinates are at most $$$(3\times 3)^2=81$$$, and that immediately leads to a shortest-path problem with $$$81^2=6561$$$ states. It kinda is sad that this solution is longer, though.
Could you please tell me more details about this solution?
For each point given in the input $$$(x_p,y_p)$$$, the "important" lines are $$$x=x_p$$$, $$$x=x_p \pm 1$$$, $$$y=y_p$$$, $$$y=y_p \pm 1$$$. So, there are three points $$$(X_A,Y_A)$$$, $$$(X_B,Y_B)$$$, $$$(X_C,Y_C)$$$, and thus at most $$$9$$$ "important" lines for $$$x$$$ and $$$y$$$. The "important" coordinates are the intersection of "important" lines, and thus there are at most $$$81$$$ of them. Now everything can be compressed into a weighted grid graph with at most $$$81$$$ vertices. It is not hard to prove that the shortest solution using this weighted grid graph is equal to the actual solution of the problem. For convenience, we will call the $$$x=x_p$$$ and $$$y=y_p$$$ lines "very important" lines, and their intersection "very important" vertices.
Now to the implementation details. Let us call $$$S=(v_t,v_c)$$$ the "state" we are in. $$$v_t$$$ is the vertex with Takahashi, $$$v_c$$$ is the vertex with cargo. On the weighted graph we have at most $$$4$$$ neighbors to any vertex. If the vertex we want to move Takahashi to is not $$$v_c$$$, just move Takahashi to the vertex. Otherwise, move both Takahashi and the cargo "two steps further" to that direction, so the cargo stays in a "very important" vertex.
The rest is just a tedious implementation of dijkstra. As there are at most $$$81^2=6561$$$ states, it can't take too long.