infinitone
BAN USERMy first thought of a solution was to use a graph of all the possible solutions and then simply to do BFS distance on the final score node. I think this is the best solution from a optimal perspective as it can achieve linear time. However, it does take quite a bit of code.
You can always do a recursive solution but this isn't efficient, heres my go. Note: I count a tie breaker as a leader change.
public static int getMax(int s1, int s2, int[] plays, int c) {
if (s1 == 0 && s2 == 0) return c;
int max = -1;
for (int i=0; i<plays.length; i++) {
for (int j=0; j<plays.length; j++) {
int s1_play = s1 - plays[i];
int s2_play = s2 - plays[j];
if ((s1_play < 0 || s2_play < 0) || (plays[i] == 0 && plays[j] == 0)) continue;
if ((s1 > s2) && (s2_play >= s1_play)) {
c++;
System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+" "+c);
} else if ((s2 > s1) && (s1_play >= s2_play)) {
c++;
System.out.println(s1+":"+s2+"->"+s1_play+":"+s2_play+" "+c);
}
int x = getMax(s1_play, s2_play, plays, c);
if (x > max) {
max = x;
}
}
}
return max;
}
Oh yeah and for maximum changes on the example 10, 6 is 9 times for me.
- infinitone August 25, 2014