rahulgoel's blog

By rahulgoel, history, 2 months ago, In English

1691A - Нет нечетности!

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

Hint 1
Hint 2
Solution
C++ Code

1691B - Обмен обувью

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

Hint 1
Hint 2
Solution
C++ Code

1691C - Сумма подстрок

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

Hint 1
Hint 2
Solution
C++ Code

1691D - Максимум не меньше суммы

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

Hint 1
Hint 2
Solution
C++ Code

1691E - Число групп отрезков

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

Hint 1
Hint 2
Hint 3
Solution
C++ Code

darkkcyan's solution without using sets in python.

Python code

TheScrasse's $$$nlog^3n$$$ solution for E using Boruvka and Mergesort tree :D

Code

1691F - Дерево и k-подмножества

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

Hint 1
Hint 2
Hint 3
Solution
C++ Code
 
 
 
 
  • Vote: I like it
  • +141
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a very nice contest.

PS: O(n) Solution for D

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    here's my python DP O(n) solution for D O(n) DP solution for D

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      An even more simple o(n) solution for D

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain how this works? It looks much simpler than what i did. Also, how did you get this thought process.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I tried something like sliding window but seems the testcases are weak hence it passed.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            yes many other participants also did similar thing and their submission is passed in system testing.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              I also saw some submissions with O(n*n) complexity, but still accepted very weak test cases.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It gives WA when using this algo

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

»
2 months ago, # |
  Vote: I like it -155 Vote: I do not like it

What F*ckhead created problem C ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    First of all, that language is not ok in a public forum. Secondly, accounts of setters are given with each problem.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    says the guy who only solves A and B in contests (NO OFFENCE)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    A very smart guy.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was really panicking when I saw no error in my C, but just after the contest I saw the test case finally and I mishandled the case with only single '1'. Really such problems test our patience, but you can use it to improve your temperament.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think problem E can be solved using segment tree, is that right?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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:

    1. l2 <= l1 <= r2
    2. l2 <= r1 <= r2
    3. 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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The same idea came to my mind during the contest, unfortunately, time wasn't on my side.

      Thank you so much for the explanation.

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

With video editorials and hints for each problem. You cannot argue that these are not one of the best editorials to be seen in a while on CF.

»
2 months ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

D admits an O(n) solution. It is sufficient to check that the sums of the subarrays between any positive integer and the next/previous greater (or equal) integer, are negative and greater in absolute value than the positive integer itself. If this holds for all positive integers, then we return yes.

Intuitively this makes sure that no positive integer can contribute positively to some other positive integer which is greater than it.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    word

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, i think i have done something similar. don't know whats wrong https://codeforces.com/contest/1691/submission/159059179

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    I try to prove your solution. (edit: earlier proof was wrong)

    Suppose a subarray which violate the condition be $$$a[i:k]$$$ and let the index of maximum element in this subarray $$$i$$$. Also let us say wlog, that the subarray extends towards the right, ie, $$$[a_i, a_{i+1}, ... a_{k}]$$$. Let us say that the element just smaller than $$$a_i$$$ be at index $$$j$$$ in this subarray.

    $$$[a_i, \color{red}{ a_{i+1}, a_{i+2} ... }, \color{turquoise}{ a_j,} \color{blue} {a_{j+1}, a_{j+2}...a_{k}}]$$$

    If the sum of blue subarray, ie, $$$a[j+1:k]$$$ is positive, then, we find new subarray which violates the condition to be $$$a[j:k]$$$ of the same structure as $$$a[i:k]$$$ and repeat the process on this subarray

    Otherwise if sum of $$$a[j+1: k]$$$ is not positive, then we safely discard this subarray, and here we end up with $$$a[i:j]$$$ as violating subarray, which we check in your solution. (because if $$$a[i+1:k]$$$ is positive and $$$a[j+1:k]$$$ is non positive then $$$a[i+1:j]$$$ is positive)

    it it correct or there is some flaw

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you find the "nearest" greater element than $$$a_i$$$ for each $$$i$$$ in linear time?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10 -4 3 -4 10 should be "NO" and your solution will give "YES" if I understand correctly

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can the person who added the binary search tag for D, share his approach?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think, in segment tree you use some kind of binary search, and intended solution for D uses segment trees :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can find closest greater on right/left using the binary search and some data structure like segment tree or sparse table.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was nice round! I really liked problem D, I hope to see more similar problems in future rounds :)

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The best way of editorial. Loved it!

