MCO16301 - Editorial

Author: Zi Song Yeoh

CAKEWALK

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.

RELATED PROBLEMS:

1 Like

I was just looking to try my hand at this problem but that practice link (for all the problems) doesn’t seem to work!

It just says : “Problem is not visible now. Please try again later.”

//