Skip to content

Latest commit

 

History

History
45 lines (27 loc) · 1.61 KB

README.md

File metadata and controls

45 lines (27 loc) · 1.61 KB
Raw

Team Unagi

Team Unagi's repository for ICFPC 2021

Members

  • Takuya Akiba
  • Kentaro Imajo
  • Hiroaki Iwami
  • Yoichi Iwata
  • Toshiki Kataoka
  • Naohiro Takahashi

Programming Language

We thoroughly used Rust for writing solvers and common logics. We also used Go, JavaScript, TypeScript and Python for utilities.

Approaches

Exact Approaches

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.

Heuristic Approaches

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).