»
2 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Editorials with hints are the best :):)

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please help me find where I am wrong in problem D 159462704. Thank you

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

here's my python DP O(n) solution for D O(n) DP solution for D

»
2 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

HI boys Can anyone explain why am I getting a Runtime Error here 159082911

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For n == 1 you're not taking the input array (a single element) which is becoming n for next inputs which is causing RTE.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem c I didn't get how all middle ones contribute to 11?? Can anyone help with this

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great contest and solutions too!!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

x

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Sorry but your solution is hacked.

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

D was doable with a classic algorithm called cses. So you maintain a segtree which returns the maximum subarray sum of the entire array. You insert the values in in increasing order of arr[i]. At every stage, if the maximum subarray sum is > the value inserted, the answer is NO, otherwise it is YES. Let's say the current value inserted is x. Since the values are inserted in increasing order, the maximum value in the entire array cannot exceed x, so the maximum subarray sum will be greater than any possible "max value of a subarray" if it is greater than x.

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone tell the time complexity of this code? That code seems to be O(n^2), but this code got accepted in problem D . Please check. Submission link: https://codeforces.com/contest/1691/submission/159084501

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The tests in problem D are weak. Actually for the worst case it works in O(n^2) and it is hacked now.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the 1213th case in the 7th test of D? I am getting WA. Here is my submission.

I will be really obliged if someone finds the error. Thanks in advance.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting a run time error on my submission can anyone chech why that is https://codeforces.com/contest/1691/submission/159039369 thanks in advance!!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for this great contest.

PS: i think that there is a typo in the last statement of the solution of problem C,i believe it's 11 not 10.

*** The remaining 1s can stay where they are as they will anyways be contributing a value of 10 no matter which position they take.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really liked the editorial with hints, and video solutions make this editorial to next level. Thanks for such a great editorial

»
2 months ago, # |
  Vote: I like it +113 Vote: I do not like it

There is another solution of F. It is simiral to editorial, but a bit shorter. We can fix a root of the sub-tree $$$v$$$, then for each edge $$$e$$$ between $$$v$$$ and $$$u$$$ let's calculate

$$$\sum\limits_{R \in subtree_u} \sum\limits_{S \subseteq V, |S| = k}f(R, S) = (cnt(v) - {size_u \choose k}) * (n - size_u) * size_u$$$

where $$$subtree_u$$$ — vertexes if the sub-tree of $$$u$$$ if $$$v$$$ is the root of the tree, and $$$w$$$ is connected to $$$v$$$. $$$size_u$$$ is a number of roots of the tree, $$$n - size_u$$$ is size of the sub-tree, $$$cnt(v) - {size_u \choose k}$$$ is a number of subsets of size $$$k$$$ such that sub-tree of $$$v$$$ is the minimum-size sub-tree covering it entirely and $$$R \in subtree_u$$$

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The remaining 1s can stay where they are as they will anyways be contributing a value of 10 no matter which position they take.

There should be 11 instead of 10 in the above sentence.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks! The editorial is fixed. Please wait a little bit for it to reload.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't Hint 2 of problem D Editorial of no use at all?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial as well as making this round, enjoyed it a lot!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was C that hard to implement ? I wonder my approach is correct or not My C submission

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where are video editorials?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The corner case of n=1 in B !! Did anyone else mess this up also xD

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Haha video Editorial!I like it!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I do not get it, is there some more hidden edgecase in C?

Why my 159111480 fails?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    for this test case your code is failing

    test case :
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem D can be solved in $$$O(n)$$$ operations, in a quite straight-forward manner with a monotonic stack, without any special consideration for positive/negative values, etc: 159111942.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
2 months ago, # |
  Vote: I like it +19 Vote: I do not like it

A solution for problem E using only vectors:

First, consider the segments that are completely inside another segment of the same color. Let's call these "islands".

If an island intersects with any segment of the other color, we can completely ignore it — because any connection chain involving the island can use the bigger segment instead. If the island does NOT intersect with any segment of the other color, then it is its own connected component — so it contributes 1 to the answer but can otherwise be ignored.

