Shayan's blog

Codeforces Round 957 (Div. 3) — Video Editorial
By Shayan, history, 5 months ago, In English

1992A — Only Pluses

1992B — Angry Monk

1992C — Gorilla and Permutation

1992D — Test of Love

1992E — Novice's Mistake

1992F — Valuable Cards

1992G — Ultra-Meow

  • Vote: I like it
  • +36
  • Vote: I do not like it

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

E was quite good tbh.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me the solution of problem E in detail ...i am too dumb to understand this

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

    I struggled quite a lot with problem E. Hope this explanation helps you.

    Let’s first look at the constraints of the problem, here the value of (n = 100) and the value of (a <= 10^4) and (1 <= b <= 10000). We have to find the value of the expression (n * a — b). So, what can be the max value of this expression? If n = 100 and a = 10^4 and assuming b = 1 (because the minimum value of b can be 1) we get that the max value of the expression becomes (n * a — b = 10^2 * 10^4 — 1) = 999999. From this deduction what can we say? There will be 6 digits maximum in the final solution we want to find. If there are more than 6 digits we can simply ignore those answers because we found out the max value to be of 6 digits. So, the problem has been reduced to a minimized version and can be solved with brute force on the value of 'a' only.

    If we run a loop for a from 1 to 10^4, and inside that loop we firstly find digits(n) * 'a', which is basically the number of digits in the number (n * a) for each value of 'a'. Now as we know this value (digits(n) * a) must not be greater than 6. Because as we discussed earlier those values will not contribute to our answer. So, we run a loop of digits(d) from 1 to 6 and can find from that b = (digits(n) * a — d). In case you didn't get this point what was the original equation supposed to be? (digits(n) * a — b = d).

    From this, you got the value of both a and b. Now you can calculate the original value of n * a — b and the value digits(n) * a — b and compare if both of them are equal. If both of them are equal then these (a, b) pairs will contribute to your answer. And as we are running a loop for the value of a only from 1 to 10^4 and n = 100(max) and for the digits 1 to 6.

    The total time complexity reduces to 100 * 10000 * 7 ~ 10^7(roughly). Which is fast enough to pass the test cases.

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

      thanks... understood it very well

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

      amazing explanation I was not able to understand the editorial but your explanation was to the point and simple to understand.

      → Reply
»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Your explanations are very beginner friendly ,keep going brother <3

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Shayan sir, a small suggestion from my side, if you are doing official video editorial then why don't you just give testing to the round and prepare your videos in advance?? (I know there will be no live discussion happens if this works, but I think you will get more time analyse the harder problems and come up with a good problem discussion) just a personal opinion.

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

    You are right. I will test this idea.

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for explaining question F very well

→ Reply