after about 6 months sway USACO, i decided to continue my USACO training page, and i have ben stuck in the problem "camelot" for a full day now!, here is the problem description : https://www.scribd.com/document/124295413/USACO-Training-Pages-Camelot my idea is calculating the minimum moves needed to gather at all the squares, but for the king that is hard, because we dont know when will the king get picked up.
can i have a small hint for this problem?
The idea here is to calculate knight distances from each square to every other square but adding a flag indicating whether the knight has the king or not. Then the cost of gathering at a certain location is the sum of distances for all knights to this location without the king expect for one knight, which should arrive with the king.
so this is assuming the king never moves on his own? so firstly we should calculate the minimum number of moves to get the king picked?
No, the king will move on his own to the pick-up place. If you are at a state i, j, 0 then you can move to state i, j, 1 by adding the steps the king needs in order to reach position [i, j] from his starting position.
edit: OK, i found out what i did wrong, as i suspected, its the priority_queue calling too much memory...
so i modify by doing dfs for every knight differently, and got AC with about 0.950 s
Bump:
I've now solved this problem but only with help from the idea behind the lovely solution at https://usacosolutions.wordpress.com/2012/10/20/usaco-3-3-camelot-camelot-c/, using the fact that in an optimal solution the king will move at most two places.
However, I don't fully understand either of these solutions; what's a 'flag' in tenshi_kanade's idea, and how does it move between states (what is being iterated over when?), and can someone prove rather than just give some intiution behind why the king moves at most twice in optimal solutions.
I don't think it's true that the king moves at most twice. For the solution you linked, Brian Zhang noted that it gives the wrong answer for the following two test cases:
The outputs are 6 and 26, but the correct answers are 5 and 21.
Link to my solution
I Can't believe that you are discussing USACO problems on codeforces! What a traitor!
what do you mean?
I was joking xD