Idea: senjougaharin, prepared: senjougaharin

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
using namespace std;
void solve() {
int n, d;
cin >> n >> d;
string s;
cin >> s;
for (int i = 0; i < n; ++i) {
if (s[i] - '0' >= d) {
cout << s[i];
} else {
cout << d;
for (int j = i; j < n; ++j) {
cout << s[j];
}
cout << '\n';
return;
}
}
cout << d << '\n';
}
int main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
}
return 0;
}
```

Idea: Vladosiya, prepared: senjougaharin

**Tutorial**

Tutorial is loading...

**Solution**

```
def layer(n, x, y):
return min([x, y, n + 1 - x, n + 1 - y])
def solve():
n, x1, y1, x2, y2 = map(int, input().split())
print(abs(layer(n, x1, y1) - layer(n, x2, y2)))
t = int(input())
for _ in range(t):
solve()
```

Idea: MikeMirzayanov, prepared: myav

**Tutorial**

Tutorial is loading...

**Solution**

```
#include "bits/stdc++.h"
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>b(n-1), a;
for(int i = 0; i < n - 1; i++) cin >> b[i];
a.emplace_back(b[0]);
for(int i = 0; i < n - 2; i++){
a.emplace_back(min(b[i], b[i + 1]));
}
a.emplace_back(b[n - 2]);
for(auto &i : a) cout << i << ' ';
cout << "\n";
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
```

1811D - Umka and a Long Flight

Idea: Gornak40, prepared: Gornak40

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50;
int fib[MAXN];
void build() {
fib[0] = fib[1] = 1;
for (int i = 2; i < MAXN; ++i)
fib[i] = fib[i - 2] + fib[i - 1];
}
bool solve(int n, int x, int y) {
if (n == 1) return true;
if (fib[n - 1] <= y && y < fib[n])
return false;
if (fib[n] <= y)
y -= fib[n];
return solve(n - 1, y, x);
}
int main() {
int t; cin >> t;
build();
while (t--) {
int n, x, y; cin >> n >> x >> y;
cout << (solve(n, --x, --y) ? "YES" : "NO") << '\n';
}
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int32_t num_tests;
std::cin >> num_tests;
for(int32_t t = 0; t < num_tests; t++) {
int64_t k;
std::cin >> k;
std::vector<int32_t> digits;
while(k > 0) {
digits.push_back(k % 9);
k /= 9;
}
std::reverse(digits.begin(), digits.end());
for(int32_t i = 0; i < digits.size(); i++)
std::cout << (char)(digits[i] < 4 ? (digits[i] + '0') : (digits[i] + '1'));
std::cout << "\n";
}
return 0;
}
```

