By Vladosiya, 14 months ago, translation,

1811A - Insert Digit

Idea: senjougaharin, prepared: senjougaharin

Tutorial
Solution

1811B - Conveyor Belts

Tutorial
Solution

1811C - Restore the Array

Idea: MikeMirzayanov, prepared: myav

Tutorial
Solution

1811D - Umka and a Long Flight

Idea: Gornak40, prepared: Gornak40

Tutorial
Solution

1811E - Living Sequence

Idea: Aris, prepared: Aris

Tutorial
Solution

1811F - Is It Flower?

Tutorial
Solution

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

Tutorial
Solution

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

Tutorial
Solution
• +52

| Write comment?
 » 14 months ago, # |   +6 Auto comment: topic has been translated by Vladosiya (original revision, translated revision, compare)
 » 14 months ago, # |   +12 Great problems! had so much fun during the contest. One of the most interesting Div 3 contest for sure. Happy coding :)
 » 14 months ago, # | ← Rev. 3 →   +4 The contest was good. I wish div 3 and div 4 will be arranged atleast 2 — 3 times a month for beginner like me
 » 14 months ago, # |   +3 Still i can't visualize problem D.
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ |   0 Sure will try tommorrow morning. Thanks, i guess i have to make a lot of diagrams and dry run each one of them.
•  » » » » 14 months ago, # ^ |   0 Yeah I mean atleast you'll need a whole page ;)But there's not more than lets say 3-4 cases
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   +4 Can somebody give a recursive and easily understandable solution for g1/g2?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 check out My solutionsolveMax 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.
 » 14 months ago, # |   +1 Can someone explain editorial of G1?
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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.
 » 14 months ago, # |   +28
•  » » 14 months ago, # ^ |   0 Same with me XD .
•  » » » 14 months ago, # ^ |   +3 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.
 » 14 months ago, # | ← Rev. 4 →   +3 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?
 » 14 months ago, # |   +3 Problems are seems harder than usual div3...though they are fantastic..
 » 14 months ago, # |   0 For problem C, a[i]=min(b[i],b[i+1]) at 2≤i≤n−1 is right?
•  » » 14 months ago, # ^ |   0 that is what i want to know as well.
•  » » » 14 months ago, # ^ |   0 how to understand this example{1 7 0 1}, result given by code is {1 1 0 0 1}, 7 = max(1, 0)?
•  » » » » 14 months ago, # ^ |   +3 this array b is not possible.It will not be a part of testcases They've mentioned it in solution as well.Read carefullly
 » 14 months ago, # |   +11 Interesting problem E
 » 14 months ago, # |   +8 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
 » 14 months ago, # | ← Rev. 2 →   0 in D point number 4, don't you mean $F_{n-1} \le y_n < F_n$ ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 No, the current inequality $F_{n-1} < y_n \le F_n$ is correct. The rows and columns are 1-indexed in the editorial.
•  » » » 14 months ago, # ^ |   0 Ah, i see. Thanks!
 » 14 months ago, # |   0 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.
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # | ← Rev. 3 →   -9 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
•  » » 14 months ago, # ^ |   +5 It is fair. You used the wrong language
 » 14 months ago, # |   0 I can't understand the Tutorial of E ...
•  » » 14 months ago, # ^ |   0 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,...$
 » 14 months ago, # |   +1 can Someone explain D, i really can't wrap my head around bunch of inequalities given in the tutorial!
 » 14 months ago, # |   0 For A, why does the O(n) solution run out?200968450It 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.
•  » » 14 months ago, # ^ |   0 You wrote "const int N = 100010; ", but N can be 200000. If you increase, you will solve the problem.
 » 14 months ago, # |   0 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
•  » » 14 months ago, # ^ |   0 is this called digit dp or digit dp is something else?
•  » » » 13 months ago, # ^ |   0 Not sure what they used but i solved with digit dp.let $f(x) =$ how many numbers before $x$ with digit 4use digit dp to solve $f(x)$.Then answer for the problem is $x$ where, $x-f(x)=k$. Binary search to find $x$https://mirror.codeforces.com/contest/1811/submission/202927151
•  » » » » 12 months ago, # ^ |   0 what is k here?
•  » » 12 months ago, # ^ |   0 I tried this approach, but this gives TLE Code
•  » » » 3 weeks ago, # ^ |   0 same approach #include using namespace std; templatevoid print( const T& arg ){ if constexpr( is_same_v ) arg == '\n' ? cout << arg : cout << arg << ' '; else cout << arg << ' '; }templatevoid print( const Args&... args ){ ( print( args ), ... ); } templatevoid scan( Args&... args ){ ( ( cin >> args ), ... ); } #define int long long #define ll long long const int md = 1e9 + 7, inf = 1e18, N = 1e6; int v[ 2 ][ 15 ], pw[ 16 ]; int sol( int j, int t, string& s, int& n ){ if( j >= n ) return 0; int& res = v[ t ][ j ]; if( res != -1 ) return res; res = 0; char r = t ? s[ j ] : '9'; int d = r - '0' + 1; if( r >= '4' ) --d, res += pw[ n - j - 1 ]; if( t ) --d, res += sol( j + 1, 1, s, n ); res += d * sol( j + 1, 0, s, n ); return res; } void __(){ int x, d = 0, n, ans = 0, f = 1, p = 0; scan( x ); for( int d = 0, p = 0; f or d != p; f = 0 ){ p = d; string s = to_string( x ); n = s.size(); memset( v, -1, sizeof( v ) ); d = sol( 0, 1, s, n ); x += d - p; } print( x ); cout << "\n"; } signed main(){ ios_base::sync_with_stdio( false ); cin.tie( nullptr ); int _ = 1; pw[ 0 ] = 1; for( auto i = 1; i < 16; i++ ){ pw[ i ] = 10 * pw[ i - 1 ]; } cin >> _; while( _-- ) __(); return 0; } 
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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 ;)
 » 14 months ago, # |   +1 Can someone explain editorial of G2 in detail?
 » 14 months ago, # |   0 Can anyone help me figure out why this submission has a run-time error? 201201145I have been stuck on this problem for a long time and I'm not quite sure why it has a run time error. :/
 » 13 months ago, # |   0 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.
•  » » 13 months ago, # ^ |   0 That input doesnt have an answer. The input is made from the array not the other way around.
 » 12 months ago, # |   0 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?
 » 10 months ago, # |   0 Could somebody please explain point 6 in the editorial of Problem D?
 » 7 months ago, # |   0 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.
 » 3 months ago, # |   0 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).
 » 2 months ago, # |   0 Problem B: It's a shame xth row and yth column is ambiguous. You should indicate xth row (starting the count from 1).
 » 6 weeks ago, # | ← Rev. 2 →   0 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