Get Time
statistics_w  Match Editorial
SRM 343
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.

As several competitors began working on the medium problem, a few brave souls jumped ahead to the 1000 point problem, and discovered a very simple solution that had been overlooked during testing. As a result, many competitors quickly submitted this problem for very high point values, allowing Parchandri and HardCoder to temporarily take the lead. As more people realized this, many competitors went after the hard next, followed by the medium. At the end of the coding phase, ACRush held a strong lead behind a very fast 1000 point problem. Close behind was a large pack within striking distance. The challenge phase was eventful, with ACRush picking up four successful challenges, and Petr and gawry picking up two each. As the dust cleared from system tests, ACRush emerged unscathed as the leader, with Petr, gawry and Revenger rounding out the top four.

The problem set for Division 2 turned out to be a bit more standard. The 250 and 500 gave coders plenty of opportunity to score quick points before running into a difficult 1000 point problem. At the end of the coding phase, cryonox held the lead, followed by johngull, Ivanidze and exod40. The challenge phase turned out interesting, especially for cryonox, whose random Mafia solution survived three successful challenges before finally being taken down. After system tests had finished, johngull emerged with his first SRM win, followed by Sema, and MGLC as the only three competitors to finish all three problems successfully.

The Problems

PersistentNumber rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 535 / 561 (95.37%)
Success Rate 448 / 535 (83.74%)
High Score notme for 249.45 points (1 mins 20 secs)
Average Score 212.43 (for 448 correct submissions)

The persistence of a number was first defined by Neil Sloane in 1973. It turns out that there is no number less than 103000 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 = temp;
 return ret;

CDPlayer rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 307 / 561 (54.72%)
Success Rate 140 / 307 (45.60%)
High Score LiYongchuan for 489.59 points (4 mins 9 secs)
Average Score 293.64 (for 140 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 442 / 458 (96.51%)
Success Rate 326 / 442 (73.76%)
High Score JongMan for 246.29 points (3 mins 29 secs)
Average Score 198.07 (for 326 correct submissions)

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 c-1, 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 rate it discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 54 / 561 (9.63%)
Success Rate 7 / 54 (12.96%)
High Score MGLC for 597.10 points (27 mins 37 secs)
Average Score 504.52 (for 7 correct submissions)

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.

It turns out that there is a much simpler solution. Due to the alternating day/night rules, the Mafia will (in the worst case with 16 players) have to select a player to remove at most 8 times. Since the Mafia would never kill him or herself, this means that there are only 15!! = 2,027,025 possible states, which can be brute forced with care. Each night, the Mafia tries to remove each person that is still alive, and we keep track of the maximum depth that can be reached from removing that person. The maximum of these values is what we return. If running into issues on time, optimizations can be included to return if at any point the Mafia wins the game, since there cannot be any other nights. Java code (which also prints out an optimal order in which to remove players in the night) follows:

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;
  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;

 for(int i=0; i < best.length; i++) // print out the 
  System.out.println(best[i]);      // optimal removals

 return bestlength;

MoneyGame rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 146 / 458 (31.88%)
Success Rate 100 / 146 (68.49%)
High Score ACRush for 425.33 points (12 mins 21 secs)
Average Score 273.41 (for 100 correct submissions)

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.

To efficiently code this, memorization is important; if we've already considered a game state, we don't want to have to recompute all of its children. Since a player can hold at most 10 coins at any time (each player starts with 5), we can represent the gamestate for a player using a integer between 0 and 11^3, as nika's solution shows. Alternatively, we can have a 6-dimensional memoization table, like ACRush used. Furthermore, each player wants to maximize his own score; thus, we can simply swap Lenny's and Fred's coins after each play, and play to maximize Lenny's score (rather than writing two separate functions, one for Lenny and one for Fred). See ACRush's solution for a very clear implementation of this.

RefactorableNumber rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 222 / 458 (48.47%)
Success Rate 184 / 222 (82.88%)
High Score ACRush for 995.17 points (1 mins 59 secs)
Average Score 772.19 (for 184 correct submissions)

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.

By connect4
TopCoder Member