Codeforces Round #630 Editorial
Difference between en7 and en8, changed 0 character(s)
Hope you enjoy those tasks!↵

[problem:1332A]↵

<spoiler summary="Tutorial">↵
[tutorial:1327A]↵
</spoiler>↵

<spoiler summary="Solution (python by pikmike)">↵

~~~~~↵
t = int(input())↵
for _ in range(t):↵
a, b, c, d = map(int, input().split())↵
x, y, x1, y1, x2, y2 = map(int, input().split())↵
x += b - a↵
y += d - c↵
if a + b > 0 and x1 == x2:↵
print("No")↵
elif c + d > 0 and y1 == y2:↵
print("No")↵
elif x1 <= x <= x2 and y1 <= y <= y2:↵
print("Yes")↵
else:↵
print("No")↵
~~~~~↵


</spoiler>↵

<spoiler summary="Solution (C++)">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵

int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;↵

int main(){↵
    int t;↵
    cin>>t;↵
    while (t--){↵
        cin>>a>>b>>c>>d;↵
        cin>>x>>y>>x1>>y1>>x2>>y2;↵
        xx=x,yy=y;↵
        x+=-a+b, y+=-c+d;↵
        if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){↵
            cout<<"Yes\n";↵
        }↵
        else{↵
            cout<<"No\n";↵
        }↵
    }↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

[problem:1332B]↵

<spoiler summary="Tutorial">↵
[tutorial:1332B]↵
</spoiler>↵

<spoiler summary="Solution (python by pikmike)">↵

~~~~~↵
from math import gcd↵

def getprime(x):↵
for i in range(2, x):↵
if x % i == 0:↵
return i↵
return -1↵

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]↵

t = int(input())↵
for _ in range(t):↵
n = int(input())↵
a = [int(x) for x in input().split()]↵
used = [False for i in range(11)]↵
clr = []↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
used[x] = True↵
clr.append(x)↵
cnt = 0↵
num = []↵
for i in range(11):↵
num.append(cnt)↵
if used[i]:↵
cnt += 1↵
print(cnt)↵
for i in range(n):↵
x = primes.index(getprime(a[i]))↵
print(num[x] + 1, end = " ")↵
print()↵
~~~~~↵


</spoiler>↵

<spoiler summary="Solution (C++)">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
 ↵
int n,t;↵
vector<int> ans[1007];↵
int res[1007];↵
int main(){↵
    ios::sync_with_stdio(false);↵
    cin.tie(0), cout.tie(0);↵
    auto f=[&](int u){↵
        for (int i=2;i<=u;++i){↵
            if (u%i==0) return i;↵
        }↵
    };↵
    cin>>t;↵
    while (t--){↵
        cin>>n;↵
        for (int i=1;i<=1000;++i) ans[i].clear();↵
        for (int i=1;i<=n;++i){↵
           int u;↵
           cin>>u; ans[f(u)].push_back(i);↵
        }↵
        int ret=0;↵
        for (int i=1;i<=1000;++i){↵
            if (ans[i].size()){↵
                ++ret;↵
                for (auto c:ans[i]){↵
                    res[c]=ret;↵
                }↵
            }↵
        }↵
        cout<<ret<<"\n";↵
        for (int i=1;i<=n;++i){↵
            cout<<res[i]<<" ";↵
        }↵
        cout<<"\n";↵
    }↵
    return 0;↵
}↵
~~~~~↵


</spoiler>↵

[problem:1332C]↵

<spoiler summary="Tutorial">↵
[tutorial:1332C]↵
</spoiler>↵

<spoiler summary="Solution(C++)">↵

~~~~~↵
from sys import stdin↵

