BledDest's blog

Educational Codeforces Round 160 — Editorial
By BledDest, history, 12 months ago, In English

1913A - Rating Increase

Idea: Roms, preparation: awoo

Tutorial
Solution (awoo)

1913B - Swap and Delete

Idea: BledDest, preparation: adedalic

Tutorial
Solution (adedalic)

1913C - Game with Multiset

Idea: Ferume, preparation: Ferume

Tutorial
Solution (awoo)

1913D - Array Collapse

Idea: Roms, preparation: Roms

Tutorial
Solution (Roms)

1913E - Matrix Problem

Idea: Ferume, preparation: Ferume

Tutorial
Solution (BledDest)

1913F - Palindromic Problem

Idea: Ferume, preparation: Ferume

Tutorial
Solution (awoo)
  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (48)
| Write comment?
»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it normal that in the solution of problem D the first larger element on the left is searched for, although in the author's solution it is the first smaller element?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I also think the author made a mistake in writing.Largest and smallest are written backwords.

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

      I understand :). It's just misleading.

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

    It may even be easier to understand the solution for maximums at first (hard tutorial), and then solve the problem yourself with a minimum

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

good D

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

in problem B in 4th case, where s=111100 we can delete first 2 1's in cost 2 and we can swap rest of the 0's and 1's, it will cost only 2 but author is calculating for cost 4.

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it
    • 111100
    • delete first 2
    • it is now 1100
    • original string — 1111 | 00
    • so new string — 1100 |
    • how will you swap now so that s[i] != t[i] for all i such that 0 <= i <= |t|
    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      original string — 1111 | 00 can you explain this statement?

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

        The original string was "111100" and the new string is "1100" compare the first 4 characters now

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

          original string:"111100" after deleting s becomes="1100" right.Now for t you can swap s1,s4 and s2,s3 to get "0011" , Now when you compare string t with string s : "1100" and "0011" they dont match , so the answer should be 2 I guess not 4

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

            I mean do you really think the given test case can be wrong? given that the contest ended and thousands of users solved it. Try to find a flaw in your logic

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

            Don't compare the new string t(0011) with "1100", we have to compare it with the original initial string i.e. s = 111100

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

            you need to compare final string (0011) with initial string(111100) ,but here s3,s4 matches so we need to delete that too,that's how you get 4.

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

      you need to compare final string (1100) with initial string(111100) ,but here s1,s2 matches so we need to delete these too as swapping won't help,that's how you get 4.

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

    You did not notice when you delete two '1', the total number of t is four. As a result, you need to focus on the case that '1' will appear on the left and there are many '1' on the left of s.

    → Reply
»
12 months ago, # |
  Vote: I like it +23 Vote: I do not like it

I created video editorial for D: Array Collapse.

I also created some practice problems on the prerequisites for this problem (Montonic Stacks + DP), details of which can be found here.

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

Can anyone please explain how to arrive at the formula: no. of operations = sum_matrix — res.first + res.second?

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

In promble E:

add a directed edge from C_j to T with capacity A_i and cost 0.

Why is the capacity A_i instead of B_j？

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

Alternative solution for problem D:

We can break down the problem recursively. If we look at some range [l,r] of the array, let the index of the minimum element of a[l...r] to be idx, we can notice that the ranges [l,idx-1] and [idx+1,r] are independent, because no matter what operations we do (in [l,r]), the element at position idx will never be erased, so it acts like a wall between the left part and the right part.

Then, we can define solve(l,r) as the answer for a [l,r], and compute it by calculating solve(l,idx-1)*solve(idx+1,r).

One more detail is that when we are looking at [l,r], we need to know if the minimum element above us (from the previous recursion) is to the right or to the left (or both), because when this happens we can erase any suffix/prefix in [l,r], including the minimum element, so we have to add in our answer to [l,r] the answer to [l,idx-1] or to [idx+1,r] (or both). We do that with a 2 bits mask.

Code snippet:

ll solve(int l, int r, int dir) {
    if (l > r) return 1;
    auto [val, id] = st.query(l, r);
    ll L = solve(l, id - 1, dir | 1);
    ll R = solve(id + 1, r, dir | 2);
    ll ret = L * R % mod;
    if (dir & 1) ret = (ret + L) % mod;
    if (dir & 2) ret = (ret + R) % mod;
    if (dir == 3) ret = (ret - 1 + mod) % mod;
    return ret;
}

Obs: if the previous minimums comes from both left and right (i.e. the mask is equals to 3), we subtract 1 from the current answer because we counted the empty array twice.

This solution works in O(n log(n)) because of the sparse table build.

