Anti Brute Force Lock
Author: Suhendry Effendy
Let G be a (complete) graph representation of all keys where the cost of edge (u,v) denotes the minimum number of rolls needed to change from key u to key v. Finding the minimum cost to unlock all keys is equal to finding the cost of minimum spanning tree of G (try to review the behaviour of Prim’s Algorithm).
The minimum rolls that is needed to change digits [a1 a2 a3 a4] into [b1 b2 b3 b4] can be calculated by a simple formula:
note: use only positive result for each modulo operation.
The MST of G can be calculated either using Prim or Kruskal. The initial digits  is not a key (unless it’s stated otherwise in the input data), so we shouldn’t include  in our graph. To connect  with G, we only need to find one nearest key from .
Several teams misunderstood the problem as they thought the keys should be unlocked in input order while the problem has stated clearly that keys can be unlocked in any order (I think they just missed that part).
This problem was solved by 17 teams. The first team to solve this problem: Joy (minute 30).
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament