I think for C you can simply output the longest contiguous sequence of 'L' plus one.
@samarpanharit42684 жыл бұрын
yes
@tmwilliamlin1684 жыл бұрын
For contests like these, speed matters a lot, so I implement the first thing which comes to my mind. This causes me to miss simple solutions like these :P
@AndreOliveira70514 жыл бұрын
@@tmwilliamlin168 Gotcha!
@brayaon4 жыл бұрын
why that solution works? I mean which approach did you use?
@samarpanharit42684 жыл бұрын
@@tmwilliamlin168 happens with me too
@mohammedshoaib16354 жыл бұрын
Thank you for posting these! There aren't people who post the contest solutions and this is very helpful in understanding how to solve the problems. So please do keep posting the solutions if you can :) Congrats on ranking 1st!
@thallium544 жыл бұрын
In problem D, you can simply sort the a-b array and do binary search. since every pair is counted twice so just output half of the answer.
@myIndianPride_4 жыл бұрын
In problem D If u use the orderedset from gfg which is essentially same as what u have used here U don't need to create pair as its a multiset.
@PsychicRogueGaming4 жыл бұрын
Thanks william lin,youre awesome.keep posting these div 3 ones whenever you can.im very much interested!subbed and liked.
@stevenfei36294 жыл бұрын
There is an another solution for D. Let's make c[i] = a[i] - b[i]. To meet the constaints, we need to make (i) i < j (ii) c[i] < - c[j] ==> c[i] + c[j] < 0. However, the first constraint is unnecessary, the index i and j is commutable. So we just need to sort the array c and use two ptr to find the ans.
@stevenfei36294 жыл бұрын
But I have to admit that I never heard of pb_ds before. It's a very powerful tool. Thank you, William.
@chaitanyab9284 жыл бұрын
Appreciate your Effort Man Thanks Very much!
@divyanshagarwal8494 жыл бұрын
Hey William Can you plz guide me where to study heavy topics like dynamic programming, divide and conquer, graphs,etc. I am just not able to start them. Thanks in advance!!
@tmwilliamlin1684 жыл бұрын
I use google to find multiple sources for them.
@divyanshagarwal8494 жыл бұрын
@@tmwilliamlin168 Ok but should I start them with solving problems or reading theory
@tmwilliamlin1684 жыл бұрын
@@divyanshagarwal849 solving
@divyanshagarwal8494 жыл бұрын
William Lin, You are doing very good work Hats off to you man😍. After every contest of codechef codeforces atcoder, your videos clear our doubts. Thanks a lot man!!
@wiktorsiatkowski9834 жыл бұрын
It would be nice to see some div1 A/B/C/D explanations on your channel
@dhvanilvadher13564 жыл бұрын
Thanks, William Lin.
@kaziabrarfaiyaz94284 жыл бұрын
Thanks a lot LIN this was very helpful for us
@raamxD4 жыл бұрын
Thanks for the cast!! I found D easier than C tbh.
@sarthakjain45714 жыл бұрын
Thanks for your explanation
@ManojKumar-hj7fh4 жыл бұрын
This is really helpful, kindly keep making more explanation videos;
@xiquandong11834 жыл бұрын
Thanks for the explanation. I solved problem E the same way in O(n*h) during the contest . However, in submissions page I saw some O(n*n) dp solutions too which I am not able to understand. Can you just explain the state transitions in O(n*n) dp if possible ? Edit: Nvm, I got it.
@PasselivreEdicoes4 жыл бұрын
Hey thanks a lot for these screencasts they are super helpful.
@sajidaansari26114 жыл бұрын
In problem E Why did you take maximum from from all states of dp[n][i] Instead of taking maximun form interval ( l , r )
@tmwilliamlin1684 жыл бұрын
The maximum is not guaranteed to be from the interval [l, r].
@vaibhavrastogi70684 жыл бұрын
@William In E you probably used a very small value due to memory constraints and then you initialised dp[0][0] with 0. My question is that why doesn't my code work when I initialise all dp[0][i] with 0. Any idea??
@tmwilliamlin1684 жыл бұрын
Because he has to start at hour 0.
@arjuntomar2154 жыл бұрын
loved it solved 5 problems in contest
@saikat93ify4 жыл бұрын
My main concern for F was that it didn't have a root and I did not understand what a 'subtree' meant and where to anchor it.
@gamingbutnotreally60774 жыл бұрын
saikat93ify It clearly defines what a sub tree is in the problem
@milindbishnoi97264 жыл бұрын
Thanks ! This really helps !
@shmaestro4 жыл бұрын
Brilliant! I know it was trivial for you but how would we know if E is to be done via dp?
@gamingbutnotreally60774 жыл бұрын
shmaestro It is a pretty motivated dp in that there is an aspect at every time he sleeps, he has two choices of sleeping ai or ai - 1, so just try both choices
@tmwilliamlin1684 жыл бұрын
A lot of it comes from practice. I recognized that only the hour that he wakes up matters in deciding whether or not he will have a good sleeping time, so that was part of my DP state.
@charan7754 жыл бұрын
I have been practicing from long time but I am still not improving. Can you please suggest what did you do in your initial stages?
@tmwilliamlin1684 жыл бұрын
Hackerrank algorithms section was useful for me to learn basic algorithms
@naveenrawat62784 жыл бұрын
Hello, William. For C, I just counted the longest contiguous sequence of L and returned count+1 as the answer. Do you think of any case where my approach fails?
@naveenrawat62784 жыл бұрын
I see that yours is much better in time complexity.
@thallium544 жыл бұрын
What if there's no L? Your idea is correct, maybe just some issue on implementation.
@sankalanchanda6694 жыл бұрын
codeforces.com/contest/1324/submission/73097839 Here's the implementation of the same, but the complexity is much higher.
@sankalanchanda6694 жыл бұрын
@@thallium54 the ans would be 1.
@AndreOliveira70514 жыл бұрын
Why are you guys saying the complexity is higher? Longest contiguous substring is O(n), his solution is O(n*log(d))
@shubhamkaushik44704 жыл бұрын
Thanks for the wonderful explanation but in question E why we iterate on hours as it is given that he will sleep exactly ai hours after he woke up. I didn't get this thing. Pls, help.
@gamingbutnotreally60774 жыл бұрын
Yes but notice that you will be changing the time he wakes up based on the dp, as per the problem statement he can choose to either sleep ai or ai - 1 hours
@tmwilliamlin1684 жыл бұрын
The statement is confusing, as he can sleep either ai or ai-1 hours. So, we need to iterate over the hour that he wakes up as it can be different depending on the choices he made for the first i sleeps.
@nsarda4 жыл бұрын
Can you please explain or provide any resource (I searched but only got to know that only "0" and "-1" is possible for integers) to understand "0xc0" in this statement- memset(n,0xc0,sizeof(n)) ?If this is for negative infinity (as you said just as INT_MIN I guess),what is the corresponding for positive infinity? Thanks in advance .
@tmwilliamlin1684 жыл бұрын
0x3f
@nsarda4 жыл бұрын
@@tmwilliamlin168 Is there any logic to find it (seems hexdecimal)?
@tmwilliamlin1684 жыл бұрын
It's just a big/small hexadecimal value.
@nsarda4 жыл бұрын
@@tmwilliamlin168 Its value=INT_MIN or INT_MAX right?
@tmwilliamlin1684 жыл бұрын
@@nsarda no, it's like 1/2, so when I add 2 together, I don't overflow
@anshitmishra4 жыл бұрын
How do I view PPT files on the website using the Django framework?
@piyushnaithani76894 жыл бұрын
@williamlin i tried to solve problem D using set/multiset but it gave TLE, but when i use pb_ds it got AC why?
@tmwilliamlin1684 жыл бұрын
I don't know how you could replace pb_ds with set. Could you provide a link to your submission?
@piyushnaithani76894 жыл бұрын
@@tmwilliamlin168 codeforces.com/contest/1324/submission/73072757 this was using multset
@rishushukla32864 жыл бұрын
Why do we initialize only dp[0][0] as zero and not all of dp[0][i] for i 0 to h
@tmwilliamlin1684 жыл бұрын
Since we have to start at hour 0, not any hour.
@anktrj4 жыл бұрын
Hey, Is the tree rooted at 1 or something in Problem F
@tmwilliamlin1684 жыл бұрын
The tree is not rooted in the problem, but in order to solve the problem, my solution roots it at 1.
@anktrj4 жыл бұрын
@@tmwilliamlin168 Actually I was thinking to solve it first on my own then watch the video. Thanks
@Hound774 жыл бұрын
why you took size 4*n+4 in memset ??
@tmwilliamlin1684 жыл бұрын
The elements are numbered from 1 to n, and I didn't subtract all elements by 1, so occ[] needs to be an array of size n+1. So I reset 4*(n+1) bytes.
@Hound774 жыл бұрын
@@tmwilliamlin168 thanks
@sherlock28534 жыл бұрын
Me having same question and still not getting it can someone elaborate it please
@santi-sd9hy4 жыл бұрын
Can anyone help me understand why is the size of array in memset in problem B equal to 4times n plus 4 but not just 4 times n??
@tmwilliamlin1684 жыл бұрын
The elements are numbered from 1 to n, and I didn't subtract all elements by 1, so occ[] needs to be an array of size n+1. So I reset 4*(n+1) bytes.
@khanshammo51394 жыл бұрын
Where can I learn "DP on tree" ??
@tmwilliamlin1684 жыл бұрын
There are many sources on google, I forgot the ones I used, though.
@qleo25634 жыл бұрын
can you give me your code of F problem? I want to study it
@tmwilliamlin1684 жыл бұрын
You can go to my codeforces profile to see my submissions.
@qleo25634 жыл бұрын
@@tmwilliamlin168 ok, thank you so much
@qleo25634 жыл бұрын
rank1 OMG!!!
@shameekagarwal48724 жыл бұрын
Arrays.sort(a); long ans = 0; for(int i=0; i
@tmwilliamlin1684 жыл бұрын
Arrays.sort is O(n^2) worst case (for very bad inputs), maybe someone tried to hack it.
@shameekagarwal48724 жыл бұрын
@William Lin what is a workaround for this? i read up it already uses quick sort with two pivots P.S. you are making upsolving contests for me really easy i dont know how to thank you enough...
@tmwilliamlin1684 жыл бұрын
@@shameekagarwal4872 only primitives will use quick sort, so you can use Integer[] or List. Or you could random shuffle the array before sorting it.
@shameekagarwal48724 жыл бұрын
@@tmwilliamlin168 Integer worked...thanks a lot!!!
@kumarmangalam12724 жыл бұрын
I am doing the same in question no. 1 ,but not getting the correct result . can u plzz help me with this by pointing out the mistake. #include using namespace std; #define ll long long #define l long #define pb push_back #define mp make_pair #define mt make_tuple int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--) { int n; cin>>n; if(n>1) { int z,temp,ok=0; cin>>temp; for(int i=0;i>z; if(z%2!=temp%2) { ok=1; } } if(ok==1) cout
@@kumarmangalam1272 You are not taking input for n=1 case. Try 1 1 100. Your code will print YES even before taking 100 as input
@kumarmangalam12724 жыл бұрын
@@pavanchaithanya9633 Its not like that . I am taking input of the first no. in temp and comparing the parity of temp with the rest no.s , therefore i have to take input of just n-1 elements. Infact it is working on lots of test cases. Plzz refer to the code one more time.
@pavanchaithanya96334 жыл бұрын
@@kumarmangalam1272 Keep the cin>>temp right after cin>>n and it will work.