Match Editorials

The 1,000-point problem turned out to be easy in this match, with 40 coders successfully solving it. Weiqi took the lead after the coding phase but, thanks to two +75s in challenge phase, Burunduk1 got up to the first place and won his third HS SRM in a row. Weiqi finished second, third place went to Loner, and fourth and fifth went to newcomers rlp and ilyakor respectively.

The Problems

Value	250
Submission Rate	110 / 123 (89.43%)
Success Rate	98 / 110 (89.09%)
High Score	Zuza for 249.38 points (1 mins 25 secs)
Average Score	221.30 (for 98 correct submissions)

This problem asked for a value that occurs most times in the given array. Constraints were so low that it was not neccessary to use any sophisticated data structure; you could just iterate values and, for each value, count the amount of times it occurs in the array, then choose the best according to the criteria described in the problem. Java code follows:

public String findBestSeller(String[] items) {
   int n, i, j, best, cur;
   String ret;
   n = items.length;
   best = -1;
   ret = "";
   for (i = 0; i < n; i++) {
      cur = 0;
      for (j = 0; j < n; j++) if (items[j].compareTo(items[i]) == 0) cur++;
      if (cur > best || (cur == best && items[i].compareTo(ret) < 0)) {
         best = cur;
         ret = items[i];
      }
   }
   return ret;
}

Value	450
Submission Rate	90 / 123 (73.17%)
Success Rate	63 / 90 (70.00%)
High Score	MB__ for 426.66 points (6 mins 43 secs)
Average Score	320.85 (for 63 correct submissions)

First of all let's write a function which will be able to say whether the word b might be obtained from word a without violating the rules (i.e. without cheating). Java code of this function follows:

boolean ok(String a, String b) {
   if (b.length() == a.length() + 1 && b.indexOf(a) != -1) return true;
   else return false;
}

public int getCheater(String[] first, String[] second, String[] third) {
   int n, i, j;
   String s;
   s = first[0]; // The original word
   n = Math.max(first.length, Math.max(second.length, third.length));
   for (i = 0; i < n; i++) {
           if (i == first.length) break;
      // Notice that there is no previous move for the first move in the game
           if (i == 0 || ok(s, first[i])) s = first[i];
           else return 3;
           if (i == second.length) break;
           if (ok(s, second[i])) s = second[i];
           else return 1;
           if (i == third.length) break;
           if (ok(s, third[i])) s = third[i];
           else return 2;
   }
   return -1;
}

If some player saw a word that could not be obtained from the previous word, it would indicate that the previous palyer is a cheater.

Value	1000
Submission Rate	56 / 123 (45.53%)
Success Rate	40 / 56 (71.43%)
High Score	Weiqi for 992.28 points (2 mins 30 secs)
Average Score	723.05 (for 40 correct submissions)

Here you were asked to find such f₁, f₂, ..., f_m, that they sum up to n and their product is maximal. Let's forget that all f's must be integers. Suppose that they may be float, but don't forget that they must be non-negative. Now let me prove, that all f's must be equal in order to maximize their product. Let's take some two of these numbers, say f_i = a and _j = b. Then:
ab <= ((a + b) / 2)²
ab <= (a² + 2ab + b²) / 4
4ab <= a² + 2ab + b²
0 <= a² - 2ab + b²
0 <= (a - b)²
Now we know that all f's must be equal. Let's call it x. So we need to find this x. It's obvious that x > 1, and x < 5 (because we can decompose 5 to 2 + 3, so 2 * 3 = 6, which is more than 5 itself). More definitely x is even less than 4, beacuse 4 = 2 + 2, 2 * 2 = 4, which is not less than 4 itself. So, because 2 and 3 are the only integer numbers which satisfy condition 1 < x < 4, we can just check them both and find out, that 3 is better. Nice and fast C++ code of Weiqi follows (original code is a bit changed):

struct BestDecomposition {
   int maxProduct(int n) {
      int i, j, k;
      k = 1;
      while (n > 4)
      {
         k *= 3;
         k %= 10007;
         n -= 3;
      }
      k *= n;
      k %= 10007;
      return k;
   }
};