Monday, December 11, 2006 Match summaryIn 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 ProblemsGoodExhibitionUsed as: Division One - Level One:
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:
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.
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:
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.
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; |
|