Hope you enjoy those tasks!
Tutorial
Tutorial is loading...
Solution (python by pikmike)
t = int(input())
for _ in range(t):
a, b, c, d = map(int, input().split())
x, y, x1, y1, x2, y2 = map(int, input().split())
x += b - a
y += d - c
if a + b > 0 and x1 == x2:
print("No")
elif c + d > 0 and y1 == y2:
print("No")
elif x1 <= x <= x2 and y1 <= y <= y2:
print("Yes")
else:
print("No")
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;
int main(){
int t;
cin>>t;
while (t--){
cin>>a>>b>>c>>d;
cin>>x>>y>>x1>>y1>>x2>>y2;
xx=x,yy=y;
x+=-a+b, y+=-c+d;
if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){
cout<<"Yes\n";
}
else{
cout<<"No\n";
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (python by pikmike)
from math import gcd
def getprime(x):
for i in range(2, x):
if x % i == 0:
return i
return -1
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
used = [False for i in range(11)]
clr = []
for i in range(n):
x = primes.index(getprime(a[i]))
used[x] = True
clr.append(x)
cnt = 0
num = []
for i in range(11):
num.append(cnt)
if used[i]:
cnt += 1
print(cnt)
for i in range(n):
x = primes.index(getprime(a[i]))
print(num[x] + 1, end = " ")
print()
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
int n,t;
vector<int> ans[1007];
int res[1007];
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
auto f=[&](int u){
for (int i=2;i<=u;++i){
if (u%i==0) return i;
}
};
cin>>t;
while (t--){
cin>>n;
for (int i=1;i<=1000;++i) ans[i].clear();
for (int i=1;i<=n;++i){
int u;
cin>>u; ans[f(u)].push_back(i);
}
int ret=0;
for (int i=1;i<=1000;++i){
if (ans[i].size()){
++ret;
for (auto c:ans[i]){
res[c]=ret;
}
}
}
cout<<ret<<"\n";
for (int i=1;i<=n;++i){
cout<<res[i]<<" ";
}
cout<<"\n";
}
return 0;
}
Tutorial
Tutorial is loading...
Solution(python by pikmike)
from sys import stdin
t = int(stdin.readline())
for _ in range(t):
n, k = map(int, stdin.readline().split())
s = stdin.readline()
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]
for i in range(n):
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1
ans = 0
for i in range(k // 2):
ans += 2 * n // k - max(cnt[i])
if k % 2 == 1:
ans += n // k - max(cnt[k // 2])
print(ans)
Solution(C++)
#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int n,k,ans=0;
int cnt[maxn][26];
string s;
int differ(int u,int v){
int ret=0,mx=0;
for (int j=0;j<26;++j){
ret+=cnt[u][j]+cnt[v][j];
mx=max(mx,cnt[u][j]+cnt[v][j]);
}
return ret-mx;
}
int main(){
int t;
cin>>t;
while (t--){
cin>>n>>k>>s;
for (int i=0;i<k;++i){
for (int j=0;j<26;++j){
cnt[i][j]=0;
}
}
for (int i=0;i<n;++i){
cnt[i%k][s[i]-'a']++;
}
int ans=0;
for (int i=0;i<k;++i){
ans+=differ(i,k-1-i);
}
cout<<ans/2<<"\n";
}
return 0;
}
Tutorial
Tutorial is loading...
Solution(python by pikmike)
k = int(input())
x = 2**17
print(2, 3)
print(x^k, x, 0)
print(k, x^k, k)
Tutorial
Tutorial is loading...
Solution 1(python by pikmike)
MOD = 998244353
n, m, l, r = map(int, input().split())
if n * m % 2 == 1:
print(pow(r - l + 1, n * m, MOD))
elif (r - l + 1) % 2 == 0:
print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)
else:
print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)
Solution 2(python by pikmike)
MOD = 998244353
n, m, l, r = map(int, input().split())
if n * m % 2 == 1:
print(pow(r - l + 1, n * m, MOD))
else:
e = r // 2 - (l - 1) // 2
o = (r - l + 1) - e
print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)
Tutorial
Tutorial is loading...
Solution(C++)
#include<bits/stdc++.h>
#define int long long
#define ULL unsigned long long
#define F first
#define S second
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define range(a) a.begin(), a.end()
#define PI pair<int,int>
#define VI vector<int>
#define debug cout<<"potxdy"<<endl;
using namespace std;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn=300007;
const int mod=998244353;
int n,dp[maxn][2],f[maxn];
VI vec[maxn];
int mult(int u,int v){
u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;
return 1ll*u*v%mod;
}
void dfs(int u,int p){
dp[u][0]=dp[u][1]=f[u]=1;
for (auto c:vec[u]){
if (c==p) continue;
dfs(c,u);
dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);
dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);
f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);
}
}
#undef int
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n;
for (int i=1;i<n;++i){
int u,v;
cin>>u>>v;
vec[u].pb(v), vec[v].pb(u);
}
dfs(1,0);
cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;
return 0;
}
Contributor of idea of the solution: awoo
Tutorial
Tutorial is loading...
Solution (C++)
#include<bits/stdc++.h>
using namespace std;
const int maxn=200007;
int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];
int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;
int ans1[maxn][4],ans2[maxn][4];
set<int> s;
bool cmp1(int u,int v){
return a[u]<a[v];
}
bool cmp2(int u,int v){
return a[u]>a[v];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;++i){
cin>>a[i];
}
p1=p2=r1=r2=0;
s.insert(n+1);
for (int i=n;i>0;--i){
while (p1){
int u=st1[p1];
if (a[u]>a[i]){
t[u]--;
if (!t[u]) s.insert(u);
p1--;
r1=0;
}
else{
break;
}
}
while (p2){
int u=st2[p2];
if (a[u]<a[i]){
t[u]--;
if (!t[u]) s.insert(u);
p2--;
r2=0;
}
else{
break;
}
}
s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;
b[i]=i+max(r1,r2)+1;
ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];
if (s1&&s2){
c[i]=*s.lower_bound(max(st1[s1],st2[s2]));
if (c[i]<=n){
int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2;
ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i];
}
}
else{
c[i]=n+1;
}
st1[++p1]=i;
st2[++p2]=i;
r1++, r2++;
t[i]+=2;
if (i<n&&b[i]>b[i+1]){
b[i]=b[i+1];
for (int j=0;j<3;++j){
ans1[i][j]=ans1[i+1][j];
}
}
if (i<n&&c[i]>c[i+1]){
c[i]=c[i+1];
for (int j=0;j<4;++j){
ans2[i][j]=ans2[i+1][j];
}
}
}
while (q--){
int l,r;
cin>>l>>r;
if (r>=c[l]){
cout<<"4\n";
for (int j=0;j<4;++j){
cout<<ans2[l][j]<<" ";
}
cout<<"\n";
}
else{
if (r>=b[l]){
cout<<"3\n";
for (int j=0;j<3;++j){
cout<<ans1[l][j]<<" ";
}
cout<<"\n";
}
else{
cout<<"0\n\n";
}
}
}
return 0;
}
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
Video tutorial for D
Here you can see how to prove the described solution, which is similar with the editorial's approach.
I saw your video tutorial but I am not able to understand the complete solution.
I understood that we want to generate a matrix such that the answer by Bob's algo is 0, and optimal answer achievable is K.
But other than that I am not able to understand anything.
Like what is the actual fault in Bob algo and why his algo not able to achieve optimal answer. And how you are coming up with the matrix given in editorial.
So can you help me?
in order for a bit to be present in the final answer we must ensure that the bit is present in all the numbers from the path. Even though the dp can be correct at some step, greedily taking the best bitwise AND up to some (i, j) may prevent us from using subsequent bits which may have ended up in the answer
But can you explain what is the correct approach to find maximum answer using DP because bob's approach is incorrect.
Clear and lucid explanation. Thanks.
Why is nobody talking about the fact that the question initialized dp0,1 as a1,1. Why was it done? What is it's implications? Is it just to make the dp work? Could it be dp1,0 as a1,1?
it does not affect anything tbh. i wrote it because it is the shortest way to implement (tho the naive dp idea is incorrect as the statement suggests).
Thanks for such a fast editorial! Nice round!
Fastest editorial in the west :3
There is the tutorial of problem 1327A instead of 1332A
UPD: now fixed
thanks for pointing it out. it is now fixed.
Why editorial for A is an editorial to another problem?
EDIT: fixed now
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
.
k = 3
Thanks!
Why so many people get "Wrong answer on test 57"(problem E)?
Because their code fails to produce correct output on test 57 of problem E?
So do I. Hope somebody can tell me what happen.
I guess it is because Fermat's little theorem is not true if gcd(a, p) != 1
I figured out why many people(including me) got wa on test 57 in E)
it was because of %(mod-1)
x^y≡x^(y%(p-1))mod p
but there is a condition that x needs to be coprime to p
the following test case was a corner case- 998244352 2 1 998244353
the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests
"the sad thing is that %(mod-1) wasn't even needed."
Just realize it and feel sadder :(
I think I know what happened on it.
This test is:
998244352 2 1 998244353
So, in my program, there is somewhere that are expected to calculate: (998244353^998244352)%998244353, the correct output for it should be 0. That's ok.
However, if you use Euler Theorem there to calculate, then what you do is indeed calculating (998244353^(998244352%998244352))%998244353=(998244353^0)%998244353
AND, MY QUICKPOW() FUNCTION CONSIDERED THE VALUE OF 998244353^0 IS 1 !
And this lead to the eventual WA.
People have used DSU/DFS in their solutions for problem C. Could someone explain how that works?
I approached C using DSU. For this, we needed to find out about what all indices should have the same char. Now, let's consider a string of length n and k=k. Condition 1: A/c to question indices i, i+k, i+2k.... should have the same char at their index. Hence, we will union(i,i+k) , union(i, i+2k) ..... Condition 2: String should be a palindrome. So, index (0,n-1) , (1,n-2) , (2,n-3)...should have the same char at these positions. Hence, we will also do a union of these indices. After these operations, our DSU will provide which all indices belong to the same connected component. Now, that we have the info about the connected components we can easily find the char which has occurred the most number of times in that component. The rest of the char needs to be replaced for that component and added to our overall sum.
Sorry for my bad English.
For dfs, if you are currently at position $$$i$$$, the position $$$i+k$$$ and $$$n-1-i$$$ should have the same character as position $$$i$$$. So you can do dfs an find which positions should have same characters and calculate the answer based on which character appears the most times on each group. Similar idea to DSU solution.
The round definitely made me think
(and question my existence). Kudos to triple__a.I am not satisfied with the pretests of C. My $$$O(n^2)$$$ solution passed them. It would have been trivial to fix it, so now I am feeling a bit bitter.
E too :(
nice 1;
C is doable with dfs. It'll be an easier approach.
Could u elaborate
Yeah sure, In the graph connect the indexes which will have the same value. ie. (i) with (n+1−i) and (i) with (k+i) now each connected component of the graph will have same value in the final string. Optimal count of the characters to be deleted can be obtained using map. I am weak in calculating time complexity but according to my understanding it'll be O(N). Link to the AC soln
I want to know if the input is 1 12 6 3 5 7 11 13 17 19 23 29 31 37 The output is 12 1 2 3 4 5 6 7 8 9 10 11 12 but I think the first data could belong to the color 2 so we can use only 11 color
well， the condition said that all inputs are great or equal to 4
numbers must be composite
Tiny correction triple__a, You've written Solution(C++) but the code isn't C++ for problem C. Thanks for the fast editorial, and a great round
thanks for pointing it out,but i am not convenient to edit right now. i will fix it tmr
upd: it is now fixed
I would like to give an alternative solution for E using dp and matrices. From the editorial, we have a proof that the answer only depends on the number of ways choosing odd number of odd cells and that of choosing even number of odd cells.
Let $$$dp_{odd}[i]$$$ and $$$dp_{even}[i]$$$ be the number of ways choosing $$$i$$$ cells with odd number of odd cells and even number of odd cells respectively.
$$$dp_{odd}[i] = dp_{odd}[i-1] \cdot E + dp_{even}[i-1] \cdot O$$$
$$$dp_{even}[i] = dp_{even}[i-1] \cdot E + dp_{odd}[i-1] \cdot O$$$
Then we can use matrix and binary exponentiation to calculate the answer.
74978938
This is cool! BTW, I think this is a mistake, dp[i] should depend on dp[i — 1].
Thanks for your correction! :)
haha(lol); :) Interesting code!
oh I see you're a man of culture as well
74987963
You can prove by induction that $$$dp_{even}[i] - dp_{odd}[i] = (-1)^i$$$ if $$$L, R$$$ are odd, $$$(-1)^{i+1}$$$ if $$$L, R$$$ are even, $$$0$$$ otherwise. Moreover, $$$dp_{even}[i] + dp_{odd}[i] = (R - L + 1)^i$$$. You can find $$$dp_{even}[i]$$$ and $$$dp_{odd}[i]$$$ by solving the resulting system of equations.
Thank you!
niu
Good English
Is there solution for D if we say that values in matrices are
a[i][j]<=1e5?I think, if k == 65536 (2 ^ 16), there isn't any solution.
Proof by contradiction: There is an optimal way with score not less than k (at least 65536). Then dp solution can find a way which score is at least 65536 too. The optimal way can't have score more than 2 * 65536 — 1 due to all numbers are at most 100'000. So difference between optimal way and dp way is less than k.
In the problem it is mentioned that all numbers can be in range [0, 300000]
Yes, but the question was about range [0, 100'000]
triple__a Thanks for such a good round in these days!! No queueforces even after Contest and fast editorial!! Kudos
I have done c using dsu it is efficient in this manner
but anyone did it using dp or is it not possible ? explain your solution if possible(any complexity)?
here is an easy solution- https://mirror.codeforces.com/contest/1332/submission/74991949
My solution of E failed on test 57. I removed b % phi(mod) in the power function and it passed. Can anyone tell why? (a ^ b) % m = (a ^ (b % phi(m) ) % m. Since m is prime, so phi(m) = m-1 Although it was not needed, I think this shouldn't fail.
a and m need to be co-prime for this. Test 57 violates this.
Case 57 is
998244352 2 1 998244353. (Let the modulo be $$$M = 998244353$$$)So $$$r - l + 1 = M$$$ and $$$n m = 2 (M - 1)$$$
The answer should be $$$M^{2 (M-1)} \mod M = 0$$$.
But if you use $$$b\mod \phi(M)$$$ as the exponent, you are computing $$$0^0$$$ and the code returns 1 instead.
problem C first solution — wrong language (python code, linked as c++)
1 13 6 10 15 7 11 13 17 19 23 29 31 37 41 for this input m = 11 but my code give m = 12 and still accepted.
is this valid input? bcoz i checked many code for this input and every code giveing m = 12.
This input isn't valid, input must contain only composite numbers
The input is not valid because it can only have composite numbers not prime.
I think $$$k=3$$$ case is harder for problem F, I understand how to check if answer is 3 or 0, but how to reproduce the indices for $$$k=3$$$?
i b[i]-1 and b[i] will work if b[i] is the smallest index such that the answer is 3.
How to write spj for D?
for the optimal answer, it can be done by checking bits from the most significant one to the least and run a bfs or dfs
Good problem. This is the original version of D.
As problem-setter said, use bfs to greedily check by bits.
I got it, thanks.
I don't understand it. I think the bits are not independent. Can you please explain it further?
upd:Oh I think I have understood it... I'm a fool.
can you give me an idea of how to do it, like i understood that we will go bit by bit from the most significant to the least significant, but what value to keep and discard as we do the transition.
Let's assume
a[i][j]is your outputs, andcur[i][j] = (a[i][j] >> k) & 1when you check the k-th bit.Set an array
flagwhich is filled with 1 initially, andflag[i][j] == 1means (i, j) is in legal routes when you finish checking the previous bit. Set an arraytmp, which is used to check the current bit. Then, for each cell (from the upper left corner to the lower right corner),tmp[i][j] = (tmp[i - 1][j] | tmp[i][j - 1]) && cur[i][j] && flag[i][j], which means (i, j) is in legal routes iff (there should be at least 1 legal source) and (this cell is legal in the current bit) and (this cell is legal in the previous bit). At last, replace flag array with tmp array to check the next bit.This is what my code do. If you want, BFS also works.
thanks
For E, can someone give more details about how to apply Newton expansion? I really cannot see a direct mapping :'(.
$$$(a+b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}b^i$$$
$$$(a-b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}(-1)^ib^i$$$
Then we have $$$(a+b)^n-(a-b)^n=\sum\limits_{i=0}^n\tbinom{n}{i}a^{n-i}(1-(-1)^i)b^i$$$
If i is even, then $$$1-(-1)^i=0$$$,else $$$1-(-1)^i=2$$$
So $$$(a+b)^n-(a-b)^n=\sum\limits_{i=1,3,5,...}^{i\leq n}2\tbinom{n}{i}a^{n-i}b^i$$$.
In other words, $$$\sum\limits_{i=1,3,5,...}^{i\leq n}\tbinom{n}{i}a^{n-i}b^i=\frac{1}{2}((a+b)^n-(a-b)^n)$$$
can you please tell me how you guys write such mathematical expression in such a nice format and notation.
See this https://mirror.codeforces.com/blog/entry/20729
for 1332A can someone please explain why shouldnt we consider both height and width at the same time
why taking only x axis in calculations. thank u!
because once you give a valid walk something like UDUDLRLRUD. you may rearrange it so that UD is in the front and LR part in the back and it will be also valid
what if there is a case where u dont cross the limit horizontally so it satisfies the condition in 1D but in vertical distance u go out of range!!
the answer is no if x-axis says no or y-axis says no
I solved F in this way.dp[0][x] and dp[1][x] mean the results in x's subtree and x in edge induced subgraphs.than the subtree combine with the father and add to the father node so I get this:
dp[0][x]=dp[0][x]+dp[0][x]*(dp[0][ed[i].v]+dp[1][ed[i].v]); dp[1][x]=dp[1][x]+dp[1][x]*dp[0][ed[i].v];initially, every node's dp[0][x]=1; dp[1][x]=1; for example,1-2,2-3,2-4, first 3 and 4 node are both (1,1), than in node 2, first I choose the 3 to mix 2 ,node 2 get (3,2) ,means now 2-3 this tree's ,with node 2 in edge induced subgraphs, results .than mix 4 to 2 ,get node 2 (9,4) as the question required, add all dp[0][x] and dp[1][x] to answer and remove the one node set , so ans-=2*n it shows right in two examples. what's wrong with me? could someone help me?
I actually did the exact same thing (also I think you mean problem F, not E). I think it might be that this doesn't allow for combining groups of disjoint sets of the subgraph (this dp only allows the groups to be one connected component), but I'm not sure how to modify it to include this.
ok, I get it.edge induced subgraphs isn't connected graph .
Maybe the shortest solution for E
why are you using 2*mod??
To avoid the affect of mod if I divide ret by 2 later.
Writing several times within one explanation that it is easy and how easy it is does not makes it more understandable, or even easy.
hope everyone uploads the tutorials this fast as we r eager and curious about problems solutions!
How did my solution for problem G get TLE on test 109?
The pre-calculation costs only 202ms on test 109, and answering a query only needs constant time. So I don't think it could get TLE. However, the same code got accepted with 64-bit compiler (Submission). So strange.
Python solution for Problem C is incorrectly mentioned as C++, please correct it triple__a.
I was pretty sure that there is a formula solution for E, but during the contest I wasn't able to come up with a correct idea... So now you can check out my solution that uses matrix multiplication:74968680
Why verdict on task D test 2 is WA? Difference equal to 1...
At cell (3, 2) the algorithm will choose from 2&2 and 3&2 which are both equal to 2, and the optimal answer is 2 to begin with.
I used DSU for C. My submission
We can start by assigning each position of the string as a disjoint set.
Then we do a union on all those positions which have to be equal according the the Palindrome condition and the Period of size K condition.
After that I assigned characters to each disjoint set greedily. (ie for every disjoint set of positions, I assigned the character with maximum occurence in the particular disjoint set).
To begin, this post has nothing to do with the contest (i just need help with a topic is all)..
I want to learn "binary search the answer" and other details of the algorithm, I tried searching the internet and Codeforces blogs but couldn't find anything specific to the topic that I was looking for.. I think I understand discrete binary search (about monotonicity of the sequence for some predicate.. but I think that's standard and commonplace) but I need to master the details so that I can solve problems that aren't "apparent to involve anything with binary search yet does so beautifully". Can anyone help?
I think this explains it Link to geeksforgeeks.org
This should help: https://www.youtube.com/watch?v=GU7DpgHINWQ
I did actually see that a few days back.
If no one, Pashka listened.
This might help — https://leetcode.com/discuss/general-discussion/786126/python-powerful-ultimate-binary-search-template-solved-many-problems
Can someone pls explain C in ann easy way?
Problem
Given a string s of length n and a "period" k, find the minimal number of changes such that the string becomes a palindrome AND every kth character is identical (i.e. s[i] = s[i+k] = s[i+2*k] = ..)
For eg. if the string is "abba", and k=2, this is not a valid string because the 0th and 2nd chars are different, and so are the 1st and 3rd. So you'd need to change 2 characters to make this "aaaa" and so the answer would be 2.
Solution
How are we ensuring putting the most frequent character will make the String a palindrome?
For every character in position i, you're collecting all i+kth chars, and also finding the mirror positioned chars for each of them. Then you look for the most frequent amongst all of these and change all 4 to this character.
So if the string is "abcaab" and k = 3:
1) In your first pass (i.e., i=0) you will consider 4 characters: a b c a a b. Since a is the most frequent character, change all 4 to a b a a a a. It's still not a palindrome at this stage.
2) In your next pass (i=1), you will consider the following: a b a a a a (this is your entire set of i, i+k palin_i, palin_i+k). Since "b" and "a" are equally frequent, you could use either one (say you choose "b") and your string becomes a b a a b a, which is now a palindrome.
3) The next and final iteration (i=2) would consider the same four elements as the first iteration. All 4 are already the same and nothing else needs to be done.
At the end of this, you have a string that meets the criteria, including being a palindrome.
I saw your solution for this problem I must it's very easy to understand just one query why are we outputing ans/2 in the end instead of ans
Thank you
It's because each set of points is visited twice. So when the string is "abcaab", and k = 3, then at the first iteration (i=0) I visit 4 indices 0, 3 (0 + k), 5 (mirror of 0), 2 (mirror of 0 + k). On the second iteration (i=1), I visit 1 and 4 — twice (since 1 and 4 are the mirror positions of themselves). Then in the final iteration, I visit 4 indices — 2, 5, 3, 0 (the same as the first iteration). All for a total of 4 + 4 + 4 = 12 times.
So n=6 and I've counted a total of 12, resulting in a factor of 2. I could avoid this division by 2 by not overcounting in the first place. For eg. I could stop iterating at k = n/2, and in the last index, make sure that if the mirror positions are the same as the indices, not to count them twice. This involves a couple of extra conditions, and sometimes its just easier to overcount and account for it at the end, so I chose that route instead.
In problem C, n is supposed to be divisible by k. However, for test 3, n=200000 and k=64. Isn't that wrong?
200000 / 64 = 3125
Can someone please tell me where my logic is wrong for problem F? https://ideone.com/zhB5cl
It's failing for the sample test cases too.
EDIT: Was able to solve it. https://mirror.codeforces.com/contest/1332/submission/75045994
Noob here so sorry if this is obvious
In question A, why don't we add an or condition for the y-axis also? (x2<=x-a+b<=x1 || y2<= y-c+d <= y1) I mean, what there's a case if x condition is satisfied but not y
Thanks
You are correct, both the x and y-axis have to be considered. The author simply skipped the y-axis since he said at the beginning that it was the same for both.
You have to check both x1 <= x+b-a <= x2 and y1 <= y+d-x <= y2, plus the special cases also mentioned in the tutorial.
It's so sad that my E FSTed.. I can reach rk1 if it's not.. Again a quick power error!!
В Е есть ещё несложное решение, где не надо думать. Заметим, что если мы знаем кол-во полосок с чётной и нечётной суммой $$$1*k$$$ и $$$1*t$$$, мы можем узнать кол-во полосок с каждой суммой для $$$1*(k+t)$$$. А дальше то же самое с $$$n*k$$$ и $$$n*t$$$ -> $$$n*(k+t)$$$. И узнаем ответ для $$$n$$$ и $$$m$$$, как в быстром возведении в степень. Работает за $$$\log(n)+\log(m)$$$.
I liked E among the first 5 problems of the round.
I couldn't get accept during the round but fixed the problem after the contest.
the approach of solving this problem was a bit cooler than the others !
First c++ code is python code in problem C
Can someone elaborate why we need
*(MOD+1)in the solution1 of problem E? Thanks in advance.$$$\frac{MOD + 1}{2}$$$ is the inverse of $$$2$$$ for any odd modulo.
Oh did realize this, thanks!
Hi, I am wondering can this be generalised to (MOD + 1) / X where gcd(MOD, X) = 1 ?
It works only if $$$(MOD + 1)$$$ is divisible by $$$X$$$ — then $$$\dfrac{MOD + 1}{X} \cdot X \equiv 1 \pmod{MOD}$$$.
Oh yes that makes obvious sense thanks :) !!
Sorry I still can't understand the case when $$$n*m$$$ is even and $$$k$$$ is even. You said that only one grid can't be paired but I can't figured out which one. My current understanding is that when $$$a_{0,0}=k$$$ we can't xor it with 1, but this will give us many unpaired grids. Or we need other method to pair those grids? Great thanks!
Honestly, it doesn't matter that much what algorithm you choose to match them. I just found that second algorithm is the easiest to describe (odd $$$k$$$ case is only an easier example of it because every cell is modifiable).
For the even $$$k$$$ I basically wanted to choose any cell which can be modified with $$$xor~1$$$. The point is that if we modify a valid grid with this algorithm, the corresponding invalid grid should also get modified to that exact valid grid (I mean that's why I called that "pair up"). So I chose "the first cell" (idk like smallest row and smallest column in that row) value of which is not $$$k$$$.
So the only case that can't be matched is that all the cell is $$$k$$$ right?
Yup
Finally understand it. Thank you so much!
can anyone please explain how, dp is working in the f question how they ended up with these three equations??
Thank you :)
can anyone explain proof why there can’t be more than 11 in B ? it’s little foggy in editorial
First remember that any given $$$a$$$ is a composite number, that is it can be expressed as a product of $$$2$$$ integers both strictly greater than $$$1$$$.
Let $$$a$$$ be one such integer, $$$a \leq 1000$$$. Let $$$a = bc$$$ with $$$b,c > 1$$$. If both $$$b$$$ and $$$c$$$ are strictly greater than $$$\sqrt{1000}$$$ then $$$a > 1000$$$ which yields a contradiction.
Therefore at least one of them is smaller than $$$\sqrt{1000}$$$, and from now on let's consider that $$$b\leq\sqrt{1000}$$$. If $$$b$$$ is not prime, then there is one prime (smaller than $$$b$$$, therefore smaller than $$$\sqrt{1000}$$$) which divides $$$b$$$ and therefore divides $$$a$$$. If $$$b$$$ is prime, then $$$b$$$ is a prime number smaller than $$$\sqrt{1000}$$$ that divides $$$a$$$.
Now we know that for any given $$$a$$$, there is always a prime number smaller than $$$\sqrt{1000}$$$ which divides it. And it turns out there are only $$$11$$$ primes that meet this requirement !
So any given $$$a$$$ will be divisible by one of those $$$11$$$ primes. We can then greedily assign our colors with this in mind :)
thank you
what should be the answer of this test case? 1 3 2 1 97
elements of $$$a$$$ are guaranteed to be composite numbers.
As triple__a said, none of your numbers is valid. You should have read the first line of my message... $$$a$$$ can't be a prime or $$$1$$$ because it is composite.
In $$$E$$$, the omitted proof for matching grids with an even $$$k$$$ could be the following :
Take away all grids for which $$$a_{0,0} = k$$$ and do a regular matching. Then the set of all grids such that $$$a_{0, 0} = k$$$ remains unmatched. What we should do with it is applying the same trick but with an other $$$a_{i,j}$$$. The remaining unmatched grids will then be the ones for which $$$a_{0,0}=a_{i_,j}=k$$$. We may keep doing this until only the grid with $$$a_{i,j}=k$$$ for all $$$(i,j)$$$ remains. This is the only unmatched grid, and it is a valid one, hence the formula.
Thank you OP and every organizers for the contest ;)
Hey in question E can you plz help me to understand the observation 5 in the editorial.As they said that if n*m is even and every cell is odd we are not able to reach our goal but why? Like if we take 1*4 and the cell values as 1 3 5 7 then if we increase cell height by 2 at some point of time we are able to make it all equal i know i am missing something but not able to find it.Can you plz help me..thankyou.
it means the sum of elements are odd, not that every elements are odd
Nezzar is right, they said that the sum of all cells is odd. Any operation we make doesn't change the parity of such a sum. If we were to complete the game, as there is an even number of cells, the sum of all of them would be even, which in our case won't ever happen !
It's a small thing, but in editorial, k is defined as R — L(not R — L + 1), so your explanation is for not odd, but even k, isn't it?
You're right, it's for an even $$$k$$$, thank you.
I have used the exact same method as stated in the editorial for Question B — Composite Coloring but I got one of the test cases (not pretests) wrong. Here's my submission 74980482. Can anyone tell me why my code was wrong? Thanks.
How solve C using dfs. I saw some code used dfs to solve. But no node comes in my brain...
Basically for each i in range 1 <= i <= n — k , s[i] = s[n + 1 — i] , and s[i] = s[i + k]. Now you have to count how many letters should be the same in this cycle. The nodes are the indices. You can see my code, maybe you will understand.
Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).
Can anyone explain how the dp formula in problem F works in detail? I don't understand it. Thanks a lot.
Lets say a node has n children. Consider the child(v) along with the edge connecting the child as one group. The contribution for one group in the first formula is as follow:-
The edge is included in your edge-induced subgraph:- dpv1 + dpv0 Explanation:- You just have to take all possibilities.
The edge is not included in your edge-induced subgraph:- (dpv1-dpv) +dpv0 Explanation:- The term dpv is added because you need to remove the cases which would make v an isolated vertex.
By summing up both the terms you would get 2dpv0 + 2dpv1 -dpv, and now you just need to multiply the contributions of all the children.
I guess this will help you derive the other formulas. Let me know if you find any problems.
You mean dpv1 also counts the case that v is colored but isolated from all its children?
Yes
So dpu0 means we don't choose point u(no matter add edges or not), dpu1 means we must choose point u(no matter add edges or not), and dpu means for all sons of point u, we don't add the edge (u, v)? I don't know is it true to explain it in this way?
Yes thats correct if by "we don't choose"- you mean they are not chosen as part of the independent set
Yes, I get it. Thank you a lot.
!
1 is subtracted to remove the no edge case.
got it, thanks
How do we calculate dpu? It seems like it should be 2*(dpv1 +dpv0 — dpv) as it can come from cases when dpu is either coloured or uncoloured.
dpu is only needed for dpu1.
As my question below, it will be easier to understand dpu1 if it excludes dpu in the first place. When including dpu in dpu1, it actually includes case where u is isolated and colored. That's why when no edge between u and v and still need v in independent set, there must be some edge between v and its children. Thus it's needed to remove dpu from dpu1.
But for dpu0, it doesn't care whether there is an edge between u and its child v or not.
Thanks for the explanation.
But why include dpv in dpv1 rather than exclude dpv from dpv1 directly? Isn't the latter approach more intuitive? And the editorial emphasized on no isolated colored vertex. I mean when looking at dpv1, it's perfectly valid count if dpv is already excluded.
I know either way it's needed to deal with dpv. I just want to know the ideas here, or it's just happen to be this way.
Thanks.
No you need dpv to be in dpv1 because those cases will be used for the parent of v. It is fine for it to be isolated from bottom when it is connected to its parent by an edge.
Thanks again for the reply.
And I understand the part "It is fine for it to be isolated from bottom when it is connected to its parent by an edge."
Actually I can do it with dpv being excluded from dpv1.(https://mirror.codeforces.com/contest/1332/submission/75576336). It's just equivalent transformation.
I ask the question just because including dpv in dpv1 is kinda counter intuitive to me and different from what the editorial emphasized.
Never mind now. Thanks again. Happy coding.
Great contest and editorial
Great contest :))
What's the meaning of
s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;in the code of problem G?
Why can't we use
s1=p1,s2=p2;instead ?because you need to make the answer fit into range [L,R] instead of [L,n].
Since the code is doing precalculating, where does this $$$[L,R]$$$ come from?
since you should do carefully when $$$R=c[L]$$$. (check the code for notation.)
Now I think you are coping with equal elements.
s1：右边最后一个大于等于a[i]的位置+1 -> 右边第一个小于a[i]的位置
s2：右边最后一个小于等于a[i]的位置+1 -> 右边第一个大于a[i]的位置
So you will skip the equal elements to find "the closest to the right element greater than the top one" and "the closest to the right element smaller than the top one".
BTW：The code is slightly different from the solution about details. Hope you could provide one that does what the solution says.
the s1 and s2 is coping with the case where elements is the same as you mentioned. However, for range $$$L$$$ to $$$c[L]$$$, we cannot simply pick the element in the stack different from $$$a[i]$$$.
Consider the following case:
in this case and $$$i=1$$$, you are supposed to pick 3 and 7 instead of the second top element of the stack which should be 4 and 6 if you follow the implementation the code presents. (the conception is mentioned in the $$$O(n^2)$$$ indeed)
Can you explain more how to recover the min/max after we got the first and last index in a k=4 sequence? I am not understanding how to do this with just the stack.
Nvm, i was able to fix my solution to ac. i still don't get some parts of the editorial tho
to recover the index for $$$k=4$$$ case, my approach is pick the largest one in stacks so that it will not exceed $$$c[i]$$$. so the index should be i c[i] and those two if $$$b$$$ starts with $$$a[i]$$$.
Nice
I wonder if there is a typo in the formula of the combinatorics solution for task E. It should be $$$(E+O)^{nm}=\sum_{i=0}^{nm/2}E^{2i}O^{nm-2i}\binom{nm}{2i} + \sum_{i=1}^{nm/2}E^{2i-1}O^{nm-(2i-1)}\binom{nm}{2i-1}$$$ instead of $$$(E+O)^{nm}=\sum_{i=0}^{nm/2}E^{2i}O^{2i}\binom{nm}{2i} + \sum_{i=1}^{nm/2}E^{2i-1}O^{2i-1}\binom{nm}{2i-1}$$$ And similar for $$$(E-O)^{nm}$$$, could someone explain it?
Yes, you are correct. This is just the binomial expansion, $$$ (x+y)^n = \sum\limits_{i=0}^{n}{ n \choose i } {x^i y^{n-i} } $$$
Sorry, I got mixed up between your and editorials formula.
sorry, i will fix it!
I have taken a little while to realize this, now it's nice that you have fixed it! It 's much clearer now! :)
Worst contest ever
Actually I think this contest is really good.
The problems have very interesting ideas and appropriate difficulty.
And the problem writer is also a very nice man.
Then maybe my bad day, but somehow in any contest pikemike is involved i end up not even solving A. :(
To solve problem A, maybe you shouldn't think the problem in a too complex way?
practice more. Hope you good luck next time.
It's a very enjoyable round
Can someone who got acc on D to tell me how they thought to get to that solution?
Just a doubt for D though, what if we get a problem stating that find the maximum value you can get for going through (1,1) to (n,m), this dp in question is wrong for sure, then what is the correct dp or approach to solve this type of problem
I think backtracking is the only way to solve it correctly.
hmm, going through every possible path.
It's correct that dp solution goes through all the possible paths so apparently should give the best result. But the problem is the absence of optimal substructure in the problem, as taking the maximum AND of left and up paths isn't optimal. Correct me if I am wrong because I was really curious as how can dp not give the correct result.
check this floor
I know its trivial but,
Can you please tell me the intuition behind Problem B?
Because $$$a_i\leq 1000$$$, while in other problems $$$a_i$$$ is always $$$\leq 10^9$$$. It's very strange. And that means maybe we can find the answer from the relationship between $$$1000$$$ and $$$11$$$. Then it may be easier to realize that there are only 11 primes smaller than $$$\sqrt{1000}$$$.
In problem A, why I need the condition a+b=0?
It is given that x is in-between x1 and x2 and with the condition a+b=0 there is no need for movement in the x direction, so the verdict is a 'yes'.
And why do we need x2>=x1 and y2>=y1....these conditions?
Those are constraints given in the question.
Then explain me how the following test case prints a no: 1 1 1 1 1 1 1 1 1 1 Because in this test the final position of cat is (1,1) which is the very same position her cat starts walking from and which satisfies the given constraints in the question i.e x>=x1 && x<=x2 && y>=y1 && y<=y2. Then why does it prints a no. Also my second question that if the cat is at the same position with Alice after moving a,b,c and d moves that means the cat is safe and not being lost then again, WHY should it print a NO??
Let me explain why the cat goes in danger in the x axis. The cat is initially at x=1, and it is given that a=1 and b=1 so the cat now needs to move to x=0 or x=2 both of which are not 'safe' hence the answer is NO.
Why are you just considering 1D case??
That is sufficient to show that the answer is a no. I think you misunderstood the question, its not about checking weather the final position of the cat is safe instead the cat needs to be safe in the whole jurney. I suggest you to re-read the question.
In 1332A - Exercising Walk why can't we set y = y-(d-c). If I set x = x-(a-b) and y = y-(d-c), my output is wrong.
i think you can try with (c-d)..
It works for c-d. That's why I am asking why it doesn't work for d-c.
d is for moving along positive y direction and c is for moving along negative y direction why would you subtract your current position(initial y) with d and add it with c,rather you are supposed to do the opposite(which is y+d-c=y-(c-d))..it's so obvious.
Is B solvable using graph coloring where edge exist between two elements if their gcd is 1.
i don't know how you do the graph coloring. it really depends on your implementation. if you do it greedily, then the answer is no, and we have provided some tests against it in pretest 4.
I'm just curious in problem d ..since that dp algorithm fails...could there be a different dp approach which would actually lead to a correct solution triple__a ?
tbh i don't know if there is one solving this task with pure dp. but the checker i provide is checking bits from the most significant to the least, and it can be done with dp. idk if that counts or not.
Okay ..thank you:)
I think it's proper for a Chinese video solution(no it's just a recording) appearing under a Chinese contest editorial.
So, the link here : bilibili BV1at4y1m7V8.
Bullet screens and comments are welcomed.
If you like the video, please subscribe and leave a like (and 一键三连)!
If you don't like the video, leave your suggestions in the comment area below!
really appreciated! btw,
(and 一键三连)
Can you make tutorial available in English for F and G problems?
Can anyone explain Problem D. Tutorial isn't enough.
Another take on problem E:
Define polynomial multiplication like this: $$$x^{i} \times x^{j} = x^{(i + j) \mod 2}$$$. For example, $$$(1 + x)^{2} = 1 + 2x + x^{2}$$$ will be simply $$$2 + 2x$$$.
Let $$$p = $$$ number of even numbers in range $$$[L, R]$$$ and $$$q = $$$ number of odd numbers in range $$$[L, R]$$$. For even $$$nm$$$, the answer is the constant term of $$$(p + qx)^{nm}$$$, and for odd $$$nm$$$ the answer is sum of its both coefficients. Complexity will be $$$O(\log nm)$$$ with binary exponentiation. (Code)
This solution is also easy to generalize for different modulo classes and the polynomial multiplication be made faster with FFT if the modulo class is big.
In Problem E, It's mentioned that There is a general solution for this kind of problems.Can anyone provide any resource and more problems like that?
Let me appreciate the fact, Problem E was really nice!!
Please Explain C without DSU
Refer https://mirror.codeforces.com/blog/entry/75432?#comment-595594
why we have done ans/2 in 1332-C ?
i have checked for all pairs (i,j) such that $$$i+j=k-1$$$. so something like (k-1,0) and (0,k-1) will be both counted.
I'm trying to understand the solution of 1332E - Height All the Same. In the proof of observation 2 it says that you connect 2 cells of the same parity via a route. Let's take a more simple problem say you have an empty grid and you have 2 * k marked cells in this grid. You want to connect these up into k pairs such that the routes connecting different pairs are not crossing(i.e. they don't have a common cell). I think the proof of observation 2 assumes this is always possible. I don't yet see it why this is true.
I realized that
Ris only a bound in the beginning. I misunderstood the problem statement. Although the solution also stands whenRis a bound in the end because when you have 2 * k marked cells on an n * m grid you can connect them such that no 2 routes cross each other. Just take a Hamiltonian path in the grid(not too hard to find one) and pair up the elements along this path. What this means is that you can change the parity of the even number of elements by raising their value by 1 and raising the value of the elements along the routes by 2. This obviously requires the routes not to go through cells which already have height R."You want to connect these up into k pairs such that the routes connecting different pairs are not crossing(i.e. they don't have a common cell)"
crossing is allowed.
Yeah I figured that out in the meantime. I meant that if
Ris a bound in the beginning and the end as well and you haven * m % 2 == 1,L = 0andR = 2and an even number of 1s and an odd number of 0s you have to be able to connect them pairwise without crossing. This is possible, just line up the pairs on one of the Hamiltonian paths of the grid.What will be the correct DP algorithm for the D problem I want tabulation method correct algorithm for finding the path for a given grid where the and of all the element on the grid is maximum as possible
check this floor
can some one explain the easy intuition solution of pikmike (problem E) ?
You can just draw it out, like for these grids:
1x2, l = 1, r = 2;
1 1
1 2
2 1
2 2
1x2, l = 1, r = 3
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
There's 4 grids for the first one and half of them are even, and there's 9 grids for the second one and (9+1)/2 of them are even. I assumed it would be like that for all grids.
The intuitive part is that imagining all combinations of numbers, something like half of them will be even (we're looking for evens because there needs to be an even amount of odds, so sum has to be even).
Guys I found D solution so non-trivial and brilliant. How did you guys figured this out during the contest. What is the general thought process for approaching constructive algorithm based question.
Think how the DP approach might give a nonoptimal result.
triple__a I am wondering what is the checker code for problem D :)
For problem F, don't we need to consider stack overflow when using recursive dfs since n <= 3e5?
Nah, I think I'd solved some 5e5 problem using recursive DFS and still OK.
I don't have many ideas when I meet the constructive algorithm problems. Such as 630 div.2 D. I found that advanced CF players can solve those problems quickly. Can anyone give me some suggestions to improve my skill? Thanks a lot.
An alternative solution for D. Consider the example —
The algorithm uses: 11111 -> 10000 -> 11111 -> 1001, answer = 0
Optimal answer: 11111 -> 1111 -> 11111 -> 1001, answer = k
I used a quite different approach to solve the dp in problem F. Here instead of removing edges I just calculated the value of w(H) for any subgraph that may lie in the subtree of v. Then to calculate this assume dp[v][0] be the total value of sum(w(H)) for any subgraph that does not have any edge coming out of v, dp[v][1] be the value when there is at least one edge from the vertex v to at least one of its children but v is not counted in those independent subsets, and finally dp[v][2] be the value such that there is at least one edge to a child and also v is counted in the subsets. Then we obtain the following dp:
We can find it by assuming that if there are no edges from v then we can add any subgraph in a child to another subgraph in other children including a null graph. And by multiplying them we sort of add the independent sets together. Similarly, for the case where there is at least one edge from v to a child, we consider both cases for each child of whether to include it or not and subtract the cases when we don't include any one of them (inclusion-exclusion). The link to my submission: 76447494.
I don't understand one thing in solution of B. In the first test i have 10 different numbers, but also the number 11.
23 437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961
11 8 2 3 1 2 7 1 2 2 3 7 3 4 4 5 5 6 6 7 7 8 10 11
There is not the number 9. Why it isn't working? Please help
According to the problem statement, "for each color from 1 to m there is at least one element of this color". So, your m is 11, but there must be an element with color 9 too.
I know there must be 9, but when a do a solution like in this blog, there isnt 9
I solved the same way as in the editorial and got the correct answer. Maybe you should double check your code.
OK, I will do that, thanks
is there a problem in my code , i am getting tle on test 5 https://mirror.codeforces.com/contest/1332/submission/83755735
triple__a I guess solution provided for 1332A contains some bugs. kindly verify it by checking against following test case
1 2 3 0 0 0 0 0 0 1 0
Hi awoo, can you explain this line for your solution for Div2D?
how the question 1332C — K-Complete Word is from topics dsu and dfs, it didn't use any such algorithm but is listed in topic tags of dfs and dsu.
whu i get wrong answer in test 1 can someone help me??problem (B) https://ideone.com/uKkSIq