doreshnikov's blog

By doreshnikov, history, 3 weeks 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
  • +133
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Please fix the code for problem G.

»
3 weeks ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

Similar stuff in video format :

video solutions

»
3 weeks 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!

  • »
    »
    3 weeks 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!

  • »
    »
    3 weeks 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.

»
3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

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

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

»
3 weeks 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.

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

    I solved it like this too. Very elegant.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

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

    I had the same idea but messed something up

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

    Why do you use &cut?

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
3 weeks 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.

»
3 weeks 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.com/contest/1579/submission/130186425

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone find the mistake in my submission for Problem C ? 130292992 I started from the right bottom and marked the possible ticks visited, otherwise If I couldn't find any possible tick for any "*" cell and it has been not visited(not part of any previous tick) then I simply output "NO"

»
3 weeks ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

Alternative solution for 1579D - Productive Meeting. 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

»
3 weeks 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.

  • »
    »
    3 weeks 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.com/blog/entry/11080.

    • »
      »
      »
      3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        2 weeks 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)$$$.

      • »
        »
        »
        »
        2 weeks 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.

»
3 weeks 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.
  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What an absolute lovely editorial, I really like the proof in the editorials.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A is much more intuitive to just check s.count("B") == s.count("A") + s.count("C").

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

    How do you define "much more intuitive"? :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D I used a priority queue to keep track of most sociable people which was the most intuitive for me.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem E1 nearly the same as shown above. Can anyone tell me my fault? Solution link: https://codeforces.com/contest/1579/submission/130123127

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • You use vector and insert will cost high complexity. vector::insert() function has complexity of O(n+m) where n is number of elements inserted and m is number of elements moved.
    • So you get hacked because this case 200000...->....1. got TLE.
    • SOLUTION is you can use deque with push_front or use 2 vector: one for back and one for front.
»
3 weeks 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.

  • »
    »
    3 weeks 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

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

      Thank you so much. I finally get it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just want to note that in the solution for problem C we don't need a separate loop to check status, and instead check it in the original loop as we go since a painted cell is either the center cell of a tick or it's center cell is in a row below.

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
3 weeks 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.

»
3 weeks 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.com/contest/1579/submission/130371833 gets TLE, I thought its complexity was O(n log n) as expected by the correct answer.

  • »
    »
    3 weeks 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
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, yeah, huge thanks, I always assumed it was O(1).

»
3 weeks 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 ?

»
3 weeks 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
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me in understanding D ?

I am unable to know the exact reason why we are taking max and second max element .

I have read tutorial 2 times but still unable to understand the proof, can anybody help me? Thanks in advance.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E2 is like a standard merge sort tree implementation problem , I really liked it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand the offset in problem B? From the problem description: [1,4,1,3] -> [3,1,4,1], offset 1 and [4,1,3,1] -> [3,1,4,1], offset 2. I understand this, l and r for these are 1 and 4.

Then there's this example: [1,3,2,8,5], where choosing l=2, r=4 and d=2 yields [1,8,3,2,5] Shouldn't this be [1,2,8,3,5]? Am I missing something stupid? Any help would be appreciated.

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

    same doubt I also have.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's worded as "the sequence [1,4,1,3] is a cyclic shift of the sequence [3,1,4,1]" therefore the starting sequence is [3,1,4,1] and the result is [1,4,1,3]. This matches the emphasized "left" elsewhere in the text.

    The offset 2 example is ambiguous as the result is the same for either direction.

    Subsequent examples, look at the position of the 8 going left by 2 slots...

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

      Clearly, I didn't read the "left" bolded part and implemented a "right" shifting soln. Thanks a lot!

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi everyone, For Problem D, is there a test case which would fail, if I keep max heap as my priority_queue and always fetch top two elements and make the number of pairs, equal to the min of the two, for example.

Test Case — 5 4 4 4. So I take 5 and 4, make 4 pairs of them and insert the remaining one back, now my pq is — 4,4,1.

So using this approach, I will get 8 pairs, wouldn't this also work, instead of subtracting 1 each time from the top two?

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

    it fails for 2 2 2, u will get 2 pairs and u are left with one unused 2. if u follow the approach in the editorial u can endup with 3 pairs.

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

      Thanks Jaxk, this is helpful, makes sense actually.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody please tell how to solve third problem "ticks" recursively.

»
3 weeks 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!

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's binary indexed tree (or Fenwick Tree)

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your reply. It was very useful!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone help me why I go Memory Limit Exceeded in this ?https://codeforces.com/contest/1579/submission/130159419

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

forget it

»
2 weeks 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.com/problemset/submission/1579/130623552 I did as said in editorial. Used a pq for choosing two persons with max sociability.

»
2 weeks 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 "

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem E2 be solved using segment trees? If yes can you please help with the solution

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, the shift described in the question is left cyclic shift but what is explained in the tutorial and also the code is right cyclic shift.