For problem D, could someone explain why Poby and Rekkles are always able to find fresh "B"'s in their strategies? What if the array is (8, 8, 9), then one of them touches 9, then the other two elements are type A...

You don't need binary search. Let x be the largest subarray to the left, and y be the largest subarray to the right. You can set a[i] to k — x — y.

Out of curiosity, what kinds of other heuristics did people use?

I wonder if the problem would be "fixed" by making the complexity requirements more strict to force the simple solution.

Very smart.

What is the motivation for thinking in terms of decreasing relative frequency rather than increasing it? Is it that the max operations is 2n acts as some sort of hint?

Genius! Thank you.

How does E work?

We know for all x,y that x ^ y <= x + y. And the equality case is when there are no shared bits between x and y. So you need to add some k to both x and y such that they no longer share bits.

What exactly does it mean that you can always move values backwards?

I understand why it is guaranteed min_val <= min(floor(sum[0..i]/i)), but why must they be equal at optimal(max-min)? What if this value of min_val makes us have some bad max_val?

One query is sufficient for the first character because if "1" is not a substring, you don't need to check "0" — the string must be only "0"'s.

Anyone else lost question C by initializing dp to -1 instead of -inf? :(

I think your algorithm is n^2 which is too slow, regardless of correctness.

You can use fermat's little theorm.

$$$a^{p-1} \equiv 1 \pmod p \implies a \cdot a^{p-2} \equiv 1 \pmod p.$$$

So the inverse of $$$a$$$ is $$$a^{p-2}.$$$

Extended Euclidean Algorithm also works.

Lol yeah, that solution doesn't look correct. Very interesting that it passed.

F was set way too high IMO. It was easier than both D and E.

F was easier than D/E lol.

Ah yeah, I got that pretest wrong and my mind blanked... I was so convinced that Iris could only score 1 even after drawing it on paper.

I guess it is important to observe that the first move is "useless," so by moving first, you are actually at a disadvantage.

What was your thought process for realizing that Iris can "win" an extra leaf by "passing" turn to opponent sometimes?

Whst if the root is not question marked?

Naming convention for B sucks. l and r is really misleading... should have used l/u for lower/upper bound or something.

From cppreference:

std::sqrt is required by the IEEE standard to be correctly rounded from the infinitely precise result. In particular, the exact result is produced if it can be represented in the floating-point type. The only other operations which require this are the arithmetic operators and the function std::fma. Other functions, including std::pow, are not so constrained.

I suppose the concern is, what if the infinitely precise result of sqrt(a) is n-epsilon for some integer n and small epsilon, that the nearest float is n.

I don't think this is true. Using order 1, n, 2, n-1, ... does not maximize the changes.

Imagine the sequence 1, 2, 2, 2, 3. Using the order 1, n, 2, n-1, ... we would get 1, 3, 2, 2, 2. This is two changes. We can get five changes with the sequence 2, 1, 2, 3, 2.

I tried alternate most frequent character with all others, it passed pretests.

No git link?

I found problem A very easy to misread as well. I wish the sample tests were better.

You are looping from l to r for every test case. Imagine if there is 10000 test cases, each has a=1 and b=200000. Then you will TLE.

You are looping from a to b for every test case. Imagine if there is 10000 test cases, each has a=1 and b=200000. Then you will TLE.

Why is Problem G two parts? Is there really a solution for G1 that will not pass for G2?

Bruteforces

My guess (without reading your code) is that log2(a) — log2(b) was incorrectly rounded up due to precision.

I had same solution. I was surprised it passed, because if $$$\frac{\ln a_i}{\ln a_{i+1}} = 2^x$$$ and it gets calculated slightly too large, then it might be rounded up.

Not sure if there is a hack that can break this solution.

Let there be cakes with tastiness 1, 2, 2, 3, 3, 4, 4, 4, 5 Bob will want to eat the cakes with tastiness 3 first.

Bob sometimes may want to eat a less tasty cake with a higher frequency over a cake that has lower frequency but high tastiness.