BledDest's blog

Educational Codeforces Round 147 — Editorial
By BledDest, 19 months ago, In English

1821A - Matching

Idea: BledDest

Tutorial
Solution (BledDest)

1821B - Sort the Subarray

Idea: BledDest

Tutorial
Solution (BledDest)

1821C - Tear It Apart

Idea: BledDest

Tutorial
Solution (awoo)

1821D - Black Cells

Idea: adedalic

Tutorial
Solution (adedalic)

1821E - Rearrange Brackets

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1821F - Timber

Idea: BledDest

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

Comments Comments (32)
| Write comment?
»
19 months ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

was waiting eagerly, couldn't solve D

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

in Problem E ,

Please explain,

k = 1, RBS = (()()(())), then ANS = 1

HOW ?

which bracket we will move such that our answer becomes "1".

please someone elaborate.

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

    Move first one to match the last. ()()(())()

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

Initially, we thought that we could just use PIE to calculate the exact answer from that — $$$\sum_{x=0}^m f(x) \cdot (-1)^x$$$. And the results of this formula coincided with the naive solution, so we thought that everything should be fine. But unfortunately, even though the formula is right, using PIE in the described way is incorrect.

That is precisely how I thought of doing PIE for this problem as well, so I'm surprised to hear it's wrong. Why is that?

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

    I think that's because the coefficient $$$2^{m-x}$$$ remains the same ($$$x$$$ is the exact size of the set), but the size of a subset you emurate during PIE doesn't.

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

      I don't think the coefficient being constant is necessarily an issue, there are plenty of applications of PIE which have fixed coefficients based on subset size such as counting derangements:

      $$$ \sum_{x=0}^n (-1)^x \binom{n}{x} (n-x)! $$$

      According to this reference, PIE can be used to count "exact" constraints based on "at least" constraints:

      $$$ N_{= \emptyset} = \sum_{T \subseteq E} (-1)^{|T|} N_{\supseteq T} $$$

      In this case, the property is that a segment is long instead of short, and the formula counts exactly none of the segments being long in terms of subsets of segments such that at least these segments are long, so under these lens the simple PIE solution seems valid.

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

        The example you mentioned differed from this situation. The coefficients used in counting derangements are just the number of certain permutations.

        The PIE can be paraphrased as: given 2 functions $$$f,g$$$ on sets that satisfy

        $$$ f(S) = \sum_{S \subseteq T} g(T) $$$

        Then

        $$$ g(S) = \sum_{S \subseteq T} f(T)(-1)^{|T|-|S|} $$$

        In this problem, the $$$f$$$ we calculated is not the sum of $$$2^{m-|T|}$$$ over all possible T, but the number of Ts multiplied by the same $$$2^{m-|S|}$$$. So the formula isn't valid here.

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

          Ok, so tell me if I'm understanding this correctly.

          The $$$f(x)$$$ used in the "wrong" solution is

          $$$ f(x) = \binom{m}{x} \binom{n-x(2k+1)-(m-x)(k+1)+m}{m} \cdot 2^{m-x} $$$

          Now go to the subset interpretation of PIE, if we define $$$f$$$ and $$$g$$$ as:

          • $$$f(S)$$$ is the number of ways where at least the intervals in $$$S$$$ are long
          • $$$g(S)$$$ is the number of ways where exactly the intervals in $$$S$$$ are long

          then

          $$$ f(T) = \binom{n-|T|(2k+1)-(m-|T|)(k+1)+m}{m} \cdot 2^{m-|T|} $$$

          as this is just the $$$f(x)$$$ mentioned in the editorial (without the $$$\binom{m}{x}$$$ because we're only considering one subset and not all subsets of size $$$x$$$), and

          $$$ \begin{align} g(S) &= \sum_{S \subseteq T} f(T) (-1)^{|T|-|S|} \\ &= \sum_{S \subseteq T} \binom{n-|T|(2k+1)-(m-|T|)(k+1)+m}{m} \cdot 2^{m-|T|} \cdot (-1)^{|T|-|S|} \end{align} $$$

          and therefore our answer is

          $$$ \begin{align} g(\emptyset) &= \sum_{T} \binom{n-|T|(2k+1)-(m-|T|)(k+1)+m}{m} \cdot 2^{m-|T|} \cdot (-1)^{|T|} \\ &= \sum_{x=0}^m \binom{m}{x} \binom{n-x(2k+1)-(m-x)(k+1)+m}{m} \cdot 2^{m-x} \cdot (-1)^x \end{align} $$$

          The coefficient used here is $$$2^{m-|T|}$$$, not $$$2^{m-|S|}$$$. And this reasoning seems identical to the reasoning used for the "wrong" solution, which is expressing $$$g$$$ as an alternating sum of $$$f$$$.

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

            Oh, I see. I think it's right.

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

            I think it may be because when you say

            \begin{align} g(S) &= \sum_{S \subseteq T} f(T) (-1)^{|T|-|S|}\end{align}

            it should be

            \begin{align} g(S) &= \sum_{S \subseteq T} {{m — |S|} \choose {|T| — |S|}} f(T) (-1)^{|T|-|S|} \end{align}

            because you need to choose which of the current short segments are long segments in the terms of the PIE.

            Interestingly, they give the same result though.

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

A few typos in F editorial, based on my understanding:

"If there're at least k free spots, then the tree can only fall from the left side of that segment." "left" should be right.

"For x trees, make their segments of length 2k+1-k+1 for the tree itself and k extra cells to the left of it." "2k+1-k+1" should just be k+1.

In the formula two lines above "Overall complexity", there are two $$$F(z)$$$. One of them should be deleted.

Hopefully this clears things up for people reading the editorial.

Also, here is a problem utilizing Inclusion-Exlusion that is very similar to the subproblem in F:

link

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

Please link this to the contest materials.

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

Here is my thoughts about how to solve F: let $$$a_i$$$ be the number of configurations of fallen logs such that exactly $$$i$$$ logs have a gap of $$$k$$$ empty space to their left. We want to compute $$$\sum\limits_{i=0}^{m} 2^{m-i} \cdot a_i$$$. But, the only information we have right now is a separate array $$$b$$$ such that $$$b_i = \sum\limits_{j=0}^{m} {j \choose i} \cdot a_j$$$. If you imagine arranging all the coefficients of $$$a$$$ in $$$b_i$$$ in a matrix where $$$M_{i,j}$$$ is the coefficient of $$$a_j$$$ in $$$b_i$$$, then the matrix is an upper triangular matrix which looks like pascal's triangle. We want to do something kind of like gaussian elimination on the matrix in order to determine which coefficients on the rows yield the vector $$$[1, \frac 1 2, \frac 1 4, ...]$$$ when you add the rows up to get one horizontal vector. The correct coefficients (and I just extrapolated this after trying the first few columns by hand) are $$$[1, -\frac 1 2, \frac 1 4, - \frac 1 8, ...]$$$. Then you can try to prove the general fact that $$$\sum\limits_{k=0}^{n} {n \choose k} (-2)^{-k} = 2^{-n}$$$. I think this is more intuitive than magically rearranging the long expression in the editorial so that a known identity shows up.

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

    If I am not wrong bi is number of m-tuples that add up to n such that at least i numbers is greater than k? How to find array b?

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

      $$$b_i = {n - (k+1) \cdot m - k \cdot i + m \choose m} {m \choose i}$$$

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

        It seems like I misunderstood the $$$ b_i $$$ and interpreted it as $$$ b_i $$$ = $$$\sum_{j=i}^{m} a_j$$$ and was wondering how to calculate it.
        Thanks for reply.

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

I think you forgot to link the editorial in the contest materials section.

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

Can someone explain, for problem F:

Why is the first mention of answer using PIE approach told as wrong?

$$$ \begin{align} \displaystyle ans &= \sum_{x=0}^m f(x)\cdot(-1)^x \\ where \hspace{3em} f(x) &= \binom{m}{x} \cdot \binom{n-x\cdot(2k+1)-(m-x)\cdot(k+1)+m}{m}\cdot2^{m-x} \hspace{3em} \text{(as told in one paragraph above it)} \end{align} $$$




UPD: I'm still not sure if this approach is supposed to be seen as wrong or not. But my submission 203209129 using this approach definitely ACed.

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

    "But unfortunately, even though the formula is right, using PIE in the described way is incorrect." The editorial is saying that it isnt technically correct but the formula is right.

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

Problem E can be solved like this: using a map to denote the diffrence of left and right bracket and the last position this value of diference occured, the number of right bracket is between is the "influence" it has if it is removed, here is my code: https://mirror.codeforces.com/contest/1821/submission/203164677

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

    I did exactly this in the practice today. I think it is certainly much easier to come up with than that dp solution. and more efficient too! Submission->1821E->230735566

    This one is $$$O(nk)$$$ ish

    I think the authors didn't know about this one as it doesn't feel like a Div-2 E with this solution.

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

a

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

cna we solve D using Dynamic Programming ? if not, please tell the reason. if yes, please tell how ?

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

In problem B, why are we looking to expand our range to left and right, since they are same they should not be in the sorted subarray, right?

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

    Because the problem asks us to maximize l...r range too. for ex: v1:[2,3,6,8,4,9] v2:[2,3,4,6,8,9] now for l=3,r=5, v1 gives v2, but for l=1 and r=6, v1 gives v2 too and clearly the latter is the bigger range and thus the answer. that is why we need to check for expansion on both ends if possibe.

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

I was confused regarding the proof for problem E's claim that there exists an optimal answer such that each moves results in an $$$RBS$$$. (Note that the condition of the problem is that only the resulting sequence after all $$$k$$$ moves should be an $$$RBS$$$, no condition about the intermediate sequences).

So, I managed to come up with a decent proof. First of all, we know in one move we remove some bracket and place it somewhere. We can freely first choose to remove all $$$k$$$ brackets then start placing these brackets in their required positions. Clearly, both are equivalent. Consider an optimal sequence of moves in which —

Say, we have removed $$$($$$ at positions: $$$i_1, i_2, i_3..$$$ and we placed some $$$($$$ at positions $$$j_1, j_2, j_3..$$$

We can map these $$$i's$$$ with $$$j's$$$ arbitrarily. Suppose we map $$$(i_2,j_3)$$$ then we can consider bracket at position $$$i_2$$$ "moving" at position $$$j_3$$$. We can call a pair of mapping a move also. Call a pair of mapping $$$(i_a,j_b)$$$ "good" if $$$i_a \le j_b$$$.

Also, define this stuff similarly for $$$)$$$ type of brackets. (We again map their indexes from which they are removed to the indexes where they have been placed, however in this case call a pair of mapping $$$(k_a,w_b)$$$ "good" if $$$w_b \le k_a$$$, here $$$k_a$$$ is the index where bracket is removed and $$$w_b$$$ is the index where it is inserted back).

Now here comes the important part, if the sequence is an $$$RBS$$$, then performing a "good" mapping pair over it will always result in the sequence which is an $$$RBS$$$ too. Also, once the sequence turns $$$non-RBS$$$ then any "bad" mapping pair/move performed will never turn it to $$$RBS$$$ again. So, the $$$k$$$ pairs of mapping that we got, just sort them such that all "good" mappings are to the left of any "bad" mapping.

This will be the sequence of moves such that after every move the resulting sequence is an $$$RBS$$$. Initially sequence is an $$$RBS$$$, and goes through all the "good" pairs of mapping, the sequence is guaranteed to remain an $$$RBS$$$, then it goes through "bad" pairs of mappings, now the sequence can't turn into $$$non-RBS$$$ because, if it turns into $$$non-RBS$$$ then it contradicts the fact that after all the $$$k$$$ moves have been performed the final sequence is an $$$RBS$$$ ! (There is no way the sequence can switch from $$$non-RBS$$$ to $$$RBS$$$ which going through the pairs of "bad" mappings !)

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

$$$E$$$ is a very pretty problem, but is there any way to modify the statement so that others who upsolve it like me won't lose time due to the confusing statement ? I didn't notice the clarification of 1 bracket per operation at first

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

thanks

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

I see fft tag for F, does anyone have any idea about it pls?

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

    My solution used fft. Consider $$$m$$$ segments with length $$$k+1$$$, the length of the interval between the $$$(i-1)^{th}$$$ segment and the $$$i^{th}$$$ segment($$$[-k,0]$$$ as the $$$0^{th}$$$ segment) is $$$l_i$$$. Hence we have $$$\sum\limits_{i=1}^{m} l_i \le n - (k+1)m$$$ and $$$l_i \ge 0$$$ for $$$i=1,2,...,m$$$.

    Now we will determine whether each tree is at the left or right endpoint of the segment. To avoid repetition, we claim that for each tree it must fall down to the left unless it can't fall down to the left side. So the tree of the $$$i^{th}$$$ segment can be left endpoint only if $$$l_i< k$$$. And in any case a tree can always be a right endpoint. So the answer is $$$\sum\limits_{l_1+...+l_m\le n-(k+1)m} 2^{\sum\limits_{i=1}^{m}[l_i < k]}$$$.

    Now consider $$$f(x)=2(1+x+...+x^{k-1})+(x^{k}+x^{k+1}+...)=\frac{1}{1-x}+\frac{1-x^{k}}{1-x}=\frac{2-x^{k}}{1-x}$$$, the answer is $$$\sum\limits_{i=0}^{n-(k+1)m}[x^i]f^m(x)$$$, where $$$f^m(x)=(2-x^{k})^m(1-x)^{-m}$$$, we have $$$(2-x^{k})^m=\sum\limits_{i=0}^{m}\binom{m}{i}(-1)^i2^{m-i}x^{ki}$$$,$$$(1-x)^{-m}=\sum\limits_{i=0}^{\infty}\binom{m+i-1}{m-1}x^i$$$, so use fft, we can get $$$f^m(x)$$$, and then we can get answer. This solution is $$$O(n\log n)$$$.

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

If anyone here from the TLE cp sheet code for B:

int n;cin>>n;

vectora(n),b(n);

for(auto &it:a)cin>>it ; for(auto &it:b)cin>>it;

int l=0,r=n-1;

while(l<n && a[l]==b[l])l++; while(r>=0 && a[r]==b[r])r--;

while( l>=1 && b[l]>=b[l-1])l--; while(r<(n-1) &&b[r]<=b[r+1] )r++;

cout<<l+1<<" "<<r+1;

→ Reply