Codeforces Round

[@AndreOliveira7051]

I think for C you can simply output the longest contiguous sequence of 'L' plus one.

[@samarpanharit4268]

yes

[@tmwilliamlin168]

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

[@AndreOliveira7051]

@@tmwilliamlin168 Gotcha!

[@brayaon]

why that solution works? I mean which approach did you use?

[@samarpanharit4268]

@@tmwilliamlin168 happens with me too

[@mohammedshoaib1635]

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!

[@thallium54]

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_]

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.

[@PsychicRogueGaming]

Thanks william lin,youre awesome.keep posting these div 3 ones whenever you can.im very much interested!subbed and liked.

[@stevenfei3629]

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.

[@stevenfei3629]

But I have to admit that I never heard of pb_ds before. It's a very powerful tool. Thank you, William.

[@chaitanyab928]

Appreciate your Effort Man Thanks Very much!

[@divyanshagarwal849]

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!!

[@tmwilliamlin168]

I use google to find multiple sources for them.

[@divyanshagarwal849]

@@tmwilliamlin168 Ok but should I start them with solving problems or reading theory

[@tmwilliamlin168]

@@divyanshagarwal849 solving

[@divyanshagarwal849]

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!!

[@wiktorsiatkowski983]

It would be nice to see some div1 A/B/C/D explanations on your channel

[@dhvanilvadher1356]

Thanks, William Lin.

[@kaziabrarfaiyaz9428]

Thanks a lot LIN this was very helpful for us

[@raamxD]

Thanks for the cast!! I found D easier than C tbh.

[@sarthakjain4571]

Thanks for your explanation

[@ManojKumar-hj7fh]

This is really helpful, kindly keep making more explanation videos;

[@xiquandong1183]

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.

[@PasselivreEdicoes]

Hey thanks a lot for these screencasts they are super helpful.

[@sajidaansari2611]

In problem E Why did you take maximum from from all states of dp[n][i] Instead of taking maximun form interval ( l , r )

[@tmwilliamlin168]

The maximum is not guaranteed to be from the interval [l, r].

[@vaibhavrastogi7068]

@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??

[@tmwilliamlin168]

Because he has to start at hour 0.

[@arjuntomar215]

loved it solved 5 problems in contest

[@saikat93ify]

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.

[@gamingbutnotreally6077]

saikat93ify It clearly defines what a sub tree is in the problem

[@milindbishnoi9726]

Thanks ! This really helps !

[@shmaestro]

Brilliant! I know it was trivial for you but how would we know if E is to be done via dp?

[@gamingbutnotreally6077]

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

[@tmwilliamlin168]

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.

[@charan775]

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?

[@tmwilliamlin168]

Hackerrank algorithms section was useful for me to learn basic algorithms

[@naveenrawat6278]

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?

[@naveenrawat6278]

I see that yours is much better in time complexity.

[@thallium54]

What if there's no L? Your idea is correct, maybe just some issue on implementation.

[@sankalanchanda669]

codeforces.com/contest/1324/submission/73097839 Here's the implementation of the same, but the complexity is much higher.

[@sankalanchanda669]

@@thallium54 the ans would be 1.

[@AndreOliveira7051]

Why are you guys saying the complexity is higher? Longest contiguous substring is O(n), his solution is O(n*log(d))

[@shubhamkaushik4470]

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.

[@gamingbutnotreally6077]

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

[@tmwilliamlin168]

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.

[@nsarda]

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 .

[@tmwilliamlin168]

0x3f

[@nsarda]

@@tmwilliamlin168 Is there any logic to find it (seems hexdecimal)?

[@tmwilliamlin168]

It's just a big/small hexadecimal value.

[@nsarda]

@@tmwilliamlin168 Its value=INT_MIN or INT_MAX right?

[@tmwilliamlin168]

@@nsarda no, it's like 1/2, so when I add 2 together, I don't overflow

[@anshitmishra]

How do I view PPT files on the website using the Django framework?

[@piyushnaithani7689]

@williamlin i tried to solve problem D using set/multiset but it gave TLE, but when i use pb_ds it got AC why?

[@tmwilliamlin168]

I don't know how you could replace pb_ds with set. Could you provide a link to your submission?

[@piyushnaithani7689]

@@tmwilliamlin168 codeforces.com/contest/1324/submission/73072757 this was using multset

[@rishushukla3286]

Why do we initialize only dp[0][0] as zero and not all of dp[0][i] for i 0 to h

[@tmwilliamlin168]

Since we have to start at hour 0, not any hour.

[@anktrj]

Hey, Is the tree rooted at 1 or something in Problem F

[@tmwilliamlin168]

The tree is not rooted in the problem, but in order to solve the problem, my solution roots it at 1.

[@anktrj]

@@tmwilliamlin168 Actually I was thinking to solve it first on my own then watch the video. Thanks

[@Hound77]

why you took size 4*n+4 in memset ??

[@tmwilliamlin168]

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.

[@Hound77]

@@tmwilliamlin168 thanks

[@sherlock2853]

Me having same question and still not getting it can someone elaborate it please

[@santi-sd9hy]

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??

[@tmwilliamlin168]

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.

[@khanshammo5139]

Where can I learn "DP on tree" ??

[@tmwilliamlin168]

There are many sources on google, I forgot the ones I used, though.

[@qleo2563]

can you give me your code of F problem? I want to study it

[@tmwilliamlin168]

You can go to my codeforces profile to see my submissions.

[@qleo2563]

@@tmwilliamlin168 ok, thank you so much

[@qleo2563]

rank1 OMG！！！

[@shameekagarwal4872]

Arrays.sort(a); long ans = 0; for(int i=0; i

[@tmwilliamlin168]

Arrays.sort is O(n^2) worst case (for very bad inputs), maybe someone tried to hack it.

[@shameekagarwal4872]

​ @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...

[@tmwilliamlin168]

@@shameekagarwal4872 only primitives will use quick sort, so you can use Integer[] or List. Or you could random shuffle the array before sorting it.

[@shameekagarwal4872]

@@tmwilliamlin168 Integer worked...thanks a lot!!!

[@kumarmangalam1272]

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

[@tmwilliamlin168]

Could you give me a submission link?

[@kumarmangalam1272]

@@tmwilliamlin168 codeforces.com/contest/1324/submission/73029066

[@pavanchaithanya9633]

@@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

[@kumarmangalam1272]

@@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.

[@pavanchaithanya9633]

@@kumarmangalam1272 Keep the cin>>temp right after cin>>n and it will work.

[@anirudhsingh1337]

1st