Match Editorials

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

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

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

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;