Codeforces Round #782 (Div. 2) Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.

1659A - Red Versus Blue

Idea: TimeWarp101
Editorial: TimeWarp101

Hints

Solution

Implementation (C++)

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,r,b;
    cin>>n>>r>>b;
    int p=r/(b+1),q=r%(b+1);
    for(int i=0;i<q;i++)    cout<<string(p+1,'R')<<'B';
    for(int i=q;i<b;i++)    cout<<string(p,'R')<<'B';
    cout<<string(p,'R');
    cout<<endl;
}
return 0;
}

Implementation (Python)

t = int(input())
for i in range(t):
    n, r, b = map(int, input().split())
    p = r % (b + 1)
    y = ""
    for j in range(int(r / (b + 1))):
        y = y + "R"
    ans = ""
    for i in range(b + 1):
        if i > 0:
            ans = ans + "B"
        ans = ans + y
        if p > 0:
            ans = ans + "R"
            p = p - 1
    print(ans)

Feedback

1659B - Bit Flipping

Idea: Newtech66
Editorial: Newtech66

Hints

Solution

Implementation (C++)

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    vector<int> f(n,0);
    int tmpk=k;
    for(int i=0;i<n && tmpk>0;i++)
    {
        if(k%2==s[i]-'0')
        {
            f[i]=1;
            tmpk--;
        }
    }
    f[n-1]+=tmpk;
    for(int i=0;i<n;i++)
    {
        if((k-f[i])%2==1)   s[i]='1'-(s[i]-'0');
    }
    cout<<s<<endl;
    for(auto& e:f)  cout<<e<<" ";
    cout<<endl;
}
return 0;
}

Implementation (Python)

t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    kc = k
    s = input()
    f = [0] * n
    ans = ""
    for i in range(n):
        if k == 0:
            break
        if kc % 2 == 1 and s[i] == '1':
            f[i] = f[i] + 1
            k = k - 1
        elif kc % 2 == 0 and s[i] == '0':
            f[i] = f[i] + 1
            k = k - 1
    f[n - 1] = f[n - 1] + k
    for i in range(n):
        flip = kc - f[i]
        if flip % 2 == 0:
            ans = ans + s[i]
        else:
            if s[i] == '1':
                ans = ans + '0'
            else:
                ans = ans + '1'
    print(ans)
    for i in range(n):
        print(f[i], end = ' ')
    print()

Feedback

1659C - Line Empire

Idea: Newtech66
Editorial: Newtech66

Hints

Solution

Implementation (C++)

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol inf=1e18+8;
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n;
    lol a,b;
    cin>>n>>a>>b;
    vector<lol> x(n+1),p(n+1);
    x[0]=0;
    for(int i=1;i<=n;i++)   cin>>x[i];
    partial_sum(x.begin(),x.end(),p.begin());
    lol ans=inf;
    for(int i=0;i<=n;i++)
    {
        ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i]));
    }
    cout<<ans<<endl;
}
return 0;
}

Feedback

1659D - Reverse Sort Sum

Idea: Newtech66
Editorial: Newtech66

Hints

Solution

Implementation (C++)

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n;
    cin>>n;
    vector<lol> v(n);
    for(auto& e:v)  cin>>e;
    int k=accumulate(v.begin(),v.end(),0ll)/n;
    vector<int> b(n),ans(n,0);
    int lf=n-k;
    for(int i=lf;i<n;i++)   b[i]=n-1;
    for(int i=n-1;i>=0 && lf<=i;i--)
    {
        int cur=v[i]-(b[i]-i);
        if(cur==i+1)    ans[i]=1;
        else if(cur==1)
        {
            ans[i]=0;
            lf--;
            b[lf]=i-1;
        }
    }
    for(auto& e:ans)    cout<<e<<" ";
    cout<<endl;
}
return 0;
}

Feedback

Challenge

1659E - AND-MEX Walk

Idea: Newtech66
Editorial: TimeWarp101

Hints

Solution

Implementation (C++)

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
 
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
 
struct dsu {
    vi d;
    dsu(int n) : d(n, -1) {}
    int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
    void join(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y]; d[y] = x;
    }
    bool is_joined(int x, int y) {
        return find(x) == find(y);
    }
};
 
