A. Guess the DNA!
We will describe an approach that solves this problem in at most 3∗n+3 queries. The first 3 queries are for getting the counts of A,T,G,C.
We can search for 2 characters at once:
Assume that the queried string is "yyyyyyyy...yyyyxyyyyyyy...yy" (x and y are 2 different characters)
If the similarity count has increased by 1 from "yyyyyyyyyyyyyyyy...y" then the character is x, else, if it has decreased by 1, then it is y.
We search for the first 2 characters with the most count, which will take 2∗n queries.
Then we search for the last 2 characters, which will take n queries at most (since at least n characters have been searched in the string before).
Complexity: O(n2).
Code: https://mirror.codeforces.com/contest/1981/submission/263736407
B. Bit GCD
It is easy to observe that the gcd is <= min, and one popcount operation reduces the min to <= log(a).
So we can just brute force all gcds from 2 to log(a), note that each element takes O(log∗(a)) iterations to be reduced to 1.
Complexity: O(n∗log(a)∗log∗(a)).
Code: https://mirror.codeforces.com/contest/1981/submission/263736978
C. Permu Shift
One can see that pressing the button k times applies 2k times the original permutation on [1,2,3,...,n].
To find how many times the permutation need to be applied on to go back to [1,2,3,...,n], one can just use any solution of 1249B2 - Books Exchange (hard version) with the note that it is the LCM of the cycles.
To check for the power of 2 fast one should use GCC builtins (that can do it in O(1) instead of O(log(n))).
Complexity: O(n).
Code: https://mirror.codeforces.com/contest/1981/submission/263738042
D. Biased Coin
The probability of rolling a head after rolling k heads and n coins is (50+n−2∗k)%.
Let's use this fact to build a dp solution.
Let hp(k,n) being (50+n−2∗k)∗828542813 if 0≤k≤n, else 0. (you will see why later).
dp[heads][n]≡(hp(heads−1,n−1)∗dp[heads−1][n−1])+((1−hp(heads,n−1))∗dp[heads][n−1])) (mod 998244353).
with dp[0][0]=1.
But: this solution is O(n2)!
There is an observation that is needed to solve the problem.
It is:
The condition for dp[i][j] to be nonzero is ⌈j/2⌉−25≤i≤⌊j/2⌋+25.
So by shifting the positions in the dp array,
Let's create two new variables shift1, shift2 with shift1 being the shift on dp[n] (dp[heads][n] now turns to dp[heads-shift1][n]) and shift2 is the same for dp[n-1].
Set shift1 to ⌈n/2⌉−25 and shift2 to ⌈(n−1)/2⌉−25. Let's modify the dp formula to use them. Now the dp formula is:
dp[heads−shift1][n]≡(hp(heads−1,n−1)∗dp[heads−1−shift2][n−1]) +((1−hp(heads,n−1))∗dp[heads−shift2][n−1])) (mod 998244353) for heads satisfying ⌈n/2⌉−25≤heads≤⌊n/2⌋+25.
Since there are only a maximum of 51 values of dp[heads][n] that is nonzero, we get a O(n) solution.
Why 828542813? 828542813∗100≡1 (mod 998244353).
Code: https://mirror.codeforces.com/contest/1981/submission/263741468