5

Educational Codeforces Round 147 — Editorial

 1 year ago
source link: https://codeforces.com/blog/entry/115296
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By BledDest, 3 days 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)

3 days ago, # |

← Rev. 2 →  

-7

was waiting eagerly, couldn't solve D

3 days ago, # |

← Rev. 3 →  

0

For the newer contestants who want some extra practice, but probably for the benefit of a lot of others reading as well:

Could people comment on what specific past problem(s) do each problem in Educational Codeforces Round 147 remind them of?

Update: I have also asked this question to the general community on my blog here: https://codeforces.com/blog/entry/115305

3 days ago, # |

← Rev. 3 →  

0

in Problem E ,

Please explain,

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

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

please someone elaborate.

  • 2 days ago, # ^ |

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

2 days ago, # |

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?

  • 22 hours ago, # ^ |

    ← Rev. 2 →  

    0

    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.

    • 17 hours ago, # ^ |

      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.

2 days ago, # |

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

2 days ago, # |

Please link this to the contest materials.

31 hour(s) ago, # |

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.

  • 25 hours ago, # ^ |

    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?

    • 20 hours ago, # ^ |

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

      • 20 hours ago, # ^ |

        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.

30 hours ago, # |

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

27 hours ago, # |

← Rev. 4 →  

+13

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.

20 hours ago, # |

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://codeforces.com/contest/1821/submission/203164677

13 hours ago, # |

← Rev. 4 →  

0

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK