Thursday, February 1, 2018

USACO - Combination Lock

After you read the problem statement you must have some insights about the solution (brute force over all possible settings, mark them and finally count them to print the answer).
We have to brute force over all possible settings that open the combination, the tricky case is where one setting opens both combinations, you must not count this twice, I used a set data structure to mark good settings (a setting that opens at least one of the combinations).

Now you have to decide how you want to do the brute force? Since I like recursions I did it using a simple recursive function.
A recursive functions consists of repetitive work on some state :

In my recursive function "markThem", I work on x[ idx ] and call the same method to work on x[idx + 1]. What must happen to x[ idx ]? It can have any value in range [x[idx]-2, x[idx]+2], so there are 5 possible values for x[idx], at each step (in for loop) I assign a value from that range to x[idx] and call markThem with argument idx+1.
What is the stop condition? When idx equals 3, then we have changed values of x[0], x[1] and x[2] and we have a possible settings and we must mark that.

Finally in main function I print size of the set data structure as the answer.

No comments:

Post a Comment