Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
string s;
cin >> s;
int ans = 1;
if(s[0] == '0') ans = 0;
if(s[0] == '?') ans = 9;
for(int j = 1; j < s.size(); j++)
if(s[j] == '?')
ans *= 10;
cout << ans << endl;
}
}

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
int n;
scanf("%d", &n);
vector<int> a(n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
vector<int> a1(n);
for(int i = 0; i < n; i++)
scanf("%d", &a1[i]);
int diffl = -1, diffr = -1;
for(int j = 0; j < n; j++)
{
if(a[j] != a1[j])
{
diffr = j;
if(diffl == -1)
diffl = j;
}
}
while(diffl > 0 && a1[diffl - 1] <= a1[diffl])
diffl--;
while(diffr < n - 1 && a1[diffr + 1] >= a1[diffr])
diffr++;
printf("%d %d\n", diffl + 1, diffr + 1);
}
}

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

for _ in range(int(input())):
s = input()
n = len(s)
ans = n
for x in range(26):
c = chr(x + ord('a'))
i = 0
cur = 0
while i < n:
j = i
while j < n and (s[j] == c) == (s[i] == c):
j += 1
if s[i] != c:
cur = max(cur, j - i)
i = j
if cur == 0:
ans = 0
break
pw = 0
while (1 << pw) <= cur:
pw += 1
ans = min(ans, pw)
print(ans)

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(' ').map { it.toInt() }
val l = readln().split(' ').map { it.toInt() }
val r = readln().split(' ').map { it.toInt() }
var ans = 2e9.toInt()
var cntShort = 0
var lenLong = 0
for (i in 0 until n) {
val curLen = r[i] - l[i] + 1
if(curLen > 1)
lenLong += curLen
else
cntShort++
if (lenLong < k) {
if (lenLong + cntShort >= k) {
val cntSegs = (i + 1 - cntShort) + (k - lenLong)
ans = minOf(ans, r[i] + 2 * cntSegs)
}
}
else {
ans = minOf(ans, r[i] - (lenLong - k) + 2 * (i + 1 - cntShort))
break
}
}
if (ans == 2e9.toInt())
ans = -1
println(ans)
}
}

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution 1 (awoo)**

#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const long long INF64 = 1e18;
long long dp[2][11][11][6];
int main(){
int t;
cin >> t;
while (t--){
int k;
cin >> k;
string s;
cin >> s;
int n = s.size();
forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1) dp[0][balo][balc][mv] = INF64;
dp[0][k][k][0] = 0;
int act = 0;
forn(ii, n){
int i = ii & 1;
int ni = i ^ 1;
forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) forn(mv, k + 1)
dp[ni][balo][balc][mv] = INF64;
forn(mv, k + 1) forn(balo, 2 * k + 1) forn(balc, 2 * k + 1) if (dp[i][balo][balc][mv] != INF64){
int bal = act - balo + balc;
if (balo >= 0 && mv < k)
dp[i][balo - 1][balc][mv + 1] = min(dp[i][balo - 1][balc][mv + 1], dp[i][balo][balc][mv] + bal);
if (balc >= 0 && mv < k && bal > 0)
dp[i][balo][balc - 1][mv + 1] = min(dp[i][balo][balc - 1][mv + 1], dp[i][balo][balc][mv]);
if (s[ii] == '('){
dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv] + bal);
if (balo + 1 <= 2 * k)
dp[ni][balo + 1][balc][mv] = min(dp[ni][balo + 1][balc][mv], dp[i][balo][balc][mv]);
}
else{
if (bal > 0)
dp[ni][balo][balc][mv] = min(dp[ni][balo][balc][mv], dp[i][balo][balc][mv]);
if (balc + 1 <= 2 * k)
dp[ni][balo][balc + 1][mv] = min(dp[ni][balo][balc + 1][mv], dp[i][balo][balc][mv]);
}
}
act += (s[ii] == '(' ? 1 : -1);
}
printf("%lld\n", *min_element(dp[n & 1][k][k], dp[n & 1][k][k] + k + 1));
}
}

**Solution 2 (awoo)**

for _ in range(int(input())):
k = int(input())
s = input()
n = len(s)
st = []
cnt = [0 for i in range(n + 1)]
ans = 0
for i in range(n):
if s[i] == '(':
ans += len(st)
st.append(i)
else:
cnt[(i - st.pop()) // 2] += 1
for i in range(n, -1, -1):
t = min(k, cnt[i])
ans -= t * i
k -= t
print(ans)

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vector<int> fact(2 * n + 1), rfact(2 * n + 1);
fact[0] = 1;
for (int i = 1; i <= 2 * n; ++i) fact[i] = mul(fact[i - 1], i);
rfact[2 * n] = binpow(fact[2 * n], MOD - 2);
for (int i = 2 * n - 1; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
auto cnk = [&](int n, int k){
if (k < 0 || n < 0 || k > n) return 0;
return mul(fact[n], mul(rfact[k], rfact[n - k]));
};
auto snb = [&](int n, int k){
return cnk(n + k, k);
};
int pw2 = 1;
int ans = 0;
for (int i = m; i >= 0; --i){
int cur = 0;
if (n - (m - i) * 1ll * (k + 1) - i * 1ll * (2 * k + 1) >= 0)
cur = mul(snb(n - (m - i) * (k + 1) - i * (2 * k + 1), m), mul(pw2, cnk(m, i)));
ans = add(ans, i & 1 ? -cur : cur);
pw2 = mul(pw2, 2);
}
printf("%d\n", ans);
}

was waiting eagerly, couldn't solve D

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

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.

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

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?

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.

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:

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

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.

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

Then

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.

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

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

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

then

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

and therefore our answer is

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

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

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.

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.

If I am not wrong b

_{i}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?$$$b_i = {n - (k+1) \cdot m - k \cdot i + m \choose m} {m \choose i}$$$

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.

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."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.

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

Cool!

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.

a

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

Sorry for that I can't understand this: In 1821C P3,

If some operation contains both ones and zeros, then taking ones out of it doesn't make any zeros in it adjacent., if I didn't think it stupidly, why is that so?For example, if we got a string

`1001000`

, and we move the $$$2^{nd}$$$`1`

out of the string, then`00`

and`000`

is adjacent. Did I think wrong? Please tell me where I was wrong, I really appreciate it, thanks.Problem E in C++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?

i wonder too

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

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

importantpart, 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 willneverturn 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?

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

Thank you ^^ I will try it