Processing the islands can be done with sorting and the two-pointer technique (or binary search).

Now, for the rest of the segments. Sort the segments of each color separately (note: since we got rid of the islands, sorting by left endpoint is the same as sorting by right). Now, go left to right, keeping track of the rightmost point reached with each color. If it's possible to intersect the next interval of either color with this point, do so. Otherwise add 1 to the result.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wrong answer in 4957th token, what's the testcase? 159113795

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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"

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Add the problem ratings please.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Someone, please tell me why I am getting TLE on B My Solution on test case 30. I think it is just O(n).

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

C and B good problems

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a really nice round. And thank you for adding hints in the editorial.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

liked the contest. no stories. clear problem statements.

»
2 months ago, # |
  Vote: I like it +26 Vote: I do not like it

For E we can also run dfs and extract edges using segtree/merge sort tree.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C :

Can Someone Explain Me why my code failed

Wrong Answer on test 3 (33 number differ) 159060194

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    got it : ) not mistake in logic but mistake in code found

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, can anyone tell me why I am getting TLE on this 159020121 when I submit using GNU G++ 17 7.3.0 but the same solution gets accepted when I submit using GNU G++ 14 6.4.0 (159121654)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem 1691E — Number of Groups, I implement using the way as editorial did

  • First using a set for ordering the points (159130522) gets WA
  • Then I tried to change it by using a vector (159131112) gets AC

Why is the set solution getting WA while the vector solution getting AC where I used the same custom comparator in both submissions?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it isn't enjoyable ..XD the wrong answer expected NO, found YES [4957th token]

can someone tell me/(give any tc) where it's failing? 159139893

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Here is my O(n log n) solution, but it's much shorter and simplier to understand than in editorial. The main idea is that we iterate through elements in increasing order, then we should look for the segment that has the maximum possible sum and contains our element as maximum. How do we do that? Let's mark elements in the array if we have already looked at them. Also let's store segments of continious marked elements. In these segments we will store sum, starting and ending point of segment, maximum prefix sum and maximum suffix sum (it can be zero). For simplicity we will store segments in array. If we have array [l, r] we will store it only in a[l] and a[r]. Imagine we have element x in position i, then we should look for the segments which are stored at a[i - 1] and a[i + 1] (if it is possible and they are marked). Then we count maximum sum, it is (i ? a[i - 1].suf : 0) + x + (i + 1 < n ? a[i + 1].pref : 0), if it's greater than x, then answer is NO. Then we update sum, pref, suf and store new segment in a[a[i - 1].start] and a[a[i + 1].end]]. Here is code 159141199.

PS: sorry for bad english)

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

sorry, could someone explain what marks in this formula "F(s)=10×s^1+11×s^2+11×s^3…11×s^n−1+1×s^n" from the explanation under task C values s^1 or s^ 2

»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Why in F you asked for answer for only one k, and not sum over all? Solution doesn't change I think but implementation becomes easier a bit

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem D, why do we need to subtract pref[i-1] when we're only querying max prefix sum from [i, next greatest element]? Having max prefix sum[i, next greatest element] greater than a[i] would satisfy the requirement, what is the purpose of subtracting pref[i-1]?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In F,why ans_new=ans_old−cntsz_old(OR)−cntsz_new(NR)+cntsz_new(OR)+cntsz_new(NR)? -cntsz_new(NR)+cntsz_new(NR)=0.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the problem B the solution is not correct ! The corner test case :

INPUT.TXT 1 4 2 1 2 1

OUPUT.TXT 3 4 1 2

But the result of the tutorial solution is -1

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the approach of finding max prefix sum in question D. I have implemented it differently but I am not getting editorial one. Thankyou

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1691/submission/160003829

I feel like my solution is same as editorial.I have tried hours to find the bug but can't fine.Can anyone help?

UPD : I found my Bug & AC now

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can we do problem E with dfs? I have tried but I'm not understanding what is wrong.
I have separately sorted red and blue according to 1) start points, 2) end points.
And then found the range of other color which will lie within the same color range. and visited the segments using DFS. I have considered the dfs as bipartite graph.

code

Anyone, pls help

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E problems , can someone tell me why the sort way of the struct in set will cause the wa on 36 I think the only metters is the first element.

wa on 36

accept