JOIN
 Match Editorials
TCHS SRM 3
Monday, June 19, 2006

Match summary

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

BestSeller
Used as: Level One:
 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;
}
```

KidsWordGame
Used as: Level Two:
 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;
}
```
Now we can write the solution itself:
```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.

BestDecomposition
Used as: Level Three:
 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 f1, f2, ..., fm, 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 fi = a and j = b. Then:
ab <= ((a + b) / 2)2
ab <= (a2 + 2ab + b2) / 4
4ab <= a2 + 2ab + b2
0 <= a2 - 2ab + b2
0 <= (a - b)2
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;
}
};
```

By gevak
TopCoder Member