1316A  Grade Allocation
Author: gaurav172
Development: gaurav172, ishita_3110, night_fury208
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll test;
cin>>test;
while(test)
{
ll n,m;
cin>>n>>m;
ll s=0;
for(ll i=1;i<=n;i++)
{
ll x;
cin>>x;
s=s+x;
}
cout<<min(s,m)<<"\n";
}
return 0;
}
1316B  String Modification
Author: preet_t
Development: preet_t, shaanknight, night_fury208
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
string modified(string& s, int n, int k) {
string result_prefix = s.substr(k  1, n  k + 1);
string result_suffix = s.substr(0, k  1);
if (n % 2 == k % 2)
reverse(result_suffix.begin(), result_suffix.end());
return result_prefix + result_suffix;
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string s, best_s, temp;
int t, n, best_k;
cin >> t;
while (t) {
cin >> n >> s;
best_s = modified(s, n, 1);
best_k = 1;
for (int k = 2; k <= n; ++k) {
temp = modified(s, n, k);
if (temp < best_s) {
best_s = temp;
best_k = k;
}
}
cout << best_s << '\n' << best_k << '\n';
}
return 0;
}
1316C  Primitive Primes
Author: naruhodou
Development: naruhodou, shaanknight,ishita_3110
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,i,m,x,a,p,fir,sec;
cin >> n >> m >> p;
a=0;
for(i=0;i<n;i++)
{
cin >> x;
if(x%p && !a)
{
a=1;
fir=i;
}
}
a=0;
for(i=0;i<m;i++)
{
cin >> x;
if(x%p && !a)
{
a=1;
sec=i;
}
}
cout << fir+sec << endl;
return 0;
}
1316D  Nash Matrix
Author: shaanknight
Development: shaanknight, riz_1_, coder_h,Altitude
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int M = (1<<10)+5;
char mat[M][M];
int x[M][M],y[M][M];
int n;
bool connect(int p,int q,int r,int s,char d1,char d2)
{
if(x[r][s] == 1)
{
mat[p][q] = d1;
if(mat[r][s] == '\0') mat[r][s] = d2;
return 1;
}
else
return 0;
}
void dfs(int p,int q,char d)
{
if(mat[p][q] != '\0') return;
mat[p][q] = d;
if(x[p][q] == x[p+1][q] && y[p][q] == y[p+1][q])
dfs(p+1,q,'U');
if(x[p][q] == x[p1][q] && y[p][q] == y[p1][q])
dfs(p1,q,'D');
if(x[p][q] == x[p][q+1] && y[p][q] == y[p][q+1])
dfs(p,q+1,'L');
if(x[p][q] == x[p][q1] && y[p][q] == y[p][q1])
dfs(p,q1,'R');
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i,j;
cin >> n;
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
cin >> x[i][j] >> y[i][j];
}
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(x[i][j] == 1)
{
bool res = (mat[i][j] != '\0');
if(res == 0) res = connect(i,j,i+1,j,'D','U');
if(res == 0) res = connect(i,j,i,j+1,'R','L');
if(res == 0) res = connect(i,j,i1,j,'U','D');
if(res == 0) res = connect(i,j,i,j1,'L','R');
if(res == 0)
{
cout << "INVALID" << "\n";
return 0;
}
}
else if(x[i][j] == i && y[i][j] == j)
dfs(i,j,'X');
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(mat[i][j] == '\0')
{
cout << "INVALID" << "\n";
return 0;
}
}
}
cout << "VALID" << "\n";
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
cout << mat[i][j];
}
cout << "\n";
}
return 0;
}
1316E  Team Building
Author: gaurav172
Development: gaurav172, shaanknight, coder_h, madlad
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll M=1e5+5;
ll dp[M][(1<<7)+1],skill[M][7];
ll ind[M],a[M];
bool cmp(ll p,ll q)
{
return a[p]>a[q];
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,p,k;
cin>>n>>p>>k;
memset(dp,1,sizeof(dp));
for(ll i=1;i<=n;i++)
cin>>a[i];
for(ll i=1;i<=n;i++)
for(ll j=0;j<p;j++)
cin>>skill[i][j];
for(ll i=1;i<=n;i++)
ind[i]=i;
sort(ind+1,ind+n+1,cmp);
dp[0][0]=0;
for(ll i=1;i<=n;i++)
{
ll x=ind[i];
for(ll mask=0;mask<(1<<p);mask++)
{
ll ct=0;
for(ll j=0;j<p;j++)
if((mask&(1<<j)))
ct++;
ll z=(i1)ct;
if(z<k)
{
if(dp[i1][mask]!=1)
dp[i][mask]=dp[i1][mask]+a[x];
}
else
{
if(dp[i1][mask]!=1)
dp[i][mask]=dp[i1][mask];
}
for(ll j=0;j<p;j++)
{
if((mask&(1<<j)) && dp[i1][(mask^(1<<j))]!=1)
{
ll z=dp[i1][(mask^(1<<j))]+skill[x][j];
if(z>dp[i][mask])
dp[i][mask]=z;
}
}
}
}
cout<<dp[n][(1<<p)1]<<"\n";
return 0;
}
1316F  Battalion Strength
Author: gaurav172
Development: gaurav172, shaanknight
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const ll M=6e5+6;
const ll mod=1e9+7;
ll val[4*M],lt[4*M],rt[4*M];
int no[4*M];
ll pw[M],ipw[M];
int P[M],idx[M],qr[M],n,q;
vector<pair<int,int> > v;
ll power(ll a,ll b)
{
ll val=1;
while(b)
{
if(b%2)
val=(val*a)%mod;
b/=2;
a=(a*a)%mod;
}
return val;
}
void build(int i,int s,int e)
{
if(s==e)
{
if(v[s].ss>n)
return;
val[i]=0;
lt[i]=v[s].ff;
rt[i]=(v[s].ff*ipw[1])%mod;
no[i]=1;
return;
}
int m=(s+e)/2;
int lc=2*i,rc=2*i+1;
build(lc,s,m);
build(rc,m+1,e);
ll tp=(ipw[no[lc]]*rt[rc])%mod;
tp=(tp*lt[lc])%mod;
val[i]=(val[lc]+val[rc]+tp)%mod;
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;
no[i]=(no[lc]+no[rc]);
}
void update(int i,int s,int e,int x,int y)
{
if(s==e)
{
if(y==1)
{
val[i]=0;
lt[i]=0;
rt[i]=0;
no[i]=0;
}
else
{
val[i]=0;
lt[i]=v[s].ff;
rt[i]=(v[s].ff*ipw[1])%mod;
no[i]=1;
}
return;
}
int m=(s+e)/2;
int lc=(i<<1),rc=(lc1);
if(x<=m)
update(lc,s,m,x,y);
else
update(rc,m+1,e,x,y);
ll tp=(ipw[no[lc]]*rt[rc])%mod;
tp=(tp*lt[lc])%mod;
val[i]=(val[lc]+val[rc]+tp)%mod;
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;
no[i]=(no[lc]+no[rc]);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
pw[0]=1;
ipw[0]=1;
ll inv=power(2,mod2);
for(int i=1;i<M;i++)
{
pw[i]=(pw[i1]*2)%mod;
ipw[i]=(ipw[i1]*inv)%mod;
}
cin>>n;
v.pb({1LL,1});
for(int i=1;i<=n;i++)
{
cin>>P[i];
v.pb({P[i],i});
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>idx[i]>>qr[i];
v.pb({qr[i],n+i});
}
sort(all(v));
std::vector<int> pos(n+q+1,0);
for(int i=1;i<sz(v);i++)
pos[v[i].ss]=i;
build(1,1,n+q);
cout<<val[1]<<"\n";
for(int i=1;i<=q;i++)
{
update(1,1,n+q,pos[idx[i]],1);
pos[idx[i]]=pos[n+i];
update(1,1,n+q,pos[idx[i]],1);
cout<<val[1]<<"\n";
}
return 0;
}
E can be solved in $$$\mathcal{O}(np + \text{poly}(p))$$$ with mincost flow: 72472865.
We for sure will have the $$$k$$$ most valuable audience members fill some positions. Initially have them fill the audiencepositions, then move to fill the other positions in the team. The candidates for position $$$j$$$ in the team are
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 mincost flow graph on $$$\mathcal{O}(p^{2})$$$ vertices, with $$$\mathcal{O}(p^{2})$$$ edges. This mincost flow problem may then be solved in time polynomial in $$$p$$$.
1316E  Team Building can be solved too running $$$p$$$ times a mincostmaxflow algorithm where the maxflow is $$$p$$$: 72494005
Can you please explain to me how to build this graph,thanks a lot.
I can explain how to build this graph only in chinese. You can contact me with my qq:164950760.
what is &mdash in b solution ?

