Vladosiya's blog

By Vladosiya, 14 months ago, translation, In English

1811A - Insert Digit

Idea: senjougaharin, prepared: senjougaharin

Tutorial
Solution

1811B - Conveyor Belts

Idea: Vladosiya, prepared: senjougaharin

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?

Idea: Vladosiya, prepared: Vladosiya

Tutorial
Solution

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

Idea: Vladosiya, prepared: Vladosiya

Tutorial
Solution

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

Idea: Vladosiya, prepared: Vladosiya

Tutorial
Solution
  • Vote: I like it
  • +52
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been translated by Vladosiya (original revision, translated revision, compare)

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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   Vote: I like it +4 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

Still i can't visualize problem D.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain editorial of G1?

  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +28 Vote: I do not like it
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same with me XD .Screenshot-2023-04-05-214607

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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   Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that is what i want to know as well.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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, # |
  Vote: I like it +11 Vote: I do not like it

Interesting problem E

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It is fair. You used the wrong language

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried this approach, but this gives TLE Code

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same approach

      #include <bits/stdc++.h>
      using namespace std;
      template<typename T>void print( const T& arg ){ if constexpr( is_same_v<T, char> ) arg == '\n' ? cout << arg : cout << arg << ' '; else cout << arg << ' '; }template<typename... Args>void print( const Args&... args ){ ( print( args ), ... ); }
      template<typename... Args>void 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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain editorial of G2 in detail?

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :/

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

Problem E can be solved using Base conversion

since 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