int32_t main() {
    fastio;
    int n, m; cin >> n >> m;
    vector<tuple<int, int, int>> edges;
    rep(i, m) {
        int u, v, w; cin >> u >> v >> w;
        edges.eb(--u, --v, w);
    }
    vector<dsu> zero(30, n), one(30, n);
    rep(j, 30) {
        for(auto& [u, v, w]: edges) if(w >> j & 1) {
            zero[j].join(u, v);
        }
    }
    vb even(n);
    rep1(j, 29) {
        for(auto& [u, v, w]: edges) if((w >> j & 1)) {
            one[j].join(u, v);
        }
        vb vis(n);
        for(auto& [u, v, w]: edges) if(!(w & 1)) {
            vis[one[j].find(u)] = 1;
            vis[one[j].find(v)] = 1;
        }
        rep(i, n) if(vis[one[j].find(i)]) even[i] = 1;
    }
    auto check = [&](int u, int v) -> int {
        rep(j, 30) if(zero[j].is_joined(u, v)) return 0;
        if(even[u]) return 1;
        rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
        return 2;
    };
    int q; cin >> q;
    while(q--) {
        int u, v; cin >> u >> v; --u, --v;
        cout << check(u, v) << endl;
    }
}

Feedback

Challenge

1659F - Tree and Permutation Game

Idea: Newtech66
Editorial: Newtech66

Bench0310 has written another proof for the solution to this problem here and here. Many thanks to him!

Hints

Solution

Implementation (C++)

#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
 
pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist}
{
    pair<int,int> res{u,0};
    int mx=0;
    for(auto v:g[u])
    {
        if(v==p)    continue;
        pair<int,int> cur=dfs(v,g,u);
        cur.second++;
        if(mx<cur.second)
        {
            res=cur;
            mx=cur.second;
        }
    }
    return res;
}
 
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--)
{
    int n,x;
    cin>>n>>x;
    vector<vector<int>> g(n+1);
    vector<int> p(n+1),deg(n+1,0);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
    }
    //find diameter of tree with 2 DFSes
    int diam=dfs(dfs(1,g).first,g).second;
    //if diam>=3, Alice always wins
    //if diam=1, n=2, have to check if p=[1,2]
    //otherwise we have a star graph and cases follow
    if(diam>=3) cout<<"Alice";
    else if(diam==1)    cout<<((p[1]==1)?"Alice":"Bob");
    else
    {
        //we need to check if we have already won or can win in the first move
        //this is possible if the permutation is already sorted
        //or if there are two marked elements and the chip is on neither of them
        vector<int> marked;
        for(int i=1;i<=n;i++)
        {
            if(p[i]!=i) marked.push_back(i);
        }
        if((int)marked.size()==0)
        {
            cout<<"Alice";
        }else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1]))
        {
            cout<<"Alice";
        }else
        {
            //we haven't won yet and it is not possible to win in one move
            //cases follow
            //first find center, it will have deg>1
            int center;
            for(int i=1;i<=n;i++)
            {
                if(deg[i]>1)
                {
                    center=i;
                    break;
                }
            }
            //is chip on center?
            bool chiponcenter=(x==center);
            //is center marked?
            bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end());
            //list the cycles
            vector<int> vis(n+1,false);
            vector<vector<int> > cycles;
            for(int i=1;i<=n;i++)
            {
                if(vis[i])  continue;
                int j=i;
                cycles.push_back({j});
                vis[j]=true;
                while(!vis[p[j]])
                {
                    cycles.back().push_back(p[j]);
                    vis[p[j]]=true;
                    j=p[j];
                }
            }
            //min number of swaps
            int swapcnt=0;
            for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1;
            //parity
            int parity=(swapcnt+!chiponcenter)%2;
            //cases
            if(!centerismarked)    cout<<(parity?"Alice":"Bob");
            else if(chiponcenter && centerismarked)  cout<<"Bob";
            else    //chip not on center and center is marked
            {
                //need to check if we can unmark center on first move
                //it is impossible if x is on p[center] (since we need to move p[center] to get center
                //to the right place, but p[center] is blocked)
                bool cannotunmarkcenter=(p[center]==x);
                if(cannotunmarkcenter)  cout<<"Bob";
                else    cout<<(parity?"Alice":"Bob");
            }
        }
    }
    cout<<endl;
}
return 0;
}

Feedback

Комментарии (40)

Показать архивные | Написать комментарий?

wolfram_

3 года назад, # |

+12

Writing for the ones I solved:

I noticed many people complaining about A in the main thread. Although I wasn't affected by the judge server failing, I thought the observations needed for this problem were fairly straightforward, although maybe for some it could have been tricky to implement.
Problem B also had a very simple idea, but I found implementation for this problem to be quite hairy. Still a decent problem although a bit trollish for the second spot.
Problem C required a very straightforward greedy observation. I think this should have been swapped with the B problem.
Problem D is interesting. There exist other solutions than the one provided in the editorial. I'm not exactly sure how to describe it but the code is here.

I spent more time on problem B than problems A, C, D combined, although that's mostly my fault.

→ Ответить

Esomer

3 года назад, # ^ |

