Match Editorial

In Division 1, after some time spent working on the easy problem, most coders divided into two distinct groups. The first group opened the medium problem (600 points) next, while the second went for the hard (800 points). At first glance the second group seemed to have the better approach, but many of the hard problem solutions turned out to be wrong. bladerunner took the 1st place with the help of 7 successful challenges, lovro was 2nd and Savior finished in 3rd. sabbir_yousuf became yellow by taking the 4th place. Interestingly, dexter_bg gained 297 rating points without passing any problems.

In Division 2, the top performer was Protean, followed by crem and xaep. More than 70 coders finished with all three problems correct.

The Problems

Value	250
Submission Rate	278 / 308 (90.26%)
Success Rate	264 / 278 (94.96%)
High Score	DamnEcuadorian for 249.50 points (1 mins 17 secs)
Average Score	215.27 (for 264 correct submissions)

We can convert all elements of the given string array to integers and put them into some numerical array. After that we can sort new numerical array in a usual way and convert its back to the string array.

   int[] tmp = new int[sequence.length];
   for(int i = 0; i < sequence.length; i++)
      tmp[i] = Integer.parseInt(sequence[i]);
   Arrays.sort(ret);
   for(int i = 0; i < sequence.length; i++)
      sequence[i]=""+tmp[i];

Another way to solve this problem is to use a sort function which receives a comparing function (called 'comparator') as an argument.

   Arrays.sort(sequence,
          new Comparator<String>() {
             public int compare(String a, String b) {
               return new Integer(a).compareTo(new Integer(b));
             }
           });

Value	500
Submission Rate	264 / 308 (85.71%)
Success Rate	246 / 264 (93.18%)
High Score	agray for 488.25 points (4 mins 25 secs)
Average Score	389.23 (for 246 correct submissions)

Value	250
Submission Rate	242 / 246 (98.37%)
Success Rate	236 / 242 (97.52%)
High Score	antimatter for 249.20 points (1 mins 36 secs)
Average Score	228.72 (for 236 correct submissions)

First, we can count how many times each word appears in the player lists. This information can be stored in associative array (like hash map). After that we can iterate over the words of each player and calculate his score. Here is antimatter C++ solution who have made this problem in 1.5 minutes.

   string score(vector <string> a, vector <string> b, vector <string> c) {
      map<string,int> C;
      for (int i = 0; i < a.si; i++) C[a[i]]++;
      for (int i = 0; i < b.si; i++) C[b[i]]++;
      for (int i = 0; i < c.si; i++) C[c[i]]++;
      int AA=0,BB=0,CC=0;
      for (int i = 0; i < a.si; i++) AA += 4-C[a[i]];
      for (int i = 0; i < b.si; i++) BB += 4-C[b[i]];
      for (int i = 0; i < c.si; i++) CC += 4-C[c[i]];
      char buf[100];
      sprintf(buf, "%d/%d/%d", AA,BB,CC);
      return string(buf);
   }

Value	1000
Submission Rate	155 / 308 (50.32%)
Success Rate	75 / 155 (48.39%)
High Score	xaep for 854.77 points (12 mins 8 secs)
Average Score	545.36 (for 75 correct submissions)

The example 2 hints how to solve this problem. Function F(N) can take a very few values within the problem limitations. So the sequence X will be repeated in first 10-25 elements and we can find its period. If we know that sequence X has a period of length L starting from the index i (i > K) the X_K will be the same as the element with the index (K-i) mod L + i. Here is a sample Java code.

   Map<Integer, Integer> seen = new HashMap();
   List<Integer> sequence = new ArrayList<Integer>();
   int X = 0;
   for (int i = 0;; i++) {
      if (seen.containsKey(X)) {
         if (i > K) 
            return sequence.get(K);
         int L = i - seen.get(X);
         int ind = seen.get(X);
         return sequence.get(ind + (K-ind) % L);
      }
      seen.put(X,i);
      sequence.add(X);
      X = A*F(X)+B;
   }

Value	600
Submission Rate	59 / 246 (23.98%)
Success Rate	46 / 59 (77.97%)
High Score	loopy for 507.11 points (12 mins 38 secs)
Average Score	314.39 (for 46 correct submissions)

It is quite easy to write solution that iterates from 1 to N-1 and checks each number if it is a valid PLU code. This solution works much slower than required 2 seconds, but it is acceptable to generate all answers and hardcode each 100000th answer into array inside a solution source. After that we can start counting invalid PLU codes not from 1 but form the index that closer to N.

Another (more honest) way to solve this problem is a dynamic programming. Let function A[d1,d2,L,N] be a number of invalid PLU codes of length L that less or equal N. Moreover this function allows PLU code to start from the '0' digit and considers PLU codes started from d2 as invalid if d1=d2. Let n0 be a first digit of N and N1 be a number N without a first digit.

Now A[d1,d2,L,N] can be calculated using following algorithm (pseudocode):

A[d1,d2,L,N] = 0;
for(char ch='0'; ch<n0; ch++)
   A[d1,d2,L,N] += (d1==d2 && d2==ch) ? 10L-1 : A[d2,ch,L-1,10L-1-1];
A[d1,d2,L,N] += (d1==d2 && d2==n0) ? N1+1 : A[d2,n0,L-1,N1];

Using this folmula it is clear how to solve the task.

Value	800
Submission Rate	125 / 246 (50.81%)
Success Rate	10 / 125 (8.00%)
High Score	Savior for 738.94 points (8 mins 18 secs)
Average Score	625.64 (for 10 correct submissions)

How are the odd-digitable numbers produced? There are five one-digit odd-digitable numbers. To produce the odd-digitable number of length L (L > 1) we should get the odd-digitable number of length L-1, multiply it by 10 and add one of the one-digit odd-digitable numbers.

Let put all one-digit odd-digitable numbers into the queue, then put all odd-digitable numbers produced from 1, all odd-digitable numbers produced from 3 and so on. This way we'll get all odd-digitable numbers in the increasing order. Finally, take all numbers in the queue modulo N.

There are no sense to put duplicates into the queue because they will generate the same numbers, so we'll skip produced numbers which are already in the queue. Here is the sample Java code.

   List<Integer> al = new ArrayList(); 
   List<String> as = new ArrayList();
   boolean[] mark = new boolean[N];
   al.add(0); 
   as.add(""); 
   for (int i = 0; i < al.size(); i++) {
      int c = al.get(i);
      if (c == M && i > 0) return as.get(i);
      for (int j = 1; j <= 9; j+=2) {
         int x = (c*10+j)%N;
         if (mark[x]) continue;
         mark[(c*10+j)%N] = true;
         al.add(x);
         as.add(as.get(i)+j);
      }
   } 
   return "-1";