Team Unagi's repository for ICFPC 2021
- Takuya Akiba
- Kentaro Imajo
- Hiroaki Iwami
- Yoichi Iwata
- Toshiki Kataoka
- Naohiro Takahashi
We thoroughly used Rust for writing solvers and common logics. We also used Go, JavaScript, TypeScript and Python for utilities.
For some problems, we can achieve zero dislike. Due to the scoring rule, it is very important to achieve zero dislike for these problems. So, we developed approaches to exactly solve these problems.
One approach is to use back-tracking search with pruning (src/bin/{zenkan.rs, zenkan2.rs. ...}). We placed vertices one by one, and pruned by using metrics such as distances.
The other approach is to conduct manual work. We developed GUI (gui/...) and spent plenty of time to search solutions by hand.
For other problems, we mainly used heuristic solvers based on simulated annealing (src/bin/chokudai.rs).
It searches better solutions by repeatedly perturbate some points.
We used the partial solutions generated by back-tracking as the initial solutions.
Another approach is to use SAT solvers (src/bin/sat_hillclimber.rs).
We translated a problem to improve the score while satisfying constraint into a SAT instance.
We improved scores by repeatedly solving SAT instances by using state-of-the-art SAT solver glucose.
This approach was generally used to improve solutions generated by simulated annealing.
We also used this SAT approach to complete the hand-crafted partial solutions to satisfy constraints (src/bin/sat_calibrator.rs).