doreshnikov's blog

Codeforces Round #744 (Div. 3) Editorial
By doreshnikov, history, 3 years ago, In English

1579A - Casimir's String Solitaire

Idea: MikeMirzayanov

Tutorial
Solution

1579B - Shifting Sort

Idea: doreshnikov

Tutorial
Solution

1579C - Ticks

Idea: MikeMirzayanov

Tutorial
Solution

1579D - Productive Meeting

Idea: doreshnikov

Tutorial
Solution

1579E1 - Permutation Minimization by Deque

Idea: MikeMirzayanov

Tutorial
Solution

1579E2 - Array Optimization by Deque

Idea: doreshnikov

Tutorial
Solution

1579F - Array Stabilization (AND version)

Idea: doreshnikov

Tutorial
Solution

1579G - Minimal Coverage

Idea: doreshnikov, MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +141
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Please fix the code for problem G.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Similar stuff in video format :

video solutions

→ Reply
»
3 years ago, # |
  Vote: I like it +104 Vote: I do not like it

Really sorry the editorial took longer than usual. I'll try to post it sooner next time!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Still, this is one of the highest-quality editorials I've seen, great job!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    problem B : solution -> actions.push_back({l,min_pos}); "l" is not defined here.

    → Reply
»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Regarding E2:- I have faced similar kind of concept in many problems "finding elements smaller or larger than current element occurring before it"... someone please tell me a source to learn __gnu_pbds::tree (or) balanced binary search tree (or) any best way to solve this.

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

in problem A how can it handle "BABA" case its answer should NO but according to above solution its give YES

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    the string is of length 4, and there are 2 B's which is half the size so it would print yes.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      But I guess, it clearly mentioned that we can't pick two adjacent character

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        They don't have to be adjacent, but they can be.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

There is a nice way to implement G with bitset. Let's do a binary search on answer. DP for checking if we can stay inside the segment of fixed length $$$m$$$ looks like this:

bitset<3000> d;
forn(i,0,m+1) d.set(i);
auto cut = d;
for(auto x : a) d = ((d>>x)|(d<<x))&cut;

Basically bit $$$i$$$ in $$$d$$$ being equal to 1 after processing some numbers from $$$a$$$ means that we could be on position $$$l+i$$$ of some segment $$$[l, r]$$$ without going out of its borders until this point. If at least one bit is 1 after this cycle then the answer is $$$>=m$$$, otherwise it's $$$<m$$$. Complexity is $$$O(n\cdot \frac{l_{max}}{64} \cdot \log(l_{max}))$$$ which is pretty much the same.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I solved it like this too. Very elegant.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Can you please explain what we are doing in this line
      for(auto x : a) d = ((d>>x)|(d<<x))&cut; is working,
      sorry to bother you but my potato brain is unable to understand and visualise.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        After i loops, j'th bit of b represents whether it is possible to reach position j after considering i segments, or in other words, j'th bit represents whether it is possible for the "end" of i'th segment to be at position j. Now, say we are in the i'th loop. j'th bit of b currently represents whether it is possible to reach position j after considering i-1 segments. So, if we consider the i'th segment now, position j is reachable if and only if either position j-x is reachable after i-1 segments or position j+x is reachable after i-1 segments. This transition is equivalent to

        new_b[j]=b[j+x]|b[j-x];

        which is equivalent to 

        new_b = (b>>x)|(b<<x);

        But the issue is that bitsets have to have constant size at compile time. So, we set the size to the max possible size that we might require, and after each loop we set b[j]=0 for all j>m, which is a way of saying that it is not possible for any segment to end at j>m. A simple way to do this for any bitset b is

        b = b&cut;

        where cut has j'th bit=1 for j<=m, and 0 for j>m.
        After n iterations, j'th bit of b represents whether it is possible to reach position j if we start from any of the positions p for 0<=p<=m. If this is true for any j, where 0<=j<=m, then we return true, else we return false.

        Hope you understood that. Sorry I'm not good with markdown.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same idea but messed something up

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why do you use &cut?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You actually need a bitset of size $$$m+1$$$ but you can't do that in runtime. It's basically emulating that.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1579/submission/130289614 pls tell me why this soln for D gets WA if u have time. PS : ignore it, i got it why im getting it rong..

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i wonder why this solution: https://codeforces.net/contest/1579/submission/130179380 got WA but same logic just few changes got AC:https://codeforces.net/contest/1579/submission/130194128

