Записи в блоге

№	Пользователь	Рейтинг
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	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	163
2	cry	161
3	maomao90	160
4	-is-this-fft-	159
5	awoo	158
6	atcoder_official	157
7	adamant	155
7	nor	155
9	maroonrk	152
10	Dominater069	148

Блог пользователя Pa_sha

Codeforces Round 970 (Div. 3) Editorial

Автор Pa_sha, история, 3 недели назад, По-английски

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

Полный текст и комментарии »

Разбор задач Codeforces Round 970 (Div. 3)

Pa_sha
3 недели назад
191

Codeforces Round 970 (Div. 3)

Автор Pa_sha, история, 3 недели назад, По-английски

Hello Codeforces!

I am pleased to invite you all to participate in Codeforces Round 970 (Div. 3), which will start on Sep/01/2024 17:35 (Moscow time).

The format of the event will be like any Div. 3 rounds:

6-8 tasks;
ICPC rules with a penalty of 10 minutes for an incorrect submission;
12-hour phase of open hacks after the end of the round (hacks do not give additional points)
after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
by default, only "trusted" participants are shown in the results table.

I encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.

Only trusted participants of the third division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

take part in at least five rated rounds (and solve at least one problem in each of them),
do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

Also, it will be the first round with unrated register. If you already registered as rated participant you can change registration type here.

I would like to thank

MikeMirzayanov for creating Codeforces and Polygon and testing the round.
Vladosiya for beautiful coordination and helping in preparation.
FBI, SashaT9 and Skillful_Wanderer for not only testing but also discussion of the problems.
gmusya, Axial-Tilted, chen_zexing, Mr.Pie, XYZ_Herry, gvancak, Layk, CLown1331 and aboodsalman04 for testing and useful feedback.

Good luck!

UPD:

Editorial has been published.

Полный текст и комментарии »

Анонс Codeforces Round 970 (Div. 3)

+221

Pa_sha
3 недели назад
249

[Tutorial] Another way to look at the segment tree and many other data structures

Автор Pa_sha, история, 5 недель назад, По-английски

I haven't seen anyone to write about this technique, so I decided to make a blog about it. I know that it is mostly general intuition, but not everyone really understand it. Also, I would be happy if you add something in comments or correct some errors. Also, before reading this blog I recommend to have some knowledge about segment tree and divide and conquer.

I would like to thank riazhskkh and FBI for reviewing this blog.

The main idea

When we have some divide and conquer algorithm, we can memorize each recursive call to be able to operate with it as data structure. For example, when we do merge sort, we can memorize how array looked after sorting on each call. Using this we can get merge sort tree. Also, if we memorize quick sort in such way, we will get wavelet tree. A lot of standart ways to use divide and conquer would lead to segment tree. But, it also can be used when we divide array on 3 parts or more, when we divide considering parity of indexes of array and so on. One of the main usage of it, that we can do almost all operation which we can do on segment tree, such as lazy propagation or tree descent, (in fact it depends on the task that we are solving) and in the most cases it optimize solutions alot. For example, if we havee recursion that recursevily divide array on even and odd elements,

Here is what I mean

void rec(vector<int>&v)
{
    int mx=0;
    vector<int>odd;
    vector<int>even;
    for(int i=0;i<v.size();i++)
    {
        mx=max(mx,v[i]);
        if(i%2==0)
        {
            even.push_back(v[i]/2);
        }
        else
        {
            odd.push_back(v[i]/2);
        }
    }
    if(mx==0)
    {
        return;
    }
    rec(even);
    rec(odd);
}

and assume we memorize at each level (even and odd array each time), then we can do lazy propagation here. For example, we can add $$$x$$$ to all elements on the segment $$$[l,r]$$$, in the same way as in the segment tree. But this recursion can also solve queries to add $$$x$$$ to all elements with even (or odd) indexes on the segment $$$[l,r]$$$, or such indexes that are equal 3 by modulo 4, or in general any index that has last $$$k$$$ bits equal to some number. Also, as you may see, if we replace indexes by numbers, we would get a classic binary tree (a prefix tree).

The problem

We will solve this problem.

Solution

Firstly, we will solve the problem without queries. To make it easier, we can change vertex numbers on the tree using DFS.

For example, from this as in the statement to this .

After changing graph indexing, we can use divide and conquer to check if the permutation is good. In fact, for any vertex, all vertexes in its subtree after sorting should be continuous. It is true because of the way we change vertex numbers. So, it can be easily verified by just taking maximum and minimum of all subtrees and checking if there is the same number of elements between maximum and minimum as there is in the tree (It works because all elements are distinct). Important thing is that we can do it on segments, since segment [1,n] represents the whole tree, while segment [2, $$$\lfloor\frac{n+1}{2}\rfloor$$$ ] represents its right subtree, and segment [ $$$\lfloor\frac{n+1}{2}+1\rfloor$$$ ,n] represents its left subtree. Also, it is important to check if the depth of the vertex is the same. You see, in any DFS order, the depth of all vertices doesn't change, but it is easy to come up with a test, where divide and conquer solution will give yes and depths will be wrong.

