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
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.
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.
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
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.
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
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.
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?
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.
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.
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()
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++.
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
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.
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
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.
@@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()
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
he's a good teacher let him conduct these videos awesome
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.
You don’t know how much helpful this has been for me ❤
Thankyou!
many many thanks . This channel is now probably the best for solution after contest.
solved A,B,C even D was easy but C took so long i had no time left.
whats your rating?
@@_cr7_216 1050
I wrote 9 if else
Nicely explained.
Thanks!
wow E was quicker to get and easier for me how you explained..thanks Viraj
the instructor was good . nice explanations
I hope this instructor is there in all contest solution vids
please mute everyone mic before it is distracting if someone speaks in between. like during explanation phase
Noted, I’ll take care for this.
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?
@@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)
@@maazhasan2874 that formula works only when m is prime
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.
oddsum/cntodd == evensum/cnteven
why to check this?
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.
43:53 The guy should be banned
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)
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.
@JaiPKapoor99 ahh nice... So that makes it almost O(n) in any case
Yes, atmost 10 iterations for a number to go left.
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
Nice solution bro.
Ye modulo aur multiplicative inverse ne toh dimag kharab kar diya
Yes, for lower constraints this works.
@@Ayush37262 The idea here was to understand newer concepts. Let's say the string was even bigger, brute would have not worked then.
@@VirajChandra Yes, After revisiting your solution I understood it and it was amazing.
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
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.
in B can't we directly check that whether sum is divisible by n or not
If you try out the sample cases, you will see this does not work.
@@VirajChandra Okay. Thanks for the response.
i had doubt in problem F, why are we considering difference array instead cant we apply segment tree on the original array itself?
Try to apply this for the first test case.
@VirajChandra ok, thanks sir
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
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.
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?
because long long can have numbers upto length 18-19, but in ques C, length of the same can go upto 1e5
A simple integer will not accommodate a number of 10^5 length order. Hence we use a string.
Is G the solution of Tourist??
General idea was taken.
43:53 i was on speaker's 🥲
Didnt understand logic of diffrence array why it cannot be done without diffrence array
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.
@@VirajChandraGot it thankyou for the explanation
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.
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()
@@bishwashkumarsah171 try passing the string by reference in solve function
Hi, can you send your submission link? Just the number of the submission. I'll make sure to help.
@@VirajChandra
id : 295241691
id: 295342641 ( with pos = i + j) too it is giving run time error for test case 16.
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++.
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
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.
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
Only solved 1😢
Same😢
could not understand problem E. just rushed it. could have shown tree diagram.
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.
@@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()
@@bishwashkumarsah171 Please provide a submission number.
@@bishwashkumarsah171 Seems stack space issue, pass your strings by reference. I have also mentioned this at timestamp 1:45:40
bhai woh C question mai red ink use kiya aapne. agli baar plz woh colour use mat karo black background ke saath
Noted. Thanks
I solved A,B,C,D remaning i got bored
Tip - Upsolving the problems will help a lot!
Viraj bhaiya aap hi kiya karo stream plz , apki explaination jada ache se samjh aati h
Live class hoti h kya apki viraj sir?
Yes, in Tle Paid Courses.
Yes, I take classes in Level 1.
@@VirajChandra Thank you sir for all your classes, I learned a lot from them :)