Codeforces Round 970 (Div. 3) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	cry	157
3	nor	157
5	atcoder_official	156
6	-is-this-fft-	155
7	maroonrk	154
8	adamant	153
9	Um_nik	152
10	djm03178	146

2008A - Sakurako's Exam

Tutorial

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")

Rate the problem

2008B - Square or Not

Tutorial

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")

Rate the problem

2008C - Longest Good Array

Tutorial

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)

Rate the problem

2008D - Sakurako's Hobby

Tutorial

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])))

Rate the problem

2008E - Alternating String

Tutorial

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)

Rate the problem

2008F - Sakurako's Box

Tutorial

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)

Rate the problem

2008G - Sakurako's Task

Tutorial

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)

Rate the problem

2008H - Sakurako's Test

Tutorial

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])

Rate the problem

#include <bits/stdc++.h> #define pb push_back #define int long long #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define lb lower_bound #define ub upper_bound #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std; #define MOD 1000000007 using namespace std; int modmul(int a , int b , int mod){ return (a % mod * b % mod) % mod; } int fastpow(int a, int b, int mod) { int ans = 1; a = a%mod; while (b > 0) { if (b & 1) { ans = modmul(ans,a,mod); } a = modmul(a,a,mod); b >>= 1; } return ans%mod; } int inv( int a , int p){ return fastpow(a , p-2 , p); } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum = (sum + a[i])%MOD; } sum = (sum%MOD * sum%MOD)%MOD; int pairsum = 0; for(int i=0;i<n;i++){ pairsum = (pairsum + ((a[i]%MOD*a[i]%MOD)%MOD))%MOD; } int paircnt = (n*(n-1))%MOD; int num = (sum%MOD - pairsum%MOD); int paircnt_inv = inv(paircnt,MOD)%MOD; num = (num%MOD*paircnt_inv%MOD)%MOD; cout << num << endl; } return 0; }

Comments (46)

Write comment?

hellotherehello

4 hours ago, # |

← Rev. 9 →

+14

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 a if n == 1 so 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/VSP4VCne

we 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.

Spoiler

→ Reply

axrav1saini

2 hours ago, # ^ |

Great work lmao

LightSky

In problem F, I guess it should be "divide" instead of "delete first value by second" :)

MisterReaper

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.)

Spoiler:

Dominater069

4 hours ago, # ^ |

I solved the same misread on E initially

It is straight forward dynamic programming after fixing the alternating string characters

unRated110

https://mirror.codeforces.com/contest/2008/submission/279144095

Why this solution get TLE for Problem D

Butcher_77

3 hours ago, # ^ |

try implementing dfs without funtion

may be recurion calls is taking time;

DDato

In the problem G tutorial there should have been k = k — a2 + a1 + 1 instead of k = k — a2 + a1 — 1

MathModel

← Rev. 4 →

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

$$$\frac{n(n+1)}{2}$$$

, and can be optimized to $$$\mathcal{O}(1)$$$ by quadratic equation , Check 279123925

Overall nice contest Pa_sha orz

shiinamashiro_

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})$$$

s3yoonpark

I don't think that last linked submission of yours is constant time. It uses the sqrt() function.

Check time/ standings

Pa_sha

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

KhozmoS

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.

Im_Gonna_Be_King_Of_Reds

← Rev. 3 →

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.

arihant_j

77 minutes ago, # ^ |

great explanation

3 hours ago, # |

+16

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

← Rev. 2 →

-7

Also, Why isnt there more discussion on this?

Authors fucking changed constraints midway but a slightly too hard div2C gets more hate???

returnAC

-6

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.

CF_contest_practice_2

64 minutes ago, # ^ |

I think he just accidentally got a little carried away due to his recent rating boosts.

HexShift

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

SkibidiPilav

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!

Kolyanchick

Thank you for fast editorial

ckayra9

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

AkramElOmrani

Very good problem H!

pranshu_2004

2 hours ago, # |

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

saba_goduadze

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.

avisharma444

99 minutes ago, # |

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.

Ashar-Usmani

96 minutes ago, # ^ |

The latter is also correct

89 minutes ago, # ^ |

This code gives WA on 4 but if i change line

int num = (sum%MOD - pairsum%MOD);

int num = (sum - pairsum + MOD)%MOD;

it gets AC'ed why so ?

aryanc403

78 minutes ago, # ^ |

Try 1 1 1 1 1 1 1 1000000000

67 minutes ago, # ^ |

Thanks!

If i understood it correctly then ->

sum - sumsq >= 0 but (sum%MOD - sumsq%MOD) might be negative hence will not work.

30 minutes ago, # ^ |

My bad, you are correct it's due to negative, because if it was a + sign between the two,your formula would have worked

re.Think

72 minutes ago, # |

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.

57 minutes ago, # ^ |

if (k > (n - 1) * (gcd - 1))
Potential int overflow here.

62 minutes ago, # |

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

Pa_sha's blog