E can be solved in $$$\mathcal{O}(np + \text{poly}(p))$$$ with min-cost flow: 72472865.

We for sure will have the $$$k$$$ most valuable audience members fill some positions. Initially have them fill the audience-positions, then move to fill the other positions in the team. The candidates for position $$$j$$$ in the team are

1. The $$$p$$$ among the top audience members with maximum $$$s_{i, j} - a_{i}$$$
2. The $$$p$$$ among the top $$$p + k$$$ audience members, not in the top $$$k$$$ audience members
3. The $$$p$$$ not among the top $$$p + k$$$ audience members with maximum $$$s_{i, j}$$$

Breaking ties arbitrarily. If the player for position $$$j$$$ comes from the top $$$k$$$ audience members, they can, without loss of optimality, come from 1 by a swapping argument. If the player comes from the top $$$p + k$$$, not top $$$k$$$, they obviously come 2. Otherwise, they come from 3. Thus considering these $$$3p$$$ options is sufficient.

We have $$$\mathcal{O}(p)$$$ options for each position, of which there are $$$p$$$, so with some consideration we can build a min-cost flow graph on $$$\mathcal{O}(p^{2})$$$ vertices, with $$$\mathcal{O}(p^{2})$$$ edges. This min-cost flow problem may then be solved in time polynomial in $$$p$$$.

what is &mdash in b solution ?

We know that cumulative gcd of coefficients is one in both cases. Hence no prime divides all the coefficients of the polynomial.

can someone please explin me the meaning of line and from where it comes from.

In problem B, if only those values of $$$k \equiv n \pmod{2}$$$ are allowed, we can solve it in $$$\mathcal{O}(n\log(n))$$$, since it can be reduced to finding the minimum lexicographic rotation of the modified string $$$\star, s_1,s_2,\star,s_3,s_4,\star, \dots,\star, s_{n-1},s_n$$$ if $$$n$$$ is even, where $$$\star$$$ is an auxiliary character lexicographically smaller than any lowercase latin letter. This case can be handled similarly if $$$n$$$ is odd.

Is there a way to solve the problem in $$$\mathcal{O}(n\log(n))$$$ when the suffix is reversed ($$$k$$$ and $$$n$$$ of different parity)?

Why condition involving variable a is included in solution of problem c code ?

Another mathforces round

Editorial of problem C is a little bit blurry. How can we say the terms inside parenthesis is divisible by prime p? Can anyone please explain?

In problem C, I understand till the part where we can guarantee a[i]*b[j] will not be divisible by p. How did they arrive at the summation result, where they take all bracketed terms to be divisible by p and only a[i]*b[j] to be not divisible? Can't there be two elements in the summation each individually not divisible by p, but their summation is divisible?

Detail Explanation For C (pardon my mistakes)

As Gcd of (a1,a2,a3,a4.......) =1

so p cant divide all of them if p divides all of them then gcd would be p

same goes for (b1,b2,b3,.......)

So there is atleast one ai and bi such that p does not divides them

Now if you see closely

x0 's coefficient = a0*b0

x1 's coefficient = a0*b1 +a1*b0

x2 's coefficient = a0*b2 + a1*b1 + a2*b0

and so on...

Now suppose a2 is one of the number which is not divisible by p (all previous number are divisible ex. a0,a1)

and b2 is one of the number from b set which is not divisible by p ( all previous one are divisible b0,b1)

now x4' s coefficient = a0*b4 +..... +a2*b2+........a4*b0

All the number before a2*b2 is divisible by p as a0,a1 are divisible by p then there multiple

will also be divisible

All the number after a2*b2 is divisible by p as b0,b1 are divisible

Now if a%m==0 and b%m==0 then (a+b)%m==0

So sum of all the numbers before a2*b2 and after a2*b2 is divisible by p

Now if a%m==0 and b%m!=0 then (a+b)%m!=0

(a2*b2)%p!=0 As a2 and b2 are not so there product will also be not divisible by p

So total sum of X4's coefficient is not divisible by p

Hence this is one of the answer

So what you need to do is Loop through set A and Set B find the least number which is not divisible by p

from above example its a2 and b2

So your answer will be 2+2 == 4 (which your coefficient's power)

Sample Code in C++

Auto comment: topic has been updated by gaurav172 (previous revision, new revision, compare).

In problem C: I read some submission seem choose any a[i] and b[j] which are not divisible by p :>. Is it indeed a violation ?? Because it does not satisfy the formula in solution !!

In task C:

Why if we give similar, we wont get coefficients, which become divisible by p?

can someone plz explain how in coefficient of pow(x,i+j)

can plz somebody explain me that how other tems in coefficient of pow(x,i+j) other than ai*bi are divisible by p??

In problem F , the value 「val」 in the segment tree sould be $$$\sum_{i=1}^{n} \sum_{j=i+1}^{n} prob_{i,j} \cdot p_i \cdot p_j$$$ but not $$$\sum_{i=1}^{k} \sum_{j=i+1}^{k} p_i \cdot p_j$$$ @gaurav172

In B problem, won't suffix of the answer string be S1S2....Sk-1 when n and k have opposite parity since total operations is n-k+1 and even operations will result in same order of the substring. Plz help!!!

In problem B why the condition (n%2==k%2) is used? Can someone please explain it?

Can some one please elaborate in detail how to solve E. I am unable to understant it :(

Can someone explain the suffix part(about the parity of n and k) in problem B?

Any FFT solution or tutorial for the C problem

yo, B is messed up for java or something? I'm using stringbuilders and everything, I did EXACTLY what the editorial said, and still TLEing. Is it because Java is a slow language or what?

Problem B : Can someone explain how the O(n^2) per testcase(total 5000 testcases, n <=5000) is okay? Isn't total time complexity should be O(n^3) considering testcases and that might cause TLE ?

for question B i tried to solve this in college(pretending like i am attending the lecture but i solve questions mostly time) ,i come with exact same approach but i implement it wrong i guess ,after almost 15 days i didnt got the perfect idea and now after seeing editorial i feel stupid and happy at the same time

In B, Can someone prove , how this is true- "It can be observed that the suffix will be s1..sk−1 if n and k have the same parity and sk−1..s1 otherwise."

I am not getting it ...

My solution for this prob isn't as nice as the editorial's, but I thought I'd share it. An observation is that if we sort array A in increasing order, then we will have to select the last k people plus p extra people in the prefix. The way we choose which ones will be part of the team and the audience is up to us however. Let's let dp1[i][j] be the best answer considering the first i people and filling up all the positions in the team denoted in bitmask j. We'll ignore the audience for now. Now let's let dp2[i][j] consider the people from the last person to the ith person. If we choose to add a person to the team, we will add their position strength but subtract their audience strength. Finally, we'll iterate over the size of the suffix as it can range from len = k to k+p. For each size, we'll iterate over all bitmasks who have len-k bits on, and then compute the sum of dp2[start of suffix][some bitmask] + dp1[start of suffix-1][complement bitmask] + sum of all audience values in the suffix.

239550098