and above first solution is more optimized!! can someone give a TC where is fails?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I reflected a LOT on problem G and i observed the dp solution, but didnt come up with the idea that answer never exceeds 2.lmax :( beautiful problem over all.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me how mysolution is getting a wrong answer even though I did it exactly how the editorial says . https://codeforces.net/contest/1579/submission/130186425

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are inserting into the beginning of the vector, which takes O(n), because it shifts everything for one step. Better solution would be use data structures that allows you to add elements in O(1). It can be deque, list (which is based on linked list). Another solution is using vector with two pointers in the middle (and shift them while you are adding elements to the left or to the right). Thus you don`t need to shift all elements each time when you need to put smth in the beginning. Your solution fails on tests like (200000, 199999, 199998...), because time complexity becomes O(n^2), which it too slow for this task.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

Alternative solution for 1579D - Продуктивная встреча. Think of following question: what arrays $$$a$$$ you can turn into 0? Suppose sum of $$$\sum\limits_{i=1}^n a_i = S$$$ (same as in editorial). If $$$S$$$ is odd — obviously we can't. Also, by simplest pigeonhole principle we know if there is $$$a_i > S/2$$$, then we can't reduce all $$$a_i$$$ to zero. But, if there is $$$a_i > S/2$$$ it's easy to see that it's maximum of array, and it's unique.

So idea to decrease corresponding $$$a_i$$$ in a way to make it possible to turn them into zero. To do that, calculate $$$S$$$. Find $$$a_i > S/2$$$ if it exists. And, decrease it by one while $$$a_i > S/2$$$ still holds (decrease $$$S$$$ correspondingly). Because this maximum was unique, no need to search anything else. Now $$$S$$$ can be odd, but we'll handle it later. Now, we'll make list of all participants with their repetition. So, in case $$$a$$$ = [1,2,3] we will get $$$p$$$ = [1,2,2,3,3,3]. Its length is $$$S$$$, and if it's odd, remove last one element. Now, I claim answer is pairs of $$$(p_i, p_{i + len(p)/2})$$$. The only thing to prove that is left is: $$$p_i \neq p_{i + len(p)/2}$$$, but this follows from $$$a_i \leq S/2$$$. Time complexity is $$$O(S)$$$. 130295963

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When up-solving, I tried to solve Question E2. I have been getting TLE on test case 3.

My logic

Any help regarding where I went wrong would be greatly appreciated. My submission.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    The BST code you've used does not maintain any balancing, and as a result, might work in O(n) per insert. Try to insert consecutive integers and you'll notice, the height of the tree is linear to the size.

    There are efficient BST variants, like Red-Black Tree, AVL Tree or Splay Tree, which are a bit more complicated, but maintain O(log(n)) time per query (amortized or not).

    For this problem though, you could use ordered_set from pbds. Refer to this blog by Adamant for more info https://codeforces.net/blog/entry/11080.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank You!! The explanation helped a lot. And yeah, I tried using ordered_set from pbds and my solution got accepted.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you help me ? Why it is giving TLE : E2 Code

      and it is accepted : E2 Code

      Thanks in advance. map is used just to store frequency

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Perhaps there is an anti-hash test there. Because of it, unordered_map can run in $$$O(n)$$$.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No need to use map if you use ordered_set. both structures may yield high working times resulting in your TLE.

        → Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I was going to answer a comment with a different proof of D (always take the two largest elements) that I came up with, but it got so long that I figured it would look better here with spoilers and math mode. This is mostly a result of bashing out a ton of different cases that could happen. Feel free to point out any mistakes (which can include forgetting to format somewhere).

There are two cases (as the editorial mentions):

1. The largest element is greater than the sum of all of the other elements.
2. The opposite: largest element is less than or equal to the sum of all other elements.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah this was how I implemented a previous problem that asked the same thing. Solution here : 111076508

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem G, Can someone explain why we are taking 0 as the leftmost boundary and never crossing that? I am stuck with this idea for two days.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    In problem G ,we are maintaining the relative position of the start with respect to the left and right boundaries, not the actual position of start. So, if in any case we are going to cross the leftmost boundary of our segment, we would be assuming that leftmost point(<0) as the new leftmost boundary and start also.
    That's why we are always maintaining 0 as the leftmost boundary and never crossing that. You can watch galen_colin's stream to get a better understanding. Link:- https://www.youtube.com/watch?v=JRuAgCCwi0M

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much. I finally get it.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, in problem E2, I use discretion and Binary Indexed Tree to count numbers and it lead to TLE, but this solution complexity should be $$$O(nlogn)$$$, I do not know why this solution cannot ac, this is my code link

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You memcpy the whole array while you need only n elements. Use vectors to avoid such mistakes.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I use the map insted of unordered map. It got AC 193683141

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any similar problems like problem G? I really liked the idea.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I've got TLE in E2, but I used multiset with lower/upper_bound which works with $$$\ O(logN) $$$ complexity. So, I guess that my submission should work with $$$\ O(NlogN) $$$ time. Here my submission 130358299, can you tell where I'm wrong.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If it does not bother you, can someone please tell me why this submission : https://codeforces.net/contest/1579/submission/130371833 gets TLE, I thought its complexity was O(n log n) as expected by the correct answer.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I believe here the distance function takes O(n) time. It is much better to use a structure like __gnu_pbds::tree. You can read about it here.

    Spoiler
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D, will choosing the min and max element at each turn, work similar ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem $$$F$$$ can be solved using $$$Binary\ Lifting$$$ although it is not optimal.

Idea
Sample Code
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

About the problem E2, I see someone write the solution like this:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,a[N],b[N];
long long c[N];
long long ans=0;
int lowbit(int x){return x&-x;}
void add(int x){
    while(x<=n){
        c[x]++;x+=lowbit(x);			
    }
}
long long query(int x){
    long long ans=0;
    while(x){
        ans+=c[x];x-=lowbit(x);
    }
    return ans;
}
int main(){
	
    cin>>t;
    while(t--){
        cin>>n;ans=0;
        for(int i=1;i<=n;i++)	cin>>a[i],c[i]=0,b[i]=a[i];
        sort(b+1,b+1+n);
        int len=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)	a[i]=lower_bound(b+1,b+1+len,a[i])-b;
		
        for(int i=1;i<=n;i++){
            long long cur=min(query(a[i]-1),query(n)-query(a[i]));
            ans+=cur;
            add(a[i]);
        }	
        cout<<ans<<"\n";
    }
	
	
	
    return 0;
}

I guess the query() and add() operation is to calculate some like partial sum or adjacent difference, but I don't understand how and why, can someone explain that? Thank you!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone help me find why my code for D is failing? Any edge cases I need to check for? It always fails on tc 69.Anyone knows what that tc is :( ? https://codeforces.net/problemset/submission/1579/130623552 I did as said in editorial. Used a pq for choosing two persons with max sociability.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the test case "2 2 2", correct answer is 3 conversations.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

for D, will the following algorithm work? : " Choosing two people i and j such that ith person has maximum remaining sociability and j can be any other person with non zero sociability and stop this process when less than 2 people are left with non zero sociability "

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
if ai≥S−ai, the answer cannot be more than (S−ai)+∑j≠iaj=2⋅(S−ai).

In first point of Problem-D editorial, How is this true?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Graphical Solution for problem F is

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " " << x << endl;
#else
#define debug(x);
#endif

#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define sortall(x) sort(all(x))



using ll = long long;
const int MOD = 1e9 + 7, INF = 1e9;

/*---------------------------------------------------------------------------------------------------------------------------*/
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
ll mod_add(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
ll mod_mul(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
ll mod_sub(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
ll mod_div(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}  //only for prime m
/*--------------------------------------------------------------------------------------------------------------------------*/


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while(tt --)
    {
        int n, d;
        cin >> n >> d;
        vector<int>v(n);
        for(int i = 0 ;  i < n; i++) cin >> v[i];
        vector<int>v1;
        set<int>st;
        for(int i = 0; i < n; i++)
        {
            if(v[i] == 0)
            {
                v1.push_back(i);
            }
            else st.insert(i);
        }
        int ans = -1;
        for(auto it : v1)
        {
            int k = 1;
            while(st.find((it + k * d) % n) != st.end())
            {
                st.erase(st.find((it + k * d) % n));
                k++;
            }
            ans = max(ans, k - 1);
        }
        if(st.empty()) cout << ans << endl;
        else cout << -1 << endl;
    }
}
→ Reply