I think the time you spend on each problem just depends on you, not on the problem's quality. I spent more time on A, than on B or C. Also, I do not get why you say B's implementation was hairy, I didn't have any problems implementing it and the idea was easy to get.

I agree that the idea was very simple. For me personally, I overcomplicated the implementation and ended up falling in a lot of traps. I knew that it was mostly my fault, but I saw that others had similar experiences, so I thought it would be fairly reasonable to bring it up.

pigmike

-45

Who tf asked?

vuhuydiet

15 месяцев назад, # ^ |

← Rev. 2 →

i asked.

Bobrosoft

For the problem D, I have the same solution as you. It is pretty hard to explain, because it is a result of making several observations.

The first thing I noticed is that the first number is the (0-indexed) position of the first zero in the original array; n means that there is no zero. That is because we either have a zero there (which will never be replaced) or a one (which will be replaced as soon as we encounter a zero). After thinking for a while, I was able to extend this logic to "if $$$A_i = 1$$$, then $$$C_i$$$ is the 0-indexed position of the i-th zero in $$$A$$$". That's because we will replace 1 with 0 as soon as we find the i-th zero, but no sooner since we first have to set the first (i-1) elements to 0. From this, we infer the first rule: if $$$A_i = 1$$$, then $$$A_{C_i} = 0$$$.

Now what about the case when $$$A_i = 0$$$? Well, if there aren't any 1's before it in A, then (and only then) $$$C_i = 0$$$. Otherwise, it will become a 1 on the i-th step, because it will be the last sorted element. And after that, it will become a 0 again when we add the i-th zero. That means that $$$C_i = Z_i - i$$$, where $$$Z_i$$$ is the position of the i-th zero. Thus, if $$$A_i = 0$$$ and $$$C_i \neq 0$$$, then $$$Z_i = C_i + i => A_{C_i + i}$$$ = 0.

One last thing we need to observe is that after we encounter the first non-zero $$$C_j$$$, we always know $$$A_i$$$ before processing it, because we know the position of the (i-1)-st zero and there is at least one 1 before this point.

adityagamer

How do you prove that this is sufficient?

Essentially, we learn the position of every zero in the array. On all the other positions there can only be ones. So there is only one solution, and we find it.

How can you say that "at all other positions, there can only be ones"?

Because there isn't a zero, and the only other option is one.

Good explanation. Breaking it up into the core "observations" is a good way to put it.

learningcurve_

Thank you problem writers for problem B. I enjoyed solving it. Made me get my brain to work for the first time.

achvanov

+51

I remember seeing blogposts that said A’s are too ad-hocish and if you are new to CP and have no math competitions background you can’t really solve them. And some even suggested that first problems should be more about implementation than about math observations. But yesterday’s A was about pigeonhole principle and outputting such string. So basic math (you may even not know what pigeonhole principle is but you understand it intuitively) plus implementation. However people complained that A is too hard. So may I ask what the hell is going on?

jiagengchang

Here is an equivalent version of this rounds problem A that is rated 1500.

https://codeforces.me/problemset/problem/746/D

I suspect the authors were heavily inspired from this problem. So what you are saying is that the rating for problem A should be 1500?

tezk

Oh so that why I got WA on A, I'm suck at string problem as usual

And I got the exact idea for B quickly but I outsmarted myself lol

_ajthreac_

nice problems to training my weak brain.

And i've been struggled on B for more than 30min :)

epsilon_573

For Problem D, We can also iterate from left to right in C and determine indexes of 0 in A.

Video Solution : Problem A-D

lz666

In the implementation of E, this line seems redundant: rep1(j, 29) if(one[j].is_joined(u, v)) return 1; Because rep(j, 30) if(zero[j].is_joined(u, v)) return 0; is easier to satisfy than the above.

F99_ll_H21

So nice problems for div2.I love them,especially D and E.

brobat

Solution for the challenge of problem D:

First, we can check if the sum of values in $$$C$$$ is divisible by $$$n$$$, if not, then the array is invalid. Now, lets just solve the problem considering the array is valid, and later check if the resulting sequence produced by our algorithm can make the array $$$C$$$ or not. The goal is now to solve the reverse problem — we have the array $$$A$$$ and need to create the sums-array $$$C$$$ from it.

I'll assume one-based indexing from here on. Consider finding the sum of ones for an index $$$i$$$ in the array $$$A$$$.

First of all, we check its contribution in the first $$$i - 1$$$ iterations. Until then, $$$A[i]$$$ will remain unchanged, so, if $$$A[i] = 1$$$, then $$$C[i] = (i - 1)$$$, else $$$C[i] = 0$$$.

