Thursday, March 22, 2007 Match summary
In one of the final warmups before TCO qualifications, 1127 competitors showed up to battle it out in SRM 343. In Division 1, competitors were greeted with a reasonable easy problem. JongMan was the first to submit, followed shortly thereafter by Petr and Burunduk3. Shortly thereafter, the points began to fly.
The ProblemsPersistentNumberUsed as: Division Two  Level One:
The persistence of a number was first defined by Neil Sloane in 1973. It turns out that there is no number less than 10^{3000} with a persistence greater than 11 (in fact, it's postulated that there is no number with persistence greater than 11), and a maximum persistence of 9 within the constraints of this problem. Thus, to calculate the persistence, we can simply calculate the product of digits until we get a single digit number, with no fear of timeout. Java code follows: public int getPersistence(int n) { int ret = 0; while(n > 9) { ret++; int temp = 1; while(n > 0) { temp *= n%10; n/=10; } n = temp; } return ret; }CDPlayer Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem was inspired by the CD player in my car, which seems to have an algorithm similar to that described in the problem statement. In order to check whether the CD player uses the algorithm, we can simply check all possible starting points. For each starting point j (with c songs on the CD), we check that two conditions: the first j letters contain no repeats, and that all substrings starting at j+i*c (where i=0,1,2...) contain no repeats. Within the constraints, it is easily possible to try all values of j between 0 and c1, inclusive. If any work, we return it right away; otherwise, we return 1. Java code follows: public int isRandom(String[] songlist, int n) { String s = ""; for(int i=0; i < songlist.length; i++) s += songlist[i]; int i = 0; for(i=0; i < n; i++) { boolean[] used = new boolean[n]; int j; for(j=0; j < i; j++) { if(used[s.charAt(j)'A']) break; used[s.charAt(j)'A'] = true; } //System.out.println(i + " " + j); if(j < i) continue; for(; j < s.length(); j++) { if(j%n == i) used = new boolean[n]; if(used[s.charAt(j)'A']) break; used[s.charAt(j)'A'] = true; } if(j < s.length()) continue; return i; } return 1; }Mafia Used as: Division Two  Level Three:
The game of Mafia is a fun party game played regularly among my group of friends. Often times, players will have predetermined biases of guilt prior to the start of the game, and this problem was an attempt to model this. The constraints indicate that the problem can be solved through dynamic programming, storing whether players are still in the game ("alive"), or removed from the game ("dead"). Unfortunately, the way in which the game is played prevents this from working; a death during the night changes the state differently than a death during the day, which means that simply keeping track of who is alive is insufficient.
int N, me; int[] curguilt; int[] best; int[] status; int[][] reactions; int[] curkills; int bestlength; int maxf; boolean flag; public int daykill() { int kill = 0; while(status[kill] > 0) kill++; for(int i=0; i<N; i++) if(status[i] ==0 && curguilt[i] > curguilt[kill]) kill = i; return kill; } public int doit(int cur) { if(cur > bestlength) // Save the best depth reached { best = curkills.clone(); bestlength = cur; if(bestlength==maxf) flag = true; // if the Mafia win, stop caring } if(status[me] > 0) return 0; for(int i=0; i<N; i++) { if(i==me  status[i] > 0) continue; status[i] = 2; curkills[cur] = i; for(int j=0; j<N; j++) curguilt[j] += reactions[i][j]; int daydie = daykill(); status[daydie] = 1; doit(cur+1); if(flag) return 0; for(int j=0; j<N; j++) curguilt[j] = reactions[i][j]; status[daydie] = 0; status[i] = 0; } return 0; } public int play(int [] guilt, String[] responses, int n) { N = guilt.length; maxf = N / 2; // the maximum number of nights me = n; curguilt = guilt.clone(); status = new int[N]; reactions = new int[N][N]; for(int i=0; i < N; i++) for(int j=0; j < N; j++) reactions[i][j] = responses[i].charAt(j) > 'Z' ? 1*(responses[i].charAt(j) 'a' + 1) : responses[i].charAt(j)  'A'+1; best = new int[N]; curkills = new int[N]; bestlength = 0; if(N%2 == 1) status[daykill()] = 1; flag = false; doit(0); for(int i=0; i < best.length; i++) // print out the System.out.println(best[i]); // optimal removals return bestlength; }MoneyGame Used as: Division One  Level Two:
This is a game that was introduced to me by a friend, using pennies, nickels, and dimes. Due to the fact that you lose money every turn (since you take back less money than you put in), the game must eventually terminate, and one player will win. The decision of what coins to retrieve does not seem to follow an empirical formula, and so it is best to try making all possible moves. As the goal of the game is to maximize the money Lenny wins (and thus minimize Fred's winnings), this falls into the category of a minimax search. When it is Lenny's turn, we try all possibilities, and store the best possible score that Lenny will make. On the other hand, Fred will try all possibilities, attempting to minimize Lenny's score.
Used as: Division One  Level Three:
Refactorable numbers, originally discovered by Cooper and Kennedy in 1990 under the name of "Tau numbers", were among the first sequences (re)discovered by a computer (by Colton). This problem turned out to be far easier than it had been thought during testing, as many competitors (including ACRush) proved with their high submission rate. The strategy involves using a number sieve to count the factors of each number, similar to the Sieve of Eratosthenes. We create an array called tau, where tau[n] stands for the number of divisors of n. We then go from 1 to n, and for each number, increment the count of all multiples of that number. Once this is done, we can simply loop through all of the numbers from low to high, and pick up any values that were missed. The solution by ACRushserves to run very quickly, and is sufficient for the constraints. Similarly, one can use the strategy employed by Petr. Using some basic information on prime numbers, he calculates the number of factors based on the prime factorization. A modification to his solution can count all refactorable numbers under 10 million in 1 second.

