Codeforces Round 991 (Div 3) | Video Solutions - A to G | by Viraj Chandra | TLE Eliminators

Поделиться
HTML-код
  • Опубликовано: 14 дек 2024

Комментарии • 78

  • @TLE_Eliminators
    @TLE_Eliminators  9 дней назад +1

    TLE 12.0 - our Competitive Programming course TLE 12.0 is live!
    Enrol now at www.tle-eliminators.com/login?referralCode=F0362968
    Please fill the Feedback form for PCD: forms.gle/n8Eir1rcTPRVkPh76

  • @thirumalainambi6068
    @thirumalainambi6068 8 дней назад +16

    he's a good teacher let him conduct these videos awesome

  • @ayushwalker2003
    @ayushwalker2003 8 дней назад +7

    Solved, A, B, C and D. D was much easier than C.
    I get the intuition of C within a minute, but coding it while taking considerations of Corner cases and also thinking of a solution which doesnot give TLE takes most of my time.

  • @sajid7368
    @sajid7368 8 дней назад +2

    You don’t know how much helpful this has been for me ❤

  • @theflame3791
    @theflame3791 3 дня назад

    many many thanks . This channel is now probably the best for solution after contest.

  • @dhawalshinde124
    @dhawalshinde124 8 дней назад +9

    solved A,B,C even D was easy but C took so long i had no time left.

  • @random_color_lemon
    @random_color_lemon 7 дней назад +1

    Nicely explained.
    Thanks!

  • @aankie
    @aankie 7 дней назад +1

    wow E was quicker to get and easier for me how you explained..thanks Viraj

  • @tahmiszubair1644
    @tahmiszubair1644 8 дней назад +1

    the instructor was good . nice explanations

  • @kevinjoythomas6528
    @kevinjoythomas6528 8 дней назад +1

    I hope this instructor is there in all contest solution vids

  • @bishwashkumarsah171
    @bishwashkumarsah171 8 дней назад +9

    please mute everyone mic before it is distracting if someone speaks in between. like during explanation phase

    • @VirajChandra
      @VirajChandra 8 дней назад +2

      Noted, I’ll take care for this.

    • @maazhasan2874
      @maazhasan2874 6 дней назад +1

      I can't get that
      To calculate multiplicative inverse pow(b,m-2)mod m
      But 128 mod 9 is 2
      So how come u wrote 5?

    • @VirajChandra
      @VirajChandra 6 дней назад

      @@maazhasan2874 A small example would be to find 2*a = 1mod7.
      2^(7-2) = 32mod7 = 4
      (2*4)mod7 = 1 (making 4 the inverse of 2)

    • @ITACHIUCHIHA-dr8sz
      @ITACHIUCHIHA-dr8sz 5 дней назад

      @@maazhasan2874 that formula works only when m is prime

  • @jashanpreet.753
    @jashanpreet.753 4 дня назад +1

    I had thought the idea of the problem G but still, was unable to solve it on my own. Happens very frequently with questions involving DP on trees.

  • @Haxaze
    @Haxaze 4 дня назад +1

    oddsum/cntodd == evensum/cnteven
    why to check this?

    • @VirajChandra
      @VirajChandra 4 дня назад

      Hi, so after you have made all the values at even location as evensum/cnteven and you have made all the values at odd location as oddsum/cntodd, those two values should also be equal since the whole array has to have same elements. Hence the check.

  • @UjjwalSharma385
    @UjjwalSharma385 8 дней назад +3

    43:53 The guy should be banned

  • @SohanKumar-fp4ix
    @SohanKumar-fp4ix 8 дней назад +4

    In problem D, how are we sure about the time complexity:
    I thought we had to do in O(nlogn) but here we are doing it in o(n^2)

    • @JaiPKapoor99
      @JaiPKapoor99 8 дней назад

      Each digit will travel no more than 10 places because each digit is less than 10 and its value decreases by 1 for each place.

    • @SohanKumar-fp4ix
      @SohanKumar-fp4ix 8 дней назад +2

      @JaiPKapoor99 ahh nice... So that makes it almost O(n) in any case

    • @VirajChandra
      @VirajChandra 8 дней назад

      Yes, atmost 10 iterations for a number to go left.

  • @sujansinhthakor2314
    @sujansinhthakor2314 8 дней назад +1

    for c problem you can even with try with every possible combination of 2's and 3's.
    sorry bad naming
    for (long i = 0; i

    • @Ayush37262
      @Ayush37262 8 дней назад +1

      Nice solution bro.
      Ye modulo aur multiplicative inverse ne toh dimag kharab kar diya

    • @VirajChandra
      @VirajChandra 7 дней назад +1

      Yes, for lower constraints this works.

    • @VirajChandra
      @VirajChandra 7 дней назад

      @@Ayush37262 The idea here was to understand newer concepts. Let's say the string was even bigger, brute would have not worked then.

    • @Ayush37262
      @Ayush37262 7 дней назад

      @@VirajChandra Yes, After revisiting your solution I understood it and it was amazing.

  • @AdityaGupta-kv5ip
    @AdityaGupta-kv5ip 8 дней назад +1

    can you please explain the meaning of "sum of n over all test cases does not exceed 2*10^5" . what does this mean and should i accommodate it while calculating the time complexity

    • @VirajChandra
      @VirajChandra 8 дней назад +1

      Hi, this basically means that for a single test file, all n values in it sum up to 10^5 order, hence we can consider our time complexity with respect of a test file not with respect to each testcase in a test file.

  • @PiyushSingh-vn7ql
    @PiyushSingh-vn7ql 7 дней назад +2

    in B can't we directly check that whether sum is divisible by n or not

    • @VirajChandra
      @VirajChandra 7 дней назад

      If you try out the sample cases, you will see this does not work.

    • @PiyushSingh-vn7ql
      @PiyushSingh-vn7ql 7 дней назад

      @@VirajChandra Okay. Thanks for the response.

  • @rev10034
    @rev10034 8 дней назад +2

    i had doubt in problem F, why are we considering difference array instead cant we apply segment tree on the original array itself?

    • @VirajChandra
      @VirajChandra 8 дней назад

      Try to apply this for the first test case.

    • @rev10034
      @rev10034 8 дней назад

      @VirajChandra ok, thanks sir

    • @HridoyNandi-cn3qk
      @HridoyNandi-cn3qk 8 дней назад

      a congruence b mod m is satisfied when (a-b)%m = 0 so we make the difference array and query the gcd in the l to r-1(r-1 because the difference array has 1less size) and we take gcd as gcd is the biggest number that divides some set of numbers

    • @VirajChandra
      @VirajChandra 7 дней назад

      Hi, as I mentioned in the video also.
      If you have two numbers, a and b.
      You wish to find a%m = b%m, which means by modulo rules, |a-b|%m = 0. This means m has to be a divisor of the difference of a and b. Now, we can extend this equation to all adjacent pairs, finally deriving that m has to be a divisor of all adjacent differences. Since m has to be largest as per our condition, that is a true defination of GCD.
      So, taking difference array, and finding GCD on the segment of that array works the solutions. Let me know if you have any doubts.

  • @priyanshusingh3208
    @priyanshusingh3208 8 дней назад +1

    I have a general doubt , In problem C why take the number in string format when its easily can be stored in int or long long ? why taking it in a string affect the solution?

    • @Abhishek-e6d2c
      @Abhishek-e6d2c 8 дней назад

      because long long can have numbers upto length 18-19, but in ques C, length of the same can go upto 1e5

    • @VirajChandra
      @VirajChandra 8 дней назад

      A simple integer will not accommodate a number of 10^5 length order. Hence we use a string.

  • @nookalareshwanth1785
    @nookalareshwanth1785 8 дней назад +1

    Is G the solution of Tourist??

  • @furyfist_
    @furyfist_ 8 дней назад +2

    43:53 i was on speaker's 🥲

  • @amansinghrawat604
    @amansinghrawat604 8 дней назад +1

    Didnt understand logic of diffrence array why it cannot be done without diffrence array

    • @VirajChandra
      @VirajChandra 7 дней назад +1

      Hi, as I mentioned in the video also.
      If you have two numbers, a and b.
      You wish to find a%m = b%m, which means by modulo rules, |a-b|%m = 0. This means m has to be a divisor of the difference of a and b. Now, we can extend this equation to all adjacent pairs, finally deriving that m has to be a divisor of all adjacent differences. Since m has to be largest as per our condition, that is a true defination of GCD.
      So, taking difference array, and finding GCD on the segment of that array works the solutions. Let me know if you have any doubts.

    • @amansinghrawat604
      @amansinghrawat604 7 дней назад +1

      ​@@VirajChandraGot it thankyou for the explanation

  • @bishwashkumarsah171
    @bishwashkumarsah171 8 дней назад +1

    Nice PCD. I solved only A but after this PCD i did till D and almost E but i keep getting run time error in python at test case 16 for my recursive solution. please someone help what is wrong in my code.

    • @bishwashkumarsah171
      @bishwashkumarsah171 8 дней назад +1

      import sys
      from os import path
      import math
      from collections import *
      def input():
      return sys.stdin.readline().strip()
      def solve(a, b,c):
      cache = {}
      def recu(i,j,k):
      if i >= len(a) and j >= len(b):
      return 0

      if (i,j,k) in cache:
      return cache[(i,j,k)]

      res = float("inf")
      if i < len(a):
      if c[k] != a[i]:
      res = min(res,1+recu(i+1,j,k+1))
      else:
      res = min(res,recu(i+1,j,k+1))
      if j < len(b):
      if c[k] != b[j]:
      res = min(res,1 + recu(i,j+1,k+1))
      else:
      res = min(res,recu(i,j+1,k+1))
      cache[(i,j,k)] = res
      return cache[(i,j,k)]
      return recu(0,0,0)


      def main():
      t = int(input())
      for _ in range(t):
      a = input()
      b = input()
      c = input()
      print(solve(a, b, c))
      if _name_ == "__main__":
      if path.exists("input.txt"):
      sys.stdin = open("input.txt", "r")
      sys.stdout = open("output.txt", "w")
      main()

    • @kripanshu877
      @kripanshu877 8 дней назад +1

      @@bishwashkumarsah171 try passing the string by reference in solve function

    • @VirajChandra
      @VirajChandra 7 дней назад +2

      Hi, can you send your submission link? Just the number of the submission. I'll make sure to help.

    • @bishwashkumarsah171
      @bishwashkumarsah171 7 дней назад

      @@VirajChandra
      id : 295241691
      id: 295342641 ( with pos = i + j) too it is giving run time error for test case 16.

    • @VirajChandra
      @VirajChandra 7 дней назад +1

      import sys
      from os import path
      def input():
      return sys.stdin.readline().strip()
      def solve(a, b, c):
      n, m, l = len(a), len(b), len(c)
      # If lengths don't match, return -1
      if n + m != l:
      return -1
      # Initialize the DP table
      dp = [[float("inf")] * (m + 1) for _ in range(n + 1)]
      dp[n][m] = 0 # Base case: Both a and b are fully processed
      # Fill the table from bottom-right to top-left
      for i in range(n, -1, -1):
      for j in range(m, -1, -1):
      k = i + j
      if k < l:
      # If we can take a character from `a`
      if i < n:
      cost = 1 if a[i] != c[k] else 0
      dp[i][j] = min(dp[i][j], cost + dp[i + 1][j])
      # If we can take a character from `b`
      if j < m:
      cost = 1 if b[j] != c[k] else 0
      dp[i][j] = min(dp[i][j], cost + dp[i][j + 1])
      return dp[0][0]
      def main():
      t = int(input())
      for _ in range(t):
      a = input()
      b = input()
      c = input()
      print(solve(a, b, c))
      if __name__ == "__main__":
      if path.exists("input.txt"):
      sys.stdin = open("input.txt", "r")
      sys.stdout = open("output.txt", "w")
      main()
      Tabulation works, recursion fails. It is a common issue with python on cf. One of the many reasons why we prefer C++.

  • @HarshitKumar-dj4ev
    @HarshitKumar-dj4ev 8 дней назад +1

    To be Frank u r not convincing enough. It feels rushed. Like in f and g. F why to take difference or how that makes the problem simpler. No talk about it

    • @VirajChandra
      @VirajChandra 7 дней назад +1

      Hi, as I mentioned in the video also.
      If you have two numbers, a and b.
      You wish to find a%m = b%m, which means by modulo rules, |a-b|%m = 0. This means m has to be a divisor of the difference of a and b. Now, we can extend this equation to all adjacent pairs, finally deriving that m has to be a divisor of all adjacent differences. Since m has to be largest as per our condition, that is a true defination of GCD.
      So, taking difference array, and finding GCD on the segment of that array works the solutions. Let me know if you have any doubts.

  • @efddccv8229
    @efddccv8229 8 дней назад

    Ah I was so close to solving G, in the contest, I wrote the same dp transitions and all but couldn't realize that I have to add that +2 at last and thought my dp states were incorrect😞. Btw if anyone can explain why we are adding that +2, it would be helpful, as I am not able to visualize why we should add it again

  • @kaushikkundu
    @kaushikkundu 8 дней назад +1

    Only solved 1😢

  • @bishwashkumarsah171
    @bishwashkumarsah171 8 дней назад +1

    could not understand problem E. just rushed it. could have shown tree diagram.

    • @VirajChandra
      @VirajChandra 8 дней назад +1

      Hi, this is a standard LCS type problem of DP. Recursive tree was not required to pick up the states. The transition is simply taking pointers and trying to cover all the letter from A and B, while also covering in C, taking one cost if letters don’t match. Let me know if you have doubts.

    • @bishwashkumarsah171
      @bishwashkumarsah171 8 дней назад +1

      @@VirajChandra i did the recusive approach but it gives me runtime error every time. (in python/pypy). Is my recursive approach valid? Even with memo it give run time error on test case 16.
      import sys
      from os import path
      import math
      from collections import *
      def input():
      return sys.stdin.readline().strip()
      def solve(a, b,c):
      cache = {}
      def recu(i,j,k):
      if i >= len(a) and j >= len(b):
      return 0

      if (i,j,k) in cache:
      return cache[(i,j,k)]

      res = float("inf")
      if i < len(a):
      if c[k] != a[i]:
      res = min(res,1+recu(i+1,j,k+1))
      else:
      res = min(res,recu(i+1,j,k+1))
      if j < len(b):
      if c[k] != b[j]:
      res = min(res,1 + recu(i,j+1,k+1))
      else:
      res = min(res,recu(i,j+1,k+1))
      cache[(i,j,k)] = res
      return cache[(i,j,k)]
      return recu(0,0,0)


      def main():
      t = int(input())
      for _ in range(t):
      a = input()
      b = input()
      c = input()
      print(solve(a, b, c))
      if __name__ == "__main__":
      if path.exists("input.txt"):
      sys.stdin = open("input.txt", "r")
      sys.stdout = open("output.txt", "w")
      main()

    • @VirajChandra
      @VirajChandra 7 дней назад

      @@bishwashkumarsah171 Please provide a submission number.

    • @VirajChandra
      @VirajChandra 7 дней назад

      @@bishwashkumarsah171 Seems stack space issue, pass your strings by reference. I have also mentioned this at timestamp 1:45:40

  • @Saisomeone
    @Saisomeone 8 дней назад +1

    bhai woh C question mai red ink use kiya aapne. agli baar plz woh colour use mat karo black background ke saath

  • @thirumalainambi6068
    @thirumalainambi6068 8 дней назад +1

    I solved A,B,C,D remaning i got bored

    • @VirajChandra
      @VirajChandra 8 дней назад +1

      Tip - Upsolving the problems will help a lot!

  • @shreshth1961
    @shreshth1961 8 дней назад +2

    Viraj bhaiya aap hi kiya karo stream plz , apki explaination jada ache se samjh aati h

  • @shreshth1961
    @shreshth1961 8 дней назад +4

    Live class hoti h kya apki viraj sir?

    • @furyfist_
      @furyfist_ 8 дней назад +1

      Yes, in Tle Paid Courses.

    • @VirajChandra
      @VirajChandra 8 дней назад +2

      Yes, I take classes in Level 1.

    • @furyfist_
      @furyfist_ 6 дней назад +1

      @@VirajChandra Thank you sir for all your classes, I learned a lot from them :)