JOIN
 Match Editorials
TCHS SRM 23
Monday, December 11, 2006

## Match summary

In total, 188 members made 358 submissions for HS SRM 23. This set of problems turned out to be rather difficult. While more than 70 competitors submitted all three problems, only 11 of them successfully solved all three, and 43 members didn't solve any of the problems. MB__ earned 225 points during the challenge phase, which put him over the top and won him the match with 1639.81 points. TICKET_112022 took second place with 1556.68 points, and Stray was third with 1509.76 points.

# The Problems

GoodExhibition
Used as: Division One - Level One:
 Value 250 Submission Rate 154 / 176 (87.50%) Success Rate 143 / 154 (92.86%) High Score tomekkulczynski for 249.21 points (1 mins 36 secs) Average Score 216.40 (for 143 correct submissions)

To solve this problem, competitors needed to perform the required operations in the most naive way. The shortest way to solve it was to use HashMap<String, Integer>.

```public int numberOfPictures(String[] labels, int K) {
int ans = 0;
HashMap<String, Integer> NUM = new HashMap<String, Integer>();
for (String s : labels) {
int now = 0;
if (NUM.containsKey(s)) now = NUM.get(s);
NUM.put(s, now + 1);
}
for (Integer x : NUM.values()) {
ans += Math.min(x, K - 1);
}
return ans;
}
```

Apportionment
Used as: Division One - Level Two:
 Value 500 Submission Rate 99 / 176 (56.25%) Success Rate 54 / 99 (54.55%) High Score tomekkulczynski for 487.40 points (4 mins 35 secs) Average Score 341.94 (for 54 correct submissions)

This problem is fairly simple. Let's assume that a side of the original square is (N * M) units in length. If so, the sides of the required squares must be divisible by N and by M. There are exactly (N - i + 1) * (M - i * M / N + 1) different squares with i * M side length. Looking over all the possible side lengths, we can calculate result as a sum of those products.
Code follows:

```public long numberOfSquares(int N, int M) {
long ans = 1;
for (long i = 1; i < N; i++) {
if (i * M % N == 0) {
ans += (long)(N - i + 1) * (long)(M - i * M / N + 1);
}
}
return ans;
}
```

Collector
Used as: Division One - Level Three:
 Value 1000 Submission Rate 103 / 176 (58.52%) Success Rate 13 / 103 (12.62%) High Score otinn for 901.57 points (9 mins 36 secs) Average Score 650.60 (for 13 correct submissions)

There were a large number of challenges on this problem. Most contestants supposed that the answer would be -1 if the value of one coin is divisible by the value of another coin. But this hypothesis is wrong, and test {3, 5, 8} shows it.

Let sum be the sum of all elements in coins. Actually, result will be -1 if and only if there is more than one way for the cash machine to return sum. If there is exactly one way, then the result will be sum (because cash mashine will give each coin once). Now we need to calculate the number of ways to present sum. It is a Dynamic Programming problem. num[j] is the number of ways to present j using some set of coins.

My solution is shown below:

```int ans = 0;
for(int i = 0; i < coins.length; ++i)
ans += coins[i];
int[] num = new int[ans + 1];
num[0] = 1;
for(int i = 0; i < coins.length; ++i) {
for(int j = 0; j <= ans - coins[i]; ++j) {
num[j + coins[i]] = Math.min(num[j + coins[i]] + num[j], 2);
}
}
if (num[ans] > 1) ans = -1;
return ans;
```

By VitalyGoldstein
TopCoder Member