USACO(JAVA) : Algorithms Complete Search

Question

So here is the link to problem statement : http://train.usaco.org/usacoprob2?a=ZSMwtXwq7ro&S=comboProblem Statement.

EDIT 1: So the problem is this : There is a lock and there are 2 valid 3 digit combinations for the lock. One which is set by the user and other one is the master key set by the manufacturer. Also the lock has certain tolerance for errors, ie it will open even if the numbers on the dials are each within at most 2 positions of a valid combination.

For example , suppose user set key was 1, 2, 3 and the master key (manufacturer set) was 4, 5, 6. For these 2 keys 1, 3, 5 is a valid key since the difference between each digit(at same position) of this key and user set key is atmost 2 . But 1, 5, 6 is an invalid combo because the difference between digits of this key and user set key > 2 and same for master key.

Basically what I am doing is pretty naive, I am generating all possible lock combinations and checking for validity of each combination. Here is my code

import java.util.*;
public class combo {
    public static void main(String[] args){
        Scanner myScanner = new Scanner(System.in);
        int N = myScanner.nextInt();
        int[] keys = new int[3];
        int[] masterKeys = new int[3];
        for(int i = 0; i < 3; i++){
            keys[i] = myScanner.nextInt();
        }
        for(int i = 0; i < 3; i++){
            masterKeys[i] = myScanner.nextInt();
        }
        int cnt = 0;
        int[] combo = new int[3];
        for(int i = 1; i <= N; i++){
            combo[0] = i;
            for(int j = 1; j <= N; j++){
                combo[1] = j;
                for(int k = 1; k <=N; k++){
                    combo[2] = k;
                    if(validCombo(combo, keys, masterKeys)){
                        cnt += 1;
                    }
                }
            }
        }
        System.out.println(cnt);
    }
// bug here
/*
Valid
combo : 1, 3, 5
key :  1, 2, 3
master 4, 5, 6

Invalid
1 5 6
 */
    public static boolean validCombo(int[] combo, int[] keys, int[] masterKeys){
        boolean checkKeys = true;
        boolean checkMasterKeys = true;
        for(int i = 0; i < 3; i++){
            if(Math.abs((int)(combo[i]-keys[i])) > 2){
                checkKeys = false;
            }
            if(Math.abs((int)(combo[i]-masterKeys[i])) > 2){
                checkMasterKeys = false;
            }
        }
        return checkKeys | checkMasterKeys;
    }
}

So for inputs N = 50 , keys = 1, 2, 3 and masterKeys = 5, 6,7 , I get output 184 but the correct output is 249 (sample given test case). Can anyone please just give me a hint as to what is wrong with my logic

Answer 1

Instead of "trying" all combinations you could compute them

1. compute the number of overlapping numbers per dial
   
   if distance between the key number and the master key number
   is >= 5 --> you have 10 distinct values
is < 5 --> you have (5 - distance) overlapping numbers
   examples:
   key: 3 master key: 8 distinct numbers: 10 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
key: 3 master key: 6 distinct numbers: 8 = 1, 2, 3, 4, 5, 6, 7, 8 4 and 5 are the overlapping numbers for this dial

2. if at least for one dial there is no overlapping number then we have the maximum of 250 combinations

3. if all dials have at least one overlapping number we can compute the
   number of overlapping combinations by multiplying the overlapping numbers
   of all dials
4. unique combinations can be computed as max. number - overlapping combinations

example: key: 3, 4, 5 master key: 7, 8, 9

 1  2  3 -+
 2  3  4  |
 3  4  5  |<-- the combinations close to the key
 4  5  6  |
 5  6  7 -+<-- the only overlapping number
 6  7  8  |
 7  8  9  |<-- the combinations close to the master key
 9 10 11  |
10 11 12 -+

There are 249 valid combinations.

Here a short snippet for the computation.

int numbersPerDail = 50;
int dials = 3;
int[] keys = {2, 2, 3};
int[] masterKeys = {48, 5, 6};

int[] overlappingNumbers = new int[dials];
for (int i = 0; i < dials; i++) {
    int distance = Math.max(keys[i], masterKeys[i]) - Math.min(keys[i], masterKeys[i]);
    if (distance >= 46) { // the dial is circular 
        distance = numbersPerDail - distance;
    }
    overlappingNumbers[i] = 5 - distance;
}

int doubleCombos = 0;
if (overlappingNumbers[0] > 0 && overlappingNumbers[1] > 0 && overlappingNumbers[2] > 0) {
    doubleCombos = overlappingNumbers[0] * overlappingNumbers[1] * overlappingNumbers[2];
}
System.out.println("valid combinations = " + (250 - doubleCombos));

Answer 2

You aren't taking into account the fact that the numbers wrap around - i.e., when N = 50, then 50 is 1 away from 1, 2 away from 2, etc.

When trying to debug something like this, it might help if you printed out exactly what your program was counting as solutions, and then comparing to the output listed on the problem site, if they give you such details, or just using the extra information to validate your own thought process.