Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
int cnt1,cnt2;
cin>>cnt1>>cnt2;
if(cnt1%2)
{
cout<<"NO"<<endl;
}
else
{
if(cnt2%2==0)
{
cout<<"YES"<<endl;
}
else
{
if(cnt1==0)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
}
}
}
}
Solution in Python
t=int(input())
for _ in range(t):
a,b=map(int,input().split())
if a%2==1:
print("NO")
continue
if a==0 and b%2==1:
print("NO")
continue
print("YES")
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
int id=0;
while(id<n&&s[id]=='1')
{
id++;
}
if(id==n)
{
if(n==4)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
else
{
if((id-1)*(id-1)==n)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
}
return 0;
}
Solution in Python
for _ in range(int(input())):
n=int(input())
s=input()
i=0
while i<n and s[i]=='1':
i+=1
if i==n:
if n==4:
print("Yes")
else:
print("No")
continue
i-=1
if i*i==n:
print("Yes")
else:
print("No")
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
long long a,b;
cin>>a>>b;
b-=a;
long long l=2,r=1000000000;
while(l<r)
{
long long m=(l+r)/2;
if(m*(m-1)/2<=b)
{
l=m+1;
}
else
{
r=m;
}
}
cout<<l-1<<endl;
}
}
Solution in Python
for _ in range(int(input())):
a, b = map(int, input().split())
i = 0
while a + i <= b:
a += i
i += 1
print(i)
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
long long p[n+1]={0},b[n+1]={0};
int us[n+1]={0};
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
string s;
cin >> s;
for(int i=1;i<=n;i++)
{
if(us[i])continue;
int sz=0;
while(!us[i])
{
us[i]=1;
sz += s[i - 1] == '0';
i=p[i];
}
while(us[i]!=2)
{
b[i]=sz;
us[i]=2;
i=p[i];
}
}
for(int i=1;i<=n;i++)
{
cout<<b[i]<<" ";
}
cout<<endl;
}
}
Solution in Python
t = int(input())
for _ in range(t):
n = int(input())
b = [0] * (n + 1)
us = [0] * (n + 1)
p = [k-1 for k in map(int, input().split())]
s = input()
for i in range(0, n):
if us[i]:
continue
sz = 0
while not us[i]:
us[i] = 1
sz += s[i] == '0'
i = p[i]
while us[i] != 2:
b[i] = sz
us[i] = 2
i = p[i]
print(" ".join(map(str, b[:-1])))
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
int res=s.size();
if(n%2==0)
{
vector<int>v[2]={vector<int>(26),vector<int>(26)};
for(int i=0;i<n;i++)
{
v[i%2][s[i]-'a']++;
}
for(int i=0;i<2;i++)
{
int mx=0;
for(int j=0;j<26;j++)
{
mx=max(mx,v[i][j]);
}
res-=mx;
}
cout<<res<<endl;
}
else
{
vector<int>pref[2]={vector<int>(26),vector<int>(26)};
vector<int>suf[2]={vector<int>(26),vector<int>(26)};
for(int i=n-1;i>=0;i--)
{
suf[i%2][s[i]-'a']++;
}
for(int i=0;i<n;i++)
{
suf[i%2][s[i]-'a']--;
int ans=n;
for(int k=0;k<2;k++)
{
int mx=0;
for(int j=0;j<26;j++)
{
mx=max(mx,suf[1-k][j]+pref[k][j]);
}
ans-=mx;
}
res=min(res,ans);
pref[i%2][s[i]-'a']++;
}
cout<<res<<endl;
}
}
}
Solution in Python
t = int(input())
for _ in range(t):
n = int(input())
s = input()
res = len(s)
if n % 2 == 0:
v = [[0] * 26 for _ in range(2)]
for i in range(n):
v[i % 2][ord(s[i]) - ord('a')] += 1
for i in range(2):
mx = max(v[i])
res -= mx
print(res)
else:
pref = [[0] * 26 for _ in range(2)]
suf = [[0] * 26 for _ in range(2)]
for i in range(n - 1, -1, -1):
suf[i % 2][ord(s[i]) - ord('a')] += 1
for i in range(n):
suf[i % 2][ord(s[i]) - ord('a')] -= 1
ans = n
for k in range(2):
mx = 0
for j in range(26):
mx = max(mx, suf[1 - k][j] + pref[k][j])
ans -= mx
res = min(res, ans)
pref[i % 2][ord(s[i]) - ord('a')] += 1
print(res)
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
constexpr int mod=1e9+7;
long long binpow(long long a,long long b)
{
if(b==0)
{
return 1;
}
if(b%2)
{
return (a*binpow(a,b-1))%mod;
}
return binpow((a*a)%mod,b/2);
}
int main(){
int t;
cin>>t;
while(t--)
{
long long n;
cin>>n;
long long a[n],sum=0,sumsq=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];sum%=mod;
sumsq+=a[i]*a[i];
sumsq%=mod;
}
sum*=sum;sum%=mod;
sum=(sum-sumsq+mod)%mod;
sum=(sum*binpow(2,mod-2))%mod;
long long cnt=n*(n-1)/2;cnt%=mod;
cout<<(sum%mod)*binpow(cnt,mod-2)%mod<<endl;
}
}
Solution in Python
import sys; input = sys.stdin.readline
for i in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 0
s = 0
mod = int(1e9 + 7)
for i in range(n): s += a[i]
s %= mod
for i in range(n):
s -= a[i]
ans = (ans + a[i] * s) % mod
ans = (ans * pow(n * (n - 1) // 2, mod - 2, mod)) % mod
print(ans)
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
long long a[n+1],g=0,mx=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
g=__gcd(g,a[i]);
mx=max(mx,a[i]);
}
if(g==0)
{
cout<<k<<endl;
continue;
}
sort(a,a+n);
int q=-g;
if(n!=1)
{
for(int i=0;i<n;i++)
{
q+=g;
a[i]=q;
}
}
a[n]=1e16;
long long lst=-1;
for(int i=0;i<=n;i++)
{
if(k<=a[i]-lst-1)
{
break;
}
k-=max(a[i]-lst-1,0ll);
lst=a[i];
}
cout<<lst+k<<endl;
}
}
Solution in Python
import math
t = int(input())
for _ in range(t):
n, k = map(int, input().split())
a = list(map(int, input().split()))
g = 0
mx = 0
for i in range(n):
g = math.gcd(g, a[i])
mx = max(mx, a[i])
if g == 0:
print(k)
continue
a.sort()
q = -g
if n != 1:
for i in range(n):
q += g
a[i] = q
a.append(10**16)
lst = -1
for i in range(n + 1):
if k <= a[i] - lst - 1:
break
k -= max(a[i] - lst - 1, 0)
lst = a[i]
print(lst + k)
Tutorial
Tutorial is loading...
Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
int n,m;
cin>>n>>m;
vector<int>a(n);
vector<int>c(n+1,0ll);
for(int i=0;i<n;i++)
{
cin>>a[i];
c[a[i]]++;
}
for(int i=1;i<=n;i++)
{
c[i]+=c[i-1];
}
int res[n+1]={0};
for(int x=1;x<=n;x++)
{
int l=0,r=x;
while(l<r)
{
int mid=(l+r)/2;
int cnt=c[mid];
for(int k=1;k*x<=n;k++)
{
cnt+=c[min(k*x+mid,n)]-c[k*x-1];
}
if(cnt-1>=n/2)
{
r=mid;
}
else
{
l=mid+1;
}
}
res[x]=l;
}
while(m--)
{
int x;
cin>>x;
cout<<res[x]<<" ";
}
cout<<endl;
}
}
Solution in Python
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
c = [0] * (n + 1)
for i in range(n):
c[a[i]] += 1
for i in range(1, n + 1):
c[i] += c[i - 1]
res = [0] * (n + 1)
for x in range(1, n + 1):
l, r = 0, x
while l < r:
mid = (l + r) // 2
cnt = c[mid]
for k in range(1, n // x + 1):
cnt += c[min(k * x + mid, n)] - c[k * x - 1]
if cnt - 1 >= n // 2:
r = mid
else:
l = mid + 1
res[x] = l
for _ in range(m):
x = int(input())
print(res[x])
Great problem E. I had a little fun and leaked the solution with a useless if statement (that makes no logical sense and that is wrong):
if < 2: print(best + 2)and just a bit above that aif n == 1so that it would still AC even though there is something useless and wrong. This will make it easy to report cheaters. This is a new thing I think we should all do. Leak solutions with easy to spot but hidden watermark for those who don’t understand the algo. https://pastebin.com/VSP4VCnewe just need to crawl all AC and check those with a
if n < 2.This is an example of a cheater that would have never been caught otherwise: https://mirror.codeforces.com/contest/2008/submission/279191114 Because he or she was clever enough to really rework my solution.
Removing the useless
< 2and+ 2obviously still passes (I took his solution and removed the useless statement) and those who have read the problems will understand why + 2 makes absolutely no sense (and also doingif n == 1and just after thatif n < 2) https://mirror.codeforces.com/contest/2008/submission/279249347Great work lmao
It didn't work, MikeMirzayanov didn't see my comment :( https://mirror.codeforces.com/contest/2008/submission/279191114 didn't get skipped.
Smart!!!
It didn't work, MikeMirzayanov didn't see my comment :(
however if they have a brain and catch the weird code as they read, they might remove it which gives them a free AC (i guess plagiarism check will catch their solution if its similar but still)
If you need help for Div3.E you won't find the weird code. And the goal is to instil fear among cheaters, not to catch them all.
bro why havent the ratings been adjusted yet, any idea?
In such contests, there are long hacking phases. After them the new test cases from hacking are used to judge the accepted solutions. This is system testing. Once it finishes, there will be the ratings.
Another victim submission
So they cheated and didn't even manage to get AC, lmfao.
It didn't work, MikeMirzayanov didn't see my comment :( https://mirror.codeforces.com/contest/2008/submission/279191114 didn't get skipped.
Instead of that, why not just leak a hackable solution so you don't have to report it—just hack their code?
I'm not clever enough to do that unfortunately, but you should do it next contest if you have the IQ to do it!
Many people leak hackable codes; all you need to do is add a case that is not covered in the pretests and print a random answer for that case. Many dumb ppl fall for this.
I'm going to have to step up and spend some weeks learning how to leak hackable codes because the guy didn't even get skipped lol
The fact that the guy i mentioned didn’t get skipped is sad
@MikeMirzayanov MikeMirzayanov?
In problem F, I guess it should be "divide" instead of "delete first value by second" :)
Great round, I loved G and H very much.
Anyways, I read E wrongly during the round and I assumed we can do deleting operation as much as we want. Can anyone solve it? (if you can solve that, you can solve E easily.)
I solved during the contest too, all answers are same except "abacba", in that our answer will be 2 because we can erase 'c' and any 'a'.
My solution is based on dp (saving minimum number operation for i.th prefix, and our current string length is odd or even) and brute forcing 1st and 2nd char.
I added only one dimension for did I used any operation, if we delete that you can solve easily infinity version: 279135317
I solved the same misread on E initially
It is straight forward dynamic programming after fixing the alternating string characters
Can you explain how the misread problem is a dp problem? Even though I misread and can't solve E, I still want to solve the misread version more.
I have such solution. Fix first two characters and use dp for levenshtein distance. But it takes $$$O((k\cdot n)^2)$$$ time where k is the size of the alphabet
https://mirror.codeforces.com/contest/2008/submission/279276801 what I believe is correct.
The dp state is the parity of the string taken till now. the transitions come naturally from either deletion or modification or doing nothing
Brother, what happened to your rating in fall of 2023?
Looks like he's trolling.
Hey, sorry for bothering you, but I'm curious about your dp solution. During the contest, I attempted to solve it with dp but failed. Could you explain your approach a bit more, please?
Lemme explain, What MisterReaper has defined is this: dp[i][j][k] = minimum cost to build a k parity array from prefix i, and j is whether you have used a removal operation yet or not.
The transitions are better explained by looking at his code directly, but the general idea is to understand that when you want to build an even parity alt string with prefix i, then if: if your current character s[i] is suitable to take the place of the end of the string you are building that that's always optimal. Obviously then you would have to "pull" the rest of the answer from dp[i — 1][j][!k], !k because when replacing the alt string's last char, we would be building the rest of the string of a different parity. It's always a replacement unless we are making the deletion (obv!).
Now the "only one deletion" bit is not to difficult to infuse from here, if you trying to figure out the transitions of a state like dp[i][1][j] it can be pulled from two different states actually, which corresponds to whether you have already used up your operation (in which case you will pull from the dp[i — 1][1][!k] state, a replacement) and if you are going to use the operation on the current s[i] itself, in which case you need to pull from a dp[i — 1][0][k] state, note its k and not !k, because deletion will not change the parity of the string we are willing to build, we just need to "borrow" what i — 1 has already calculated.
Note that now the problem can be extended even more freely by changing the cost of the operations. Since we are taking care of every transition, adding the cost of deletion whenever we are deleting and similar for replacing and doing nothing (cost 0) is not a very difficult extension to the problem.
Thank you so much for the clarification! After reading your explanation, I believe I understand the logic behind this. However, I have one more question, we don't need to visit every state like his code, right? For example, when we tried to build the first character of the alt string, we simply needed to visit dp[1][0][0] and dp[1][1][0]. Is that correct?
Indeed for the forst character there are only two possible paths, however in general, all dp states needs to be transitioned properly, a state will automatically end up as "inf" if as you are implying, was unreachable.
Thank you, now I got it! Btw, I've just written a code for this problem. Although the time complexity I think is equal, I got TLE somehow. Is it because it has many if else statements in it? 279423444
Ahh, so the problem is the language version I chose, I didn't know gcc 13-64 run faster than gcc 7-32.
Thank you for your help, I appreciate it! Have a good day man!
you got this!
https://mirror.codeforces.com/contest/2008/submission/279144095
Why this solution get TLE for Problem D
try implementing dfs without funtion
may be recurion calls is taking time;
yes use for loop , that might help.
dfs would take time and would give tle, as the number of calls are more, subsequently you are doing additional operations on top of this,try via dsu (the existing structure is already in dsu format), have a look to my solution — https://mirror.codeforces.com/contest/2008/submission/279831257In the problem G tutorial there should have been k = k — a2 + a1 + 1 instead of k = k — a2 + a1 — 1
In C , Can be solved in $$$\mathcal{O}(\sqrt{r-l})$$$ and can be optimized by binary search in $$$\mathcal{O}(\log (r-l))$$$ using
, and can be optimized to $$$\mathcal{O}(1)$$$ by quadratic equation
The maximum length of array $$$a$$$ is obtained when the difference of two consecutive differences is minimized ; Thus we set the difference of two consecutive differences is only 1 , For example consider $$$l=1,r=10$$$ thus we can consider the following array as the optimal choice
thus the maximum length is $4$ , Notice we can form an $$$\textbf{Optimal Model}$$$ , $$$a$$$ can be considered as :
since each time we've an element $l$ + Sum of First $$$n$$$ integers called Triangular Numbers
We want to determine the value of $x$ above i.e.
We can reverse this with Quadratic Formula :
Consider
Since we may have rational part We've to perform ceiling , thus
279123925
Overall nice contest Pa_sha orz
because no one should be solving A like that
Optimization when not needed Bad solutions when not intended
At least I solved C assuming $$$(1 \le l,r \le 10^{18})$$$
Ok , I up-hacked some recursion solutions :D
279153158 Yerbool
279088236 NeIsenn
Hack by the hack of MathModel >_<
I'm wondering how the test used in hack MathModel didn't appeared in judging above hacked submissions ?!
I don't think that last linked submission of yours is constant time. It uses the sqrt() function.
Check time/ standings
It's not constant time. sqrt() is log2.
Reference
But sometimes, they may give wrong answer. So, it is better to use binary search to find sqrt in any case
Hi. Your solution for A cannot pass because it is $$$O(t\cdot (a+b)\cdot 2^{a+b})$$$ which is a lot. On maximum tests it is $$$100\cdot 20\cdot 2^{20}$$$ which is approximetly $$$10^9$$$.
For C you are right. In fact, $$$O(\sqrt{r-l})$$$ is okey for Div3B, so we didn't take it away.
Thanks for your feedback
please someone explain to me in problem: 2008G — Sakurako's Task. Why the gcd of all numbers is the key, I cant see the idea behind.
So there is a basic concept. If I give you 2 numbers like 2 and 3 and say you that you can use 2 and 3 any number of times and you can either add them or subtract them then what are the possible numbers you can generate.
Answer :- You can generate any integer from 2 and 3.
Reason :- GCD of 2 and 3 is 1 therefore you can use 2 and 3 to create 1 (3 — 2)
Now for any integer x you can generate it by using (3 — 2) x times.
Now take 2 and 4 for example. Their gcd is 2 so you can generate 2 from them (4 — 2). Now you can generate any even number from its gcd by repeating (4 — 2) any number of times but you cannot make any odd number using it.
Go in G after taking gcd of all, suppose gcd is x therefore optimal array to form will be [x, 2x, 3x, ... ]
Sorry if I made you more confused by my explanation but if your doubt is not cleared I will try to explain with a different approach.
great explanation
is there any blog that you can suggest to read for this topic
Actually there is a concept named Linear Diophantine Equation similar to this. You can look it up on Cp algorithms. Hope it helps.
But why this array is optimal... means how is it helping in finding kth mex maximum??
Ok so assume you have 2 arrays [1, 2, 3, 4] and [0, 1, 2, 3] what do you think which one of them will have max value of mex1
Array 1 will have mex = 0 and array 2 will have mex = 4.
Intuition :- It is best for us to make array elements as low as possible till zero and all the elements must be unique. This will ensure all the small elements are present in the array so the mex can be as large as possible.
Now combining all info above.
Let's assume you have an array [6, 2, 6, 4, 18]
For this to calculate the optimal array we need to calculate their gcd which is 2.
So optimal array looks like [0, 2, 4, 6, 8] if I tell you to find it's mex5 so the answer is 9
But we can also form our final array somewhat differently like [0, 4, 6, 8, 10] or [2, 4, 6, 8, 10] and mex5 in both the cases will be 7.
Why :- Because we ignored to form 1 more possible small number which minimized our mex value.
I hope you can understand this. If this is not clear now also then you can again message me I will try to help as much as I can.
thanks for the explanation! I also remembered that the euclidean gcd algorithm is very similiar to the described process. (Just substract b to a until a turns a % b, and then viceversa)
Updating the tests instead of the model seems like the wrong decision to me (i am biased though)
The last few cases I remember of a wrong model (but there exists a solution), they fixed the model and rejudged the solution
Can you explain why it was not done like that here? I remember an edu round and a div2 round where we got rejudged midcontest after the model was fixed
Vladosiya Pa_sha
Relevant meme :
Situation : Unit tests are failing
Vladosiya and Pasha : delete the unit tests
Also, Why isnt there more discussion on this?
Authors fucking changed constraints midway but a slightly too hard div2C gets more hate???
You don't need to curse or be rude every time. You're not umnik, and will never be.
you would be pissed off too if you spent 30minutes wondering where your code might go wrong and then it turns out authors cannot write a correct model.
I do not want to be a umnik, i want to be myself. Cursing comes naturally to me and I dont see the need to restrain from it.
Dominator orz, please calm down, I can't see my idol frustrated.
HurtfulI think he just accidentally got a little carried away due to his recent rating boosts.
is the div2C ur talking about from recent div 2? cuz i haven't been active lately
just in general, you will find tons of comments complaining about a hard div2C or something.
But, there are almost no comments complaining about how constraints were changed mid round...
i think the reason no one complain about the constraint change in this round's G is because the constraint change does not affect the initial solution for the problem pre-change, and all the change did is probably made some coders mildly annoyed because they had written some edge cases for the problem before the change.
i do agree tho that constraints change midway through contest can be fatal
You are right that the constraint change isnt the issue
The issue was that the authors wrote the wrong solution, and thus my correct solution was marked as incorrect before rejudging with the changed test data.
So it was me who was extra careful, while mostly everyone else wasnt
The reason for almost no complaint is pretty obvious imo. There were barely any solves from rated participants at that time. It was even before I submitted it, so I doubt if many people in rated range even read this problem at this point, so most people were unaffected by it.
Not saying that this decision was good, but you can see why the community's reaction is very different from the
hard Div. 2 C's, and probably the authors also had that in mind.Its probably because its a G, so many didnt even get to it. I personally got to it only after constraints changed, and only realised after contest that anything actually happened. Im not saying this justifies it or anything, just giving an explanation :D
Hi, first of all, I want to say sorry to you for this. For me, it is sad to look at all of this, because, I put the most afford in G among all tasts (I think because it has been changed little before contest).
For me, two solutions (your and what we have done) seem like equally good. I mean, if you know how to solve this problem, you should know how to do with that tests. But if we would notice this test before contest, it would be put in the samples, since in other case there would be wa2 everywhere. But we cannot change samples during the contest. So, I think this decision was better in this case.
One more time, sorry for inconvinience. We didn't want such think to happend.
it was a great contest, and i found G really enjoyable even though i upsolved it 15 mins after the round, thank you very much!
Was the original "main correct solution" wrong with the initial constraints? I mean, that's what they're saying but it looks like some other people just moved on to problem H (implying that they probably didn't get WA in the first place).
It is wrong, i asked a clarification, rhey admitted it
It fails on array = [0, 0, 4, 8] for example
So I guess many others did the same mistake, makes sense. Anyways, most people couldn't even be aware of what actually went wrong before it was fixed, so it's no surprise that this is not being discussed much.
It failed at tests where was more than one 0, because they cannot be changed.
But you did change samples during contest right....(0s to 1s) also somehow changing tests is fine but not changing samples?
I dont see why this is an issue. Not every error gets caught by samples and thats fine. It would have been much more fairer since wrong logic would not get AC.... I got penalized for being more correct, other people did not get penalized despite being wrong. This is just bad.
Why did you actually make the decision on G? I think its because you are more afraid of downvotes than being "fair" (even rejudging is sort of unfair, but I think its the less unfair choice since CF doesnt guarantee your results are final). Afterall, you will get more downvotes if people see they are getting wrong answer
Decision wasn't made by me and I don't know who made it is the first place, but I think that this decision is okey. In fact, I was not saying about "fair" or something like this, but I want it to be fair. Also, I don't see how contribution can be involved here. You are the only who says lot of bad staff about this situation. I mean, yeah, it was bad, but you don't need to be rude and write lots of comments like "it is bad, selfish, wrong decision". I see that you have wrong answer, but why you are ready to argue with it in a whole day while bad wa for contest where you are not official takes 30 minutes? I mean, I already said that I am sorry about it and as we saw almost no one get affected, so no one pays attention. Of course, if I will make more tasks in future, I will try to prevent happening such things.
To summarize, I was not making decision for G, but I think that it is good decision. It is not about contribution all this things.
That is my whole issue with what you did!!!!! (not you ok, whoever made the decision, lets call him X)
X tried to sweep the problem under the rug by not informing anyone (at the least an announcement informing me model is wrong was necessary before you go to fix your tests)
X made sure that very few people will get "affected" to ensure that you don't get comments like mine. Afterall, who will complain when they got an Accepted verdict.
I am not mad because I got a wrong answer verdict for 30 minutes. I am mad because of the way the issue was handled. Everything was done so as to minimize the "number of people affected" rather than being fair to people like me who had a correct solution. Since we are in the minority, X thought its fair.
Here is how to actually handle such an issue :
https://mirror.codeforces.com/contest/1814
Note how the announcements mention that they have a wrong model solution, then they fixed it and rejudged everyone? This is what you should have done. And even if you think removing tests instead is fine, the announcement about your model being wrong is deserved.
Yeah precisely, because your main goal was to minimize number of people who will say bad stuff instead of being fair. That's my whole point.
To summarize : Every decision about this was made in an attempt to remove your responsibility, not admit your mistake and save you from negative comments by not making 95% of people aware about the issue. This is the fundamental problem I have with what X did.
Look, there was no announcement about it because almost no one has been affected. I think it can be counted on the fingers the number of people who's solution actually gave another verdict after regudging. In the case you sent, there was already lot of solution on problem D, so it should have been announced. Our case is different. Also, since this discussion is in the comments of the tutorial, I am not making 95% of people not aware of it. No one say that it is not true. And as you see, no one argue about it. I don't think that it is because they are not aware, I think it is because they just don't feel like part of it or something like this.
It's still an issue, and some people still got affected by it, even though most of them were unofficial participants. I think it would've been fair to at least state that in the in-contest announcements. Also, it's not you who made some people aware of it. It was kept hidden until Dominater069 brought it up here.
Thank you for fast editorial
Hi I am a begginer and I really liked your effort on this round thank you for the answers so I can get the clues of coding
Very good problem H!
Could someone tell me ,for problem E , why this submission is giving wrong answer for test case 97 of test 2 . https://mirror.codeforces.com/contest/2008/submission/279256847
I solved problem E in
O(nlog(26))using two sets.For even ns my solution is basically the same.
For odd ns, I brute forced the index of the character to delete. First I deleted the first character from the string and inserted frequencies of other letters on odd and even indexes in each of these sets. Then for other characters, I updated the set of frequencies by erasing, updating and inserting a frequency of character.
you can also check my code if you're interested: 279194144
I did the same, actually. Couldn't work out all the kinks in time to submit it to the contest, but I had that idea and was able to finish implementing it later on
very nice idea for problem H. also, the sentence "we need to find the smallest element which has at least $$$\big\lfloor \frac{n}{2} \big\rfloor$$$ elements in the array that is less or equal to it" in the editorial for H is kinda confusing since some people might interpret it as "find the smallest element $$$h$$$ which has at least $$$\big\lfloor \frac{n}{2} \big\rfloor$$$ elements in the array that is less or equal to $$$h$$$ including $$$h$$$".
my suggestion is to change it into "we need to find the smallest element such that it has at least $$$\big\lfloor \frac{n}{2} \big\rfloor$$$ other elements in the array that is less or equal to it" or smth along that line. also, i can see that you use translator (probably) to write this edi.
In the editorial solution for F, why do we do
sum=(sum-sumsq+mod)%mod;instead of
sum=(sum%mod -sumsq%mod);to the best of my knowledge it is done when we want to take modulo of negative numbers however this doesn't make sense to me here since difference of sum — sumsq can't be negative mathematically , or i may be wrong some where plz help.
The latter is also correct
This code gives WA on 4 but if i change line
int num = (sum%MOD - pairsum%MOD);to
int num = (sum - pairsum + MOD)%MOD;it gets AC'ed why so ?
The reason for this is that in C/C++, the
x % MODoperation does not guarantee that the result will be in the range[0, MOD). In fact, whenMOD > 0, its range is(-MOD, MOD): for cases wherex >= 0, the range is[0, MOD), otherwise, the range is(-MOD, 0]. In your example,sum % MOD - pairsum % MODcan result in a negative number, which would makenumfall in the range(-MOD, 0]. This doesn't guarantee that the final answer is in the range[0, MOD), which can cause a Wrong Answer. By using(sum - pairsum + MOD) % MOD, you ensure that the result is always non-negative and within the desired range, which is why it gets AC. This is because whensum >= 0andpairsum < MOD,sum - pairsum + MOD > 0, which ensures the result is in the range[0, MOD).In fact, I would suggest writing
((sum - pairsum) % MOD + MOD) % MODinstead, as it offers better generality. Regardless of the ranges ofsumandpairsum, as long asMOD > 0, you will always get a result in the range[0, MOD). Note that ifsumandpairsumhave values that are very close to the upper or lower limit of the integer type (usuallylong long), using((sum % MOD - pairsum % MOD) % MOD + MOD) % MODprovides better reliability. However, since in most casessumandpairsumare already results after taking modulo withMOD, and the absolute value of their initial values are usually not large, not doing this is generally acceptable.Try
1 1 1 1 1 1 1 1000000000Thanks!
If i understood it correctly then ->
sum - sumsq >= 0 but (sum%MOD - sumsq%MOD) might be negative hence will not work.My bad, you are correct it's due to negative, because if it was a + sign between the two,your formula would have worked
G — Sakurako's Task gives TLE when using Binary Search but succeeds when I use linear search. Can anyone explain why? Shouldn't the binary search ideally take log(n) time?
Here are the two solutions -
Binary Search — https://mirror.codeforces.com/contest/2008/submission/279260235 Linear Search (as given in tutorial) — https://mirror.codeforces.com/contest/2008/submission/279260712
The diff is in last few lines, where I use either binary search or linear search.
if (k > (n - 1) * (gcd - 1))Potential int overflow here.
imo you should have made l and r constraints on C 10^18, so that linear search doesnt pass, and it would have to be binary search, but great contest nonethelesz
how to derive the second expression for problem F ?
Can someone explain how we are able to get every multiple of gcd in problem G? I understand that after doing operations whatever number we get, will be a multiple of the gcd. But after doing one operation we are also replacing the number. How can we prove that we will be able to get all the multiples
0, g, 2*g, 3*g, ...?Step 1 : First get gcd. You can follow Eculidean Algorithm for all pairs of adjacent elements in order and in the end you will have atleast 1 element = gcd.
Step 2 : convert every other element to gcd. We can just subtract gcd from each element while they are > gcd
Step 3 : make one elememt go to 0, make one stay at gcd, and make the others go up to i * gcd for i >= 2. We can always vhoose to add the element that we keep constant at gcd.
In the problem, we are allowed to add/subtract smaller array element to the larger one. I can't understand how your
Step 2is doing the same, like the operations. We are not allowed to directly subtract the gcd itself, right?Take a look at arr=[5,2] for example. You reduce 5 to 1 by using the 2, and then you reduce the 2 to zero using the 1.
Looks like I misread step 1 to just calculate the gcd of the whole array, lol. Got it know, thanks.
Can you please clarify some of the samples, copied below, from 2008G - Sakurako's Task?
Query: Can we not generate every positive number from 1 and 1? How can there be any mex other than 0?
Query: Can we not generate every positive number from 1 and 2? How can there be any mex other than 0? Also, 3 is part of the input array. We can choose to operate only on the 1 and 2, always leaving the 3 in the input array. How can it be a mex?
Query: Similar to previous case.
Read the problem statement again and notice why $$$k$$$ exists in the input.
Also, you don't 'generate' numbers. You can only 'change' the numbers.
Consider the initial array
(1, 1). As per the rules, the following is possible:Every positive number can thus be obtained.
Sorry if I am overlooking something trivial.
The problem wants you to find $$$mex_k$$$ on the array. Thus, being able to 'obtain' such numbers doesn't mean anything. For example, if $$$k=3$$$, $$$mex_k$$$ on the array (1, 7) is only 3. $$$mex_k$$$ on the array (1, 9999999999999...) is still only 3. One of the possible arrays you need to make in this case is (1, 2), so that $$$mex_k$$$ becomes 4.
Read the definition of $$$mex_k$$$:
mex_k is the k-th non-negative integer that is absent in the array.If you don't know what 'absent' is, it means that it should NOT exist in the array. So making large number is meaningless, because that number "exists" in the array, while you want it to "not exist" in the array.Thank you for explaining patiently.
is this hackable ???[submission:https://mirror.codeforces.com/contest/2008/submission/279192059]
Just a Newbie question, here in Problem C what is the maximum time complexity solution which will definitely pass. Though I've have used solution which takes O(sqrt(n)) or O(log n)(not sure about the time complexity of the c++ std sqrt() function) per test case and I think a solution with complexity greater than this might not pass. Anyone ?
Also can anyone explain how can we just by looking at the constraints here , which is 1<=t<=1e4 and 1<=l<=r<=1e9, guess the time complexity of a solution which will pass ?
if you use binary searc, where k is the answer then r can not be greater than l+(sum of first k-1 natural numbers. So the max number of searches you need is sqrt(r-l) or sqrt(10^9)
It's not O(long n) .It's O(log(n)) log for logarithmic . Also the c++ sqrt function is O(1) as mentioned by this comment
This contest rated or un rated??
https://mirror.codeforces.com/contest/2008/submission/279229487 can someone please tell me what I am missing here, thanks a lot
Not sure but i had the same problem . This is how i fixed it . tot=(n * (n — 1)) *inv(2); Or just multiply it at the end
There's a $$$O(nB+q\frac{n}{B}\log(\frac{n}{B}))$$$ solution in 2008H - Sakurako's Test.
279266745
(I can't tell the min value of the time complexity.In the submission,$$$B=2\times \sqrt n$$$,Welcome to hack.)
I think it is exactly the intended solution except that you precalculate the answers for $$$x \le B$$$. It is $$$O(nB + n \log^2 n)$$$ and is intended solution if you set $$$B = 0$$$ and don't recalculate the answer for same $$$x$$$.
Submission to D problem
Why is this submission giving a TLE? I am using DSU to solve and according to my analysis it shouldnt give TLE. Can anyone point out what might be going wrong?
You're visiting every components in the cycle for every node, it'll take n^2
Thanks for replying, but that wasnt the case actually. My friend pointed out what exactly was wrong and i was able to fix it. i was creating the array black of size N = 1e5 for all test cases t = 1e4 which was creating a complexity of O(1e9) and hence i was getting TLE. Plus i wasnt clearing my global vectors after each test case which was again leading to wrong answers
Was only able to solve 3 problems. Got stuck in the first one :(. Got nervous because I am contesting after long time
H. Sakurako's Test Why do we have to precompute answer for every x in 1..n? Max number of queries is the same as max n, so should be same amount of work even without precomputation.
It's because the time complexity of the Check function of the binary search has different time complexity depending upon the value of $$$x$$$.
Therefore, if you query all $$$x$$$ exactly once, then it works in $$$O(n + n/2 + n/3 + \dots) = O(n \cdot log(n))$$$
But if all queries contain $$$x = 1$$$, then it works in $$$O(n^2)$$$.
You don't really need precomputation. You just need to save the answer for each query, and reuse it when you encounter the same query again. Precomputation is just a way to make these answers in advance so that you don't need to make any decision on actual queries (just print the precomputed answer always).
AC 6 problems but only +12 expected delta... I want to be pupil.
good problem G and problem H
My E's solution passed with O(N * 26 * 26) .....
I'm praying, please system test doesn't burn me :(
Problem A The tutorial explains the concept well, but there is something that i could not understand in the python code. if a=4 and b=5, the output through the python code is "YES", but i am unable to figure it out how?
(1,1,1,1) and (2,2,2,2,2)
4 ones will cancel out 2 twos, then there will be remaining 3 twos which does not give 0 in any way by adding +/- operations.
lets take 3 pluses and 2 minuses for b, the value will now be 2, we can subtract 2 using two 1's from a, then we can add 1 and subtract one, making the final value 0
Yeah, I got it. Thanks!
why are the ratings not updated?
Typo in the editorial of B, it should be first character of the 'second' line
My solution for E had TLE when submitted twice in C++ 17 during the contest, but it got accepted when submitted in C++20 after the contest!
Perhaps the reason is not using fastio?
mathforces
Why RTE for D, https://mirror.codeforces.com/contest/2008/submission/279198427 ?
Python has a recursion limit, it cannot handle deep recursion. Your
dfsfunction probably got called over 1000 times deep, which made it RTE. You can set it by usingsys.setrecursionlimit()but it is still capped and you shouldn't rely on it. For workarounds, see https://mirror.codeforces.com/blog/entry/80158.Thanks!!
I am new to codeforces, it's my first contest, was that a rated contest ? if yes when the rating will be published ?
first time solved 5 problems in div.3!
did the rating changed for you ?
no,this round is an unrated round due to the poor network
Thanks for the round!
Does the condition $$$a_i \ge a_j$$$ in problem G affect anything in the current version of the problem? I feel that's the root cause of the issue; having unnecessary details (from the perspective of the model solution) can introduce unexpected cases.
do I get any rating for solving 4 questions here? m a newbie and had no idea that there are penalties. If anyone can clarify this it will be greatful.
The ratings have already been published, so I think you have already got your answer, but just to clarify, looking at your submissions, failure on the first first (aka sample tests) or a compilation error doesn't count as a penalty, so you only got one penalty for question A, which can be seen here: https://mirror.codeforces.com/contest/2008/standings/participant/190613374#p190613374
okkk thnx mate
E was harder that F and G
Problem F. Wrong.
Test 3 5 1 2 3 4 5
All pairs: (1,2+3+4+5)=14 (2,3+4+5)=24 (3,4+5)=27 (4,5)=20 SUM = 85 AMOUNT OF PAIRS = 10 So the expected value is 8.5 Can be shown as 17/2 -> P = 17, Q = 2
Now the fun part: Q^(-1) = 1/2 So P*Q^(−1) = 8.5 (mod 10^9+7) = is still 8.5
Okay, it can be a mistake and we wanted to output P*Q
P*Q = 34. How. We. Get. 500m. ?
I guess it's me who is in wrong here, because many contestants did the task. But unless i see normal explanation how we get 500m here, i will continue to claim that the problem is wrong. I see that solution uses division by modulo, but here you have a simple test, that doesn't need it. And it's seems to be wrong.
its unfortunate that author did not tell what $$$Q^{-1}$$$ means especially because this is div3
$$$Q^{-1}$$$, defined for $$$0 < Q < 10^9 + 7$$$, is the unique integer in $$$(0, 10^9 + 7)$$$ such that $$$Q \cdot Q^{-1} = 1$$$. In this definition, you can check that $$$2^{-1}$$$ is $$$5 \cdot 10^8 + 4$$$.
$$$17 \cdot 2^{-1}$$$ is thus $$$17 \cdot (5 \cdot 10^8 + 4)$$$. You can verify this comes to $$$500000012$$$
Stop whining about the author in every comment. First, check your own rounds on CodeChef — your samples are unclear and ambiguous. If you are too much concerned about a beginner than look your codechef rounds you expect someone to understand the problem by looking at 2 samples and that to with n = 1 or 2. And if you think you are providing the feedback than learn how to give feedback like this by djm03178. No one had any problem with this round and just you are shouting and you are getting frustated because no one cares about your opinions and this is also shown by the downvotes you received on this posts.
Just because you had a decent showing in a recent contest doesn’t mean you should start acting superior. You’ll always be a kid of um_nik.
i dont want to reply to a unlinked account but i am curious.
This is the second time someone mentioned um_nik and how i will never become him. Why lol? I am genuinely curious. Is it just because of that one comment?
you don't want to reply to an unlinked account because you don't have any points to counter and reply. It is what it is. This account is registered 2 years ago which is same as your account.
um_nik started acting rudely after winning multiple div1s and created his personality just like that and most of the time he does it in a funnier and sarcastic way. but you are trying to replicate the same behaviour of um_nik without even getting in top 10 in div1. even if you don't agree on this but all your comments about this round are just like that.
i think i have every right to such comments when author messed up model solution and DID NOT EVEN ACKNOWLEDGE IT (this is the bigger issue). I dont care whether you think my comments are right or not, because they are right to me.
One can always argue about how criticism is communicated, but the core of Dominater069’s argument is 100% valid. The authors should not have changed the problem mid-round, but instead should have been open about their mistake and should have corrected their own solution. The impact was limited this time around as it mainly impacted higher-rated participants who were out-of-competition, but it probably robbed neal of a first place and the same handling of the issue in a division 1 or 2 contest would have resulted in a lot more noise.
thanks, i agree that maybe i was overly rude and etc. I was frustated and author did not want to admit they made a mistake, which only piled onto it.
You must be my biggest fan, because I myself cannot remember when I "started acted rudely" or "created my personality", and whether it was after I won multiple div1s. Probably because I was "rude" (which is a word people use when I'm technically correct but not polite and not quiet about it, and they can't actually argument with me, so they have to dismiss me in a different way) long before I even registered on Codeforces.
Now about Dominater's comments on this round. Some comments are just chatting with others or helping newbies with questions. Actually, the comment that started your unwarranted crusade is exactly this: a person asked a question, and Dominater answered the question. Yes, with a reasonable remark about the fact that in div3 there should be a definition of inverse element modulo $$$P$$$. What troubled you, other than the fact that you wanted to vent, — I don't know.
And all other comments are about (mis)handling the situation with a wrong model solution. Some might not like the tone, but he is 100% in the right.
I dont usually expect people to look at samples to understand the problem. Can you send the exact problem you are referring to? I usually dont put only n = 1 and 2 in samples.
A problem had a wrong model solution, and worst of all there was no information on it. you dont think thats an issue?
I dont care about contribution, please downvote me more.
I am not providing feedback. I know how to provide feedback thank you very much. I was frustated and I was expressing my frustation.
If you reply, I will continue in DM. I don't want to spam blog even more especially on an unrelated thread.
I dont usually expect people to look at samples to understand the problem. Can you send the exact problem you are referring to?
in this problem, the problem statement is a bit lengthy and contains a story, yet there are only two sample cases with n=2 and n=3. The problem is rated 1269, which falls under Division 4. Among the 19 Division 4 rounds held to date on Codeforces, there hasn't been a single problem with just two sample cases for n=2 and n=3. While an experienced participant might understand the problem statement just by reading it, a beginner often relies on sample cases to ensure they've understood the problem correctly. And this is just one of many examples.
A problem had a wrong model solution, and worst of all there was no information on it. you dont think thats an issue?
I'm not saying that the wrong model solution isn't an issue—the author openly admitted his mistake. What more could you ask for? The nature of problem-setting is prone to errors, and sometimes these can be overlooked. Has CodeChef never had issues with their problems? They definitely have, and many times problem statements have been changed without notifying anyone.
I dont care about contribution, please downvote me more.
When did I say that you only care about your contribution or are doing this for upvotes? I pointed out that you're getting downvotes on this, which basically means that the community disagrees with you. If a red coder is getting downvotes, it means that they're writing something stupid that others consider incorrect or nonsensical.
I am not providing feedback.
So you're saying that I'm not giving feedback, which implies you're just trolling the author. Learn to be patient in life—you're not a president somewhere and things should go exactly according to your wishes or opinions.
If you reply, I will continue in DM.
Feel free to continue this in DM—my DMs are not closed like yours.
Polygon advices (This is official codeforces guide often shared by coordinators).
Output <...> modulo $$$998\,244\,353$$$.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
can someone help in figuring out why my E fst'ed?
https://mirror.codeforces.com/contest/2008/submission/279235492
https://mirror.codeforces.com/contest/2008/submission/279123663
whats wrong with this my rank dropped from 600 to 2k after system testing
Why this gives WA for 5th test case in F
https://mirror.codeforces.com/contest/2008/submission/279369074
You can't directly do
f/2, instead you have to dof*binpow(2, mod-2) using fermat's little theoremjust like you did below itThanks for pointing out...I forgot to do modulo inverse for 2 also since I thought it wont be required
I have slightly different solution for 2008B - Square or Not than the solution given by authors: It's clearly mention that the string s is derived from a beautiful matrix, so if it has to be squared two conditions are suffices:
Initially we count how many ones and zeros are present in the mentioned beautiful matrix, It's pretty easy, right? Number of ones = r + r + c-2 + c-2
Number of zeros = n * n -Number of ones
Length of the string should be a perfect square and,
count of zeros and ones are exactly as same as we count for beautiful matrix.
And It works!!
Here is my submission: 279088062
Can anyone help me in debugging G, though i changed my approach and got AC but still no idea whats wrong there. Submission
why do we need to calculate inverse modulo of 2 in n * (n-1)/2? Can we just divide upfront and then take the inverse modulo of the quotient ?
No need take inverse modulo of 2, Yes you can, n or n-1 is even hence it's divisible by 2!! just take inverse mod of (n * (n-1)/2) % mod And it works!!
My submission: 279251237
Solution of problem D using DSU(Union-Find). https://mirror.codeforces.com/contest/2008/submission/279404607
Can anybody Tell me why this submission of mine for D using map, give TLE. Map takes log(n) times for performing insertion and extraction operations, but that has never happened before with me that using map gave TLE and array solution for storing key worked fine.
You have linked the wrong submission, but I found the code which gave you TLE anyways.
You need to replace
if(mp[i])withif(mp.contains[i])and there wouldn't be any TLE. You can check this blog out to understand (TL;DR: Usestd::map::findorstd::map::containsand notstd::map::operator.)sorry for the wrong link but thanks ser!
Hey guys I'm in doubt about 5th problem alternating string
if we have test case like "aaaaaaabab" having n=10
this will give output 2 but it should be 3 ? because if output is 2 then string going to look like "aaaaaaaaaa" which is not alternating
can anyone help??
aaaaaaaaaa is actually alternating because they didn't said that characters in even position cant be the same as odd ones
For B they have given this code.
But the issue in this code is, it will output "Yes" for this type of string also. s = "1111110101100011000111111" (Which is absolutely wrong).
I think they should review their code.
The string is always the result of writing out the strings of a beautiful matrix.
I took it from the input section of the task B. Your matrix isn't beautiful.
Solution of problem B is wrong as it will give yes in case of example like 9 111100000 or 9 111101110
All the problems were fun, this is the most I've enjoyed any contest. Thanks!
For H, when we are finding the count of elements between say 0 — m, x — x + m, 2x — 2x + m... isn't there a possibility of overcounting if the segments overlap?
(oh wait m is always < x... since it's the result after % x)
In H, I didn't understand why we have to calculate it for all k, like we already had the number of elements less than or equal to x using prefix sums then why we are calculating for all k?. Does this have anything to do with the range that m (with which we are taking mod) can span within n and then basically calculating for all these spans?Hello there, In Problem E, it is specified that the sum of n across all test cases shouldn't exceed 2e5. On test 3, n = 2e6.
In problem G, it's impossible for $$$g$$$ to be 0.
What is g?
in tutorial $$$g = gcd(a_1,a_2,....,a_n)$$$
Yes. It is impossible. There was nothing about it
There is, he said in the editorial if the g is 0 print k, and in both codes he checked whether g is zero or not.
problem H: ~~~~~ 6 2 2 2 5 1 1 6 ~~~~~ when x = 6, I can only operate on i = 6, then it will be 0 1 1 2 2 5, why can I get answer = 1? thank you!
I got it wrong, sorry.
In problem H, the fact that the values of $$$x$$$ can be repeating among the queries feels unnecessary; the requirement to precompute/store the answers in an array could be omitted. Although a very good problem!
For problem G, I don't really understand why the solution isn't about Bezout's identity. It produces a(in my opinion) much neater solution.(maybe not really)
Can you tell me about this solution?
In F for case: 5 1 2 3 4 5 shouldn't the expected value be: 5*4 + 5*3 + 5*2 + 5 + 4*3 + 4*2 + 4*1 + 3*2 + 3*1 + 2*1 all divided by 5*4/2 that is 8.5 ?
for E, bro i almost had the submission using upperbounds in 2140ms. if only there was a bit more time; feel like crying https://mirror.codeforces.com/gym/552240/submission/282607953
For the problem D. Sakurako's Hobby , did anyone's DSU solution got accepted?
Here's my code and it's giving TLE:
I think there's a better way to count the final ans.
can someone please explain why this is giving WA ? THE soln is same as that of tutorial https://mirror.codeforces.com/problemset/submission/2008/284664985
For G, I thought
a_i = (i-1) * gora_i = i * g(Multiples of g excluding 0). I took the maxmex_kout of the two sequences, I got a WA. Can anyone (whoever might see this) kindly point out why this is wrong with this?