Match Editorials

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 Problems

Value	250
Submission Rate	107 / 117 (91.45%)
Success Rate	84 / 107 (78.50%)
High Score	exod40 for 248.98 points (1 mins 49 secs)
Average Score	227.35 (for 84 correct submissions)

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

Value	500
Submission Rate	95 / 117 (81.20%)
Success Rate	75 / 95 (78.95%)
High Score	mirosuaf for 498.83 points (1 mins 23 secs)
Average Score	428.72 (for 75 correct submissions)

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.

Value	1000
Submission Rate	71 / 117 (60.68%)
Success Rate	45 / 71 (63.38%)
High Score	ahyangyi for 970.72 points (4 mins 57 secs)
Average Score	645.16 (for 45 correct submissions)

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 mark-pair).

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