Code of divide and conquer

// Check if a permutation correct on segment [l,r)
// d is array of depths. In other words, d[x] is the depth of a vertex x
bool check(int l,int r,int depth=0)
{
    if(l+1==r)
    {
        return 1;
    }
    int mid=(l+r)/2;
    return (depth==d[p[l]]&check(l+1,m)&check(m,r));
}

This solution works in $$$O(n\cdot log(n))$$$, but we can memorize all layers of a recursion call just like in the segment tree. In fact, all we need to memorize is a maximum and a minimum on a segment and if the segment is good (if check function from divide in conquer returns true or false). Then, we have queries which are to swap two elements. It is the same as changing the value of one element to the value of a second and vice versa for the second element, so all we need to be able to do is to change value of some element. Here, we can just memorize all states of recursion and make something like a segment tree, where segment [l,r) has children [l+1, $$$\lfloor\frac{l+r}{2}\rfloor$$$ ) and [ $$$\lfloor\frac{l+r}{2}\rfloor$$$ , r). So, it will work in $$$O(n\cdot log(n))$$$

Code

Note

This technique can be used not only as binary tree like segment tree, trie or other, but also as another data structures. So, if you have tree with depth $$$g$$$, then you can answer the query in $$$O(g\cdot C)$$$ time where $$$C$$$ is number of operation needed to make decision to the child of the vertex. It means, that in path graph and star graph this will work in linear time per query.

So, you can solve the last problem not only when it is binary, but also when it is random generated. It is because the depth of the random generated tree is $$$O(log(n))$$$.

Also, I believe there could be a lot more tricks like this. Like taking random vertex as a root or doing same on any graph but on MST and so on. Unfortunetly, I have no samples for this yet.

Полный текст и комментарии »

segment tree, divide and conquer, memoization, recursion

Pa_sha
5 недель назад
5

Eolymp Weekend Practice #3

Автор Pa_sha, история, 2 месяца назад, По-английски

We are excited to announce a new Weekend Practice round on August 3, at 19 UTC. This is a ranking competition at Eolymp.

Format and Difficulty

Same as in previous rounds, the competition is primarily aimed at improving practical skills. There will be 2.5 hours for 5 tasks of varying difficulty, the easiest of which can even be solved by beginners.

The scoring for each task being block-based (meaning points are awarded for each block of tests separately, and only if the solution passes all tests in the block). If there is a tie between two participants, the one whose last productive submission (i.e., a submission that added at least one point) was made earlier will be ranked higher in the leaderboard.

The statements will be available in the following languages: English, Ukrainian, French, Spanish, Azerbaijani, Russian.

Registration

You can join the competition on the competition page.

Prizes

The top-10 participants of the competition, as well as 10 random participants from those who rank from 11th to 100th place, will receive prizes in the form of t-shirts. Please, note, that we have changed how prizes are awarded,

Visit Frequently Asked Questions section to learn more.

Thanks a lot to:

arsijo for coordinating the contest
Sergey Kolodyazhnyy for creating Eolymp
FBI, SashaT9, Pa_sha for authoring the problems
Yam, MAKMED1337, Ignut, Vladosiya, Skillful_Wanderer, sashko123, waipoli for testing the contest

UPD

Congrats to the winners:

The editorial is available by the following links:

Полный текст и комментарии »

Pa_sha
2 месяца назад
26

Codeforces Round 891 (Div. 3)

Автор Pa_sha, 14 месяцев назад, По-английски

Hello Codeforces!

We are pleased to invite you all to participate in Codeforces Round 891 (Div. 3), which will start on Aug/07/2023 17:35 (Moscow time).

The format of the event will be like any Div. 3 rounds:

6-8 tasks;
ICPC rules with a penalty of 10 minutes for an incorrect submission;
12-hour phase of open hacks after the end of the round (hacks do not give additional points)
after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
by default, only "trusted" participants are shown in the results table.

We encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.

take part in at least five rated rounds (and solve at least one problem in each of them),
do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

Problems have been created and written by our team: FBI, Skillful_Wanderer, SashaT9 and Pa_sha.

We would like to thank

MikeMirzayanov for creating Codeforces and Polygon.
Vladosiya for coordination.
nigus, YocyCraft, lis05, Nazar, welleyth, pavlekn, senjougaharin, Vladithur, DJeniUp, volochai, eggag32, moonpie24, shell_wataru, Kalashnikov, Bogdan1110, ksu_, zamong_juice, myav, sonyalytv for testing the round and making it better.

Good luck!

UPD: There was an error on problem F. We fixed the tests and rejudged solutions . We apologize for that. It only affected a few people whose solutions passes all tests now. Also some hacks were already added to the tests and broke some of solutions.

UPD2: Editorial

Полный текст и комментарии »

Анонс Codeforces Round 891 (Div. 3)

+234

Pa_sha
14 месяцев назад
348

Блог пользователя Pa_sha

UPD:

The main idea

The problem

Solution

Note

Format and Difficulty

Registration

Prizes

Thanks a lot to:

Sponsors

UPD

The editorial is available by the following links: