Change the contest from HNOI to COCI.

Now it's 1 hour.

Poor input of 50.

Look at divisors of 2N.

Hint: sum of l,l+1,...,r-1,r is equal to (l+r)/2.0*(r-l+1)
try iterating over every possible value of (r-l+1)

You can solve in

intt n;
    cin >> n;
    intt a = 1;
    while (a * (a + 1) / 2 < n) {
        if ((n - a * (a + 1) / 2) % (a + 1) == 0)
            cout << (n - a * (a + 1) / 2) / (a + 1) << " " << (n - a * (a + 1) / 2) / (a + 1) + a << endl;
        a++;
    }

You will understand from that :

sum of 2 adj. numbers: m + (m + 1) = 2m + 1

sum of 3 adj. numbers: m + (m + 1) + (m + 2) = 3m + 3

sum of 4 adj. numbers: m + (m + 1) + (m + 2) + (m + 3) = 4m + 6 .. etc..

This might be overkill.

Let's denote the amount of a-s, b-s and c-s Slavko has for some some suffix of Mirko's string as sa, sb, sc. Also denote the amount of a-s, b-s and c-s in the suffix as ma, mb, mc. Then that suffix is solvable with the given letters iff the maximum flow of the following graph is sa + sb + sc:

Now we can iterate over Mirko's string and choose the lexicographically smallest character so that the remaining string is still solvable with the remaining letters.

Task Igra: implement an O(n) function to answer "is it possible to arrange a valid string if we have (a₁, b₁, c₁) free characters against (a₂, b₂, c₂) already placed characters (notice that a₁ + b₁ + c₁ = a₂ + b₂ + c₂). To do it you can iterate over what part of a₁ goes to b₂, and then all the rest if fixed and can be checked with some ifs.

Now you can iterate over each character of answer string and try to place a, then b, then c and check if it is correct. It is O(n²), obviously. By the way, the function is some kind of maxflow, so it can even be solved in nearly constant time, making O(n) operations total.

You can just pick the letter greedily, checking if choosing such letter and you can still have a valid string afterwards.

e.g. if you choose 'a' at pos i, you need to make sure no. of 'b' in Slavko[i + 1 .. n] <= (a — 1) + c, no. of 'c' in Slavko[i + 1..n] <= (a — 1) + b. you can do this O(1). where a, b, c are the number of letter that Mirko still have.

So overall time complexity is O(N).

I submitted an O(n^2) solution, but I think that it could be changed slightly to an O(n) one. How did you get an alpha^2 factor?

I didn't solve it (made pretty bad mistake), but I think this is the intended solution.

The only thing left would be to find σ, which can be done using Knuth-Morris-Pratt.

So this solution runs in O(M) time.

You can look at the scores of people in past contest to compare. Write back if you find something interesting.

I think this contest was harder than usual.

In 5th round I got 434 points, 6th round was 350 points and now I didn't even solve three problems in this round :(

Or maybe the previous rounds this season were easier than usual? At least this is how I feel about it.

Sum of every possible result divided by the number of these results. If a result can be obtained in two different ways it should be counted twice.
I haven't read the problem asking for expected value. I'm giving the general meaning

Like an hour. But initially the results only appear at the evaluator page, it takes a while before they appear at hsin.hr/coci

you can see them now

My solution was saving the values and the exponential of two considered that the answer is one of the node * power of 2. This give a linear solution. The last two were hard so I luckily got 12th by solving first 4 problems lol.

Sorry if this is stupid, but how to prove correctness of the DP for an internal(scale) node? I mean if we have scale with children having weights a and b(a ≤ b) we'd have to add b - a weight to the left child, but how do you know that it can be done while maintaining the current balance within that subtree? Wouldn't it be required for b - a to be divisible by 2^height where height =  height of the node from the bottom?

Probably handling 10⁶ strings of length 10⁶ is too much. It is better to represent the numbers in the form of a·2^b where a is some odd integer.

I assumed that and got 120. You were wrong elsewhere.

Sketch of the solution (I am an author of the problem):

Take any 3 noncolinear points and bring them all to the [5, +inf] x [5, +inf] quadrant of the plane. It can be seen that such series of moves exists if you observe the tiling of the plane by parallelogram generated from those 3 points. Now, you can just use BFS to find shortest series of moves to bring those 3 points to that part of the plane. Since coordinates are small you can check all possibilities and see that in worst case this takes around 1200 moves.

Last, you can see that after you have points A, B in quadrant [5, +inf] x [5, +inf] you can move any other point C to first quadrant with just one move.