From iteration $$$i$$$ onwards, $$$A[i]$$$ will also get sorted along with the previous elements. The $$$i^{th}$$$ value in the sorted sequence can only be $$$0$$$ if there are atleast $$$i$$$ zeros in the sequence. So, we need to find the index $$$j$$$ such that $$$A[j]$$$ is the $$$i^{th}$$$ zero in the sequence. We can do this by storing all zero value indexes in a separate array.

From iteration $$$i$$$ and until before the $$$i^{th}$$$ zero has been found, the value of $$$A[i]$$$ will be one. If it is found at index $$$j$$$, then the contribution to $$$C[i]$$$ will be $$$(j - i)$$$. (If $$$i$$$ zeros do not exist in the sequence, then the contribution to $$$C[i]$$$ will be $$$(n + 1 - i)$$$.

So, for each element, $$$C[i] = (i - 1) + (j - i)$$$ if $$$A[i] = 1$$$, and $$$C[i] = (j - i)$$$ otherwise.

Newtech66

It is actually possible to solve it without solving the reverse problem. The solution requires minimal additional casework. But good job.

P.S.

variety-jones

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

Sadid_005

Can't find a counter test case for my 153997173 of problem D ticket(s) : https://cfstress.com/status/5235 https://cfstress.com/status/5222

You've already used the website to infer that your code runs fine on thousands of small testcases, but only fails on bigger test cases on CF

What's the most popular reason for that? Integer Overflows.

Avoid using fancy stuff such as accumulate, without reading the documentation first

I leave it up to you to figure out why do we need to handle overflows.

Thanks.

Shermes

Hi guys, I have some wonders and hope to seek for explanations! In problem D:

Submission 1: I use set and get AC -> complexity O(???) (I'm still confused about this)

Submission 2: I use deque and get TLE -> I expect the complexity would be O(NlogN) So I hope you guys will point out for me where did I do wrong.

Sorry for my bad clarifications! Thanks in advance!

I have known why my code got TLE! Thanks!

← Rev. 3 →

If any one can help me finding test case for problem D which fails my submission https://codeforces.me/contest/1659/submission/153997173 it will be really helpful it passes almost all smaller test cases it is failing on when n is huge, thanks in advance.(sorry for my bad english)

Edit: no need, found the bug.

tgp07

Can someone help me figure out why my solution for A is WA'ing?

153898766

Deepesh_Dragoneel

Your code fails for the below test case: Input: 12 10 2 Output: RRRRBRRRRBRR Expected Output: RRRRBRRRBRRR According to your code 10 is begin split into 3 parts i.e., 4, 4, 2 whereas optimal division is 4, 3, 3 So we need to split the parts such that Max valued part — Min valued part is as small as possible!

My solution for reference — 153908138

Why does this matter, both have a maximum of 4?

You can look at the testing details, the failed test isn't that long. Your solution uses too many R's in the beginning, which leads to a large cluster of B's in the end.

Dragoneel248

Can someone explain how to solve problem C, I having hard time following tutorial!

In solution of D, paragraph 5, every case after "Otherwise" word is very ambiguous. Can someone explain with correct grammar please?

Menace

let cnt1 be the number of 1's in the array A
Now consider the last element in array A
if it is 1 then it will stay 1 for all arrays B[i] (B[i][n] = 1) and because we have N of them then C[n] will be equal to n
if it is 0 and cnt1 = 0 then C[n] will be 0 because (B[i][n] = 0)
if it is 0 and cnt1 > 0 then for surethe last element for array B[n] (B[n] is the array generated by sorting the whole array) is 1 (B[n][n] = 1) and that means that the sum of all element B[i][n] is 1

UUUnmei

i think i solve C in another greedy way. here it is. code

the key is to see change location as saving money for further conquer. so every iteration i compare how much to change location(c2) and how much i can save(c1). if c1 < c2, that means worthless to change. otherwise, let's do change. though it get AC, i'm curious about this greedy correctness.

hope for some help

foxy1459

In problem B, why is it correct to add all remaining moves to the last element? What if the number of remaining moves is odd? I just cant figure out how to prove the remaining number be even.

2 года назад, # ^ |

The remaining number can be odd and it may make the last element go from 1 to 0, but since we want lexicographically maximum, its better to have the earlier element maximum, and then use the remaining moves on last.

tushar_kumar

2 года назад, # |

can anyone please tell the DP approach of problem C

Spoiler

dhruv09

Can someone please tell the approach to solve this question through dp. I am trying through dp but it is getting TLE in Test Case 5 .

my dp code is

ll dp[100002];

long long solve(int i ,int i2){

long long cost =0;

if(i>n)return cost;

if(dp[i2] != -1)return dp[i2];

cost+= b*(abs(arr[i]-arr[i2]));

cost += min( solve(i+1,i2) ,a*(abs(arr[i]-arr[i2])) + solve(i+1,i)  ) ;

return dp[i2] = cost;

}

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