Idea: Vladosiya, prepared: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int sz(int v, vector<vector<int>> &g, vector<bool> &used){
used[v] = true;
int s = 1;
for(int u: g[v]){
if(!used[u]) s += sz(u, g, used);
}
return s;
}
void remove(vector<int> &from, int x){
for(int &e: from){
if(e == x){
swap(e, from.back());
from.pop_back();
return;
}
}
}
void solve(int tc) {
int n, m;
cin >> n >> m;
vector<vector<int>> sl(n);
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
int k = sqrt(n);
if(n != k * k || m != n + k){
cout << "NO";
return;
}
for(int i = 0; i < n; ++i){
if(sl[i].size() != 2 && sl[i].size() != 4){
cout << "NO";
return;
}
}
vector<bool> used(n);
if(sz(0, sl, used) != n){
cout << "NO";
return;
}
for(int i = 0; i < n; ++i){
if(sl[i].size() == 2) continue;
for(int j = 0; j < sl[i].size();){
int u = sl[i][j];
if(sl[u].size() > 2){
remove(sl[i], u);
remove(sl[u], i);
}
else{
j++;
}
}
}
used = vector<bool>(n);
for(int i = 0; i < n; ++i){
if(!used[i] && sz(i, sl, used) != k){
cout << "NO";
return;
}
}
cout << "YES";
}
bool multi = true;
signed main() {
cout.tie(nullptr);
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
```

1811G1 - Vlad and the Nice Paths (easy version)

Idea: Vladosiya, prepared: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
M = 10 ** 9 + 7
def pw(a, n):
if n == 0:
return 1
b = pw(a, n // 2)
return b * b % M * (a if n % 2 == 1 else 1) % M
def obr(x):
return pw(x, M - 2)
def cnk(n, k):
return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M
def solve():
n, k = map(int, input().split())
c = [-1] + [int(x) for x in input().split()]
if k == 1:
print(1)
return
dp = [[0] * (n // k + 1) for i in range(n + 1)] # dp[i][j] = number for i prefix with j blocks
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(0, n // k + 1):
if j > 0:
sz = 1
for s in range(i - 1, - 1, -1):
if c[s] == c[i]:
sz += 1
if sz >= k:
dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M
dp[i][j] %= M
dp[i][j] += dp[i - 1][j]
dp[i][j] %= M
for j in range(n // k, -1, -1):
if dp[n][j] > 0:
print(dp[n][j])
return
t = int(input())
fact = [1] * 101
for i in range(1, 101):
fact[i] = fact[i - 1] * i % M
for _ in range(t):
solve()
```

1811G2 - Vlad and the Nice Paths (hard version)

Idea: Vladosiya, prepared: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
from sys import stdin
input = lambda: stdin.readline().strip()
M = 10 ** 9 + 7
cnk = [[0] * (5000 + 1) for i in range(5000 + 1)]
def solve():
n, k = map(int, input().split())
c = [-1] + [int(x) for x in input().split()]
if k == 1:
print(1)
return
dp = [[0, 0] for i in range(n + 1)] # dp[i] = [number, max] for i prefix
dp[0][0] = 1
for i in range(1, n + 1):
sz = 1
for s in range(i - 1, - 1, -1):
if c[s] == c[i]:
sz += 1
if sz == k:
dp[i][1] = dp[s - 1][1] + 1
if sz >= k:
if dp[s - 1][1] < dp[i][1] - 1:
break
dp[i][0] += dp[s - 1][0] * cnk[sz - 2][k - 2] % M
dp[i][0] %= M
if dp[i][1] < dp[i - 1][1]:
dp[i] = [0, dp[i - 1][1]]
if dp[i][1] == dp[i - 1][1]:
dp[i][0] += dp[i - 1][0]
dp[i][0] %= M
print(dp[n][0])
for i in range(5000 + 1):
cnk[i][0] = 1
for i in range(1, 5000 + 1):
for j in range(1, i + 1):
cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % M
t = int(input())
for _ in range(t):
solve()
```

Auto comment: topic has been translated by Vladosiya (original revision, translated revision, compare)Great problems! had so much fun during the contest. One of the most interesting Div 3 contest for sure. Happy coding :)

The contest was good. I wish div 3 and div 4 will be arranged atleast 2 — 3 times a month for beginner like me

Still i can't visualize problem D.

You can draw some cases for Fn=5 and Fn+1=8, you will realise that there is a dark spot for columns 4 & 5, where the answer is always false, in other case you can just now cut away the 5*5 rectangle because you had to incorporate one 5*5 rectangle, and continue so on in the recursion

Sure will try tommorrow morning. Thanks, i guess i have to make a lot of diagrams and dry run each one of them.

Yeah I mean atleast you'll need a whole page ;)

But there's not more than lets say 3-4 cases

Here is a hint: break up the Fn by Fn+1 rectangle into a Fn by Fn square and a Fn by Fn-1 rectangle. Keep breaking the rectangle until you break up the larger rectangle entirely into squares.

Can somebody give a recursive and easily understandable solution for g1/g2?

check out My solution

solveMax is a function to find the maximum number of segments of length k, starting from index i.

solve is a function to count the number of ways to make a path with the maximum answer.

Can someone explain editorial of G1?

TBH it's a brute force with some memorization. if you find it hard you can train more on dp problems :)

But I'm gonna try to explain anyway. (I Hope it helps beginners)

for G1 :

first, find the longest path :

each segment must contain k elements of the same color. so to define a state for dp, you should indicate the current index, how many elements there are in the current segment, and what is the current segment's color.

for each element, you try to put in the current segment if you can (if the elements in the current segment are less than k, and the color of the current index is the same as the current segment color).

or you start a new segment from this index (if the size of the current segment is 0).

or do nothing with the current index.

Now you have the longest path value for each index, now make another dp to count the ways to construct a path with the optimal answer.

MemeSame with me XD .

This was the contest i became pupil luckily. I could solve 4. This contest was kind of lucky for me. I wish I can do better in the future.

Can someone explain this line "and these cycles do not intersect at the vertices" in problem F, when the simple cycle intersect at the vertices?

Problems are seems harder than usual div3...though they are fantastic..

For problem C, a[i]=min(b[i],b[i+1]) at 2≤i≤n−1 is right?

that is what i want to know as well.

how to understand this example

`{1 7 0 1}`

, result given by code is`{1 1 0 0 1}`

,`7 = max(1, 0)`

?this array b is not possible.It will not be a part of testcases They've mentioned it in solution as well.Read carefullly

Interesting problem E

G2 can be solved by finding the number of paths of length m for each possible m ending at each i and updating the max m divisible by k and the respective number of ways to reach max respectively. Submission: 200833766

in D point number 4, don't you mean $$$F_{n-1} \le y_n < F_n$$$ ?

No, the current inequality $$$F_{n-1} < y_n \le F_n$$$ is correct. The rows and columns are 1-indexed in the editorial.

Ah, i see. Thanks!

myav In the editorial for problem C, $$$a_i = min(b_i, b_{i-1})$$$ for $$$2 \le i \le n-1$$$. Please correct it.

Yes, it's a bug is the tutorial. Later in the proof the formula $$$a_i = \min(b_{i-1},b_i)$$$ is used. Please fix it, Vladosiya, myav and MikeMirzayanov.

Vladosiya why my solution-200898470 got TLE its same as mentioned in editorial .. the same it getting accepted in PyPy-3-200940055.During contest it got accepted in PyPy-2 but after testing i got tle and my rank reduced from 4k to 10k. It's not fair. Please look into it.

I was so close to get pupil but lost it.

BY the Way u must know PyPy-2 is faster than PyPy-3

It is fair. You used the wrong language

I can't understand the Tutorial of E ...

In the $$$9$$$ base you do not have digit $$$9$$$. In the problem you do not have digit $$$4$$$, but it is the same situation. In $$$9$$$ base: $$$1,2,3,4,5,6,7,8,10,11,12,...$$$ In problem: $$$1,2,3,5,6,7,8,9,10,11,12,...$$$

can Someone explain D, i really can't wrap my head around bunch of inequalities given in the tutorial!

For A, why does the O(n) solution run out?200968450

It is guaranteed that the sum of n for all test cases does not exceed $$$2⋅10^5$$$ . My English is so poor that I can't understand the meaning of this sentence.

You wrote "const int N = 100010; ", but N can be 200000. If you increase, you will solve the problem.

Another approach to solve E 1)Let our initial answer be k itself. 2)Now count the no of numbers which contain 4 until k. 3)Add this count to k(our new ans). 4)Now count the no of numbers which contain 4 until our new answer and subtract this count by previous count(as prev count was taken into consideration at step 3). 5)update our value of ans by adding the count. 6)Repeat until our ans is not updating to a new value.

Basically a Gauss-Seidal Approach.

200812209

is this called digit dp or digit dp is something else?

Not sure what they used but i solved with digit dp.

let $$$f(x) = $$$ how many numbers before $$$x$$$ with digit 4

use digit dp to solve $$$f(x)$$$.

Then answer for the problem is $$$x$$$ where, $$$x-f(x)=k$$$.

Binary search to find $$$x$$$

https://codeforces.com/contest/1811/submission/202927151

what is k here?

I tried this approach, but this gives TLE Code

same approach

Great Approach! I honestly liked this problem and the different approaches used. one of tho many(but rare) 1.5k rated that I got stuck on, but still enjoyed the solution ;)

Can someone explain editorial of G2 in detail?

Can anyone help me figure out why this submission has a run-time error? 201201145

I have been stuck on this problem for a long time and I'm not quite sure why it has a run time error. :/

Hey in problem C mike's solution doesn't stand out if the array b is 1 4 5 3 2 1 In other words if my array has a peak middle element is greater than it's adjacent elements 5 7 3 or 0 4 0 anything. Can anyone help me with it.

That input doesnt have an answer. The input is made from the array not the other way around.

how did you decide that only fib0^2 + fib1^2 + .... fib^n = fibn*fib(n+1) is the only way to split the product into n+1 numbers?

Do you have some proof regarding this?

Could somebody please explain point 6 in the editorial of Problem D?

For the solution to G1, how can we show that the number of paths is never a multiple of the mod? If the number of paths is a multiple of the mod, we would skip over the current length and go to the last longest length.

For Problem E, can we also DP on number of removed numbers? That is, number of removed numbers from 1 to 10^k, denoted as r(k), is r(k) = 10^(k-1) + 9 * r(k-1).

Problem B: It's a shame xth row and yth column is ambiguous. You should indicate xth row (starting the count from 1).

Problem E can be solved using Base conversionsince our ask is basically same as in find the number in 9 base where ( 0 — 9 are allowed except 4 )

so first we can convert the number to 9 base then after that if a digit >= 4 we can modify it by adding +1,

but doing this we also need to maintain the carry overs when we will increase 9 -> 10

my AC code using this: AC CODE