1691A - Beat The Odds

Video Editorial
Idea: amul_agrawal
Problem Setting: menavlikar.rutvij JadeReaper rahulgoel amul_agrawal
Editorial: menavlikar.rutvij rahulgoel
Video Editorial: rahulgoel

1691B - Shoe Shuffling

Video Editorial
Idea: amul_agrawal
Problem Setting: rahulgoel menavlikar.rutvij JadeReaper
Editorial: menavlikar.rutvij rahulgoel
Video Editorial: JadeReaper

1691C - Sum of Substrings

Video Editorial
Idea: amul_agrawal
Problem Setting: rahulgoel amul_agrawal
Editorial: amul_agrawal rahulgoel
Video Editorial: amul_agrawal

1691D - Max GEQ Sum

Video Editorial
Idea: amul_agrawal
Problem Setting: fangahawk amul_agrawal rahulgoel keyurchd_11
Editorial: fangahawk rahulgoel
Video Editorial: fangahawk

1691E - Number of Groups

Video Editorial
Idea: amul_agrawal
Problem Setting: akcube keyurchd_11 rahulgoel amul_agrawal
Editorial: akcube rahulgoel keyurchd_11
Video Editorial: akcube

darkkcyan's solution without using sets in python.

TheScrasse's solution for E using Boruvka and Mergesort tree :D

1691F - K-Set Tree

Video Editorial
Idea: ltc.groverkss
Problem Setting: ltc.groverkss amul_agrawal rahulgoel
Editorial: rahulgoel
Video Editorial: rahulgoel

• 6 months ago, # ^ | here's my python DP O(n) solution for D O(n) DP solution for D

  • 6 months ago, # ^ | An even more simple o(n) solution for D

    • 6 months ago, # ^ | Can you explain how this works? It looks much simpler than what i did. Also, how did you get this thought process.

    • 6 months ago, # ^ | hey your code is giving "yes" for the input 10 -6 1 1 -6 10 but answer for this case should be "no" week testcases !!!! Testers please look

      • 6 months ago, # ^ | ← Rev. 2 →   0 I tried something like sliding window but seems the testcases are weak hence it passed.

        • 6 months ago, # ^ | yes many other participants also did similar thing and their submission is passed in system testing.

          • 6 months ago, # ^ | I also saw some submissions with O(n*n) complexity, but still accepted very weak test cases.

    • 5 months ago, # ^ | It gives WA when using this algo

• 5 months ago, # ^ | My friends solution for D O(N), a <= the input array prefix_a <= prefix sum a[0] + ... + a[i] = prefix_a[i] a_ngt <= next greater value pre_ngt <= next greater value now for i in 0 to n-1, if pre_ngt[i] < a_ngt[i] return false; why because for subarray starting at index i and ending at pre_ngt[i], will have max value a[i] and a[i+1] + ... a[pre_ngt[i]] >0, since pre_ngt[i] is the index where prefix_a[ ngt] > prefix[i]. Then just reverse the main array A and apply the same check. You can check his implementation over 159050281.

  • 5 months ago, # ^ | Hey! Can we do this: 1. Find the next greater element's index for all the elements 2. Find the previous greater element's index for all the elements 3. Store the prefix sum for all the prefixes. 4. Traverse from index i = 0 to n, suppose that a[i] is the max. Then the subarray from index prev_greater + 1 till next_greater-1 will be the subarray in which we need to check. So, for this subarray, the subarray sum will be x = prefix[next_greater-1] — prefix[prev_greater]. So, then we can compare if a[i]>=x or not. Is this logic correct? I submitted this but giving WA on the 364th case of test case 2. Please let me know what's wrong. Thanks in advance!

