PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
BRUTE FORCE
PROBLEM:
Find all possible reachable scores in a contest with subtasks.
EXPLANATION:
This is mainly an implementation problem. The first subtask is solvable with O(n^2) brute force while the second subtask can be solved with bitmasks.
To solve the full problem, one way is to iterate through all integers from 0 to P - 1, where P is the product of all x_{i}. Then, we can repeated take P modulo x_{i} and divide it by x_{i} to generate all n-tuples (a_{1}, a_{2}, ..., a_{n}) with 0 \le a_{i} \le x_{i} - 1. Then, for each possibility, store the final score into a set and output the results.
Time Complexity : O(x_{1}x_{2}...x_{n}).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.