Tuesday, November 20, 2007 Match summary
Many students skipped their classes yesterday because of this match. And their lonely teachers said: "Thank god. I have time for today's SRM.". Just a joke. But really, many students participated in this match. They were faced with pretty easy problemset. 40 contestants successfully finished all three problems. Some of them finished all in less than 15 minutes. The difference in total points between successive contestants was very small (that's what easy match brings  you have to be fast). First place was taken by ahyangyi thanks to +75 in challenge phase, second by Loner (congrats for color !) and third by victorsb. Fourth and fifth were mirosuaf and smel, respectively. The ProblemsSolvingEquationUsed as: Division One  Level One:
As A, B and C are integers greater than or equal to 1, each corresponding factor can vary in relatively small interval. x can be between 0 and W / A, y between 0 and W / B and z between 0 and W / C, inclusive (all are integer divisions). If some factor exceed its upper limit, we get number greater than W, and we can't decrease it to W afterwards as negative factors are not allowed. As lengths of those intervals are at most 100, we can try all possible combinations of x, y and z. This give us O(W^3) complexity which is surely good enough. Here is simple solution in C++: int solve (int A, int B, int C, int W) { int res = 1000; for (int x = 0; x <= 100; x++) for (int y = 0; y <= 100; ++y) for (int z = 0; z <= 100; ++z) if (x*A + y*B + z*C == W) res = min(res, x + y + z); return res == 1000 ? 1 : res; }DecreasingNumber Used as: Division One  Level Two:
Simple greedy solution doesn't work here. Example is when we start from 10. If you do greedy, you'd give priority to division probably. So, you'd get 5, then 4, 2, and 1. And that's 4 operations. It can be better  decerease it by one and divide by 3 twice. So, the most intuitive solution is dynamic programming. For each number, try all possible operations on it and take one which minimizes total number of operations to achieve 1. Here is the solution in C++: int dp[1000001]; int numberOfOperations(int n) { dp[1] = 0; for (int i = 2; i <= n; ++i) { dp[i] = dp[i  1] + 1; if (i % 2 == 0) dp[i] = min(dp[i], 1 + dp[i / 2]); if (i % 3 == 0) dp[i] = min(dp[i], 1 + dp[i / 3]); } return dp[n]; } Note that, originally, constraints were much higher. Better complexity can be achieved with BFS and hashing/mapping. PaperUnfoldingUsed as: Division One  Level Three:
Logically the easiest solution is to generate all possible sequences of foldings and then check if one in the input exists in generated set. It would have worked fine as we can perform at most 11 folding operations  that is O(2^lg(N) * N) = O(N^2) complexity. But, that solution is not so easy to implement as the one that follows. Let's assume that our input paper, described by code, is valid (i.e. we got it by unfolding some folded paper). Then we can surely go backwards and fold it again to state from which it's gotten without any conflict. "Without any conflict" means that each time we are performing some folding operation, every mark on the left side of the paper, with index i, corresponds to the mark on the right side of paper with index L  i  1. (indexed from 0. L is the number of marks on the paper we are considering). We exclude middle mark as it's not important at all (it doesn't have its markpair). So, when we are checking validity of some paper described by marks, we first check if there are no conflicts. If it's false, we determine that paper is not valid product of unfolding. If it's true, then we fold paper in half (bring right part over/under left) and again check validity of new paper recursively. Terminating case is when there is at most one mark, and we surely know solution for it. Here is simple recursive algorithm in C++: bool isValid(string s) { if (s.size() == 0) return true; for (int i = 0; i < s.size() / 2; ++i) if (s[i] == s[s.size()  i  1]) return false; return isValid(s.substr(0, s.size() / 2)); } string isValidUnfolding(vector<string> code) { string s; for (int i = 0; i < code.size(); ++i) s += code[i]; string isValid(s) ? "YES" : "NO"; }

