Match Editorial

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

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 10³⁰⁰⁰ 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;
}

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)

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;

}

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

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.

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.