• 6 months ago, # ^ | Yes, the thing you can do is pretty similar to my solution. If two segments [l1; r1], [l2; r2] do intersect, it means that either: l2 <= l1 <= r2 l2 <= r1 <= r2 l1 <= l2 <= r2 <= r1 Lets forget about the third case for a moment. We take, for example, red segments. Then we make two arrays. One of them stores right ends of red segments. Another one stores left ends. We sort the arrays. Then we iterate through blue segments [l; r] and for each we find all the right ends l <= r1 <= r and all the left ends l <= l1 <= r. It's obvious that all the l1s make a continuous segment in left ends array. The same thing works for the right ends. That means that we can find the smallest l1 (r1) and the greatest one. Then we want to unite all the segments between them and the blue segment we are looking at. Using the seg tree, we will mark whether the segment should be united with the previous one in left (right) ends order. Back for the third case, it's obvious that l1 <= l2 <= r2 <= r1 also means that l1 <= l2 <= r1. So to count all the intersections from the third case, you basically just need to use the solution above two times with different colors. P.S. The part with the seg tree can be done easily without it. Our task is to add on some segments and then find the modified array. There is a nice trick to do it. We will count difference array d[]. To increase by x on segment [l; r], we need to add x to d[l] and substract x from d[r + 1]. Then, after we applied all the operations, to get the modified array we simply need to calc prefix sums on this array. My solution:159060471

  • 6 months ago, # ^ | The same idea came to my mind during the contest, unfortunately, time wasn't on my side. Thank you so much for the explanation.

• 6 months ago, # ^ |

• 6 months ago, # ^ | ← Rev. 2 →   +13 I try to prove your solution. (edit: earlier proof was wrong) Suppose a subarray which violate the condition be and let the index of maximum element in this subarray . Also let us say wlog, that the subarray extends towards the right, ie, . Let us say that the element just smaller than be at index in this subarray. If the sum of blue subarray, ie, is positive, then, we find new subarray which violates the condition to be of the same structure as and repeat the process on this subarray Otherwise if sum of is not positive, then we safely discard this subarray, and here we end up with as violating subarray, which we check in your solution. (because if is positive and is non positive then is positive) it it correct or there is some flaw

  • 6 months ago, # ^ | The way I verified it myself before writing it was very similar; I also tried to demonstrate that you can safely chop off the sides and condense the violating subarray to one which is sandwiched between these two particular elements. I think it is sound.

  • 6 months ago, # ^ | That's wrong proof bro. You are saying if sum of blue array will be positive then you'll have a smaller subarray violating this condition. You're totally wrong here. Case: 2, -1, 1, -1, 2 [0,4] is the smallest one. [2,4] has sum > 0 but it is not the smallest.

    • 6 months ago, # ^ | blue subarray was just to the right of second smallest element, in this case it would be empty. Earlier proof was wrong but this was not the issue, please check now

• 6 months ago, # ^ | How do you find the "nearest" greater element than for each in linear time?

• 6 months ago, # ^ | 10 -4 3 -4 10 should be "NO" and your solution will give "YES" if I understand correctly

  • 6 months ago, # ^ | Edited my comment to say we search for nearest greater than or equal integer, not strictly greater. Doing that, between 10 and 10 we have-4+3-4 is not less than -10, hence allowing the 10 to connect with the other 10 positively, violating the condition and giving us a NO.

• 6 months ago, # ^ | I think, in segment tree you use some kind of binary search, and intended solution for D uses segment trees :)

• 6 months ago, # ^ | You can find closest greater on right/left using the binary search and some data structure like segment tree or sparse table.

• 6 months ago, # ^ | Can you please help me in finding where I am wrong for Problem D, I checked on cfstress but its not finding any test cases. Please help. Solution link : 159144970 Thank you in advance

  • 6 months ago, # ^ | Sure, take a look at Ticket 9649 for a simple counter example.

    • 6 months ago, # ^ | Thanks a lot

• 6 months ago, # ^ | Can you please help me find where I am wrong in problem D 159462704. Thank you

  • 6 months ago, # ^ | Sure, take a look at Ticket 10434 which contains an array of length 3 with all negative numbers. Naturally it'd satisfy the conditions, but your code prints NO.

    • 6 months ago, # ^ | Thank you very much