Fixed
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.
if we assume that all the coefficients are divisible by p then the gcd of all the coefficients will not be 1.So we will have atleast one coefficient which is not divisible by p.
GCD of all coefficients is 0 means the only common factor all of them have is 1 and 1 cannot be broken down into any product of primes. So basically there is no common prime factor for all coefficients. Eg. If the GCD would have been say 10(2*5), then all the coefficients would have had 2 and 5 as common prime factors.
It means that if a prime p had divided all the coefficients then the gcd would have been some multiple of that prime and not 1.
Hey! Hey! Hey!
Hey Hey Hey to the best player in Karasuno Nishinoya
watch this video . https://www.youtube.com/watch?v=wi14d0zcjCw
thank you! very helpful!
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_{n1},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)?
The problem turns into: split the string into XY, then it turns into YX or Y(X') depending on parity. Try to do a comparison as fast as you can. Then you can solve in O(N * comparison cost). First, you can do O(nlogn) easily using hash + binary search. You can push that even further, computing the suffix tree of STRING + '#' + REVERSEDSTRING and using lcp (in the tree's case the lcp of two suffixes is the lca of them in the tree). You can do LCA in O(1) using O(N) preprocessing so you can actually solve the whole thing in O(N).
This is something crazy I though after the contest, just proving a bound. There's probably a way to do it that's way simpler tho, I'd be interested in that if someone knows it.
Thank you so much.
The solution where you do the same naïve algorithm, but compare 2 strings with binary+hashing using segments of $$$s_1 \dots s_n$$$ or $$$s_n \dots s_1$$$ is exactly what I was looking for.
While preparing the problem we tried solving the problem in O(N) , but we could think of the solution for a particular parity and not for the other parity . We tried solving using suffix array and not suffix tree , is there a way we can solve for both parities using suffix array only .
You can do the same but calculating the suffix array in O(N), there's a divide and conquer way to do it in O(N). The lcp query is just a min query in range and that can be done in O(N) preprocessing too.
Why condition involving variable a is included in solution of problem c code ?
To take the first idx that a[idx] is not divisible by p.
You can use (break) after you find such idx.
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?
Given i is the smallest index where ai is not divisible not divisible p which means a0 to ai1 are all divisible by p.So the terms in left paranthesis are divisible by p. Similarly for terms in right paranthesis also b0 to bj1 are all divisible by p.
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?
The solution is you find the first i in first polynomial ( i can be from 0 to n1 ) such that it's coefficient is not divisible by p. Since all other ak's from k = 0 to i — 1 are divisible by p , the entire thing that you put in initial paranthesis is divisible by p. The paranthesis having sum of (i1) products of two coefficients, out of which one is surely divisible by p, results in entire paranthesis sum being divisible by p.
Now we want a find a j in 2nd polynomial, similar to how we found i in first polynomial. Since now all other bk's from k = 0 to j — 1 are divisible by p , the entire thing that you put in second paranthesis is divisible by p .
The remaining thing left in expression as you have understood is not divisible by p.
Thanks a lot! Got it :)
watch this video after 7 minutes: https://www.youtube.com/watch?v=wi14d0zcjCw
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++
How
a2%p!=0
andb2%p!=0
implies(a2*b2)%p!=0
?like
4%8==4
and12%8==4
but(12*4)%8 == 0
I know p is a prime but how to prove there doesn't exit any p like 8?
Sorry i did not totally get your question This may help I used if a3%p==0 and b3%p==0 then (a3*b3)%p==0 You are saying opposite of it And there was some typo mistake Fixed now
In Your explanation, Line no 20.
How
( a2 * b2) % p! = 0
?Suppose a2 has prime factor like p1,p2,p3 and b2 has prime factor(Different from a2) p4,p5 And p is not one of them because p is one of a2 and b2 's prime factor then a2 ,b2 will be divisible by p Now a2*b2 has prime factor like p1,p2,p3,p4,p5 and p is not one of them So a2*b2 is not divisible by p
p is prime that's y this condition is satisfied otherwise not .
Really Helpfull.
why the least one should be taken?
Just to proof There maybe other co primes with p , hence other ai*bj that satisfies the condition
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 !!
Try to hack it if you think it's wrong. From the description given by you it seemed that it is in fact wrong. (Or post the submission link please
It's here. Submission of rank 1 :>
1316C
It is correct because the problem description claimed that if more than one solutions exist, you can put any of them.
I got it but if (i,j) is not the first then the terms inside parentheses are not all divisible by p. So i think it is wrong although i can not hack it :>
For intuition, you can reverse both polynomials, and it's the same as the editorial said.
Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible. Here is a hack 5 5 5 0 1 0 3 0 0 2 0 4 0 (3,1) is not divisible but 3+1=4 is not a correct answer
The reason why the submission you mentioned below passed is that he actually choose the last undivisible a[i] and b[j]. It can be proved that last and first are both correct.
：）
Wow! I got it now :>. Thank u ^_^ !
"Well It is absolutely wrong if you choose any a[i] and b[j] which are not divisible".Why this?Can you please explain?
Hack:
5 5 5
0 1 0 3 0
0 2 0 4 0
a[3] and b[1] are both undivisible. But (3+1=4) is not a correct answer. a[0]*b[4]+a[1]*b[3]+a[2]*b[2]+a[3]*b[1]+a[4]*b[0]=10
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??
I tried to explain this here.
sorry.....i was unable to understand there. Now i got it. Nice solution.
$$$x^{i + j}=(a_0 * b_{i + j} + a_1 * b_{i + j  1} + ...) + a_i * b_j + (a_{i + 1} * b_{j  1} + a_{i + 2} * b_{j  2} +...) $$$.
if $$$x_i$$$ and $$$x_j$$$ are the first coefficient that can not divisible by p, than $$$a_0$$$,$$$a_1$$$,$$$a_2$$$...,$$$a_i1$$$ and $$$b_0$$$,$$$b_1$$$,$$$b_2$$$...,$$$b_j1$$$ can divisible by p, so $$$(a_0 * b_{i + j} + a_1 * b_{i + j  1} + ...)$$$ and $$$(a_{i + 1} * b_{j  1} + a_{i + 2} * b_{j  2} +...)$$$ can also divisible by p, and also $$$a_i * b_j$$$ can not.
Thank You for your explanation. I got it
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
Fixed, Thanks a lot.
In B problem, won't suffix of the answer string be S1S2....Sk1 when n and k have opposite parity since total operations is nk+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?
To check if $$$n$$$ and $$$k$$$ have the same parity. Depending on this condition, the modified string's suffix will be $$$s_1s_2..s_{k1}$$$ or its reverse.
Why can't we reverse the strings when n & k don't have same parity?
Can some one please elaborate in detail how to solve E. I am unable to understant it :(
Which part do you want ? The sorting part or Dp part?
Yes please... I got the dp part but still didnt get why we sort.
So, you can't keep another dimension to the dp (the number of people selected as audience till now), we need to find another way to add audience contribuition to our DP. Initially, just forget about the audience and try to find just skills. suppose you keep a track of people whom you have selected for players among the $$$N$$$ people, to then select audience, we just need to select the best $$$k$$$ among the remaining as. As we have sorted in decreasing order of $$$a_i$$$, these will be the first $$$k$$$ among the remaing (nonselected people). So, we just need to add this in our DP solution, we either selected $$$i$$$ as a player or, for the current state $$$(i,mask)$$$ — we can find how many people we have not selected as players for this state, if they are less than $$$k$$$ we need to include $$$i$$$ as audience , else we have already selected $$$k$$$ audience.
Thank you..! that's exactly what i was looking for.
dp part
DP part is pretty straight forward. consider that you need to select only players, so to get optimal value at state $$$(i,mask)$$$ — you can either select $$$i$$$ as one of the players or $$$not$$$.
So you can just iterate over all the positions $$$j$$$ in the mask, and try to set $$$i$$$th person to the $$$j$$$th position. — $$$dp[i][mask] = max(dp[i][mask],dp[i1][mask \oplus 2^{j}]+s_{i,j}$$$. if we don't want to select $$$i$$$ as a player — $$$dp[i][mask] = dp[i1][mask]$$$.
This is the standard bitmask dp, I have explained the audience part in the above comment
Thank you so much I get it now :)
Can you tell me whats wrong in my solution gaurav172 Your text to link here...
use long long instead of int
Thank u so much my solution got accepted! :)
how can i be less than number of set bits in mask. I don't get that part. Because of that the number of players selected that is (i — 1 — setbits) would even become negative. Can u elaboarate how does this vaild.
Can someone explain the suffix part(about the parity of n and k) in problem B?
You just have to see the numbers of characters (n — k) i.e for eg  bbcdabcd here value of k will be k = 5 and n = 8. So numbers of characters from k are abcd i.e. equal to 4. Since 4 is even you will append the suffix part just like this i.e. your answer will be abcd + bbcd = (abcdbbcd) If string would be bbcdabcdd here the value of k will also be 5 and numbers of character from k are 5 (abcdd) which is odd. So we will first reverse the suffix part and then append it to our answer i.e. abcdd + reverse(bbcd) = abcdd + dcbb = abcdddcbb
Any FFT solution or tutorial for the C problem
We tried not to make the FFT solution pass. The constraints are really tight for normal FFT to pass, probably only those whose codes are really optimized might have passed
have anyone done E with memoization instead of DP? Mine is getting TLE. https://codeforces.com/contest/1316/submission/73085301
Is there anything that I am missing?
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?
I think total time complexity should be O(n^3) considering testcases and that might cause you TLE
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 ?
There is a restriction on sum of n over all test cases.
Thanks, now i get it.. :D