Codeforces Round 1003 Discussion Stream (with Hints)

Find the length n of the string, and then print first n-2 chars and then i.

Let n be the length of the string. Answer is either 1 or n

If there exists adjacent 2 equal chars, we can reduce the string to length 1. The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent equal chars.

Greedy. For each i, try to find a minimum value of ai which we can get and it is still sorted.

If K is the minimum possible value of a_{i-1} we can get such that the array is still sorted.

If we do not do any operation the value remains ai. This is possible only if K <= ai

If we do an operation then bj — ai >= K, this imples aj+K <= bj. So chose the minimum bj >= aj+K, and do an operation using it.

Score of an array is sum of prefix sum of the array. For an index idx = i*m+j, S_{idx} = sum of first i-1 arrays + sum of first j elements of ith array.

Try to find both of these values separately.

Contribution due to part 2 is sum of score of all arrays.

Let C = [sum(a1),sum(a2),sum(a3),…,sum(an)] Let S = maximum score we can get after rearranging C. Then contribution due to part 1 is m*S

max(x-y,y-x) is equal to abs(x-y) First try to find trivial -1 cases.

Look at the complete string first. The score is abs(n-m). If this is more than K, then maximum balance among all substring is more than K.

If n<k and m<k, then balance can never be equal K.

Otherwise the following string works for N=10, M = 11, and K = 3

111 000 111 000 111 000 11 0

If an array has a majority element, then there must exist a subarray with length 2 or 3 with that element being majority.

The problem reduces to checking length 2 and 3 paths.

Length 2 paths are just edges.

For length 3, you can fix a middle element and check if 2 adjacent elements contain same value.

There arent many cases when lcm is semi prime.

If p and q are different prime nos, then their lcm p*q is semi prime.

Otherwise, one of the element must be semi prime, and other one must be its factor.

f(t) can also be written as 1 + no of adjacent different chars.

Lets look contribution due to si and sj being adjacent. If si==sj, they add 0 to score. If si!=sj, then they add 1 to score. No of subsequences that contain si and sj adjacent are pow(2,i-1)*pow(2,n-j), basically,

• For char before i, we have 2 choices we can take them or ignore them.
• For char after j, we have 2 choices we can take them or ignore them.
• We must take i and j
• We must not take chars between i and j

Now, the hard part, how to do it with changing chars? Use Segment tree.

For each node representing s[i…j], we can maintain -

• Sum of pow(2,i-1) when si = 0
• Sum of pow(2,i-1) when si = 1
• Sum of pow(2,n-j) when sj = 0
• Sum of pow(2,n-j) when sj = 1
• Contribution due to pairs inside this segment