That was the part which took me most of the time during contest. So i wrote down a few cases and realised at the end how much ever k we have left, we can just buy whatever because we can buy inifnitely right. Suppose if my made array after buying is 1234 and my n is 4 And i have suppose 3 left So i can buy a 1, a 2, and a 3 and to add 3 more subarrays. Resulting in now 1 2 3 4 1 2 3 So adding left was giving right for all tests which i had made and hence i submitted that
That was the part which took me most of the time during contest. So i wrote down a few cases and realised at the end how much ever k we have left, we can just buy whatever because we can buy inifnitely right. Suppose if my made array after buying is 1234 and my n is 4 And i have suppose 3 left So i can buy a 1, a 2, and a 3 and to add 3 more subarrays. Resulting in now 1 2 3 4 1 2 3 So adding left was giving right for all tests which i had made and hence i submitted that
7:36 A really beginner question but how did you come up with (n * max buys) - (n - 1) ? Here the L is (n * max buys) right? or is L (n * max buys) - (n - 1)?
Length of the array made is (n * max buys) The number of subarrays of length n will be this value - (n-1) since we cant make subarrays of length n from last n-1 digits. For case 123412341234 Here we cant make subarrays from last 3 digits Same for 1234512345, it would be last 4 Hence subtracted n-1
@@formidablechief27 ok understood. Also at 9:40 what did you mean by "ek aage aur ek peeche"? Can't we just do something like if (a[i] > ans) a[i] = 1; why the need for ans + 1 and a[i] = 2 if all we are doing is checking if a[i] is greater than 0? aren't we just marking these as "ok these numbers are extra so we are using 1 or any random number as a marker"?
Its like we can try to make atmost 2 extra subarrays thats why ek aage ek peeche. We need to check whether is the original count more than how much we have already used which is = ans and hence i have checked > ans and > ans + 1 so i can know whether i have one extra or two extra. So i can add them ahead and behind.
For calculating max subarrays, we need maximum frequency of all numbers for 1 to n Thats when we will be able to have more subarrays right. So we calculate maximum frequency we can get for 1 to n. Now if i say i want to check whether is it possible to make all numbers equal to some value suppose = 5, you can return true or false right ? Depending on the amount u need to purchase and value of k. So we run a binary search saying can you make all elements == mid ?? If yes try with a higher mid if not try with a lower mid. My sub link is attached in the description, in the check function im checking whether buys
@@formidablechief27 no bro i think there was a communication gap I have understood 90% of things in your code , but I cannot understand the code where you are doing "ele++" and assigning "buy[I] = 1 and buy[I] = 2". lets suppose using binary search we find the optimal value , and we can make all the elements of arr[I] >= optimal value without exceeding the K usage. now I also understood the calculations of the "cans" variable and I have also understood why we are adding "left". but I cannot understand why we are adding those "ele" and what does that buy[I] = 2 and buy[I] = 1 means. Please help me on this.
Buy = 2 means there are atleast 2 extra of that element which u can append behind and ahead the sequence to geg extra subarrays Buy = 1 means there is one extra which u can append anywhere either back or front. So we dont need to use from k to buy that, since we are already given it from a[i] as extra so we add those as well
@@formidablechief27 thank you soo much , understood after some paper pen work. the point I was missing is that "I assumed that the best way to arrange the permutation for 123....123...123" , this made me blind and I couldn't get the answer 28 in testcase 5 (I was getting 27 always). After knowing that the order of permutation can be anything so I solved it without assuming the order and now I am clear. thank you soo much
@@PrashanthKumar-qb6im Yes what you told is actually true it can be 231,312 it can be arranged in such a way so in order to maximize the number of permutations
Please talk less draw more...do not go into deeper explanation only by talking without giving any example.. You are genius though you don't know where can one lack
Accepted Source Code : codeforces.com/contest/1972/submission/258900447
why did you directly add ele and left ?
That was the part which took me most of the time during contest. So i wrote down a few cases and realised at the end how much ever k we have left, we can just buy whatever because we can buy inifnitely right.
Suppose if my made array after buying is
1234
and my n is 4
And i have suppose 3 left
So i can buy a 1, a 2, and a 3 and to add 3 more subarrays.
Resulting in now 1 2 3 4 1 2 3
So adding left was giving right for all tests which i had made and hence i submitted that
why u directly added left i dont get that
That was the part which took me most of the time during contest. So i wrote down a few cases and realised at the end how much ever k we have left, we can just buy whatever because we can buy inifnitely right.
Suppose if my made array after buying is
1234
and my n is 4
And i have suppose 3 left
So i can buy a 1, a 2, and a 3 and to add 3 more subarrays.
Resulting in now 1 2 3 4 1 2 3
So adding left was giving right for all tests which i had made and hence i submitted that
7:36 A really beginner question but how did you come up with (n * max buys) - (n - 1) ? Here the L is (n * max buys) right? or is L (n * max buys) - (n - 1)?
Length of the array made is (n * max buys)
The number of subarrays of length n will be this value - (n-1) since we cant make subarrays of length n from last n-1 digits.
For case
123412341234
Here we cant make subarrays from last 3 digits
Same for 1234512345, it would be last 4
Hence subtracted n-1
@@formidablechief27 ok understood. Also at 9:40 what did you mean by "ek aage aur ek peeche"? Can't we just do something like
if (a[i] > ans) a[i] = 1;
why the need for ans + 1 and a[i] = 2 if all we are doing is checking if a[i] is greater than 0? aren't we just marking these as "ok these numbers are extra so we are using 1 or any random number as a marker"?
Its like we can try to make atmost 2 extra subarrays thats why ek aage ek peeche.
We need to check whether is the original count more than how much we have already used which is = ans and hence i have checked > ans and > ans + 1 so i can know whether i have one extra or two extra. So i can add them ahead and behind.
@@formidablechief27 Ohkk thank you so much for the explanation! Subbed 💯💯
Appreciate the support 🙌
Thanks
couldn't understand why are you calculating buy and how , can you please explain it more clearly.
For calculating max subarrays, we need maximum frequency of all numbers for 1 to n
Thats when we will be able to have more subarrays right.
So we calculate maximum frequency we can get for 1 to n.
Now if i say i want to check whether is it possible to make all numbers equal to some value suppose = 5, you can return true or false right ? Depending on the amount u need to purchase and value of k.
So we run a binary search saying can you make all elements == mid ?? If yes try with a higher mid if not try with a lower mid.
My sub link is attached in the description, in the check function im checking whether buys
@@formidablechief27 no bro i think there was a communication gap
I have understood 90% of things in your code , but I cannot understand the code where you are doing "ele++" and assigning "buy[I] = 1 and buy[I] = 2".
lets suppose using binary search we find the optimal value , and we can make all the elements of arr[I] >= optimal value without exceeding the K usage.
now I also understood the calculations of the "cans" variable and I have also understood why we are adding "left". but I cannot understand why we are adding those "ele" and what does that buy[I] = 2 and buy[I] = 1 means. Please help me on this.
Buy = 2 means there are atleast 2 extra of that element which u can append behind and ahead the sequence to geg extra subarrays
Buy = 1 means there is one extra which u can append anywhere either back or front.
So we dont need to use from k to buy that, since we are already given it from a[i] as extra so we add those as well
@@formidablechief27 thank you soo much , understood after some paper pen work.
the point I was missing is that "I assumed that the best way to arrange the permutation for 123....123...123" , this made me blind and I couldn't get the answer 28 in testcase 5 (I was getting 27 always). After knowing that the order of permutation can be anything so I solved it without assuming the order and now I am clear.
thank you soo much
@@PrashanthKumar-qb6im Yes what you told is actually true it can be 231,312 it can be arranged in such a way so in order to maximize the number of permutations
Please talk less draw more...do not go into deeper explanation only by talking without giving any example..
You are genius though you don't know where can one lack
Okay thank u for your valuable advice😄