was waiting eagerly, couldn't solve D

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.

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?

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

Please link this to the contest materials.

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.

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

Can someone explain, for problem F:

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

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.

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

a

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

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 !)

BledDest who is arul in 1821C?

$$$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

thanks

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

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;

In problem B,
what if
a = [ 6, 3, 2, 7, 3, 5, 7]
a'= [6, 7, 2, 7, 5 , 3, 3]
then the answer should be l=1 and r=7
but I don't think that is the correct one because the whole array is not 'not-decreasing'

BledDest The problem B is missing a test case.

Input:

1
5
1 2 3 4 5
1 2 3 4 5

Output:

1 5

The solution provided here causes undefined behavior and buffer overflow for this testcase. I think the test case should be added as I have seen some submissions giving wrong answer for this case.

Just checking the longest segment in array a` which is increasing and not equal to the segment in a ..and using stl like pair<int,pair<int,int>> = {-1,{-1,-1}} and using max on it to store the segment with largest length and not equal to the segment in a. ~~~~~~~~~~~~~~~~~~~~~~~

include <bits/stdc++.h>

using namespace std;

define ll long long

define f(i, n) for (int i = 0; i < n; i++)

define f1(i, n) for (int i = 1; i < n; i++)

define f11(i, n) for (int i = 1; i <= n; i++)

define fr(i, n) for (int i = n — 1; i >= 0; i--)

const int MOD = 1e9 + 7;

void solve() { int n; cin >> n; vector a(n + 1), b(n + 1); f(i, n) cin >> a[i]; f(i, n) cin >> b[i]; b.push_back(-1); a.push_back(-1); ll ans = -1; pair<int, pair<int, int>> p = {-1, {-1, -1}}; f(i, n) { int last = b[i]; int count = 1; int start = i + 1; vector x, y;

while ((i < n) && (b[i + 1] >= b[i]))
    {
        x.push_back(a[i]);
        y.push_back(b[i]);
        count++;
        i++;
    }
    int end = i + 1;
    if (x != y)
    {
        p = max(p, {count, {start, end}});
    }
}
cout << p.second.first << " " << p.second.second;
cout << endl;

}

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) solve(); return 0; } ~~~~~~~~~~~~~~~~~~~~~