45:10 "Technically, there is no point in writing recursive solution If you're iterating through the array". Top-Down dp approach uses recursive solution. 😪
your explanation for 2nd ques was good but you overcomplicated the implementation, here is the much simpler and easy to understand code -> void solve() { int x; cin >> x; vector ans(32); for(int i = 31;i >= 0;i--){ ans[i] = x % 2; x = x / 2; } for(int i = 31;i >= 1;i--){ if(ans[i] == 1 && ans[i - 1] == 1){ int rp = i,lp = i - 1; while(ans[lp] != 0) lp--; ans[rp] = -1; ans[lp] = 1; for(int it = lp + 1;it < rp;it++) ans[it] = 0; } } reverse(ans.begin(),ans.end()); cout
This is a tricky question. Your solution has exponential time complexity. But the starting condition of LCM() >= max. Prevents that. If we take all prime numbers in the array. The DP would become exponentially larger in each step. 2^n (Where n is the size of the array). But, this is clearly does not happen here. Obviously because the solution is accepted :). But, the logical reason is that if try to take most number of prime numbers in an array. We can take 2x3x5x7x11x13x17x19x23. If we add just one more prime number their LCM becomes more 1e9 & that gets accomodated in the first categorry. So about this array, it would have 2^9=512 total elements in the map. But, which is not too much to cause a TLE.
But during the contest the announce a comment in the problem B as :- "For all 0≤i≤n−2, (|a[i]| + |a[i+1]|) ≤ 1", where |x| is the absolute value of x." according to this , the answers like 0 0 0 1 -1 0 1 will be wrong... isn't it? or I am missing something?
For C there are appx 4e7 prime numbers from 1 to 1e9, taking 2000 from them will lead us to iterations of 2000*2^2000 which is huge I think... Please correct me if I am wrong...
I understand C and solved it but isn't worst case TC equal to 2000*10^9 which should give tle. Why because n for loop and lcm 0-10^9. I know in first iteration only 1 lcm then strat increase but how we know around n=1000 in loop lcm different values in map not near 10^9
the maximum possible number of lcm's is the number of divisors of the net lcm, which is a number less than 1e9. Hence the maximum number of lcm's possible is sqrt(1e9). Multiplying this value with n, we get a worst case tc
@@princeaharwal3391 When LCM is greater than 1e9. It means that LCM cannot be equal to any number in the array(Which is what we want) Hence, that LCM would be the LCM of all numbers. So answer would obviously me all.(size of the array)
I have given 30 contests and still haven't even reached Pupil. In the last contest of Div 1 + 2... I wasn't able to solve a single question and got -100 :'(
Please fill the feedback form: forms.gle/7i2LXnxuGJEFHySY8
ankit is back with a astonishing teaching ability this time ...keep up man
Understand the approach but can't understand your implementation for B and C problem.Need more clarity and readability.
NICE EXPLANATION EVER VIEWED FROM THE TLE ELIMINATORS
MLE would not happen because the total number of distinct lcm possible is
This makes sense, thanks!
Okay😊
45:10 "Technically, there is no point in writing recursive solution If you're iterating through the array". Top-Down dp approach uses recursive solution. 😪
your explanation for 2nd ques was good but you overcomplicated the implementation, here is the much simpler and easy to understand code ->
void solve()
{
int x;
cin >> x;
vector ans(32);
for(int i = 31;i >= 0;i--){
ans[i] = x % 2;
x = x / 2;
}
for(int i = 31;i >= 1;i--){
if(ans[i] == 1 && ans[i - 1] == 1){
int rp = i,lp = i - 1;
while(ans[lp] != 0) lp--;
ans[rp] = -1;
ans[lp] = 1;
for(int it = lp + 1;it < rp;it++) ans[it] = 0;
}
}
reverse(ans.begin(),ans.end());
cout
nice code, we can use bitset to get bits and then a vector of int to store final answer
This is a tricky question. Your solution has exponential time complexity. But the starting condition of LCM() >= max. Prevents that.
If we take all prime numbers in the array. The DP would become exponentially larger in each step.
2^n (Where n is the size of the array).
But, this is clearly does not happen here. Obviously because the solution is accepted :).
But, the logical reason is that if try to take most number of prime numbers in an array. We can take
2x3x5x7x11x13x17x19x23. If we add just one more prime number their LCM becomes more 1e9 & that gets accomodated in the first categorry.
So about this array, it would have 2^9=512 total elements in the map. But, which is not too much to cause a TLE.
Thanks for putting up the efforts
But during the contest the announce a comment in the problem B as :-
"For all 0≤i≤n−2, (|a[i]| + |a[i+1]|) ≤ 1", where |x| is the absolute value of x."
according to this , the answers like 0 0 0 1 -1 0 1 will be wrong... isn't it? or I am missing something?
Yep, we can’t have consecutive non-zero elements.
you can remove any 1 -1 occurrence with -1 0 , your example will be equivalent to 0 0 0 -1 0 0 1
I am able to make logic but not able to implement..
For C there are appx 4e7 prime numbers from 1 to 1e9, taking 2000 from them will lead us to iterations of 2000*2^2000 which is huge I think... Please correct me if I am wrong...
Thank you so much for sharing this with us ❤
I understand C and solved it but isn't worst case TC equal to 2000*10^9 which should give tle.
Why because n for loop and lcm 0-10^9.
I know in first iteration only 1 lcm then strat increase but how we know around n=1000 in loop lcm different values in map not near 10^9
there are not that many unique lcms
@@adityamangal6994 yah I realized that but it's not that simple to say
@@adityamangal6994 Brother what if we have 2000 unique prime numbers then there will be 2^2000 possible lcms? Correct me if I am wrong ...
the maximum possible number of lcm's is the number of divisors of the net lcm, which is a number less than 1e9. Hence the maximum number of lcm's possible is sqrt(1e9). Multiplying this value with n, we get a worst case tc
@@arijoymajumdar2326 yah that's the thing,👍
@TLE_Eliminators cp sheet throws an error , on access 😢?
In C problem I didn't understand 2 things
1.Why Lcm is always
according to problem constraints, 1
@@princeaharwal3391 When LCM is greater than 1e9. It means that LCM cannot be equal to any number in the array(Which is what we want) Hence, that LCM would be the LCM of all numbers. So answer would obviously me all.(size of the array)
can you give me more problems like B?
thanks, easy editorial!
Within the same week, i went from 3* to 2* on codechef and pupil to newbie on cf. its almost disheartenening
Happens dude I went from specialist to pupil. But I know you'll love it when you get back in form and get back to pupil
How many problems did you solve from this div 2 contest?
@@arkachakraborty843 thanks for motivating!!😊😊
@@Entertainmentexe 2 but took me an hour to figure B
I have given 30 contests and still haven't even reached Pupil. In the last contest of Div 1 + 2... I wasn't able to solve a single question and got -100 :'(
B solution not clear
First view
Congratulations..!
congrats....a big achievement
if x
29 se 0 tak iterate kiya h toh 30 bit hii toh hue total