ICPC Team Strategy
Co-author: Andoko Chandra, Andrian Kurniady, Evan Leonardi, Suhendry Effendy.
There are several ways to solve this problem.
This was the first approach which came to my mind after I read the problem. I’m sure if you’re fond with DP then the recurrence structure for this problem is not hard to find. Define a state in dynamic programming as f(k,S,T): the maximum number of problem that can be solved, where k is the last student who solved a problem, S is the set of solved problems, and T is the current time. Just try all the remaining students and problems combination.
k = last person who solved a problem.
S = set of solved problems.
T = current time.
i = next person to solve problem.
j = next problem to be solved.
tij = time required by i to solve problem j.
To implement set S, you will need bitmask operation (using set stl/library will not pass the time-limit). The maximum size of S is 12, so the number of distict set S is not more than 212. The overall time-complexity is O(2N . P2 . T . N), where N is the number of problems, T is the contest time (280), and P is the number of student (3).
Kurniady suggested to process each state in ascending order of T (using priority queue) and flag on [k, S]. Actually, it is Dijkstra’s Algorithm with [k, S] as nodes in the graph.
Brute Force (?)
There are 4 possibilities for each problem:
– Solved by Andi.
– Solved by Budi.
– Solved by Chandra.
– The problem is not solved by the team.
So, the idea is to brute force all of this possibilities (there are 4N combinations) and find one which give the best result. For each combination we should check whether the combination is feasible, i.e. they can solve the problems so that no student solve two problems consecutively. This can be done by checking if there is a student who solve more than half of the problems (round up). If yes, then the combination is not feasible.
The overall time-complexity is O(4N . N). I have not yet verified this approach yet as I realized there is a brute force solution after the contest. Will it pass the time-limit?
New update. I have just tested the brute force solution and it did not pass the time-limit.
If you have noticed the number of author of this problem, then maybe you will ask “why did you need so many authors just to prepare an easy problem?”. There’s a story behind this :))
This problem was solved by 8 teams. The first team to solve this problem is Joy (58).
- 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