• 6 months ago, # ^ | Explain please

• 6 months ago, # ^ | For n == 1 you're not taking the input array (a single element) which is becoming n for next inputs which is causing RTE.

  • 6 months ago, # ^ | Thanks a lot

• 6 months ago, # ^ | Ohh i think si-1.si -->Di-1 si.si+1 -->Di [Si-1*10 + (Si ]+ [ 10*Si) + Si+1] --> Si-1*10 + Si+1 + Si(11) Total contribution is 11 Got it

• 6 months ago, # ^ | The ones that are not at the extreme positions are counted once at ones position and counted once at tens position. For example in 10101 the middle "1" is a part of two numbers s2s3 (01) and s3s4(10) so this one has an overall contribution of 11.

• 6 months ago, # ^ | Sorry but your solution is hacked.

• 6 months ago, # ^ | The tests in problem D are weak. Actually for the worst case it works in O(n^2) and it is hacked now.

• • 6 months ago, # ^ | Thanks a lot.

• 6 months ago, # ^ | Here's a testcase on which your code gets WA: Ticket 9111. Not sure if it contains the reason for RE as well, but it should be a good starting point.

• 6 months ago, # ^ | Thanks! The editorial is fixed. Please wait a little bit for it to reload.

• 5 hours ago, # ^ | well, the problem observation was a lot easier than normal C problems, so the implementation was indeed harder than normal C problems to balance it out. Honestly, I suck at implementation too

• 6 months ago, # ^ | Their links are under the title of each problem.

  • 6 months ago, # ^ | Video link is not there .. can you give here please

    • 6 months ago, # ^ | Click Video Editorial letters. Or link.

      • 6 months ago, # ^ | thanks bro

• 6 months ago, # ^ | ← Rev. 2 →   +3 for this test case your code is failing test case :

• 6 months ago, # ^ | ← Rev. 2 →   0 similar with mine. I stored maximum range sum on the left and right side of each i with monotonic stack, and check if it is larger than 0. 159026276

• 6 weeks ago, # ^ | Clever idea! For ones for whom it is a bit subtle how to check island intersections with two pointers, you can sort out all islands in one array and non-islands in the other. Then take islands and non-islands of different colors, sort islands increasing right-end and non-islands increasing left ends. Then processing current island you may take the most-right non-island starting before (or at) the current island right border. Checking that right border of is inside answers whether there is any intersection. The subtleness here is that should we have sorted islands increasing left-ends the check would not have worked. Example islands [1...5], [2...3] and non-island [4...6]. We see [1...5] intersects with [4...6], but then standing in [2...3] we've already moved our non-island pointer too far and now it starts after [2...3] end.

• 6 months ago, # ^ | Don't know about that testcase but this your solution will fail on many testcases. Example Answer should be "NO" but your code will output "YES"

  • 6 months ago, # ^ | damn, thx bro

• 6 months ago, # ^ | never use unordered map in cf contests. i've just changed unordered_map to a simple map in your code. got AC. 159119935 for more details refer : blog

• 6 months ago, # ^ | got it : ) not mistake in logic but mistake in code found

• 6 months ago, # ^ | You first solution using set is failing on the following test case: CF Stress

• 6 months ago, # ^ | Your code is failing on the following test case: Ticket 9678

• 6 months ago, # ^ | According to the constraint, s[i] <= s[i + 1].

  • 6 months ago, # ^ | Oh , sorry , sorry ! I didn't see that .

  • 6 months ago, # ^ | Oh, sorry, sorry ! I didn't see that .

    • 6 months ago, # ^ | Remove you eye patch for better clarity

      • 6 months ago, # ^ | Thanks , bro !

• 5 months ago, # ^ | ← Rev. 2 →   0 Can you check what's wrong in this solution? Link Thanks in advance!