วีดีโอ

Loved it

keep doing this. Great explanation.

Hello sir! Just want to say that the videos on your channel are the best among other creators on TH-cam! This channel is so underrated, but I hope it will gain the recognition it deserves one day. The explanations are so easy to understand and very intuitive and detailed. I have been enjoying the series until now and can't wait for the next video. Will wholeheartedly support this great channel!

I think I am unable to see solutions of other users in the standings page for the contest page attached in the comment. Since its a part of gym section, solutions become visible post solving the question. But I have solved the problem but still unable to see others' solution.

Your explanation is amazing! Please keep updating more codeforces videos!

good visuals, great English narration!! -would the run time be like 3 * 2^n cause its 3 options to start but then you cant repeat what you picked last round if we were talking about the time complexity for the real problem? at 3:36 -also first time hearing about equivalence classes, seems like its related to equivalence relations. this idea you could explain better i think. thank you.

I'm gonna go and learn Binary search first 🙂

keep going ❤❤👨‍💻👨‍💻👨‍💻👨‍💻

can you recommmend similar problems ?

What tool you use to showcase your code in a styled manner?

Thank You! And this was awesome.

Although your optimisations are interesting, I believe your solution is not optimal, mainly due to your approach to solving. But it was a very interesting problem to analyse. That said, I'm only 99% certain my analysis of the problem is correct, so if anyone can present to me a counterexample to the theory that *IF THE PROBLEM IS SOLVABLE, THEN ALL STARTING POINTS BETWEEN THE LIMITS THAT CAN REACH THE FURTHER ENDS ARE VALID STARTING POINTS*, please do and I will retract my solution. If one considers the problem working in from the edges, a simple and quick (O(N)) method using a stack can be found. The length of the array (n) is also the maximum permitted value within it. We start our index (i) from the left edge with a countdown (cd) that starts at n. At each count, if the the deadline at i is less than c, we push that c onto the stack. otherwise we progress to the next i. This progresses till the countdown reaches 0, at which point we have the index of the furthest starting point from the left edge that can still reach the left edge, and also a stack containing the move-numbers not used by getting to the left edge while leaving each step to the left to the last possible moment. We can now prove the puzzle possible by continuing from i and checking that at each step the deadline is equal or later than the next available move-number from the stack. Proving the puzzle is possible from the left also proves it from the right because it proves the true success condition: that there are no subsets of the array where the subset has a deadline earlier than the width of the subset at both its ends. This analysis can also lead to a 2-pointer solution (see below) but I don't like 2-pointer solutions since they lead to poor data-streaming, often require conditional code sections (lots of branch misspredicts), etc. To determine the range of possible starting-points we now just need to perform a simplified version of the first loop (without the stacking) to determine the leftmost starting-point that can still reach the right end. the number of possible solutions is the range including these two limits. this solution is O(N) time with a stack usage of O(N) for the proof of solvability. int solve(int *dl, int n) // note: I'm writing in pure C { if((dl[0] < len) && (dl[n-1] < len) return 0; // definitely impossible int stack[n]; // definitely enough space int i = 0, stp = 0; // index, stackpointer for(int cd = len; cd > 0; --cd) { // build stack. starting from len means that the other end will always be reached in unwinding if it is possible. stack[stp] = cd; // all unused moves when left-end deadlines are met at the last possible moment are put on the stack stp += (dl[i] < cd); // move-number pushed to stack if deadline is missed at this move-number (write always, increment conditional) i += (dl[i] >= cd); // but if deadline was met, move on to the next deadline } int rl = i; // rl remains as our right-most limit for starting points. is actually one-past, but that works out for the math. // every remaining deadline should be met by the available moves if any solution is possible while(--stp >= 0) if(dl[i++] < stack[stp]) return 0; // so a failure here means there are no possible solutions // before this loop i + stp == n, so reaching bottom of stack is equal to reaching end of array int ll = n; for(int cd = len; cd > 0; --cd) // finding leftmost starting point that can reach the right end is simpler since we don't need to complete the proof twice if(cd > dl[--ll]) cd = dl[ll]; // meaning we don't need to build a stack, so we can just drop the count when the deadline is lower return rl - ll; // rl ends one beyond the limit, ll ends at the limit, so returned number is correct. } although it will be somewhat dependent on the compilers ability to find the branchless optimisations that are possible (clang will, gcc wont), this should be able to find a range of 10000 possible solutions in the maximal array of 100000 deadlines in about 130µs. ************************************************** As mentioned, there is also a *TWO POINTER* solution, based on the same theory, which uses no auxilliary array (and each element of the given array is read only once too), athough due to the dynamics of the two-pointer code, the runtime is 80% longer than the stack version above. In order to prove the solution possible we can use the property described above that *NO SUB-RANGE CAN BE LONGER THAN THE VALUE AT BOTH ITS ENDS*. One end being less is OK, but not both. Using two pointers we can shrink a range while examining its end-values in such a way that the maximal range with the minimal end-values will always be found, by just moving inward the higher end each step (if equal I move in the left end, but that is arbitrary). While doing this we can also determine the limits of the starting range by casting shadows. If one envisions the problem space as the roof of a cave hanging low in the middle, then the limits of where we can start from will be defined by the shadows cast by a diagonal parallel light source shining from each end. The shadow is defined by the lowest hanging protrusion accross that diagonal surface, and the range we can start from is the range where we can see both lights. The "shadow" of each deadline is just it's position +- it's height, and we can use max/min to track the furthest shadow from each direction. It should be noted that it is possible to see both lights (limits overlap) yet the solution is still impossible, so both the proof and the limits must be calculated. int solve(int *dl, int len) // a 2-pointer method { int lp = 0; rp = len-1; // left pointer and right pointer start at first and last element int lsl = len, rsl = -1; // these are the "shadow limits". They define the furthest point that 45° light would reach from the lowest hanging deadline. while(lp <= rp) { // until the pointers pass each other int l = dl[lp]; // read the range end values int r = dl[rp]; int w = (rp - lp); // this "width" only includes one end, so compare to w+1 by using <= instead of < if((l <= w) & (r <= w)) return 0; // no solutions possible if both l and r are less than w+1. single & forces compiler to combine the conditions before branch int rps = rp - r; // shadow cast by the right position deadline if(rsl < rps) rsl = rps; // keep if it moves the right shadow limit further right int lps = lp + l; // shadow cast by the left position deadline if(lsl > lps) lsl = lps; // keep if it mofes the left shadow limit further left lp += (l >= r); // move inward the pointer with the greater value rp -= (l < r); // scanning like this finds the minimum deadlines with the maximum width, will find failing ranges for sure. } // reaching the end of this loop means the puzzle is solvable. The left and right shadow limits define the range of starting points that can work. return (lsl - rsl) - 1; // the shadow calculations end up one greater than we want in both directions } I'm not sure even clang can work out it needs to combine the two if() conditions in the failure test into a single branch to avoid lots of misspredicts, indeed I believe it is bound by the rules of the language not to (conditions beyond a failed && must not get processed), so I directed it to do so by combining the values of the tests with & instead of combining the logic with &&. This algorithm can complete a similar maximal 100000 entry puzzle in about 230µs.