Full code: 238167605

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Understood the recursive spliting part. Now trying to process remaining parts. [The above explanation should be added in the editorial]

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

    Can you explain your code a little bit like how you are Calculating ret variable

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Omg I've accidentally deleted my answer :P, I'll type it again

      Imagine this testcase: 10 4 2 5 3 6 1 9 7 8

      The important thing to note is that subarrays to the left and to the right of element 1 are independent, so I just calculate the answer for them and multiply those values.

      [10 4 2 5 3 6] is L

      [9 7 8] is R

      Let's look at L: [10 4 2 5 3 6]

      You agree with me that I can't arbitrary erase the 10 in the beginning? But I do can arbitrary erase the 6 at the end, because there is a 1 on the right of it. In fact, I can erase any suffix of the subarray [10 4 2 5 3 6].

      When I split this [10 4 2 5 3 6] into [10 4] 2 [5 3 6], and look at [5 3 6], now I can erase both the beginning and the end of this subarray, because to the left of it we have the 2, and to the right of it we have the 1.

      The variable dir is a bitmask that tells me this, if there is a previous minimum element to the left or right of my current range. If there is some, I need to sum in my ret variable the value of L or R (or both).

      If there is both a left and a right minimum element (i. e. the mask is 3), I subtract 1 from the ret variable because in this case I counted the empty subarray twice.

      I'm sorry if it's still confusing, but feel free to ask more.

      Take a look at the full code to see if it clears out a little bit: 238167605

      There is also this submission 237782371 from Ayalla which is very similar but with some slightly difference on the base case of the recursion and in the calculation of variable ans (he doesn't need to subtract 1 from ans when mask is equals to 3), it may be more intuitive this way.

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

        Thanks for explaining.

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

        I still don't get why you add L or R if there is a previous minimum element

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

          Imagine you have some array [3 4 2 1 5 6], obviously $$$1$$$ is the minimum element, so we can break into L = solve([3 4 2]) and R = solve([5 6]), alright? I can't erase any prefix/suffix of this array, because there's no one in the left or right of my array to erase it.

          But, if I'm recursively going down and at some point I look at something like this:

          ... 1 ... [3 5 2 8] ...

          I mean, I'm looking to the range between values $$$3$$$ and $$$8$$$, but I have a $$$1$$$ in my left (which was a minimum element from previous recursions, and I know it exists by looking at the variable $$$dir$$$)

          When I'm computing the answer to the subarray [3 5 2 8], I'll break it in 2 parts splitting in the minimum element and multiplying those L and R values, this will count the number of reachable subarrays that contains my current minimum element (which happens to be 2). But, as I have a previous minimum element on my left, I need to count the number of subarrays that don't contains my current minimum element. I need to count this because I can erase any prefix of my current subarray (with the previous minimum element) and delete my current minimum, so I add variable R to my current answer.

          Is that clear? I know that it's kinda tricky to fully understand this solution

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

    upd:nevermind, I am wrong

    → Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I debug D for hours just to realize i forget to change the mod value -_-

→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For Problem D, can someone explain what is meant by this? It is easy to see that it is enough for all these elements to be smaller than the fixed one. Then they can be removed one by one from left to right. If there is at least one larger element, then the maximum of such elements cannot be removed. But the problem statement says that you can choose a contiguous subsegment of p and remove all elements from that subsegment, **except** for the minimum element on that subsegment. So my interpretation would be that it the condition should be that all of the elements be larger than the fixed one? Since the fixed one is the minimum, we can always remove the element adjacent to it. And if there is a smaller element, then we can't remove that element. I don't understand the usage of maximum and minimum in the tutorial and in my interpretation they are reversed.

e.g. Let 1 be fixed in 1 2 3 4 5 6. 1 is the minimum element, so the elements after it are larger and can be removed one-by-one. I am interpreting the tutorial as saying the opposite?

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

    You are right, if you have for example the 1-indexed array 10 3 10 12 5 then in this case dp[5] = dp[4] + dp[3] + dp[2] and then you stop because 3 < 5.

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

Can anybody help me in problem B — Valera and Fruits , why my code is not working for test case no. 5 https://codeforces.net/contest/441/submission/236088517

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

An alternate editorial for Problem D

Let us define:

  • $$$dp[i] =$$$ The number of reachable arrays for prefix of length $$$i$$$ such that we keep the $$$i$$$-th element
  • $$$res[i] =$$$ The number of reachable arrays for prefix of length $$$i$$$

The answer that we are looking for is $$$res[n]$$$.

Let $$$L[i]$$$ be the largest integer such that $$$p[L[i]] < p[i]$$$ and $$$L[i] < i$$$, then we will have the following transitions.

If $$$L[i]$$$ does not exist, i.e. $$$p[i]$$$ is the smallest in the prefix of length $$$i$$$ then:

  • $$$\displaystyle dp[i] = 1 + \sum_{k=1}^{i-1} dp[k]$$$
  • $$$res[i]=dp[i]$$$
Explanation

If $$$L[i]$$$ exist, then:

  • $$$\displaystyle dp[i] = res[L[i]] + \sum_{k=L[i]+1}^{i-1} dp[k]$$$
  • $$$res[i] = res[L[i]] + dp[i]$$$
Explanation

We can use monotonic stack and prefix sums for the transitions.

Here is my submission.

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

okok，在问题 D 的解中，搜索左边的第一个较大元素，尽管在作者的解决方案中它是第一个较小的元素，这是否正常

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

include<bits/stdc++.h>

define int long long

using namespace std;

string s; signed main() { std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { cin>>s; int n=s.size(); int w=0; for(int i=0;i<n;i++) { if(s[i]=='1') w++; } // if(w==n/2) cout<<0<<'\n'; int m=0; int q=0; for(int i=0;i<min(w,n-w)+1;i++) { if(w>=n-w&&s[i]=='0') q++; else if(w<=n-w&&s[i]=='1') q++; } for(int i=0;i<2*min(w,n-w);i++) { if(w>=n-w&&s[i]=='0') { m++; } else if(w<n-w&&s[i]=='1') { m++; } } // if(w!=n-w) if(q!=0) cout<<max(w,n-w)-m<<'\n'; // else cout<<'0'<<'\n'; else cout<<n-min(w,n-w)<<'\n'; } return 0; } This code is wa in test 2 and I can't find my problem

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

I have a bit of a different approach to C, see at 240040360. Basically, you store results from ADD queries as amounts of 1's in different binary columns, and then for each GET query, you move along the binary columns (from the end) and find how many 1's you could have at that binary column position. By comparing with the binary representation of v, you can see if your answer is YES or NO.

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

could someone help to find what's wrong with my code for question D?

https://codeforces.net/contest/1913/submission/240014709

I use interval DP with pointers in one edge pointing to another.

my code have passed 25 tests so I think there's no issue with algorithm that I applied(290ms for 3*10^5 inputs so no problem with complexity). But 26th test has raised problem and I don't why as I can't see all the inputs. Do somebody know what vulnerability is 26th test designed for?

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

You can also optimize DP in D with RURQ.

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

I found by far easier to understand C solution by ordering the weights in non-ascending order instead. I found really confusing to follow the explanation with non-descending order, is anyone able to share a more detailed explanation of how it works? would be really appreciated!

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

    I have a solution that is easier. I'm trying to understand the editorial, but it's really complicated; it might require 3 hours of tracing to understand it. My solution uses a map to store the frequency of each number given in type 1 queries. When I have a type 2 query, I just look at the binary representation of the number I want to check and iterate through its binary representation from left to right. Every time I find a bit equal to 1, I need to have that bit in my map. If I don't have it, then I need to have double the amount in the next bit. For example, if I don't have 16, then I need to have 2 * 8, and if I don't have 8 either, then I need 4 * 4. This is the whole idea, and it worked. just keep a variable called required and iterate through the binary representation if at the end required is 0 then we can form that number

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

I have a question about B. for 1 1 0 why its answer is 1? if we delet only one number of s, such as 1, the string t we got is 1 0. obviously we cna not swap 1 0 to satisfy the 1 1 0.

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

1913B - Swap and Delete Why in the sample test case 111100 have output 4 and not 2? Please explain.

Like we can swap two 1's from two 0's and delete rest of 1's and the operation cost will be 2 only. Example:- 111100(in input). - delete first two 1's. String will be 1100 and cost will be 2. - swap the rest 1's with 0's. cost 0 and total cost will remains 2. - Now the string s = 1100 and t=0011.

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

    The problem statement says: "Note that you are comparing the resulting string $$$t$$$ with the initial string $$$s$$$." So in your case, $$$s$$$ does not change and remains $$$111100$$$.

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

      Okay but the deletion operation is done on initial string s on the sample test case 011

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

        Is confusing but when you perform a deleting are on t, not in s. In the second test case s = "011", t = "101" because t is not good, you have to delete it the last one, and the cost will be 1.

        For the 4 test case s = "111100" t = "001111" when you compare you realized that you must delete the ones in position 2 and 3 in t doing that you will get the new string t' = "0011" ancompare this new t with the same s. s = "111100" t' = "0011" you again must delete the ones in position 2 and 3 to get t'' = "00" that is good.

        In total you do 4 deleting so the cost is 4.

        → Reply