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
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
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;
In 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 , Check 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})$$$
I don't think that last linked submission of yours is constant time. It uses the sqrt() function.
Check time/ standings
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.
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.
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
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!
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
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.