Some hints for solving this problem the way I was able to solve it, without greedy search

1. I used BFS search with heuristic (A* search). As a heuristic, I used the sum of the distances from the boxes to the nearest goals, taking into account that different boxes should be on different goals. It is better to distribute boxes among goals in some greedy way, so as not to spend a lot of time on this.
2. In the board states, DO NOT store the position of the player, store the places he can REACH. This will greatly reduce the number of states needed to be stored. You can store one board state in two 64-bit numbers as bit masks.
3. To find bad positions and stop further search on them, look for simple deadlocks (the box is in a corner and not on a target), dynamic deadlocks (the boxes block each other) and NOT COMPLEX corral deadlocks (the boxes are not on goals and block access to some board area, so they cannot be pushed out of there).
4. If you try to search for too complex corral deadlocks, the time spent on finding them will not be worth it. Try different settings of what difficulty of corral deadlocks to search for and when to stop the search. Store the found configurations of corral deadlocks (and the configurations in which no deadlock was found) in some sets so as not to determine them every time.
5. In addition to the forward search (pushing boxes from the starting positions to the goals), you can also use the backward search (pulling boxes from the goals to the starting positions) to reduce the depth of the search tree.
6. For the forward (backward) search, prevent situations when, for example, there are more (fewer) boxes near the wall than goals. This can greatly speed up the search for some boards.
7. To understand why your algorithm is working too long for a particular board, you can find and output long deadlock branches - a sequence of pushes/pulls in the search tree that starts from one of the board states that is in the found solution and that does not eventually lead to the solution. This way you can find bugs when the algorithm did not find one of the types of deadlocks and did not stop searching on them.

Good luck!

если второй пересыпает первому, то у первого должно быть больше, а не наоборот!

А если это a1 и b1, соответственно, то это и есть ответ! Потому что a1 и b1 это изначальные мерки, до пересыпаний, в задаче так описано

Edited by author 22.09.2024 01:35

Edited by author 22.09.2024 01:36

Edited by author 22.09.2024 01:36

Edited by author 22.09.2024 01:37

What could be the reason???

I think it sholud be said in statement that we do rounding to near number. I spent 20 minutes, understanding why my code doesn't work for sample test, but the mistake was here: floor(100*x)/100, because I thought we should round to bottom

Who can help me?
thanks.
Give me some tests.

Здравствуйте!
Не воспринимает компилятор директивы
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <tuple>
#include <string>

Ошибка:
fatal error: map: No such file or directory
    2 | #include <map>
      |          ^~~~~
compilation terminated.

-----------------------------------------------
В чём проблема?

How to prove that such constraints on bruteforce are working finely?

Edited by author 08.09.2024 07:01

You should check if the answer is >= 0 :)

I had this problems:
3
.##
###
##.
answer is 36.
If you have any problems write me john_chip<dog>mail.ru
You can write russian messages

b + 1
b+ 1

All you have to do to solve this problem is believe in yourself and your code.

when i sent my code on g++ i got RE1, then when i sent it on clang i got AC

E = 1e-11

i spent a lot of time on this task and i am very happy that i did it, i recommend that you also try to solve it yourself to improve your optimization skills

I devised that maybe I need to solve many systems of equations.

I know the solution if the system has odd equations, but how do I solve the one with even equations?

For example: solve for ai, with ki = initial cups at knight i, and F as the final cups to be achieved.

a1 + a2 + k2 = F
a2 + a3 + k3 = F
a3 + a4 + k4 = F
a4 + a1 + k1 = F

I cannot solve this, even if I could I couldn't image myself programmatically solve it.

If the solution is different, please give me some advise. Thanks!

can you help me with some tests? I tried every tests in the discussions and they're fine, I also try my own tests with big number too.

to clarify, my understanding is that, 0 <= F <= 1000 right?

so in my solution i use o(N^3) space and i got mle ( i expected that) but what makes me confused that people says they passed wih o(n^3) time i know there is a different between memory and time complexity but i have some doubts they may also used o(n^3) space too
so can someone tell me whether they added a new cases or whats is the problem?

O(n*m*k) solution is AC. Rating 731 is too big. Very simple geometry task