t = int(stdin.readline())↵
for _ in range(t):↵
n, k = map(int, stdin.readline().split())↵
s = stdin.readline()↵
cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]↵
for i in range(n):↵
cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1↵
ans = 0↵
for i in range(k // 2):↵
ans += 2 * n // k - max(cnt[i])↵
if k % 2 == 1:↵
ans += n // k - max(cnt[k // 2])↵
print(ans)↵
~~~~~↵

</spoiler>↵

<spoiler summary="Solution(C++)">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵

const int maxn=200007;↵

int n,k,ans=0;↵
int cnt[maxn][26];↵
string s;↵

int differ(int u,int v){↵
    int ret=0,mx=0;↵
    for (int j=0;j<26;++j){↵
        ret+=cnt[u][j]+cnt[v][j];↵
        mx=max(mx,cnt[u][j]+cnt[v][j]);↵
    }↵
    return ret-mx;↵
}↵

int main(){↵
    int t;↵
    cin>>t;↵
    while (t--){↵
        cin>>n>>k>>s;↵
        for (int i=0;i<k;++i){↵
            for (int j=0;j<26;++j){↵
                cnt[i][j]=0;↵
            }↵
        }↵
        for (int i=0;i<n;++i){↵
            cnt[i%k][s[i]-'a']++;↵
        }↵
        int ans=0;↵
        for (int i=0;i<k;++i){↵
            ans+=differ(i,k-1-i);↵
        }↵
        cout<<ans/2<<"\n";↵
    }↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵

[problem:1332D]↵

<spoiler summary="Tutorial">↵
[tutorial:1332D]↵
</spoiler>↵

<spoiler summary="Solution(python by pikmike)">↵

~~~~~↵
k = int(input())↵
x = 2**17↵
print(2, 3)↵
print(x^k, x, 0)↵
print(k, x^k, k)↵
~~~~~↵

</spoiler>↵

[problem:1332E]↵

<spoiler summary="Tutorial">↵
[tutorial:1332E]↵
</spoiler>↵

<spoiler summary="Solution 1(python by pikmike)">↵

~~~~~↵
MOD = 998244353↵

n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
elif (r - l + 1) % 2 == 0:↵
print(pow(r - l + 1, n * m, MOD) * (MOD + 1) // 2 % MOD)↵
else:↵
print((pow(r - l + 1, n * m, MOD) + 1) * (MOD + 1) // 2 % MOD)↵
~~~~~↵

</spoiler>↵

<spoiler summary="Solution 2(python by pikmike)">↵

~~~~~↵
MOD = 998244353↵

n, m, l, r = map(int, input().split())↵
if n * m % 2 == 1:↵
print(pow(r - l + 1, n * m, MOD))↵
else:↵
e = r // 2 - (l - 1) // 2 ↵
o = (r - l + 1) - e↵
print((pow(e + o, n * m, MOD) + pow(e - o, n * m, MOD)) * (MOD + 1) // 2 % MOD)↵
~~~~~↵

</spoiler>↵

[problem:1332F]↵

<spoiler summary="Tutorial">↵
[tutorial:1332F]↵
</spoiler>↵

<spoiler summary="Solution(C++)">↵

~~~~~↵
#include<bits/stdc++.h>↵
#define int long long↵
#define ULL unsigned long long↵
#define F first↵
#define S second↵
#define pb push_back↵
#define rep(i,n) for(int i=0;i<(int)(n);++i)↵
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)↵
#define range(a) a.begin(), a.end()↵
#define PI pair<int,int>↵
#define VI vector<int>↵
#define debug cout<<"potxdy"<<endl; ↵
using namespace std;↵
 ↵
typedef long long ll;↵
 ↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵

const int maxn=300007;↵
const int mod=998244353;↵

int n,dp[maxn][2],f[maxn]; ↵
VI vec[maxn];↵

int mult(int u,int v){↵
    u=(u%mod+mod)%mod, v=(v%mod+mod)%mod;↵
    return 1ll*u*v%mod;↵
}↵

void dfs(int u,int p){↵
    dp[u][0]=dp[u][1]=f[u]=1;↵
    for (auto c:vec[u]){↵
        if (c==p) continue;↵
        dfs(c,u);↵
        dp[u][0]=mult(dp[u][0],2*dp[c][0]+2*dp[c][1]-f[c]);↵
        dp[u][1]=mult(dp[u][1],dp[c][1]+2*dp[c][0]-f[c]);↵
        f[u]=mult(f[u],dp[c][0]+dp[c][1]-f[c]);↵
    }↵
}↵

#undef int↵
int main(){↵
    ios::sync_with_stdio(false);↵
    cin.tie(0), cout.tie(0);↵
    cin>>n;↵
    for (int i=1;i<n;++i){↵
        int u,v;↵
        cin>>u>>v;↵
        vec[u].pb(v), vec[v].pb(u);↵
    }↵
    dfs(1,0);↵
    cout<<(dp[1][0]+dp[1][1]-f[1]-1+2*mod)%mod<<endl;↵
    return 0;↵
}↵
~~~~~↵

</spoiler>↵


[problem:1332G]↵

Contributor of idea of the solution: [user:pikmike,2020-03-24]↵

<spoiler summary="Tutorial">↵
[tutorial:1332G]↵
</spoiler>↵

<spoiler summary="Solution (C++)">↵

~~~~~↵
#include<bits/stdc++.h>↵

using namespace std;↵

const int maxn=200007;↵
int n,q,a[maxn],b[maxn],c[maxn],t[maxn],sum[maxn];↵
int st1[maxn],st2[maxn],p1,p2,r1,r2,s1,s2;↵
int ans1[maxn][4],ans2[maxn][4];↵
set<int> s;↵

bool cmp1(int u,int v){↵
    return a[u]<a[v];↵
}↵

bool cmp2(int u,int v){↵
    return a[u]>a[v];↵
}↵

int main(){↵
    ios::sync_with_stdio(false);↵
    cin.tie(0), cout.tie(0);↵
    cin>>n>>q;↵
    for (int i=1;i<=n;++i){↵
        cin>>a[i];↵
    }↵
    p1=p2=r1=r2=0;↵
    s.insert(n+1);↵
    for (int i=n;i>0;--i){↵
        while (p1){↵
            int u=st1[p1];↵
            if (a[u]>a[i]){↵
                t[u]--;↵
                if (!t[u]) s.insert(u);↵
                p1--;↵
                r1=0;↵
            }↵
            else{↵
                break;↵
            }↵
        }↵
        while (p2){↵
            int u=st2[p2];↵
            if (a[u]<a[i]){↵
                t[u]--;↵
                if (!t[u]) s.insert(u);↵
                p2--;↵
                r2=0;↵
            }↵
            else{↵
                break;↵
            }↵
        }↵
        s1=lower_bound(st1+1,st1+p1+1,i,cmp1)-st1-1, s2=lower_bound(st2+1,st2+p2+1,i,cmp2)-st2-1;↵
        b[i]=i+max(r1,r2)+1;↵
        ans1[i][0]=i, ans1[i][1]=b[i]-1, ans1[i][2]=b[i];↵
        if (s1&&s2){↵
            c[i]=*s.lower_bound(max(st1[s1],st2[s2]));↵
            if (c[i]<=n){↵
                int u=lower_bound(st1+1,st1+p1+1,c[i],greater<int>())-st1,v=lower_bound(st2+1,st2+p2+1,c[i],greater<int>())-st2;↵
                ans2[i][0]=i, ans2[i][1]=min(st1[u],st2[v]), ans2[i][2]=max(st1[u],st2[v]), ans2[i][3]=c[i];↵
            }↵
        }↵
        else{↵
            c[i]=n+1;↵
        }↵
        st1[++p1]=i;↵
        st2[++p2]=i;↵
        r1++, r2++;↵
        t[i]+=2;↵
        if (i<n&&b[i]>b[i+1]){↵
            b[i]=b[i+1];↵
            for (int j=0;j<3;++j){↵
                ans1[i][j]=ans1[i+1][j];↵
            }↵
        }↵
        if (i<n&&c[i]>c[i+1]){↵
            c[i]=c[i+1];↵
            for (int j=0;j<4;++j){↵
                ans2[i][j]=ans2[i+1][j];↵
            }↵
        }↵
    }↵
    while (q--){↵
        int l,r;↵
        cin>>l>>r;↵
        if (r>=c[l]){↵
            cout<<"4\n";↵
            for (int j=0;j<4;++j){↵
                cout<<ans2[l][j]<<" ";↵
            }↵
            cout<<"\n";↵
        }↵
        else{↵
            if (r>=b[l]){↵
                cout<<"3\n";↵
                for (int j=0;j<3;++j){↵
                    cout<<ans1[l][j]<<" ";↵
                }↵
                cout<<"\n";↵
            }↵
            else{↵
                cout<<"0\n\n";↵
            }↵
        }↵
    }↵
    return 0;    ↵
}↵
~~~~~↵

</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English triple__a 2020-04-01 05:24:00 20
en9 English triple__a 2020-03-31 19:38:30 2 Tiny change: 'utorial:1327A]\n</spoi' -> 'utorial:1332A]\n</spoi'
en8 English triple__a 2020-03-31 19:31:18 0 (published)
en7 English triple__a 2020-03-31 19:29:37 16054
en6 English triple__a 2020-03-31 19:18:44 1506
en5 English triple__a 2020-03-31 19:13:22 119 Tiny change: 'n~~~~~\n\n\n<spoil' -> 'n~~~~~\n\n</spoiler>\n\n</spoiler>\n\n<spoil'
en4 English triple__a 2020-03-31 19:12:28 45 Tiny change: 'n~~~~~\n\n\n<spoil' -> 'n~~~~~\n\n</spoiler>\n\n</spoiler>\n\n<spoil'
en3 English triple__a 2020-03-31 19:05:58 55
en2 English triple__a 2020-03-31 19:04:39 5868
en1 English triple__a 2020-03-31 18:56:24 11207 Initial revision (saved to drafts)