can someone tell me the secret of how to be able to come with an equation like the one in problem C it's not intuitive at all so how do you think about it I mean the equation of (r1+r2+x-y)/2 how to be able to think about it ???
@fahimahmednafis I also made the same mistake, couldn't solve B during contest🥲.After watching this approach,I realized that string a had to be a substring, so taking a+b-lcs(a,b) won't work because it would lead to characters getting inserted in between the substring a,which is not allowed,it has to be a substring not a subsequence.
It can occur in 3 types: 1. Both 0s: causes no change in answer 2. Both 1s: we can count type of these and at last keep on adding 1 value to either score1 or score2 whichever is lower. We can do so because at max it can be up to 1e5 only. 3. Both -1s: we can count type of these and at last keep decrementing one from either score1 or score2 whichever is lower. Hope this helps
@@manmeet704do we count the 1s or -1s seperately for score 1 and score 2 or together?? Also in case 3 shudnt we decrement from the greater one of score 1 and score 2 as we need to maximize the minimum score... Plzzz clarify
@@subhayandan2839 For case 3 , you are correct. Yes, we count both 1s and both -1s separately and store it in some variable. After calculating answer from other types of values, we do computation on these
could someone tell me why this code is incorrect for question 2nd #include #include #include using namespace std; int longestCommonSubsequence(const string& a, const string& b) { int n = a.length(); int m = b.length(); vector dp(n + 1, vector(m + 1, 0)); for (int i = 1; i t; while(t--){ string a, b; cin >> a >> b;
int result = longestCommonSubsequence(a, b); int k = result;
You have to include A as substring and then find LCS Example a = "abcd" and b = "fbed" Using your method, You will get LCS as "bd" But then you will have to insert 'e' between b and d in string a then you won't get substring as "abcd" It will be "abced" or "abecd" which is wrong
For problem D I think this solution might fail for the larger constraints suppose constrainsts are a=1e6 b=1e4 c=1e7 as per your code c=1e6+1e7%1e4; Therefore, leaving us c=1e6+1e3=1e9 we have calculated dp till 1e6 hence this might fail, please correct me if i am wrong
No, It doesn't work that way, you are just considering count of characters and not the order of characters .example a - abc and b - bac your answer is 0 but actual answer is 1.
Most handsome competitive programmer.
Quite good explanation of D than others ! Thanks !
D got WA on 21!
can someone tell me the secret of how to be able to come with an equation like the one in problem C it's not intuitive at all so how do you think about it I mean the equation of (r1+r2+x-y)/2 how to be able to think about it ???
Really helpfull bro,
Thanks for the video.
Thanks for this stream
Great explanation for C. Thanks !!!
Glad it was helpful!
Thanks
your explanation is amazing...
Why are we not using binary search to find ptr? Won't this TLE?
i think the question d is giving wrong ans on - test case 21
Yes even his solution got hacked, the one given in the description
For problem B, why
string1.size() + string2.size() - LCS(s1,s2) not working?
Dry run for case: x: aaa & y: aaba. According to LCS: 4 but correct answer is 5 i.e. aaaba
@fahimahmednafis I also made the same mistake, couldn't solve B during contest🥲.After watching this approach,I realized that string a had to be a substring, so taking a+b-lcs(a,b) won't work because it would lead to characters getting inserted in between the substring a,which is not allowed,it has to be a substring not a subsequence.
.In question c why can't we simply decrease the rating of maximum one when both ai and bi are -1.
yes! but u should do it after processing all other cases first else it can lead to WA
can someone explain the 'Two Movies' problem, the case where a[i] == b[i], from 36:10
It can occur in 3 types:
1. Both 0s: causes no change in answer
2. Both 1s: we can count type of these and at last keep on adding 1 value to either score1 or score2 whichever is lower. We can do so because at max it can be up to 1e5 only.
3. Both -1s: we can count type of these and at last keep decrementing one from either score1 or score2 whichever is lower.
Hope this helps
@@manmeet704do we count the 1s or -1s seperately for score 1 and score 2 or together?? Also in case 3 shudnt we decrement from the greater one of score 1 and score 2 as we need to maximize the minimum score... Plzzz clarify
@@subhayandan2839 For case 3 , you are correct.
Yes, we count both 1s and both -1s separately and store it in some variable. After calculating answer from other types of values, we do computation on these
any reason for N = 2*1e6+20?
N=1e6 giving runtime error
Use 1e6+1 it won't give error
could someone tell me why this code is incorrect for question 2nd
#include
#include
#include
using namespace std;
int longestCommonSubsequence(const string& a, const string& b) {
int n = a.length();
int m = b.length();
vector dp(n + 1, vector(m + 1, 0));
for (int i = 1; i t;
while(t--){
string a, b;
cin >> a >> b;
int result = longestCommonSubsequence(a, b);
int k = result;
cout
You are finding longest common subsequence of two strings
You will need to take longest substring of second string which is subsequence of first string
You have to include A as substring and then find LCS
Example a = "abcd" and b = "fbed"
Using your method,
You will get LCS as "bd"
But then you will have to insert 'e' between b and d in string a then you won't get substring as "abcd"
It will be "abced" or "abecd" which is wrong
Thanks @@aryanruia3491
expected rating of d and e?
i'd say 1800 for d
@@70da24 1900, 2300 for D, E respectively
For problem D
I think this solution might fail for the larger constraints
suppose constrainsts are
a=1e6
b=1e4
c=1e7
as per your code
c=1e6+1e7%1e4;
Therefore, leaving us c=1e6+1e3=1e9
we have calculated dp till 1e6
hence this might fail,
please correct me if i am wrong
What is the value of 1e7 % 1e4?
I haven't read the problem but 1e6 + 1e3 is not 1e9..
1e6 * 1e3 is 1e9.
1e6+1e3 is 1e6+1000 ~1e6
too much poor explaination
Why does this code not work for 2nd question. Please help
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//#ifndef ONLINE_JUDGE
//freopen("input.txt","r", stdin);
//freopen("output.txt", "w", stdout);
//#endif
int t;cin >> t;
while(t--){
string a,b;cin >> a >> b;
map mpp;
for(auto i:b){
mpp[i]++;
}
for(auto i:a){
if(mpp[i] >0)mpp[i]--;
}
int sum= 0;
// for(auto i:mpp){
// cout
No, It doesn't work that way, you are just considering count of characters and not the order of characters .example a - abc and b - bac your answer is 0 but actual answer is 1.
Thanks