Solution of E: For any subarray B of A, assume we need to flip it. If there exist a pair of array S, T (T could be empty but S could not) such that B = S + T + S, then rev(B) = rev(S) + rev(T) + rev(S), so we can flip S, T, S instead of B. For any division of A, if no subarray fliped has property mentioned above, it will be the only division with the largest number of subarrays among all divisions with same result after flipping. So we can solve by dp: let dp[i] = the number of valid division of A[1...i], the transition will be dp[j] = sum(j<i, A[(j+1)...i] cannot be represented with STS form)(dp[j]), where the condition could be checked using KMP algorithm.

Solution of F: A graph with only nodes of even degree can be split into some cycles, look at "cells" surrounded by these cycles. If we add a path with positive sign and a path with negitive sign on every edges "inside" these cycles (which doesn't change the sum of paths), we can split all paths into some cells with four edges surrounded, with positive sign on the edges above and left, negative sign on the edges right and below. So we can represent the problem as "choose some cells with the largest sum of contribution, where the contribution of each cell is the weight of edges above and left, minus the weight edges right and below". For any invalid edge, the two cells adjacent to it must be both chosen or both not chosen, so we need to add a link between adjacent cells of any invalid edge (if any of them is outside the grid, mark another cell as invalid), then for every connected component formed by links, we only need to choose these with positive total contribution and without invalid cell.

Code example: 364371615

Solution of F: First put numbers from 1 to n on a binary tree, where the root is floor((1+n)/2), and the left and right child of each node represent the left and right range of the next step of binary search. For example n=12:

             6
          //   \\
       3          9
    /    \      /   \
   1     4    7      11
    \     \    \    /  \
     2     5    8  10  12

Then we can observe that for any two nodes u < v (proof omited):

(1) If u is ancestor of v, or the v is ancestor of u: beauty(u,v) = n-(v-u).

(2) Otherwise, beauty(u,v) = n- (2 + (size of subtree of right child of u) + (size of subtree of left child of v)).

We denote the formula above as n- (2 + RSZ(u) + LSZ(v)).

To calculate the answer, first we pretend that there's no situation (1). Then we iterate v from 1 to n, use a map to maintain for each possible size k, there are how many u < v such that RSZ(u) = k. By the structure of the binary tree, there are at most O(log(n)) different possible sizes of subtrees, so the complexity is O(n*log(n)).

Second, we need to deal with situation (1). Note that the height of the binary tree is at most O(log(n)), there are at most O(n*log(n)) pairs of nodes with ancestor relation, so we can brute force for every single pair.

Therefore, we solved the problem in O(n*log(n)).

In the offcial editorial of problem F, the situation where vertex $$$k$$$ is on the path from $$$x_k$$$ to $$$y_k$$$ is not mentioned (in this case, $$$(x_k,y_k)=(x_{k-1},y_{k-1})$$$).

In the official editorial of problem C,

さらに、 $$$R=0$$$ の場合、 $$$(r_i+c_i)$$$ と $$$(r_{i+1}+c_{i+1})$$$ を $$$4$$$ で割った余りが異なることから、以下の必要条件が得られます。

$$$R=0$$$ ならば、 $$$B$$$ は偶数

This conclusion is wrong. Actually it should be " $$$r_i$$$ has different parity with $$$r_{i+1}$$$ "

The fastest unrated legend LOL

A: Answer is simply initial count of '1'

B: Answer is true if and only if a[i]>2*max(i, n-1-i) for all 0<=i<=n-1

C: Do operation 2 and pick the absolute value of sum(a[i]) at this moment, as a candidate answer. Repeat until length of a[i] become 1. The initial sum is also a candidate answer

D: Assume a[i] has been decided, then the answer is sum(max(0, a[u]-a[parent(u)])), where a[parent(u)]=0 when u is the root. Then we can find the answer simply by dp

E1: For any node u, if there's any other node v such that v is not in subtree of u, and w[v]>w[u], we call u "good node". Then any good node with maximum w[u] could be the answer.

F: Sort all pairs such that for all 0<=i<n-1, we have (a[i]-b[i]<a[i+1]-b[i+1]) or (a[i]-b[i]==a[i+1]-b[i+1] and a[i]<=a[i+1]). Then candidate answers will be:

• maximum value of b[i]+a[j]+ sum(a[t]+b[t]) (i<j, sum over several t (possibly none) with i<t<j)

• maximum value of 2*b[i]+a[j1]+a[j2] + sum(a[t]+b[t]) (i<j1<j2, sum over several t (possibly none) with i<t<j2 and t!=j1)

• maximum value of b[i1]+b[i2]+2*a[j] + sum(a[t]+b[t]) (i1<i2<j, sum over several t (possibly none) with i1<t<j and t!=i2)

• maximum value of 2*b[i1]+a[j1]+b[i2]+2*a[j2] + sum(a[t]+b[t]) (i1<j1<i2<j2, sum over several t (possibly none) with i1<t<j2 and t!=i2 and t!=j1)

We can find the answer by simple DP.

A: When the MEX value of a set be positive, this set must contain $$$0$$$. WLOG assume $$$n \lt =m$$$ and $$$a_{1,1}=0$$$, then the answer will be MEX of first row plus MEX of first column. If we let $$$a_{1,j}=j-1$$$, the MEX of first row will be $$$m$$$ and MEX of first column will be $$$1$$$, the answer is $$$m+1$$$. On the other hand, value $$$1$$$ cannot be contained in both first row and first column, so the minimum value of MEX of first row and first column is $$$1$$$, therefore the answer is not greater than $$$\max(n, m)+1 = m+1$$$.

B: Let $$$T$$$ be the number of different values in array $$$a$$$, in each operation we can only reduce $$$T$$$ by at most $$$1$$$ (because all values we remove from $$$a$$$ are equal), and if we choose $$$l=1, r=n$$$ everytime, $$$T$$$ will definitely be reduced by $$$1$$$. So when $$$k=0$$$ the answer is the number of different values in array $$$a$$$. When $$$k \gt 0$$$ we need to reduce $$$T$$$ as more as possible, so we need to find value $$$a_i$$$ with minimum number of occurence annd change their value, until we used up all $$$k$$$ operations.

C: First assume $$$a, b, c \in {0,1}$$$. We can see $$$(a⊕b)+(b⊕c)+(a⊕c)$$$ is 2 when $$$a, b ,c$$$ are not the same, and $$$0$$$ otherwise. To find the answer we look at bits of $$$l, r$$$, start from the most significant: Let $$$j$$$ be the most significant bit where $$$l,r$$$ differ, so for $$$j+1$$$-th bit and higher $$$(a⊕b)+(b⊕c)+(a⊕c)$$$ can only be zero. Let $$$B$$$ be the $$$j+1$$$-th bit and higher part of $$$l$$$ and $$$r$$$, and $$$p=1\lt\lt j$$$, we have $$$l \lt (B|p) \lt = r$$$, and because $$$r-l \gt =2$$$, either $$$B|(p-2)$$$ or $$$B|(p+1)$$$ should be in interval $$$[l, r]$$$. By calculation we can see when $$$a=B|(p-2), b=B|(p-1), c=B|p$$$ or $$$a=B|(p-1), b=B|p, c=B|(p+1)$$$, the value of $$$(a⊕b)+(b⊕c)+(a⊕c)$$$ will be the maximum possible (which is $$$1\lt\lt(j+2)-2$$$).

D: We solve the problem by segment tree: For each node representing range $$$[u, v]$$$ we store these values:

• $$$max_{-}plus = \mathop{\max}\limits_{u \lt =i \lt =v}a_i+i$$$
• $$$max_{-}minus = \mathop{\max}\limits_{u \lt =i \lt =v}a_i-i$$$
• $$$min_{-}plus = \mathop{\min}\limits_{u \lt =i \lt =v}a_i+i$$$
• $$$min_{-}minus = \mathop{\min}\limits_{u \lt =i \lt =v}a_i-i$$$
• $$$ans$$$ = the answer we need for range $$$[u, v]$$$

When we need to merge 2 ranges $$$L$$$ and $$$R$$$, we first assume we pick max and min value of $$$a_i$$$ both in range $$$L$$$. In this case we don't need to extend the range outside of $$$L$$$, because we cannot get any better answer, so this case answer is $$$L.ans$$$. Similarly when we pick max and min value from $$$R$$$, the best answer is $$$R.ans$$$. If we pick max value from $$$L$$$ and min value from $$$R$$$, we need to find $$$\mathop{\max}\limits_{i \in L, j \in R}a_i-a_j-(j-i)$$$, which is equivalent to $$$\mathop{\max}\limits_{i \in L}(a_i+i) - \mathop{\min}\limits_{j \in R}(a_j+j)$$$, so the best answer for this case is $$$L.max_{-}plus - R.min_{-}plus$$$. Similarly, for the last case, the best answer is $$$-L.min_{-}minus + R.max_{-}minus$$$.

E2: For a certain query $$$(a, b, k)$$$, let's find how to check whether $$$w_k \gt = t$$$ for certain $$$t$$$. Let's assume all edges in the graph with $$$w \gt =t$$$ has cost $$$1$$$, and other has cost $$$0$$$. If we can go along any path, move from node $$$a$$$ to $$$b$$$ with cost $$$\lt k$$$, then $$$w_k$$$ will be less than $$$t$$$ in this path. Otherwise, for every paths from $$$a$$$ to $$$b$$$ we need to pass at least $$$t$$$ edges with $$$w \gt =t$$$, so we have $$$w_k \gt =t$$$ for every paths. Therefore to solve this problem, we can sort all edges by $$$w$$$ from lowest to highest, change their cost from $$$1$$$ to $$$0$$$ one by one, and for any query $$$(a, b, k)$$$, if cost from $$$a$$$ to $$$b$$$ dropped down to $$$k-1$$$ or less, we know the answer for this query is $$$w$$$. So the rest we need to do is keep updating value of $$$cost(a, b)$$$ when cost of edges changed. The initial cost can calculated by Floyd's algorithm in $$$O(n^3)$$$, and $$$cost(a,b)$$$ can decrease at most $$$n-1$$$ times, because if nodes $$$a, b$$$ is connected with edges of weight $$$0$$$, adding an edge with cost $$$0$$$ on $$$(a, b)$$$ will not cause any change of cost on this graph. Each time such decreasement occurs we can recalculate $$$cost(u, v)$$$ for all pairs in $$$O(n^2)$$$. So the problem can be solved in $$$O(n^3+ m\log(m) +q\log(q))$$$.

G: If you've planted sugar cane in Minecraft, the answer is easy to come up with: First, we find all positions $$$(i, j)$$$ where $$$-1 \lt =i \lt =n$$$, $$$-1 \lt =j \lt =m$$$ and $$$(i+3j) mod 5 = 0$$$, and try to add these positions into $$$S$$$: If position $$$(i,j) \in A$$$, we add it into $$$S$$$ directly, any otherwise for each adjacent position $$$(i', j')$$$, we add it into $$$S$$$ if $$$(i', j') \in A$$$. Therefore we've built a set $$$S$$$ satisfies the second condition. To match the first condition, we repeat this process for $$$r \in [0,4]$$$ and $$$(i+3j) mod 5 = r$$$, and pick the set with minimum size, this set will satisfy the size condition. (Prove by AC)

It's not hard to do this but I realized that after contest ended.

We can solve this problem by dp. Let dp(u, t) be the minimum value of (maximum value of a[i] on the subtree of u) if you do t operations on the subtree of u. Note that 2^60>=10^18 so t<=60. So when need to merge dp status from lc and rc: we have merged(i) = min (0<=j<=i) (max(dp(lc, j), dp(rc, i-j)). Note that the optimal j is non-decreasing when i increases, so we can merge them in O(log(A)). Then we need to used the merged value to calculate dp(u): We have dp(u, t) = min(0<=s<=t) (ceil(max(merged(s), a[u]) / b[u]^(t-s))), which means dp(u, t) = min(max(merged(s), a[u]), ceil(dp(u, t-1)/b[u])).

For two non-increasing array a[i], b[i], let c[i] = min(0<=j<=i)(max(a[j],b[i-j])), then the optimal j is non-decreasing when i increases. You can check this by drawing function image of a[j] and b[i-j] for different i.

Didn't solved F in contest, because 200000*61*8 bytes (=93.08MB) make stack overflowed... First time get so much negative delta because of stack overflow (error code 3221225725)

A: sort {a[i]} and find the maximum suffix sum with value at most k. The answer is k minus this sum.

B: Let k1 be the count of colors with only 1 occurence, and k2 be the count of colors with at least 2 occurence. For each time Alice pick ball from k1 she will gain 2 points, and when she pick from k2 she will gain 1 point. Also Alice cannot get 2 potins from k2, because Bob can take the ball with same color after Alice pick the first ball from that color. So the optimal move for Alice and Bob is take balls from k1 first, then Alice will take a ball for all colors in k2. Therefore the answer is k2+2*ceil(k1/2).

C: For each 1<=i<n, if we separate the array at the "gap" between i and i+1, the score of fishes on [i+1, n] will increase by 1, so the value of (Bob's score — Alice's score) will increase by (number of '1' in [i+1, n] — number of '0' in [i+1, n]), so we can calculate the change of balance for 1<=i<n by suffix sums, sort them and pick from the greatest to smallest.

D: Let's find the number of strongly recommended tracks with number > r[i] for each 1<=i<=n first. So we can sort users by l[i], and for each i we need to find the minimum value of r[j], for all j such that l[j]<=l[i] and r[j]>=r[i]. Here the first condition is satisfied from the non-decreasing order of l[i], then we need to find the minimum r[j] by lower_bound on std::multiset. Then we need to find the number of strongly recommended tracks with number < r[i], we can do this by {l[i], r[i]} := {-r[i], -l[i]} and do the same steps as previous case.

F: We can solve the problem by segment tree. The merge function of segment tree is something like this:

info merger(const info& L,const info& R){
	if(L.sum<=-inf) return R;
	if(R.sum<=-inf) return L;
	info I;
	I.sum=L.sum+R.sum;
	I.La=max(L.La,L.sum+R.La);
	I.Ra=max(R.Ra,R.sum+L.Ra);
	I.ans=max(max(L.ans,R.ans),L.Ra+R.La);
	I.LD=max(max(L.LD,L.sum+R.LD),max(L.La+R.ans,L.LRD+R.La));
	I.RD=max(max(R.RD,R.sum+L.RD),max(R.Ra+L.ans,R.LRD+L.Ra));
	I.LRD=max(L.La+R.Ra,max(L.LRD+R.sum,R.LRD+L.sum));
	I.D=max(L.ans+R.ans,max(L.RD+R.La,R.LD+L.Ra));
	I.D=max(I.D,max(L.D,R.D));
	return I;
}

Where: (Assuming the range represented by I is [x, y], Denoting sum(x, y) = a[x]+a[x+1]+...+a[y-1]+a[y])

• I.sum means sum(x, y)

• I.La means maximum value of (sum(x, j)+b[j]) for x<=j<=y

• I.Ra means maximum value of (b[j]+sum(j, y)) for x<=j<=y

• I.ans means maximum value of (sum(j, k)+b[j]+b[k]) for x<=j<=k<=y

• I.D means the needed answer for the range (which is maximum value of (sum(j, k) + b[j]+b[k] + sum(p, q) + b[p]+b[q]) for x<=j<=k<p<=q<=y)

• I.LD means maximum value of (sum(x, j)+b[j] + sum(k, p)+b[k]+b[p]) for x<=j<k<=p<=y

• I.RD means maximum value of (sum(j, k)+b[j]+b[k] + b[p]+sum(p, y)) for x<=j<=k<p<=y

• I.LRD means maximum value of (sum(x, j)+b[j] + b[k]+sum(k, y)) for x<=j<k<=y

The merge function is similar as what we do when finding maximum subarray sum by divide & conquer.

Who put problem E at this position?

How does checker of B implemented?

If the j-th bit of a[i] is 1. Or if ((a[i]>>j)&1)==1

E: Build a bipartite graph with n vertexs on the left and 60 vertexs on the right. For each 1<=i<=n and 0<=j<60, we add an edge if a[i] has j-th bit set on. For any subset of left nodes, the score is (number of chosen left vertexs )-(number of right vertexs with edge connected to chosen left vertexs ) = (number of chosen left vertexs )+(number of right vertexs without connection to chosen left vertexs )-60, then the answer is (Size of maximum independent set)-60. By the Konig theorem: In any bipartite graph, the size of maximum matching is same as minimum vertex corver, and (size of minimum vertex corver)+(size of maximum independent set)=n+60, we can calculate answer by any maximum matching algorithm.

Why constraint for D1 is n+69, not n+1 or n+2? Is it a kind of misleading to n+O(log(n)) solution?

There's a solution of C slightly simpler than official: Let multisets S={Ai: Ai<=X/3}, T={Ai: Ai>X/3}, then Ai, Aj and Ak cannot all come from T, and if they all come from S then Ai=Aj=Ak=X/3 so we can check if number of occurences of x/3 is at least 3. So in other cases, there could be 1 number from S and 2 from T, or vice versa. For now on we only need to keep 2 occurences for each different numbers. For the first case (second case is similar), Let f(x)=((sum(j)(x^j))^2-sum(j)(x^(2*j)))/2, where j iterates among all elements of T, then f(x)[x^p] will be the number of ways to choose different Ai,Aj from T such that Ai+Aj=p, we can use FFT to calculate them, and find some p<=X/3 such that f(x)[x^(X-p)]>0. Because we only keep at most 2 occurences, each coefficient of f(x) is at most 1000000*2^2=4000000, so we can do FFT by modulo 998244353 safely.

My O(n^5) solution (with small constant) passed F1. However it's hard to optimize to O(n^4) or better (Because I solved d1B by a suboptimal solution, which mislead my thinking of F1)

How to prove the greedy solution of E?

G2 and G3 are not div4 problems. They should only appear in div2 or div1.

The 4-th sample of D1A reduced it's difficulty a lot. Otherwise it's problem rating could increase by 100.

A: sum(c)(max(0, cnt(c)-a)) for 'A'<=c<='D'.

B: Assume there are both odd and even numbers in a[i] (otherwise answer is trivially 0), because in each operation we can reduce count of odd numbers by at most 1 in each operation, and when there's only 1 odd number we can't change its parity, we need to change all numbers to odd. So we can add the greatest odd number to smallest even number repeatedly, until there's no even number. If we can do this, the answer is (count of even numbers). Otherwise, we can add the greatest even number to an odd number, and add this odd number to all even numbers, then answer is (count of even numbers)+1.

C: Let A = max(a[i]), the number of lights turned on will change with period 2*k after A minutes, and the answer cannot be small than A, so we only need to check range [A, A+2*k-1] using prefix sums.

D: Let's find the answer by binary search. So for certain M we need to change a[i] to 1 when a[i]<M or 0 otherwise. Then we need to choose some remaining indexes {i0=0, i1, i2, ..., i_r, i_(r+1)=n+1} where i_(j+1)-i_j-1 is multiple of k (0<=j<=r), and sum(a[i_j]) is minimized. We can solve this by dp: let dp[i] = the minimum sum if we let i_r=i. Then we have dp[0]=0, dp[i]=a[i]+min(0<=j<i, j%k==(i-1)%k)(dp[j]), the minimum valid sum is min(1<=i<=n, i%k==n%k)(dp[i]).

8

1 1 100 100 10000 10000 10000 10000

1 2

1 3

2 4

1 5

2 6

3 7

4 8

Assume the order of balls are randomly shuffled before game starts, and each turn players take the first remaining ball. Then for a certain special ball, let's ignore all other special balls, we need to shuffle it with n-k normal balls randomly, it can be arranged from 1-st position to (n-k+1)-th position with equal probability, which means, the number of normal balls before it, is uniform distribution on [0, n-k].

Any data structure with point update and range sum query (Fenwick Tree for example).

The change of values in one operation will be like this:

0 0 0 ... 0 0 0

...

0 1 0 ... 0 2 0

...

0 2 0 ... 0 1 0

...

0 0 0 ... 0 0 0

Where the sum of each column and row is 0 or 3, which is 0 modulo 3.

A: Obviously a[i]=i satisfies the condition.

B: Let c[i][j]=a[i][j]-b[i][j] and we need to make c[i][j]==0. Let row[i] be the sum of i-th row, col[j] be the sum of j-th column. Notice that every operations don't change row[i] and col[j], so they must be 0 initially. In fact, if row[i]==0 and col[j]==0 initially, we can make c[i][j]==0 by operations on 2x2 subrectangles.

C: There are 6 possible relative orders of l_a, l_b and l_c, we can find the answer by brute force for all possible orders.

D: Each operation will change the parity of inversion number of a[i] and b[i], so they must be the same initially. If they are same initially, we can sort a[i] first, and b[i] will be an array with even inversion number, and we can sort b[i] by swapping adjacent elements, while swapping a[1] and a[2] repeatedly.

E: Let S1 be the sum of special balls, S2 be the sum of normal balls. If we let p1 = the probability Alice can get i-th ball when i<=k, p2 = the probability Alice can get i-th ball when i>k, then ans=S1*p1+S2*p2. For n-k normal balls, Alice and Bob will take a normal ball alternately, so p2=(ceil((n-k)/2)/(n-k)). For the i-th special ball, Alice can take it if there are even normal balls be taken before it. The number of normal balls taken before a certain special ball can be any integer in [0, n-k] with equal probability, and p1 is the portion of even numbers in this range, which is (ceil((n-k+1)/2)/(n-k+1)).

F: Let's find the answer by binary search: For certain number A we need to calculate number of pairs (i, j) where i<j and a[i, j]<A. Let f(i) be the minimum j where i<j and a[i]^a[j]<A (if not exist f(i)=n+1), then the number of valid pairs will be sum(1<=i<n)(n+1-min(i<j<=n)(f(j))). We can calculate f(i) with binary trie: Let r be the highest bit where (a[i]^a[j]) is 0 and A is 1, then valid values of a[j] will be corresponding to a node of the trie.

dp[n]=h[n], dp[i]=max(h[i], dp[i+1]+1)

Assume there's an array {t[1], t[2], ..., t[r]} and Bob need to let Alice can't eat cakes with tastiness t[i]. Then for each tastiness t of cakes, let f[t]=1 is Alice can eat it, f[t]=-cnt[t] if Alice can't eat it, then every prefix sum of f[t] must be non-negative. You need to find the maximum array size by DP.

Translation of problem E:

There are how many binary arrays of length n-1 with k-1 or more ones without "101" as subarray?

A: If the sign of (x-y) changed, then (x-y) must be 0 at some time, so answer is NO. Otherwise, the answer is YES.

B: If x<y, then the value of x will change among {1, 2, ..., y-1} periodically, so the answer will depend on k%(y-1). Otherwise, after (y-x%y) operations x will become (x+y-x%y)/y, which is not greater than (x/y)+1. Because y>=2 this can happen not more than log(x) times until x<y, so we can simulate the process in O(log(x)).

C: Let dp[i] be the anwser for first to i-th cards. We can binary search for the largest j such that sum(j+1, i)>=l, if sum(j+1, i)<=r we have dp[i]=max(dp[i-1], dp[j]+1), otherwise dp[i]=dp[i-1].

D: Let the balance of heights B=(sum of snowy heights)-(sum of not-snowy heights). If B==0 initially the answer is YES. If we let c[i][j]=1 when (i, j) is snowy, c[i][j]=-1 otherwise, then when we do operation on a k*k square, the change of balance will be sum(i,j)(c[i][j]) where (i,j) is in the square. So we can calculate the sum of c[i][j] over all k*k submatrices using 2D prefix-sum, and by the bezout's theorem, the change of balance can be any multiple of GCD of these sums. In order to make B=0, the initial value of B must be the multiple of GCD.

E: First think about case for n=2**d. If k>=d the answer is n*(n+1)/2, and if k==d-1 the answer is (n-1)*n/2, let's assume k<=d-2. We can see the answer is sum(1<=r<=k+1)((2**r-1)*(2**r)/2 * C(d-r-1,k+1-r)). Denote this as f(d, k).

Now think about arbitrary n. We can split [0, n) into several intervals with length of 2**j, where n has the j-th bit. If we let L=floor(n/2**(j+1))*(2**(j+1)), R=L+2**j, the answer on interval [L, R) will be f(j, k-popcount(L)). If popcount(R-1)>k, there will be no valid interval containing both R-1 and R, so we can add this to the answer and consider for [R, n) seperately. Otherwise, when popcount(R-1)<=k, we can see that for any R<=x<n we have popcount(x)<=k, so we can add (n-L)*(n-L+1)/2 to the answer.

F: Let L be the minimum i such that a[i]>a[i+1], R be the maximum i such that a[i-1]>a[i]. Then at least we need to sort subarray [L, R]. Let X=min(L<=i<=R)(a[i]), Y=max(L<=i<=R)(a[i]), if there are any L1<L such that a[L1]>X or any R1>R such that a[R1]<Y, then we also need to sort them. To find L,R we can maintain a set S={1<=i<n: a[i]>a[i-1]} which can be modified in O(log(n)) each operation. To find X,Y we can use a segment tree, and to find L1, R1 we can use binary search on a[i].

First time get MLE in div3 round

In problem E, if we let f[3]=2, f[4]=8, f[5]=113, what will the asymptotic behavior of f[n] be like?

It's just to avoid explaining "what infinite turns of operations means"

A: If number of players is not greater than a[1], the game is end, otherwise it will continue. Then the answer is min(n, a[1]-1).

B: Assume we have t pairs and n-2*t single cards, then the opponent will also have n-2*t single cards, and then, they have (n-(n-2*t))/2 = t pairs. Since we can always get t points from pairs, and we can only get other n-2*t points if we play these single cards after opponent plays the corresponding cards, we need to play pairs first and single cards later. So for the first 2*t turns both players will play all pairs, and then we can't get any point because the opponent will play the card we've played last turn. So the answer is t.

C: From the example for n=2 we can see we can't get {{2, 2}, {2, 2}}. In fact, for any n and pairs (i1, i2) and (j1, j2) with i1<i2, j1<j2, we can't make numbers on the 2x2 submatrix determined by row i1, i2 and colomn j1, j2 be the same. So there can be at most 2*n-1 occurences of n (they can occupy a row and a column), and for the remained n-1 rows and columns, there can be at most 2*(n-1)-1 occurences of n-1 and so on... Therefore, the maximum sum we can get is sum(i=1...n)(i*(2*i-1)=i*(i+1)*(4*i-1)/6. To achieve this value, we can make operation on the i-th row and column, from i=n to i=1, with p[j]=j.

D: Let f(L, R) means we want to make a[L]=0, a[L+1]=1, ..., a[R]=R-L. If L==R, we can achieve this by do operation on [L, L] if a[L]>0. Otherwise, we can first do f(L+1, R), then do operation on [L+1, R] to make a[R]=R-L, then do f(L, R-1). Therefore, for any range [L, R] we can make the sum on this range be (R-L+1)^2 by operations, which is also the maximum possible value if every element on [L, R] have been modified. So we can solve the problem by dp.

E1: Assume i-th to (i+2)-th monster survived for T turns. If in the last turn (i+2)-th monster takes D damage, then at j turns before, it takes at least D+j damage, so the total damage it take will be at least D+(D+1)+...+(D+T-1) >= T*(T+1)/2, which means T*(T+1)/2 <= a[i+2]. Therefore, if we let A=max(ai), then after O(sqrt(A)) turns, there will be no more than 2 consecutive alive monsters, then for any pair of adjacent alive monsters, the left will be alive the the right will die. So we can brute solve the problem by brute force.

E2: Similar with E1, there will be no more than 3 consecutive alive monsters after O(A^(1/3)) turns, but we need to calculate the total damage of the second monster, in order to determine whether the third monster alive for consecutive 3 monsters.

The first contest on CodeForces in which nobody can get AK with 0 penalty theoretically.

Pass pretest with remained time <200ms means TLE on system test mostly.

That's a bug of Codeforces systems existed for a long time, and it won't be fixed.

E: First time a problem need to hardcode from n=3 to n=13

			ll cosas = 1;
			ll p1 = 0;
			bool usar = true;
			for (ll i = 0; i < 63 and cosas > 0; i ++){
				if ((1LL << i) & n){
					p1 ^= (1LL << i);
					cosas --;
				}
			}

In this section p1 will be the lowest bit of n. Try to let p1 be the highest bit of n.

A: Sort a[i] and the answer is a[n]+a[n-1]-a[1]-a[2].

B: We can believe that for some n0, we have dp[n]=dp[n-15]+1 for all n>=n0, and we can solve the problem by brute force for n<n0. (n0=300 can pass)

C: First query for (1, 1), let answer be d0, then there will be a mine on the line L0: x+y=2+d0. Then we query for the 2 endpoints of the intersection of L0 and the grid, let these points be A1,A2 and answer be d1,d2, then the circle (A1, d1) and (A2, d2) will have exactly 1 intersection with L0 in the grid, one of them will be the answer.

D1: If n is power of 2 we cannot do any operation. Otherwise, let r=floor(log2(n)). If 2**r<=m, then (m^n)<n, we can solve the problem in 1 operation. Otherwise, let t1=floor(log2(n-2**r)), t2=floor(log2(m)). If t2<t1, we can solve in 2 operation: n --> 2**r+m --> m. If t2==t1, we also have (m^n)<n and solve in 1 operation. If t2>t1, there's no solution.

D2: Let ppc(n) be the count of '1' in the binary representation of n. Then if ppc(n) is even, we always can do some operation to turn it into n1, n2 such that ppc(n1), ppc(n2) are odd. If ppc(n) is odd, for any n1, n2 such that (n1^n2)==n, one of ppc(n1) and ppc(n2) will be even. So If the initial ppc(n) is even we play first, otherwise we play second, and we can always let ppc(n) to be even on our turn. To win in 63 turns, we can let n1=2**r, n2=n-2**r, if the opponent choose n1 they will lose immediately, if they choose n2 the value of n will be halved.

D1A/D2C: First query for the largest element, let it's index be i0, then query for indexes j such that (a[i0]|a[j]) is the maximum, finally in these j we find j0 such that a[j0] is the minimum, then (i0, j0) is the answer.

D1B/D2D: WLOG assume s[i]='<', then we do something like this: go left find the first '>' --> go right find the first '<' --> and so on... So if cnt1= the number of '>' to the left of i, cnt2= the number of '<' to the right of i, then if cnt1<=cnt2, we will turn back at all positions of '>' to the left and first cnt1 positions of '<' to the right, if cnt1>cnt2, we will turn back at all positions of '<' to the right, and first cnt2+1 positions of '>' to the left. Then we can calculate the answer by the sum of positions of points we turn back. (The contribution factor of points we turn back at left is -2, points we turn back at right is +2, and the start point is +1, the end point is +1 (if end at right border) or -1 (if end at left border))

D1C/D2E: Build a graph of n*(m+1) nodes with index (i, j) (1<=i<=n, 0<=j<=m). Then for all 1<=i<=n, 1<=j<=m, we add edges (i, 0) --> (i, j) with cost 0, (i, j) --> (i, 0) with cost c[i]. For each 1<=j<=m, we sort [1, n] by the value of a[i][j], and for adjacent (i1, i2) in the sorted array, we add edges (i1, j) --> (i2, j) with cost 0, (i2, j) --> (i1, j) with cost a[i2][j]-a[i1][j]. (So distance from (u, j) to (v, j) is the cost to let pokemon v to win pokemon u by attribute j) Therefore, go along the path (u, 0) -> (u, j) -> (v, j) -> (v, 0) means we let pokemon v beat pokemon u, then the answer is the distance from (1, 0) to (n, 0).

using tmii = map<int, int>;

tmii& dfs(int node,int prev){
	tmii& mp=*new tmii();
	for(int next:adj[node]){
		if(next==prev) continue;
		tmii& mp2=dfs(next,node);
		if(mp.size()<mp2.size()) swap(mp,mp2);
		for(auto [color,cnt]:mp2){
			if(color!=c[node]) ans+=(ll)mp[color]*cnt;
			mp[color]+=cnt;
		}
		mp2.clear();
	}
	ans+=mp[c[node]];
	mp[c[node]]=1;
	return mp;
}

A: Let L=the minimum position of i such that a[i]==1, R=the maximum position of i such that a[i]==1, the until occurences of 1 become a single block, R-L will decrease 1 if you do operation on position R, otherwise it will not decrease. So the answer is (R-L)-(cnt-1) where cnt is the count of occurences of 1.

B: For each 1<=i<=n we need sum(j:abs(x[j])<=i)(a[i])<=k*i to kill monsters with distance <=i in i turns.

C: If L==R answer is no. Otherwise, for each a[i]==1 we need some j such that a[j]>1 and let a[i]+=1, a[j]-=1. Then we need sum(i:a[i]==1)(1)<=sum(j:a[j]>1)(a[j]-1). We can check this condition in O(1) by prefix sum.

D: Assume slime i is eaten by some slime to the left (the other case is similar), and all slimes used to eat i will form an interval [j, i-1]. So we need to find the maximum j such that sum(j, i-1)>a[i]. If j==i-1, slime i-1 can eat slime i directly. If value of a[j...i-1] is not all the same, then there will be a largest slime which can eat all other slimes in range [j, i-1] then eat slime i. Otherwise, all slimes in [j, i-1] have the same size and cannot eat each other, and slime i-1 is not larger than slime i. So we need to extend this interval to the left to find some k such that a[k]!=a[i-1] (if such k exist).

E: Small-to-large merge. Let dp[u][c]= (the number of nodes v in subtree of u, such that v is color c, and nodes on the path from u to v (except v) are not colot c). Then the number of valid paths with lca=u is sum(v1)(dp[v1][color[u]]) + sum(v1,v2,c)(dp[v1][c]*dp[v2][c]), where v1,v2 iterates over childs of u, c iterates over all colors on subtree of u, and v1<v2, c!=color[u]. The first term means valid paths start from u, and second term means valid paths start and end in subtree of u. To calculate the value we have dp[u][c]=sum(v: child of u)(color[v]==c) (if c!=color[u]), dp[u][color[u]]=1, we can maintain imformation in std::map and merge them small-to-large.

22:35 is not too unacceptable for East Asian users. There are only 48 active users from Australia, and only 4 div1 users, because contest time is 01:35 for them.

Let's prove this by induction. Situation for k==1 is obvious. First, the intersection of several simple paths in a tree is empty or a simple path. Therefore, for any M>0, S(M):={j: mask[j]==M} is empty or a simple path. Then when we add a the k-th path, if S(M) is contained in the new path, then S(M) will become empty (and S(M|(1<<k)) will become previous S(M)). If S(M) have no intersection with the new path, it will remain unchanged. Otherwise, S(M) will have intersection with the new path but not contained in it, and this can only occur at two ends of the path. Therefore, the number of different values of mask[j] can increase by at most 2 when we add each new path.

The easiest div2 contest I've ever seen (but understanding problem statements is harder than solving them).

A: max(a[i])-min(a[i])

B: If you color cells (1, 1), (1, 2), ..., (1, n), (n, 2), (n, 3), ..., (n, n-1) by this order, you color 2 new diagonals for each cell. And coloring (n, 1) and (n, n) will fill last 2 diagonals. So the answer is ceil(k/2) if k<4*n-2, 2*n if k==4*n-2.

C: Suppose you place a bet of t[i] coins if you've lost i times in a row (0<=i<=x), in order to make the number of coins increase, we must have k*t[i]>t[0]+t[1]+...+t[i] for each 0<=i<=x, and t[0]+t[1]+...+t[x]<=a. So we can calculate t[i] greedily: t[i]=floor((t[0]+...+t[i-1])/(k-1))+1.

D: We consider 2 types of good set: First, assume we take node 1 as root, and for any two different nodes (u, v) in the set, u is not the ancestor of v. In this case, we can calculate the number of valid sets by dp: dp[u]=1+prod(dp[v]), where v iterates over all childs of u, and the number of sets of the first type is dp[1]. Second, assume there exist nodes (u, v) such that u is the ancestor of v. In this case, the set must be contained in the subtree of u, and if we remove u from the set, there will be exactly one child of u, such that the set is contained in the subtree of that child. For each edge (u, w), there are dp[w]-1 sets of second type(we need -1 because {u} is already counted as first type).

E: Let mask[j] = the set of paths that the j-th edge is contained in. We can calculate them by brute force in O(n*k). In fact, there can be at most 2*k different values of mask[j]. Then we let dp[mask]= the minimum number of edges we need to color paths in mask, then we have dp[0]=0, dp[mask]=min(1+dp[mask&(~ t)]), where t iterates over all values of mask[j]. Then we can solve the problem in O(k*(n+2^k)).

F: First turn the binary tree into an array by pre-order traversal, and prepend 1 at the front and append C at the end of the array. Then for each maximal block of consecutive -1 in this array, let L be the number before this block, R be the number after this block, and t be the length of this block, we need to fill this subarray by t numbers within [L, R] and sort them in non-decreasing order. By a well-known conclusion, there are C(R-L+t, t) ways to do this. Because sum(t)<=n, we can calculate it directly and solve the problem in O(n).

https://mirror.codeforces.com/blog/entry/122539?#comment-1087689

First, these ranges are considerd circular, which means for [L, R] when R<L, this range is the union of [L, n] and [1, R]. To solve this issue we can turn in into [L, R+n], and for any other range [L2, R2], if L2<=R2, then we check if [L, R+n] contains [L2, R2] or [L2+n, R2+n] (they can't both be contained), and if R2<L2, we check if [L, R+n] contains [L2, R2+n].

Then we turned the problem into this: There are some pairs of (l[i], r[i]), we have some queries in form (L, R), find number of i such that L<=l[i]<=r[i]<=R.

We can solve it by offline: Sort queries by L, and for a certain i, we add 1 to r[i] on time 1, and minus 1 to r[i] on time l[i]+1. Therefore, we add 1 to r[i] between time 1 and l[i]. Then for query (L, R), we find the prefix sum on [1, R] on time L, which will be the answer of the query.

A. Note that if a[1]==1, we will always be able to do some operation if the permutation is not sorted (consider minimum i such that a[i]>a[i+1], because a[1]==1 we have i>1), and each operation will decrease the inversion number of it, so the answer is YES. Otherwise, since we cannot change a[1] by operations, the answer is NO.

B. Consider the beginning B's and ending A's of the string, they can't be moved. So we can ignore them and assume the string begin with 'A' and end with 'B', then the string will be like this: "ABBB | AB | ABBBB | ... | AB", and if we process "ABB...BBB" blocks from right to left (and move 'A' from left to right in each block), we can get ans=len(s)-1.

C. We can assume a[i] is sorted. When we need to choose x indexes such that a[i]>b[i], and choose n-x indexes such that a[i]<=b[i], we need to choose large a[i] and small b[i] for the first type, small a[i] and large b[i] for the second type. So we can assume that a[i]<=b[i] for 1<=i<=n-x, and a[i]>b[i] for n-x+1<=i<=n. Then we need choose x smallest values of b[i] to fill the range [n-x+1, n], and n-x largest values of b[i] to fill range [1, n-x]. To satisfy the inequalities as more as possible, these values also need to be sorted within two ranges. Finally we need to check if the answer we build is valid.

D. If we maintain the total sum T of the array, if s>T the answer is no. Let's assume that s<T for remaining part. Notice that if a[1]==1, all integers in [0, T] are valid, because there must be some i such that sum[1, i]=s or sum[1, i]=s+1, and for the second situation, we have that sum[2, i]=s. For the general cases, Let's assume there are k1 occurences of 2 before the first occurence of 1, and k2 occurences of 2 after the last occurence of 1. (So a[i] is something like " I1: 22222...2 | I2: 1.....1 | I3: 2...2222") Let r=T-2*(k1+k2) be the sum of I2, then similar with cases for a[1]=1, all integers in [0, r+2*max(k1,k2)] are valid (think about subarray I2+I3 or the inverse of I1+I2), and if s>r+2*max(k1,k2), I2 must be contained in the subarray we need (for any subarray doesn't contain I2, it will be contained in I1+I2 or I2+I3), Then we have (s-r) must be even. We can find k1 and k2 by maintaining a set of indexes such that a[i]==1.

E. For each i we let range T[i]=[i, a[i]], then the answer of a[i] will be (a[i]-i)%n — (the number of other ranges contained in T[i]), and we can calculate tha number of ranges by fenwick tree.

F. If sum of s[i] is odd or s[1]!=s[2*n] there's no solution. Otherwise, we can solve the problem in 3 operations. First, Let's ignore s[1], s[2*n] and look about s[2, 2*n-1]. For each even i in [2, 2*n-2], if s[i]==s[i+1], we put "()" on corresponding positions of b, Otherwise we put "((" or "))" instead (because sum of s[i] is even, there will be even occurences of such i, so we can choose "((" for first half and "))" for second half) Then we let b[1]='(', b[2*n]=')' and do the first operation. After that, for all even i in [2, 2*n-2], we have s[i]==s[i+1]. In the second operation, b[1] and b[2*n] are the same with first operation, and we put "()" for 00 and ")(" for 11 this time. Then for all 2<=i<=2*n-1, we have s[i]==0. If s[1]==0, we are done. Otherwise we need the third operation for b="(()()()...())".

A. The answer is max(a[1], a[i+1]-a[i], 2*(x-a[n])), where 2*(x-a[n]) means you need to go from n-th gas station to point x and go back.

B. The operations means you need to choose some segments to add 1 to these segments, and find the minimal amount of segments. Assume a[0]=0 we have ans=sum(max(a[i]-a[i-1],0))-1 where -1 means we don't need to teleport for the first segment.

C. If you choose x[1], x[2], ..., x[k] for operations, the final value of a[i] will be floor((a[i]+x[1]+2*x[2]+4*x[3]+...+2^(k-1)*x[k])/2^k), so in order to make a[i] become equal, we need that max(a[i])-min(a[i])<2^k because x[1] can be chosen arbitrarily.

D. We use binary search for answer, and we need to check if x is a valid answer. Assume we use the spell on the i-th monster, and for j<i, the minimum possible damage it will take is x-(n-i)-(i-j)=x-n+j, which means we must have x-n+j>=a[j] <--> a[j]-j<=x-n. For j>i, the minimum possible damage is x-(i-1)-(j-i)=x-j+1, which means x-j+1>=a[j] <--> a[j]+j<=x+1. And we must have a[i]<=x. Therefore, if we pre-calculate prefix maximum of a[j]-j and suffix maximum of a[j]+j, we can check all i for 1<=i<=n if i-th monster is a valid initial target in O(n).

E. The problem means we need to build a subtree from the initial tree, and take the sum of a[u] for all deg[u]!=2. So we can let dp[k][u]=the answer if the highest node in the tree we build is u, and deg[u]=k. Note that we don't need to distinguish cases where k>=3.

Didn't solve D1C because 1e17+1 is not (ll)1e17+1...... and in test case 3 where sum(r[i])==1e17, my solution took it as sum(r[i])>=(ll)1e17+1

A: We can solve by greedy: Let b[i] be the minimum it can be, which means, if a[i]==b[i-1]+1 then b[i]=b[i-1]+2, otherwise b[i]=b[i-1]+1.

B: For each $$$t \in \bigcup_{i=1}^{n} S_i$$$, assume $$$t \notin S$$$, we can let $$$S = \bigcup_{t \notin S_i}^{} S_i$$$, and take it as a candidate of answer.

C: Observe that if we removed the i-th card, then for j>i we can get max(0, a[j]) score by appropriate order of operations. Assume the most top card we removed is i0-th card, then the answer will be a[i0]*[i0%2==1] + sum(j>i0)(max(0, a[j])).

D: When u is the root, it's useless to do operation on u, and for each other node v, we need to cost (a[parent[v]]^a[v])*size[v] to make a[parent[v]]==a[v]. Therefore, if we let 1 be the initial root of the tree, and u is the parent of v when root is 1, then node v will contribute (a[u]^a[v])*(n-size[v]) to the answer of nodes in subtree of v, and contribute (a[u]^a[v])*size[v] to the answer of other nodes.

E1: We can use 3 operations to swap two numbers in the permutation: [I]*s*[II]t[III] --> [II]*t*[III]s[I] --> [III]*s*[I]t[II] --> [I]t[II]s[III], and do 2 opartions on 1, n will cause no change. Therefore, we can build operation sequences for p[i] and q[i] separately, and if the parity of lengths of them is the same, we can fill (1, n) to operation sequence of p[i] if it's shorter, or fill (1, m) to operation sequence of q[i]. Otherwise, if n is odd, we can add n operations on 1 for p[i], similar for m is odd. If both n and m are even, the answer doesn't exist.

A: If e[i]>=e[1], in order to keep the 1st player to win, we need to set w>=s[i]+1. Therefore, we need to set w=max(i:i>1, e[i]>=e[1])(s[i]+1), and if w>s[1] this value is invalid.

B: We need to choose the cell with minimum cost from every column or from every row. If we choose for rows, the answer is sum(a[i])+n*min(b[i]). If we choose for columns, the answer is sum(b[i])+n*min(a[i]).

C: For each maximal substring with same character of length L, we need to do L-1 operations. So the minimum number of operations is sum(L-1). For each substring we have L choices of the remaining char, and after choosing remaining elements, we have (sum(L-1))! ways to remove other chars. So the answer is prod(L)*(sum(L-1))!.

D: We can calculate the contribution from each bit separately, and now assume a[i]=0 or 1. Therefore, If we let sum[i]=a[1]^a[2]^...^a[i], the answer will be sum(0<=L<R<=n,sum[L]!=sum[R])(R-L), we can get it by simple dp.

E: The maximum number of k is 3. Proof: if we let color[i]=depth[i]%3+1, then for each node, the color of edge to the parent is different from all edges to the childs, and we can identify them by (color[edge to parent]+1)%3=color[edge to child]. Therefore, we only need to check if k<=2. First k==1 is equivalent to parent[i]=1, 2<=i<=n. Otherwise, we can observe that the color of edge to parent must be different from edge to childs, so we have color[parent[i]]=3-color[i] if i>=2. So we can do bipartite coloring for the tree (except node 1), and for i where deg[i]!=2, we can identify the edge to parent (since the count of color[i] will be 1, and the count of 3-color[i] will not be 1). But for i where deg[i]==2, we can't identify edges up and down by just count of colors. So we need to let color[i] be the same for all deg[i]==2. Therefore, we can assume color[i]=1 for them, and find a valid bipartite coloring for each subtree of node 1. If we find someone, we have k<=2.

Thanks for fast tutorial!

What's the O(log(n)^2) solution?

A: The maximum possible mex is min(n, x+1), so we need k<=min(n, x+1). Then when k==x we can let a={0, 1, 2, ..., k-1, k-1, ..., k-1}, when k!=x we can let a={0, 1, 2, ..., k-1, x, x, ..., x}.

B: Let bi=(1<<t). If n is even, then the operation will make the t-th bit of x become 0, and if n is odd, it becomes 1. So if n is even, all operations will make x smaller, and if n is odd, all operations will make x greater. Therefore, we can use every operations or no operation to get the maximum and minimum values of x.

C: If t doesn't occur in a[i], the answer of t is 0. Otherwise, for any i,j with a[i]==t, a[j]>=t, we have b[i, j]==b[j, i]==t, so the rectangle need to contain (i, j) and (j, i), then it contains [j, j]. Therefore, If we denote S={i: a[i]>=t}, the answer of t is 2*(max(S)-min(S)).

D: First assume the i0-th operation has the minimum cost, then we need to perfrom at least floor(k/cost[i0]) operations in total. So we can assume that we perform that many i0-th operations, and we can change them into i-th operation later for i>i0 (which costs cost[i]-cost[i0] coins). Then assume cost[i1]=min(cost[j]:j>i0), then we can change as many as possible i0-th operations into i1-th operation to improve the answer. We repeat this process until there are no better operations or we spent all coins.

E: Let time[t] = the minimum i such that we can get answer t in subarray a[1, i]. For each i, we need to update for every t such that time[t]=i. The naive approach is: for every i<j<=k, we let time[t^mex(a[j, k])] <-min- k. But this approach will be O(n^3). To optimize this solution, during the dp process, we need to keep ptr[m]= the minimum k such that there exist some j, i<j<=k and mex(a[j, k])==m (we can do this by pre-calculating mex[j, k] for all 1<=j<=k<=n). The the dp formula will be time[t^r] <-min- ptr[r].

F: Let balance(t) = the change of the rank of t after sorting. Then we can see for t with same number of digits, balance(t) is monotonic. Therefore we can get the answer by binary search, the time complexity is O((log(n))^3).

A: Arrange b[i] by the reverse order of a[i] so the value of {a[i]-b[i]} will be pairwise distinct.

B: For every pair of symmetrical positions i and j, if s[i]==s[j] then we can let l[i]==l[j]==0 or 1 (make 0 or 2 occurences of '1' in t), if s[i]!=s[j] we need let l[i]!=l[j] (make 1 occurence of '1' in t). If n is odd, we can let l[(n+1)/2]==0 or 1 (make 0 or 1 occurences of '1' in t). Let the number of first kind of pair is a, and second kind of pair is b, the answer is b+2*k (0<=k<=a) if n is even, and b+k (0<=k<=2*a+1) if n is odd.

C: In the first move alice choose x=MEX(S) (the initial MEX of S), and in after moves alice always add the number removed by Bob back, then the final value will be the second MEX of initial S. This is the optimal strategy.

D: If k==1, we can only make b[i]=i. If k>=2, we build a functional grpah from b (a graph with n nodes and add edges (i-->b[i]) for 1<=i<=n), and we only need to check if the size of every cycles in this graph is k.

E2: If n%k==0 we can query for n/k segments of length k. Otherwise, observe that if we let r=n%k and make such queries: query(1), query(1+r/2), query(1+r), we can get the xor sum of segment [1, k+r]. Then we can query for floor(n/k)-1 segments of length k for the remained part.

F: I've tried for random approach but got WA on testcase 24.

A: One of "13" and "31" will be a subsequence of permutation of [1, 9], and both of them are prime.

B: Note that during the operation, the occurence of substring "01" can only be removed but can't be created. Since the first and last character can't be changed, there will be occurence of "01" in both a and b after operation, and they need to occur at the same position, so there must be some position that "01" occurs at this position both in a and b initially. On the other hand, if a[i]=b[i]='0' and a[i+1]=b[i+1]='1', we can do operation (1, i) and (i+1, n) both on a and b, then a and b will be the same.

C: We need to maintain 2 values: pos1 = the leftest possible position such that a[pos1-1]>a[pos1], pos2 = the maximum possible prefix such that a[1, pos2] is sorted. When we process query '0', we need to check if pos1<=length, then let pos2=length-1, and for '1' we need to check if pos2>=length, then let pos1=inf.

D: Suppose we need to make a[1, k] negative and a[k+1, n] positive. For making a[k+1, n] positive and sorted, we need a operation for each k+1<=i<n and a[i]>=a[i+1]. For making a[1, k] negative and sorted, we need a operation for each 1<=i<k and a[i]<=a[i+1], then we need an extra operation on [1, k] multiply by -1. Therefore we can solve the problem by keeping prefix and suffix sums.

E: When solving the problem for a single array, we can solve by greedy: Iterate i from 1 to n, when a[i-k+1, i] is a permutation and doesn't intersect with any subarray we've taken, we take it as a valid subarray. Let dp[i][j] = the answer when we consider arrays of length i and the length of the maximal suffix without duplicate elements is j, cnt[i][j] = number of arrays of length i and the length of the maximal suffix without duplicate elements is j. For 0<=j<k-1, the update is dp[i][t] += dp[i-1][j] for 1<=t<=j, dp[i][j+1] += (k-j)*dp[i-1][j] (similar for cnt[i][t]). When j==k-1, adding the missing number of the suffix with length k-1 will create a new permutation as a subarray, so the answer need to be increased: ans[i][0] += ans[i-1][k-1] + cnt[i-1][k-1], and for 1<=t<k, we have ans[i][t] += ans[i-1][k-1]. Thus we can solve the problem in O(n*k) by using prefix sum for range updates.

You need to try all possible start quests instead of checking for only one start quest.

First time solved G (by guessing) in div1+2 round, and first time got top50 in div1+2 round. I can't wait to see 100+ delta (no FST please).

A: We can record "there are how many online events in total" and "there are how many subcribers are online at most at the same time" during the process, and the first number is the maximum number of subscribers have seen the post, the second number is the minimum.

B: Let q be the inverse function of p, and count there are how many i such that q[i]>q[i+1], we can get the answer. In fact, when we choose x for operation, we let q[x-1]<q[x], and the relations of q[i-1] and q[i] for all i!=x are remained the same. So each operation will decrease #(i: q[i]>q[i+1]) by at most 1.

C: There are n distinct integers in [0, n] (n+1 integers), so there will be exactly one missing number in [0, n]. Let a[0] be this missing number, then each operation will swap a[0] and a[i] for 1<=i<=n, and this will make a[0, n] be cyclic right-shifted (a'[i]=a[i-1] for i>0, a'[0]=a[n]).

D: If there are any row or column with odd cells with domino, there's no solution. Otherwise, we can construct a solution like this: First consider vertical dominos. Because the 1st row contains even cells with domino, and each horizontal (LR) domino has 2 cells in one row, the first row must contain even U-cells (the 1st row can't contain D-cells), and we can color half of them black and half white. Then we colored the 1st row with equal black and white cells, and the D-cells in the 2nd row will also be colored equally (which means 2nd row contains even D-cells). Then because 2nd row must contain even L-cells and R-cells, the 2nd row must contain even U-cells, and we can color them equally again. By induction, we can color all vertical dominos and fill rows equally (Note that vertical dominos will always fill columns equally). Similarly, we can also color horizontal dominos equally.

E: We sort all "start quests" (quests without dependencies) by h[i] and assume we start game by the first start quest (with minimal h[i]). Let dp[i] = the earliest day we can complete quest i (the days are 0-indexed), then the time we complete i-th quest is k*dp[i]+h[i], and the dp formula is dp[j]=max(dp[j], dp[i]+(h[i]>h[j])) for dependency i-->j. Then we need to try to change the quest we start the game. For each start quest, we need to change start time to h[i+1] and change dp[i] from 0 to 1. Of course when we increase dp[i] we need to update dp[j] for all i-->j, but during the whole process, each dp[j] will be increased at most once. So we can update dp[j] by dfs.

F: We solve the problem by check every ranges [i, j] if [i, j] can be remained (we call such ranges valid). First [1, n] is valid. For range [i, j] to be valid, we need a valid range [i, k] where xor_sum[i, j]>=xor_sum[j+1, k], or valid range [k, j] where xor_sum[i, j]>=xor_sum[k, i-1]. If we let high_bit(n) be the highest significant bit of n (example: high_bit(21) = high_bit(0b10101)=0b10000=16), then a >= b is equivalent to (a^b)==0 or (a&high_bit(a^b))>0. The first condition means a==b, and the second means "on the highest bit where a and b differ, a is 1 and b is 0". So [i, j] can be obtained from [i, k] means: there's valid range [i, k] such that xor_sum[i, k]==0, or xor_sum[i, j]&high_bit(xor_sum[i, k])>0. So if we let R_flag[i] = (if there's any valid range [i, k] such that xor_sum[i, k]==0), R_mask[i]=(the bitwise or of highbit(xor_sum[i, k]) such that [i, k] is valid), we can check if [i, j] can be obtained from [i, k] in O(1), and we can check if [i, j] can be obtained from [k, j] by L_flag[j] and L_mask[j] similarly. Thus we can solve the problem in O(n^2).

G: I guessed the answer but don't know how to prove it: build a directed graph with edge i-->a[i], for each connected component, the answer is (prod(deg[u])-sum(deg[u]-1))(prod(deg[v])), where u are nodes on the cycle, v are other nodes.

This problem requires finding a permutation with score exactly equals to k, instead of the maximum possible score.

AK'ed in 82min. The memory limit of E2 might be too tight for me.

A: Obviously two players will press buttons which can be pressed by both players if possible. So we can assume the 1st player has a+ceil(c/2) buttons and the 2nd player has b+floor(c/2) buttons.

B: The problem statement is unclear: "the number of cookie sellers, such that..." can be considered as "the index of the optimal seller to be removed" instead of "how many sellers can be removed to minimize the number of cookies". Back to the solution: For 2 adjacent sellers s[i] and s[i+1], petya will eat ceil((s[i+1]-s[i])/d) cookies from position s[i] to s[i+1]-1. Therefore, if we add 2 unremovable sellers s[0]=1 and s[m+1]=n+1, the number of cookies will be sum(1<=i<=m+1)(ceil((s[i+1]-s[i])/d)), then we can brute force for every removable seller.

C: The maximum score is floor(n/2), which means (1, 2, ..., floor(n/2)) can be values of gcd(a[i], a[i+1]), because if t>floor(n/2), then 2*t>n, but if a[i]!=a[i+1] and gcd(a[i], a[i+1])=t, WLOG assume a[i]<a[i+1], then a[i]>=t and a[i+1]>=2*t, which is a contradiction. On the otherside, the permutation (1, 2, 4, 8, ..., 3, 6, 12, ..., 5, 10, ..., 2*k+1, 2*(2*k+1), 4*(2*k+1), ...) can reach this upper bound.

D: We need to find following values:

pre[t][i]: the maximum size of consecutive block of '1' in the substring s[1, i] if we can flip at most t values.

suf[t][i]: the maximum size of consecutive block of '1' in the substring s[i, n] if we can flip at most t values.

They can be found by two pointers (keeping index i, j and make sure that the number of occurence of '0' in the substring s[i, j] is no more than t). Then for every pair (i, j) such that i<=j, we can take s[i, j] as the maximum consecutive block of '0', let cnt = the occurence of '1' in s[i, j], then L0=j-i+1 and L1=max(pre[k-cnt][i-1], suf[k-cnt][j+1]). We can get a valid pair of (L0, L1) for every pair (i, j), but for each L0 we only need to keep the maximum corresponding L1. Then we can get at most (n+1) different functions f(a)=L0*a+L1, then we can evaluate the maximum values on [1, n] by brute force in O(n*2).

E1: At first we create a tree with only a root node and no value, and a stack containing this root node. Then we can translate queries like this:

"+ x": Create a new node with value x, let the node on the stack top be it's parent. Push this new node into the stack.

"- k": Push the k-th ancestor of the node on the stack top into the stack.

"!": Pop the top node from the stack.

"?": Find the number of distinct values on the path from the root to the node on the stack top.

Using binary lifting we can find the k-th ancestor in O(log(k)), then we can build the tree and get the list of queried nodes in O(q*log(q)), and using dfs to find the answer for all nodes. Then we can solve the problem offline.

E2: To solve the problem online, we need to use persistent segment tree to do update and queries on the history version of an array. However, because the low memory limit of this problem, when using 12 bytes (3 int32 variables for value, left child and right child) for a node of segment tree (there can be O(q*log(X_MAX)) = 2e7 nodes in total), I got MLE for several times. But we can make some observation:

--- Once a tree node has been created, the answer corresponding to this node will not change. So we only need to find answers when doing "+ x" operation.

--- If value x is on the path from root to the parent of new node, the answer will be increased by 1, otherwise remain the same. So we only need to check the existence of a single value, instead of checking the sum on any certain range.

Therefore, we only need to keep 2 pointers to left child and right child (we use -1 as null pointer, which means there's no value exists in the subtree), and the space for a single node of segment tree will be 8 bytes, which fit the memory limit.

A: If a[i]<=a[i+1], then 0 <= max(0, a[i+1]-1) and a[i]-1 <= a[i+1]-1 <= max(0, a[i+1]-1), therefore max(0, a[i]-1) <= max(0, a[i+1]-1), then a[i]<=a[i+1] holds after any times of operation. If a[i]>a[i+1], we need to perform a[i] operations to make a[i]=a[i+1]=0. So the answer is max(a[i]) where a[i]>a[i+1].

B: If n==1 there's no solution, let's assume n>=2. Let t be the number of occurences of 1 in a[i]. If t==0, then we can let a[1]+=n-1 and a[i]-=1 (2<=i<=n). Let's assume t>=1. Then sum(i: a[i]==1)(b[i] — a[i]) >= t because b[i] is positive integer and b[i]!=1, so b[i]>=2. Therefore, sum(i: a[i]!=1)(b[i]-a[i]) <= -t --> sum(i: a[i]!=1)(a[i]-b[i]) >= t --> sum(i: a[i]!=1)(a[i]-1) >= t. So if sum(i: a[i]!=1)(a[i]-1) < t, there's no solution. Otherwise, we can construct a solution: First turn 1 into 2, then we reduce the maximum element in a by 1 for t times. If there's some a[i] remain unchanged, then a[i]>1, then we can reduce them by 1 and add them to any occurence of 2.

C: For any 1<=i<=n-1, let's find the maximum value it can become by binary search. Assume the value we are checking is T. Then we need T-a[i] operations on i-th element. If a[i+1]>=T-1 then we are done. Otherwise, we need T-1-a[i+1] additional operations on (i+1)-th element, Then check if a[i+2]>=T-2. We repeat this process until we find some j such that a[i+j]>=T-j, or we have used more than k operations. Then we can solve the problem in O(n^2*log(k)).

D: We can solve the problem by D&C (Divide and Conquer). Assume we need to find the index of maximum element on [L, R]. If L==R then the answer is L. If L+1==R, we can do query(L, R) and the answer of query is 1 if p[L] is the maximum (0 otherwise). In general cases, we choose M close to (L+R)/2 and solve (L, M) and (M+1, R) recursively, assume their answer be x, y. Then we only need to find if p[x]<p[y]. Let's do query(x, y) and query(x, y-1), the difference of answer of the queries means "there are how many i such that x<=i<=y-1 and p[i]>p[y]". If p[x]<p[y], then we have p[i]<=p[x]<p[y] for x<=i<=M and p[i]<p[y] for M+1<=i<=y, so the difference will be 0. Otherwise we have p[x]>p[y], so the difference will be at least 1. Then we can solve the problem. The cost of queries will be not greater than 2*n^2 for the top layer, 4*(n/2)^2 = n^2 for the second top layer, 8*(n/4)^2 = n^2/2 for the third top layer and so on. So the total cost is not greater than n^2*(2+1+(1/2)+(1/4)+...)=4*n^2.

As a tester, I hope div3 users will enjoy this contest from well-prepared problems.

Maybe we need to use some persistent data structures.

D: Let difference d[0]=a[0], d[i]=a[i]-a[i-1] when i>0. If the missing prefix sum is n*(n+1)/2, then {d[i]} will be a permutation of [1, n] missing one element. Therefore, for this case we need to check in {d[i]} are pairwise distinct and inside range [1, n]. Otherwise, we will have a[n-1]=n*(n+1)/2, and n-2 elements of {d[i]} will be inside [1, n] and distinct, the last element will be the sum of 2 missing elements. So for this case we need to check if {d[i]} contains n-2 different numbers inside [1, n].

E: First for potions with infinite supply we can just set their cost to 0. Then, if potion i can be obtained mixing {j[1], j[2], ...}, we add a directed edge (j[t] --> i) for each j[t]. Since no potion can be obtained by mixing itself, these edges will from a DAG (directed acyclic graph), and we can run dp on the topological order of the DAG: Let dp[i]=sum(cost[j]) where edge (j --> i) exists, and cost[i]=min(cost[i], dp[i]).

F: If a[i], a[j] and x have only 1 bit, then if a[i]==0, a[j]==0, we can set x=1 then (a[i]^x)&(a[j]^x)=1, if a[i]==1, a[j]==1, we can set x=0 then (a[i]^x)&(a[j]^x)=1, if a[i]!=a[j], no matter how we set x, (a[i]^x)&(a[j]^x)=0. So we need to find (i, j) such that a[i]==a[j]. For general cases, we need to minimize (a[i]^a[j]) so that sum(t: 0<=t<k, the t-th bits of a[i] and a[j] are same)(1<<t) = (1<<k)-1-(a[i]^a[j]) is maximized. This can be processed using a trie, or sort a[i] and find the minimal a[i]^a[i+1].

G: For a single query (a, b, e), the maximum height of nodes on the path cannot exceed h[a]+e, which means, we can pass an edge (u, v) if max(h[u], h[v])<=h[a]+e. Therefore, we can sort queries by h[a]+e and sort edges by max(h[u], h[v]), then solving queries using dsu.

These cases can be found by setting (s, k) <-- (s+s%10, k-1) for 4 times, and each time we found the answer assuming we will use 4*t additional operations.

A: If the parity of x+y is same as any x[i]+y[i], then Vika will be caught. Otherwise, Vika will not be caught.

B: For each color we record their positions. For a certain color t, we list all positions with this color, and add 0 to the front of the list and n+1 to the back, and calculate the distance of adjacent positions. For the largest distance D, we can add a position with color t between them to make D-> floor(D/2), ceil(D/2), and (the maximum distance — 1) will be the answer for this color. We can look for all colors and take the minimum answer.

C: If a[i]=b[i]=0, they will always be zero (and this pair can be ignored), Otherwise, they will go into some circulation like (k,k,0,k,k,0,...) with period of 3, so we can find t[i]%3 where t[i]=the number of operations to make (a[i], b[i]) into (0, k). We can find t[i]%3 recursively: For (k, k) return 2, for (k, 0) return 1, for (0, k) return 0, for (a, b) where a>=2*b solve for (a%(2*b), b) recursively (because (a, b) --> (b, a-b) --> (a-b, a-2*b) --> (a-2*b, b)), otherwise let (a, b) <-- (b, abs(a-b)), solve recursively and add 1. Thus we can solve in O(n*log(max(a, b))).

D: If s%10==0, then s will not change in the 2nd operation, so the answer is s*k. If s%10==5, then s will become s+5 after any positive number of 2nd operations, so the answer is max(s*k, (s+5)*(k-1)). Otherwise, s%10 will go into the (2 --> 4 --> 8 --> 6 --> 2) circulation, and each time of loop will make (s, k) <-- (s+20, k-4). So we can do (s, k) <-- (s+s%10, k-1) for 4 times, each time we look for the maximum value of f(t) = (s+20*t)*(k-4*t) where t>=0. (We don't need to consider the case for 4*t>k because f(t) will be negative) This value can be found using ternary search in O(log(k)), or in O(1) by setting t0=max(0, (5*k-s)/40) and check f(floor(t0)) and f(ceil(t0)).

E: The answer is the number of odd divisors of X, so we can solve the problem using prime sieve, and for each odd prime factor p, we make cnt[p]++ and ans=ans*(cnt[p]+1)/cnt[p]. But since modular number M can be small, sometimes cnt[p] will be the mutiple of M and can't be inversed. So we need to record the number of p such that cnt[p]%M==0 and process case for cnt[p]%M==M-1, cnt[p]%M==0 separately.

F: We can solve for each bit of a[i] and take the maximum answer. Now assume a[i]<=1 and we can use bitset to store it. We can find that after 2^t operations a[i] will become a[i] xor a[i+2^t], so we can find the number of operations to make a[i]=0 by binary search, using shift operations of bitset. Thus we can solve the problem in O(n*log(n)^2*log(max(a[i]))/w). But this is hard to pass the time limit. But if we doing binary search like what we do for binary search on the fenwick tree or finding LCA by binary lifting, we can solve in O(n*log(n)*log(max(a[i]))/w).

I guessed the solution of E but don't know how to prove it.

For (i, j) such that 1<=i<=n-1, 1<=j<=m-1, we must have (i, j)==(i+1, j+1) (we denote a[i][j]=0) or (i+1, j)==(i, j+1) (we denote a[i][j]=1), then for any valid grid, there must be some f[i] and g[j] such that a[i][j]=f[i] xor g[j]. Then we can solve the problem by dsu.

GuessForces

AC'ed E 47s after the contest ended. My contest ruined by the corner case for [L, R]=[1, n].

You should output the index of the mimic directly after find it, instead of removing other objects and output 1.

E: n is valid if there exist k>=2, r>=2 such that 1+k+k^2+...+k^r==n. Since k^r<n we have r<log(n), so we can check for all values of r and find k by binary search, we can solve a single case in O(log(n)^3).

F: We remove no object for 1st and 2nd queries, and the mimic must change it's type during first 2 queries, so there will be exactly one t that the number of occurence of type t increased. Then we can remove all objects with type other than t in the 3rd query, then the types of all objects will be same, and mimic will not be removed. Then the mimic will change its type in the 4-th or 5-th query and we can find it easily.

G: We can build a graph with 2^n nodes (representing every possible subset of symptoms) and 2^n*m edges using bitmask, and solve the problem by dijkstra shortest path.

For this problem we can use dsu instead.

A: Sort the array of {a[i]-a[i-1]} and choose n-k minimum elements.

B: Let A=a[1]&a[2]&...&a[n]. If A>0, then for all 1<=i<=n we have a[i]>=A, so if there are more then one groups, the bitand of each group will be at least A, and the sum will be at least 2*A > A, so there can be only one group. If A==0, we can build groups greedily from left to right (by choosing the minimal prefix of remaining elements with bitand==0).

C: By trying for some small cases we can find that all possible values of strength are the xor-sum of some ranges [L, R], we can find them in O(max(n^2, n+(2^8)^2)) = O(2^8*n).

D: For numbers in [L1, R1] we let a[L1]=1, a[L1+1]=2, ..., a[R1]=R1-L1+1, because s[L1] is the first element appears in t, s[L1+2] is the second element appears in t, and so on. For numbers in [L2, R2] and not in [L1, R1] we assign values to a[i] by the order s[i] appears in t. Using an ordered set we can process all m ranges in O(m+n*log(n)). Assume there are k numbers in any range [L, R]. For answering queries, let's assume there are x occurences of 1, then for all i such that a[i]<=min(x, k), we need do operations to make s[i]=1. Then we can answer the queries by fenwick tree.

E: untested problem.

F: If we let b[i]={a[1], a[2], ..., a[n], a[1], a[2], ..., a[n]}, then we can see all values appear in {a[n+1], a[n+2], ...} are some range-bitor of b[i], and for ranges with same right bound and same value of bitor, we only need to keep the smallest range. For each right end, there are most log(max(a[i])) different values of range-bitor, and we can find them by sparse table and binary search, so we can solve the problem in O(n*log(n)*log(max(a[i]))).

How Does checker of problem C work?

In most contests of CF you don't need to worry about stack overflow when n<=2e5

We need to lift u to LCA(u, v), and lift v to the child of LCA(u, v).

E: We let t[x]=inf initially, and if we a[x]=1 on the i-th query, we let t[x]=i. Then if the segment [L, R] become beautiful at the i-th query, i will be contained in t[L, R], and there will be at least floor((R-L+1)/2) elements smaller than i. so after we sort t[L, R] increasingly, the (1+floor((R-L+1)/2))-th element will be i. So we can solve the problem by range query for k-th minimum element on t[1, n]. We can answer the queries by Mo's algorithm, in which we need to maintain a subset of [1, q]. Using sqrt decomposition we can add/remove an element in O(1) and query k-th minimum in O(sqrt(q)), so we can solve the problem in O(n*sqrt(m)+m*sqrt(q)).

F1: Assume the minimum sum of weight over all subsegments of path (u, v) is m, and the maximum sum is M. Then if sum(L1, R1)=m, sum(L2, R2)=M, when we change the subsegment (L, R) from (L1, R1) to (L2, R2) by extending or reducing the length by 1 each time, the sum of weight will be increased by -1 or +1 each time, so the sum of weight can be any integer between m and M. Therefore, we only need to find m and M for path (u, v). When u=1, we only need to check for path (1, v). Let p be the parent of p, define M(v)=the maximum sum of weight over all subsegments of path (1, v), suf(v)=the maximum sum of weight over all suffixs of path (1, v), we have suf(v)=weight(v)+max(0, suf(u)), M(v)=max(M(p), suf(v)). Similarly we can calculate the minimum sum m(v).

F2: When u can be any nodes on the tree, we need to look for what if we concatenate 2 paths. Let M=the maximum sum of weight over all subsegments, suf=the maximum sum of weight over all suffixs, pre=the maximum sum of weight over all prefixs, sum=the sum of weight over all nodes on the path. Then if we denote (L, R) be the concatenation of path L and R, we have:

(L, R).sum=L.sum+R.sum

(L, R).M=max(L.M, R.M, L.suf+R.pre)

(L, R).pre=max(L.pre, L.sum+R.pre)

(L, R).suf=max(R.suf, R.sum+L.suf)

So we can merge information of any 2 paths. Therefore, we can solve the problem by binary lifting: Let infos[r][u] be the information of the path from u to the (2^r-1)-th ancestor of u, and parent[r][u] be the (2^r)-th ancestor of u, we can find LCA(u, v) and merge path from u to LCA(u, v) and the reverse of the path from v to the child of LCA(u, v).

D1B ?????? Is this round tested?

A: The number of occurences of -1 should be even and not greater than n/2.

B: From the first different digit of L and R from the highest digit. Let L=a1*10^m+a2 and R=b1*10^m+b2 where a2,b2<10^m, we can let 0-th to (m-1)-th digits of L become 9, and corresponding digits of R become 0. Then the answer will be at least abs(a1-b1)+9*m. We can see this is also the upperbound of the answer.

C: We can see that for Bob, reversing S and reversing T are equivalent, so Alice only need to make S==T or S==reverse(T). If Alice make k changes to transform S into T, the game will end at (2*k-1+(k+1)%2)-th turn, and if Alice make k changes to transform S into reverse(T), the game will end at (2*k-(k+1)%2)-th turn — but there's a special case: if k==0 the game will end at 2nd turn.

D: Define f(i,j) be the size of [l[i], r[i]][l[j], r[j]] (which denotes the set of numbers contained in [l[i], r[i]] but not in [l[j], r[j]]), then for any two students i, j, the difference of there height will be not greater than 2*max(f(i, j), f(j, i)). Therefore, we need to calculate max(f(i, j)) over all pairs of (i, j). We need to consider 2 cases: range i is contained inside range j, and otherwise. For the first case, we need to sort all ranges by their left-end, and for 1<=i<=n checking max(r[j]-l[j]) where l[j]<=l[i], and calculate (r[j]-l[j])-(r[i]-l[i]). For the second case, we need to check min(r[j]) where r[j]<=r[i], and calculate r[i]-max(l[i]-1, r[j]).

E: Note if p is a prime number or 1, and p is in the set of lcm, p must occur in a[i], so the answer will be at most p[n] (the n-th prime number). And for each i, the number of different values of lcm(a[j], a[j+1], ..., a[i]) below p[n] is at most log(p[n]), so we can check these values by maintaining the set L[i]={lcm(a[j], a[j+1], ..., a[i]) : 1<=j<i} in O(p[n]+n*(log(p[n]))^2) for checking n*log(p[n]) values and calculating lcm in O(log(p[n])).

F: The answer of a single query is the number of indexes i such that p[i]<i. Since there are at most 2*n different status of the array (n shifts of a[i] and n shifts of reverse(a[i])), we can pre-calculate all of them using fenwick tree.

We only need to check the maximum index k where r[k]<min(l[i],l[j]).

A: If n>=5, Alice can combine n-2 ones to make the array {1, 1, n-2}, and Bob can only make it into {2, n-2} then Alice wins. If n<=4, Bob always wins.

B: A beautiful array need to be increasing, or there's an index i where a[1, i] and a[i+1, n] are increasing and a[n]<=a[1]. Therefore, we first need to check whether the queried x[i] is not smaller than the last appended element. When the first time we meet such x[i] doesn't satisfy the condition and x[i]<=x[1], we need to accept it, but we can't accept numbers where x[i]>x[1] from now on.

C: To solve this problem we need to pre-calculate 5 arrays sum[t][i]: the contribution of s[1, i] if s[i+1]==t and s[i+2, n] doesn't exist. We calculate it by the following process: First let cnt[u]=0 where 'A'<=u<='E'. When we see s[i]<t, we let sum[t][i]=sum[t][i-1]-10^(s[i]-'A') directly, since the contribution of s[i] will always be negative. Otherwise, we need to check for u where t<=u<s[i]: We let sum[t][i]-=2*cnt[u]*10^(u-'A') and cnt[u]=0, which means contribution of occurences of u changed from positive to negative. Finally we let cnt[s[i]]+=1. After we calculate the arrays, the problem can be solved by trying every possible change of s[i].

D: We sort ranges by r[i] increasingly and run dp: dp[i]=the maximum number of valid pairs for first i ranges after sorted. The transition is dp[i]=max(dp[i-1], dp[left(i,j)]+1) where j<i, r[j]>=l[i] and left(i,j) = the maximum index k where r[k]<min(l[i],l[j]).

E: Each row is divided into several segments by black cells. By greedy method we want to fill numbers in longer segments (since a consecutive segment of white cells with length k can contribute k-1 to the answer), so we need to calculate for each k, how many segments of length k in the matrix. If we scan the matrix from up to down (from n-th row to 1st row), we can see if a[j]=i, then there's a white segment being cut at position j when we scan to the i-th row. So we can let cnt[n]=n and cnt[t]=0 (1<=t<=n-1) at the beginning, when we scan to the i-th row, we cut segments at position j for all a[j]=i. When we remove a segment of length k, we let cnt[k]-=i, and when we add a segment of length k, we let cnt[k]+=i. We can store these segments by an ordered map. Finally we check segments from length n to length 2, and fill them to get the answer.

We make 500 random querise and let M = the maximum answer returned. Since a[i] is fixed initially, n>=M + 62500 means that for all 500 random queries (which will return a random integer in [1, n]) return a value <= n-62500, so the probability is ((n-62500)/n)^500 = (1-(62500/n))^500, when n<=10^6 we have 1-(62500/n) <= 0.9375, so (1-(62500/n))^500 <= 9.67e-15.

The number of a[i] is fixed initially, so if we make random queries, we will get random numbers uniformly distributed in [1, n], and if we take the maximum value we get, it will be pretty close to n, so we can reduce the number of candidates of answers.

A number which is close enough to n.

F: We denotes dp[t][i][j]=1 if we can arrive position (i, j) at time t, 0 otherwise. The initial status is dp[0][0][0]=1, and transition is dp[t][i][j]=dp[t-1][i-1][j] || dp[t-1][i][j-1] || dp[t-1][i][j]. And in each second we need to clear positions shot by railguns. We repeat this process until dp[t][n][m]=1 or for all (i, j) we have dp[t][i][j]=0. The complexity is O(n*m*(n*m+r)).

G1: We can solve the problem by sqrt decomposition: First, we use 1000 queries to get a[1], a[2], ..., a[1000]. If there are any value occurs more than once, we have n<1000 and get the answer. Otherwise, we have n>=1000. Now we can use another 1000 queries to get a[2000], a[3000], ..., a[1001000], we must return to some position in [1, 1000] at some time.

G2: The constraint n<=10^6 is too large for 1000 queries, but how can we solve this problem if we've known that M<=n<M+62500 (=M+250^2)? Well, we can use similar strategy: First use 250 queries to get a[1], ..., a[250], if n<250 we can get the answer. Otherwise, first we assume M<=n<M+250, and we query for a[M+250]. If M<=n<M+250, then 1<=M+250-n<=250, that means we will return back to [1, 250] and we can get the answer. Otherwise, we can assume M+250<=n<M+500 and query for a[M+500], then assume M+500<=n<M+750 and query for a[M+750], and so on. Finally we will solve the problem within 500 queries. So how can we use other 500 queries for finding M? Well, we only need to make 500 random queries and take the maximum value of answers. The probability that maximum value is not greater than n-62500 is ((n-62500)/n)^500, when n<=10^6 this probability is no more than 10^-14, therefore this method will pass 1000 testcases for probability >=(1-10^-11), so it's safe enough.

A: We can only create non-negative new numbers, so if there's any negative number, output it. Otherwise all numbers are non-negative, since for any a,b we have abs(a-b)<=max(a,b), the maximum number of the list will not increase during the process, so we can output the maximum value.

B: If the permutation is something like [..., 1, ..., n, ..., 2, ...] or [..., 2, ..., n, ..., 1, ...], there are only 2 subarrays which is permutation ([1] and the whole array), since any subarray containing 1 and 2 will also contain n. And by checking for cases with n=3 we can see that we always can swap 2 elements of 1, 2, n to reach this lower bound.

C: If m is even, we can arrange the matrix like:

1 2 3 ... m

m+1 m+2 m+3 ... 2*m

2*m+1 ... 3*m

...

where absolute differences are 1 and m (since m>=4 and m is even, m is not a prime).

We can transpose this construction to solve for n is even.

If both m and n are odd, we can construce the last column like: [m, (n+3)/2*m, 2*m, (n+5)/2*m, ..., n*m, (n+1)/2*m], since n>=5 absolute differences of them are mutiples of m and not less than 2*m, so they are not prime. Then we fill other columns by ans[i][j]=ans[i][j+1]-1.

D: First the length of a walk will have the same parity of n, so if n is odd all answers will be NO. Also the first char of the walk will be s[1] and the last char of the walk will be s[n], so we must have s[1]=='(' and s[n]==')'. Otherwise, we need to look at occurences of "((" and "))" in the string. If their are no such occurences the answer is YES. Otherwise, consider the first occurence of them: the prefix contain the first occurence will be something like "()()...()((..." or "()()...()*)*...". For the second situation there's no solution, because when the first time we walk to * ) * the prefix sum will be -1. So the first occurence of "((" must be before the first occurence of "))". Symmetrically, the last occurence of "((" also must be before the last occurence of "))". If both conditions are satisfied, the answer is "YES" because the string will be something like "()()...()*((*...*))*()...()()", and we can walk back and forth on * (( * and * )) * to make the sequence regular.

E: Consider the subsequence in b[i] which is same as a[i] and has the lexical minimum sequence of indexes (that means, we find the first occurence of a[1] in b[i], and find the first occurence of a[2] on the right of a[1], and so on). Then numbers before a[1] cannot be a[1], numbers between a[1] and a[2] cannot be a[2], ..., numbers between a[n-1] and a[n] cannot be a[n], and numbers after a[n] can be anything. So let t=the position of a[n] in b[i], the answer will be sum(t=n...m)(C(t-1,n-1)*(k-1)^(t-n)*k^(m-t)), since m<=1e9 we need some mathematical tricks to calculate it.

A: For each 0<=i<=n, there are at least ceil(i/k) ones on the prefix with length i, and ceil((n-i)/k) ones on the corresponding suffix, therefore ans>=ceil(i/k)+ceil((n-i)/k). We can solve the problem by brute force for 0<=i<=n.

B: Let's denote S[k]={1<=i<=n: a[i]==k}. For each integer k, we can get points from at most k lamps in S[k], because all lamps in S[k] will break simultaneously, and there we can turn on no more than k lamps in S[k] before they break. So we can classify lamps by a[i], and choose min(k,S[k].size()) lamps with maximum b[i], then we can get an upper bound of the answer. In fact, this answer is also a lower bound: If we turn on the chosen lamps by the non-decreasing order of a[i], because lamps with lower a[i] will break strictly before lamps with higher a[i], they will not make lamps with higher a[i] break before turned on, so we can get points from all chosen lamps. Therefore we can solve the problem in O(n).

C: By induction we can prove that the last element of a is 0.

So if b[n]=1, there's no solution. Otherwise we can construct a solution: First we let ans be an empty list. Then we read b[i] reversely: Let i be the largest index such that b[i]=1 and b[i+1]=0, we can assume there's an operation with p=i+1, so we append i+1 to ans and filp elements on [1, i]. If there's no such i, we end this process, append zeros to make ans.size()==n and reverse it as the answer.

D: Let [L1, R1], [L2, R2], ..., [Lm, Rm] be the ranges of indexes which has been moved in operations, then other indexes must form an increasing subsequence, and we must add a 0-ball in each [Li, Ri]. Therefore, we can solve an another problem: We can remove at most k subarrays from c[i] to make it increasing, minimize the number of elements removed. We can solve this problem by naive O(n^3) dp.

E: For any subset of {1, 2, ..., n}, we denote it S1 and it's complement S2, if sum(i in S1)(a[i])=sum(i in S2)(a[i]), then the second player can win the game: If the first player choose i in S1, the second player choose j in S2, and vice versa. We can see by this strategy sum(S1) will always be equal to sum(S2), so the first player has valid move in S1 --> sum(S1)>0 --> sum(S2)>0 --> the second player has valid move in S2. Therefore, the second always has valid move before the first player lose the game. If there're no such S1 with this property, the first player will always win: Assume for all subset S1 we have sum(S1)!=sum(S2) before a turn, and assume indexes chosen in this turn are i, j, WLOG assume a[i]>=a[j]. Then if there sum(S1)==sum(S2) after this turn, if i belong to S1, then we can assume j belong to S2(because a[i]>=a[j] before this turn, we have a[j]==0 after this turn, so move it from S1 to S2 will not change sum(S1)-sum(S2)), then we have sum(S1)==sum(S2) before this turn, which is a contradiction, so for all subset S1 we have sum(S1)!=sum(S2) after this turn. If the first player lose the game, when there's 2 positive elements in a[i], assume they are i1, i2, then we have a[i1]==a[i2] so that first player has no valid move in next turn. But in this case if we let S1={i1} then sum(S1)==a[i1]==a[i2]==sum(S2), which is a contradiction, so the first will always win the game.

Perhaps this line is wrong:

tc = (dis[b[j].S][b[i].S]-coins[j])%b[j].F;

I've got AC by change the code like this (submission:207504840):

ll dp_inc = (dis[b[j].S][b[i].S]-coins[j]+b[j].F-1)/b[j].F;
td = dp[j] + dp_inc;
tc = coins[j] - dis[b[j].S][b[i].S] + dp_inc * b[j].F;

If a pair of position is -1 -1, then we can put the team with larger number on the left or right of this pair, so each pair gives us 2 options. Otherwise, which number will be larger is determined in this pair.

Solved A-E and passed pretest of F in 3899ms (which will be TLE in system test).

A: If x%k!=0, we just need to move by x, otherwise since k>=2 we need to move by x-1, and then move by 1.

B: Consider the longest maximal block of same symbol, let it's length be k. Then If we put 1 at every local minimum and k+1 at every local maximum, we always have enough numbers from 2 to k to fill other positions.

C: We can see that a consecutive block of same numbers (0 or 1) plays the same role as a single number, and more blocks takes more operations to sort the string. Therefore, we can fill '0' into a block of '?' between '0' and '0', fill '1' between '1' and '1', and fill '0' or '1' between '0' and '1'. For these blocks at the front or the back of the string, we can assume that there's an additional '0' at front and '1' at back of the string, which won't affect the answer.

D: For any beautiful sequence the number of occurences of '(' and ')' will be the same, so if they are not the same we can simply output -1. Otherwise, there must be a solution with k<=2. In fact, we can record the prefix-sum of the string (assume '('=1, ')'=-1) and change color whenever the sign of the prefix-sum changes, then brackets with non-negative prefix-sum will form a regular sequence, and other brackets will form a reversed regular sequence.

E: We can see that teams of number [2^(k-1)+1 , 2^k] will lose in the first round, teams of number [2^(k-2)+1 , 2^(k-1)] will lose in the second round, and so on. So in the first round, we check 2^(k-1) pairs of adjacent positions, and each pair must contain a team with number larger than 2^(k-1). If any of such a pair contains 2 numbers > 2^(k-1) or 2 numbers <= 2^(k-1), there's no solution. Otherwise we have 2^a*(b!) ways to arrange teams of number [2^(k-1)+1 , 2^k], where a=(how many pairs of positions are both undefined), b=(how many pairs of positions contains no teams with number > 2^(k-1) ). Then we can eliminate teams with larger number in every pairs, and solve the problem recursively.

F: I tried to solve it by segment tree and ternary search in O(n*(log(n))^2), but it takes too long times to pass the system test. Maybe there will be solution with smaller constant.

Solved A-E. But it seems that the number of accepted solutions of F is far less than it should be.

A: Let n be the length of string s, then we only need to check first floor(n/2) chars of s. If they are all the same, we can't get any another palindrome. Otherwise we can choose 2 different chars from them and swap them (and chars on the symmetric positions on the right half) to get another palindrome.

B: Sort the array and calculate the prefix-sum. Assume we use the 1-st operation for t times, we will remove 2t elements from the front and t elements from the back of the array. We can try all possible options of t from 0 to k to get the answer.

C: First we can remove all adjacent elements with equal value, and the contrast value will remain the same. Then we only need to remain local maximum and minimum elements of the array (including the first and the last), since if a < b < c or a > b > c we have |a-b|+|b-c|=|a-c|.

D: If k<=n, we can add values from 1 to k on different elements of the array. But if k>n, some values from 1 to k will be subtracted from the array. To make the numbers subtracted be as small as possible, the increments of each operation will be like this: 1, -2, 3, -4, 5, -6, ..., k-2, k-1, k (there are n or n-1 positive values on the back of this sequence, depending on the parity of k-n), then we need to subtract 1 from any values of the array for ceil((k-n)/2) times, and add inc=(k-2*ceil((k-n)/2)) values (from k-inc+1 to k) to different values of the array. To simulate this process, we need to sort the array, and add k+1-i to a[i] for 1<=i<=inc, and find the minimum of the array (we can do this fastly by pre-calculating prefix-minimum of a[i]-i and suffix-minimum of a[i]), then do the subtract operations on some maximum values of the array.

E: The prefix-sum of a[i]:

a[1], a[1]+a[2], a[1]+a[2]+a[3]...

The prefix-sum of the array above:

a[1], 2*a[1]+a[2], 3*a[1]+2*a[2]+a[3]... (which is b[i] when k=1)

The prefix-sum of the array above:

a[1], 3*a[1]+a[2], 6*a[1]+3*a[2]+a[3]... (which is b[i+1] when k=2)

The prefix-sum of the array above:

a[1], 4*a[1]+a[2], 10*a[1]+4*a[2]+a[3]... (which is b[i+2] when k=3)

By this pattern we can solve the problem in O(n*k) by calculating the prefix-sum for k+1 times.

How to solve d1C? It's the hardest d1C I've seen in real contest.

so the total time complexity would be O(n2m/64)
, which is fast enough.

So why my solution of E 204620376 got TLE?

Update: Now I optimized it in 204648297

A: Brute force for all possible numbers of liars from 0 to n.

B: To make a[1]%x==a[n]%x we must have x is a divisor of abs(a[1]-a[n]). So the answer is the gcd of abs(a[i]-a[n+1-i]) for 1<=i<=n/2.

C: If m is a divisor of n, m can remain the same after voting, otherwise m must be decreased. So if m < the minimal prime factor of n, m will be decreased to 1.

D: Let the indexes of sights we pick are i, j, k from left to right, then definately we will let L=i, R=k. So we just need to find the minimum of b[i]+b[j]+b[k]-(k-i)=(b[i]+i) + (b[k]-k) + b[j], where i<j<k. We can do this by pre-calculating the prefix-maximum of (b[i]+i) and the suffix-maximum of (b[k]-k).

E: If model u can be ordered before model v, for all i we have r[i][u]<r[i][v]. So we can build a DAG (directed acyclic graph) in O(m*n^2), and we can solve the problem by toposort and dp. Naive approach will get TLE and we can optimize this solution to O(m*n^2/w) by bitset, which could pass the pretest (and hopefully system test).

PS: Is there any O(m*n) solution of E? I think there must be something faster than O(m*n^2) but I can't come up with it.

By the constraints of the problem, the d-th coefficient a[d]!=0. If the highest term of p(x) is a[d]*x^d, then the highest term of the difference of p(x) is d*a[d]*x^(d-1). Therefore, the first coefficient of (d-1)-th order difference is a[d]*d!, which is non-zero modulo 998244353.