Shayan's blog

Codeforces Round 991 (Div 3) — Video Tutorial
By Shayan, 6 weeks ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2050A — Line Breaks

Video

2050B — Transfusion

Video

2050C — Uninteresting Number

Video

2050D — Digital string maximization

Video

2050E — Three Strings

Video

2050F — Maximum modulo equality

Video

2050G — Tree Destruction

Video
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How come this submission doesn't work for C problem: Submission to 2050C

I used a dp array of size (n x 9) so TC and SC is O(n) isn't it? It hit TLE somehow

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

    recursion is computationally heavy

    iterative:

    295133603

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

      Yeah, but then shouldn't question constraint be designed to handle these cases? It's technically the same answer porcelli

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        u are not using dp properly u are updating the matrix only when u find a valid combinations of operations, try to think at ur tree of calls

        input : 33 every fork is a possible path and u are updating ur matrix to 1 only when u find a valid sum that is divisible by 9

                           | - 3
          | - 3  - |
          |        | - 9
dp[0][0]- |
          |        | - 3
          | - 9    |
                   | - 9

        in a bigger picture what u wrote is:

        1) i try a path

        if the sum of the digits on the path is not 0 mod 9 i'm going back and i m not updating the matrix [wrong]

        if the sum of the digits on the path is 0 mod 9 i have found a solution

        this is an exponential solution

        try to use a 3th value {-1 : idk,1:found,0: ehi bro i have already try everything from this postion is usless that we are searching there}

        sorry for bad english + it's 00:15 in my country + i'm sleeping

        infact bro i challenge u to spot the difference between ur code and my version 295135560

        btw a gigachad solution to this problems is:

        the only 2 numbers that ^2 are less than 10 are 2 and 3 and change these digits is equal to adding 2 or 6 respectevely knowing that gcd(9,6) != 0 and gcd(9,2) == 1 u can exploit some properties of modular magic and bruteforce only a small set of value cuz without going deep in the modular math world:

        from 0 if u add 6

        0 — 6 — 12 % 9 == 3 — 9 % 9 == 0 and that's it [0,6,3,0] is usless adding more than 2 six instead for the 2

        2 — 4 — 6 — 8 — 1 — 3 — 5 — 7 — 0 it's usless adding more than 8 two

        u can bruteforce every possible combinations of six and two and u have ur answer :D

        → Reply
        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Oh yea typo in code sorry I messed up the return lol. I should've returned 0 instead of the -1 didn't notice that in a hurry haha

          → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      295039913

      Can you tell me why it gave me TLE? Although it passes when I Used "vector<vector> dp" and pass it as a parameter

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

    I need help with my recursive solution for problem C in memorization here is the submission 295071317

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

im ngl if you managed to tle on this you lowkey deserve it just take the extra 10 seconds to optimize

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I wasn't trying to be rude I'm just actually curious as to why it didn't work. I am doing these questions not in the contest but in my own pace out of interest. Idm that it was tle'd but it's more or less trying to understand my solutions time complexity. My mistake was I didn't return 0 but -1 it was a silly mistake.

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

      oh sorry didnt mean to be rude, i just think that you should have extra complexity for no reason if its not any harder to implement or think about, but it seems you had another problem. happy coding!

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

        Yea it wasn't that hard, it's fine to be frank I'm doing this half asleep so I missed returning 0 and typed -1 there by mistake so it just lead to an exponential solution haha. porcelli thanks for pointing it out after you said 1,0,-1 it made me re-read the return part of the code and I saw that I forgot to return 0 xD.

        → Reply
»
6 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

Any idea on why this submission is causing a TLE for Problem D: 295113992. Could it be due to the i-- part? I don't think i-- is causing tle because the purpose of --i is to find a "better" digit that can be brought forward. This ensures that for the current position i, the best digit is brought to the front before proceeding but we bring forward k elements we will not reconsider them in constructing better digit. So number of element that can be brought forward also decrease for a given n

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

    Firstly, this is D, not C. Secondly, I believe the TLE is from sorting (which takes nlogn) within the loop making

    n^2logn

    same story for skip

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Lever So i-- is not an issue right? If I manage to optimize sorting part, the solution should work — not sure how but assuming ? I'm saying i-- is not a concern because, for example, If we're bringing forward 1e3 elements for each i, this operation will only be performed at most 200 times, given that n = max i.e. 2e5. For the first 200 iterations, we're bringing forward 1e3 better digits. After that, we can't repeat this process since there are no more elements left to bring forward.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yeah, you can do by

        Only open if stuck

        by doing this you dont need the i-- either

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

          Thanks a lot, Lever. I was stuck trying to identify the cause of the TLE so I could avoid it in future contests. I really appreciate your help!

          → Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

in problem B, why it says index picked must be 2 to n-1, i.e, the first two elements can't be picked. I can't understand the test cases also due to this condition.

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

    because by picking a number ith u need to perform operation on number ith-1 and number ith +1 for index=1 ith-1 is not exist and for nth, nth+1 is not exist as size of array is n ,it is one based indexing

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

      but index starts from 0, it should be 1 to n-1. Suppose for [3,2,1] array, I can only pick 1, so i can't change the first element. In test case they showed its possible to make every element equal but how?

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

        okay so in this if u perform operation on index=1 in such like decrease the oth value by 1 then u need to increase 2th index value by 1 now see ur array becomes [2,2,2], if u consider o based indexing then how u can perform operation n-1 index ? in 0 based indexing n-1 would be the last one and in 1- based indexing n would be last one , (we can't pick start and end elements )

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

          tbh, the problem statement sucks. "In one operation, you can pick an index I from 2 to n−1 inclusive", if I can't pick n-1, why its written like this? also generally arrays are 0 indexed. anyways got your point.

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

            The problem statements don't care about 0 based indexing. The indexing starts from 1 and ends in N in every problem unless specified.

            → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why this submission for problem C give wrong answer : submission

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

    You don't want to match the remainder in every case, just make sure the remainder is divisible by 9; considering we are converting some 2s and some 3s i.e (sum + delta) % 9 == 0

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

      okay mine approach also got ac ,actually In this submission i take input as a integer ,but when i take input as a string it got ac

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Shayan Bro, is there any way to do problem D with a custom comparator and exchange argument? I tried but failed.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why Submission: 295086417 or Submission: 295090777 didnt work?

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

    295086417: Checking for the presence of 0 or 1 in the number is redundant if the sum of the digits is divisible by 9.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hmm

→ Reply