Educational Codeforces Round 147 — Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Tutorial

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;
	}
}

1821B - Sort the Subarray

Idea: BledDest

Tutorial

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);
	}
}

1821C - Tear It Apart

Idea: BledDest

Tutorial

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)

1821D - Black Cells

Idea: adedalic

Tutorial

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

1821E - Rearrange Brackets

Idea: BledDest

Tutorial

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)

1821F - Timber

Idea: BledDest

Tutorial

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);
}

Comments (33)

Show archived | Write comment?

akm07

19 months ago, # |

← Rev. 2 →

-7

was waiting eagerly, couldn't solve D

→ Reply

papa-ka-para

← Rev. 3 →

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.

Citypop

19 months ago, # ^ |

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

smax

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?

psoet

18 months ago, # ^ |

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.

+10

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.

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.

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

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

Beaboss

16 months ago, # ^ |

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.

cockatooo

+11

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:

_wisdom

Please link this to the contest materials.

emorgan

18 months 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.

Runtime-Terr0r

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.

Hagry

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

reilu

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

kondasujay2

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

v7fgg

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.net/contest/1821/submission/203164677

The5threich

12 months ago, # ^ |

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.

nonrice

b00s

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

dv_0101

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?

gerogeVT

i wonder too

Xiao_2710

9 months ago, # ^ |

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.

ShivanshJ

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

tezk

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

OrazB

thanks

ctrller

16 months ago, # |

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

Sakuyalove

15 months ago, # ^ |

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

Ansh_007

10 months ago, # |

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;

BledDest's blog