please continue making videos like this also apart from codeforces content as always your explanation is lit! thanks

What CF rating could this problem be?

also , this is a copy of atcoder problem

great explaination

Bro pls make a video on how to get skill =10% of urs 😅

Goddddddd

Thanks a lot

Best video possible 🔥

do u mean dfs and memoization when you talk about tree dp?

Once a legend , always a legend . Keep it up bro 👍👍

Thanks bro I was struggling to understand why Jangly first used less efficient machines and only upto 100 for producing machines you cleared both the daughts

Bro you explain it very well

Bro need more videos like this 😇

Great work

Your slow speaking speed help to process the logic in one go, elsewhere i need to pause the video again and again to intuition of what does the speaker said. Thank you :)

og is back

GODLY

The video was great as usual

The GOAT has returned O7

you are missing one thing here that we need to multiply odd index by 1 so need to pick max when at odd index

Explained well. Impressive slides.

Add monotonic stacks standard problems . NeXT nearest greater ,nest nearest smaller histogram etc

Great explanation, the amount of effort you put in for the video and the website is commendable!!

Please don’t stop this CC Reflection series. Nowadays CC problems are so good <3

Answer to last question: For each edge (i, par[i]) it's contribution will be (subtree(i) * (n - subtree(i))). Do add this much for all edges to answer. Multiply weight of the edge for weighted graph.

I think some variables are not required. unlocked_sum and locked_sum are not required only one variable sum will be sufficient. Below assigned[v]+=w only do sum+=w and remove unblocked_sum and locked_sum from everywhere. At time of events your answer would be ans=sum+unlocked_count*remain Why? Because see brute force you will notice you need sum of all node's assigned[i] value and assigned [i] value is just some of w's. So, the "sum" is doing the same thing. Keep everything else same. Please correct me if i am wrong anywhere. Btw your explanations are too good keep it up.

Your explanation is so good 💛 Please upload video regularly.

Thank for your video, but modify the title and describtion, it is Educational Codeforces Round 168 (Rated for Div. 2) not 158

Do some dry run on some test cases with how data is manipulate in data structures and how algorithms flows goes on .. this will very beneficial for us .. love ur unique and very intresting containts ❤❤

Was able to solve the weighted part completey myself after fully understanding contribution technique ....great video man..please keep uploading..

I am not sure about he sliding window of size K idea should it be every window of size k must have at least one element and the last element should also be a check point because in the examples we have a example AAB and c = 2 k = 2 so A will satisfy the condition of sliding windows and give the answer as 1 but on the contrary the example gives the solution to be 2. I modified your code and added the condition for the last element to be present and the code worked but without that code it isn't working.

Bro i really liked your approach for problem solving please continue this series , very help full for competitive coders specially for higher ones .

dude this channel is a gold mine! your explanations are fantastic!

02:22, i guess at here in special dfs tree, for the current node x, if it is a leaf node, dis(x,x+ 1) would not be 1.. to find x + 1, we can keep going to the parent until we find a parent with sub_max_node[parent] > x.. great explanation man..

good slides

Really a good explanation and refreshing one in the plethora of content. Thanks for the explanation, appreciate it

Helpfull

understood 👍🏻♥️