BledDest's blog

Educational Codeforces Round 172 — Editorial
By BledDest, 5 weeks ago, In English

2042A - Greedy Monocarp

Idea: BledDest

Tutorial
Solution (Neon)

2042B - Game with Colored Marbles

Idea: BledDest

Tutorial
Solution (BledDest)

2042C - Competitive Fishing

Idea: BledDest

Tutorial
Solution (Neon)

2042D - Recommendations

Idea: adedalic

Tutorial
Solution (adedalic)

2042E - Vertex Pairs

Idea: BledDest

Tutorial
Solution (awoo)

2042F - Two Subarrays

Idea: BledDest

Tutorial
Solution (Neon)
  • Vote: I like it
  • +56
  • Vote: I do not like it

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

did anybody solved problem C using greedy or binary search only if yes then please provide the code..

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    .

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    why is that you only search for those 2 solutions? are you scared of learning a new thing, and a new approach to problems? accept that some problems are weird and require unique solutions. this question cant be binary searched because m+1 does not always yield a better answer than m, and m does not always yield a better answer than m+1. also it cant be solved greedily as you have to consider all suffix differences. stop forcing algorithms just because you're lazy to learn more of them

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      • hh
      → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi, can you tell me in which test case m+1 does not give better answer than m.

      In all test cases i thought of, m+1 gives better answer. And upon submitting my code, it gives wrong answer on test 2. And in the note it says "50th test case differ" which is not visible.

      I did go through the greedy solution and it is indeed intuitive. But I want to know the test case where my binary search fails.

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

        00000000000001, in this case 1 gives the best answer, 2 givea the same answer as 1 and anything over that gives a worse answer.

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

      I still don't understand how the solution related to the question despite it's true, I understand the logic of the code, but I don't get the idea why use that solution. Can you help me.

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

        I visualized this problem completely differently. Lets not think about subarrays, but rather consider the edges of the subarrays as "walls". A worth of a fish is the amount of walls to the left of it(we don't count the edges of the original array itself). So now let's iterate over all positions where we can put the walls, and obviously we can see that we want to put walls where the difference of suf1-suf0 is maximized.

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

        If you ignore the binary string and consider some fix choice of group partition and plot it on the 2D plane where x-axis are fishes and y-axis be there respective value, you would get a bar graph like

        ex. cut between (2, 3), (4, 5), (7, 8):
       **
    *****
  *******
--------->
123456789

        then instead of summing over value for each x, let's consider summing them for each y, then you would see if you made a cut between $$$i, i + 1$$$, then it will increase answer by $$$n - i$$$, then it would become much easier to derive the solution in the editorial.

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

          okay, so I understand the first part, but after that I don't understant why the solution do the remaining. I just know that when we pass the array from the end to find the point that are make Bob's score greater than Alice.

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

            To derive the rest of solution, just add the binary string back and you would see the contribution when cutting $$$(i - 1, i)$$$ just change from $$$n - i$$$ to (the number of Bob's fish in $$$[i, n]$$$) — (the number of Alice's fish in $$$[i, n]$$$) and you want to make sum of this stuff no less than $$$k$$$, so you just keep picking the cut point with largest weight until sum of them is no less than $$$k$$$.

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

              okay, thank you.

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

              SO the idea is that, count and take the amount of fishes in indexes that Bob's score exceed Alice's score, then sort the vals list stores those scores diff, then do k — val[i] to take the minimum of groups. Right? So when k get zero before the vals list is empty, how to know that the fished can be devided to such groups. For example, when k = 5 and there are vals list of 5 elements. But after 2 times of subtraction k get zero and there are 3 elements remain in the list. How to know that the fishes can be devide to exactly 3 groups( 2 +1 )?

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

                each val correspond to different cut points, so it's always possible

                → Reply
»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Look at what this idiot did.

Instead of using set upper_bound and lower_bound functions, this guy wrote a whole specialized segment tree. https://mirror.codeforces.com/contest/2042/submission/294446705 And it PASSED with only a single penalty.

Guess this is what happens when you solve too many range query problems.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    what's the issue, the segtree most likely does have smaller constants, it's not a totally unreasonable decision if you know I think (also idk who asked)

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      that is me. I am the idiot.

      I wrote the segtree because I forgot that lower_bound and upper_bound exist.

      Solved too many segtree problems on cses.

      → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can you explain your approach a bit and also what segtrees are returning as you are passing only index to segtree?

    And, personally I believe that it is better to do anything which comes to mind during contest instead of trying to think for best and quickest method (even though lower_bound would have been easier to code :P)

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

      I used two variations of segment trees and used coordinate compression on both of them with a map:

      1. rtree: gives the smallest number greater than equal to x, the given value is compressed but the value stored in the segtree is uncompressed, which is the value to be returned. standard lower_bound on set

      2. ltree: gives the largest value less than equal to x. can be implemented with lower_bound on a set of negative values.

      If a value is added to a segtree, the compressed index of the node will store that value, otherwise it will store INT_MIN(INT_MAX) so that we can query max(min) element between 0 and x (x and infinity).

      → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C tutorial, shouldn't it be $$$0⋅s_{a_1}+(1-0)⋅s_{a_2}+(2-1)⋅s_{a_3}+⋯+s_{a_m}$$$ the resulting sum?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'd like to add that..

    notice you only pick indexes to start a new group where str[i]=='1' and that group can go from i to the end or you can fraction that group into small groups, but for every index you pick to start a new group, the resultant score (diff bob and alice from i to end) or s[i] is positive cuz even if you divide a group into small groups at index i, you will keep the score of s[i]. Example:

    $$$n=9, k = 5$$$

    011100101

    Array $$$s$$$ will be $$${_, 2, 1, 0, -1, 0, 1, 0, 1}$$$, but you are only interested on making groups at indexes where s[i] have positive values. Now you can make a group at index where $$$s[i] = 2$$$ cuz it's the greatest in $$$s$$$. so you make a group between $$$i-1$$$ and $$$i$$$ where $$$i = 1$$$ and we get two points of score, but even if you don't keep the last group you made $$$[i:n)$$$, you'll still keep those two points: now you have groups [0:0] and [1:9). As we still have values on $$$s$$$, let's take the next greatest. Now you have groups [0:0], [1:1], [2:9), cuz in group [2:9) you have +1 of score, and you are still keeping the previous +2 points, even if you divided the [1:9) group.

    → Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.

    Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)

    Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      $$$ 0 * (p[a[1] - 1] - p[a[0] - 1]) + 1 * (p[a[2] - 1] - p[a[1] - 1]) + 2 * (p[a[3] - 1] - p[a[2] - 1]) + ... + (m - 1) * (p[n-1] - p[a[m-1] - 1]) $$$

      becomes

      $$$ 0 * p[a[0] - 1] + (0 - 1) * p[a[1] - 1] + (1 - 2) * p[a[2] - 1] + ... + (m - 2 - (m - 1)) * p[a[m-1] - 1] + (m - 1) * p[n-1] $$$

      which simplifies to

      $$$ (m - 1) * p[n-1] - (p[a[1] - 1] + p[a[2] - 1] + ... + p[a[m-1] - 1]) $$$

      $$$p[n-1]$$$ is clear, you can calculate it. Then sort all other p values and minus the minimum ones first. Of course as you minus, the m will also increase.

      Implementation: 294956283

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Not sure why but my equation was coming out to be: (m-1)*pa[m] - (pa[1] + pa[2] + ... + pa[m-1]).

        How did you arrive at your first equation, also what does aj denote in your above equation?

        → Reply
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I'm using zero-indexed arrays here and $$$a[j]$$$ denotes the start index of j'th group. This only makes sense for j = 0 -> m-1, so i also define $$$a[m] = n$$$, which is why the last part is $$$p[n - 1]$$$ not $$$p[a[m] - 1]$$$.

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

          If we're using prefix sums the information we have available is the number of fishes to the left of the cuts / gaps / boundaries of the groups. Unfortunately, the multiplier of the contribution of a fish in a group to the score differential is determined by how many cuts it is to the right of. So it's easier to use suffix sums. But we can still deduce the score in a subtractive way using prefix sums, as your formula suggests.

          Each fish is first "overvalued" by being multiplied by one less than the number of groups. This is the (m - 1) * pa[m] part. To get to the proper score differential, all fish to the left of the first cut, boundary, gap, etc., have their value decremented, same goes for all fish to the left of the second cut, and so on. This is the remainder of the formula.

          Hope that helps.

          → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Waiting for alternative way of problem D solution (Not using trees... ordered set in C++ or SortedList in python).

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

    Problem D can be solved in linear time complexity without advanced data structures.

    Sort $$$(l_i, r_i)$$$ in ascending order of $$$l_i$$$ and descending order of $$$r_i$$$ if $$$l_i$$$ and $$$l_j$$$ are equal. The problem is reduced to finding $$$j$$$ for every $$$i$$$ such that $$$j < i$$$ and $$$r_j \geqslant r_i$$$ (As for the other side of the problem, just reverse the interval as the editorial does). Through sorting, the monotonicity of $$$l$$$ is ensured, and if $$$r$$$ is somehow monotonic, we can solve the problem by a monotonic stack. At first sight the monotonicity of $$$r$$$ might be non-trivial, but consider the fact below: given three indices $$$i < j < k$$$ ($$$l_i < l_j < l_k$$$), if $$$r_i < r_j$$$, $$$i$$$ is impossible to contribute to $$$k$$$. See what I am talking about? By eliminating the elements that will be impossible to do contribution, we construct the monotonicity of $$$r$$$. At last a monotonic stack will be sufficient to solve the problem.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Damn it I forgot the sorting part. It's $$$\mathcal O(n \log n)$$$.

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

        I'll try this approach tmr, good to know. Thanks.

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

      After think through it carefully...

      Says if i < j < k and r[j] < r[i] (r[j] is not contributing to an r[i] computation), it doesn't mean we can eliminate it yet since we don't know if there's a future r[k] <= r[j].

      So I hardly sees any monotonic stacks will be meaningful, can you elaborate it in code submission? (I can read C++/Python)

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

        You misread my statement. I assumed $$$r_j > r_i$$$ when $$$i < j$$$, which on the opposite when $$$r_j < r_i$$$, $$$i$$$ can contribute to $$$j$$$ and is therefore reserved.

        For example:

        1 8
2 9
3 7

        $$$[1, 8]$$$ cannot contribute to $$$[2, 9]$$$ and is eliminated. Since $$$9 > 8$$$ and $$$1 < 2$$$, if $$$[2, 9]$$$ is unable to do contribution in the future, $$$[1, 8]$$$ is either (remember that $l$s is ascending).

        Finally if it still gives you trouble understanding, check out rainboy's submission for elaboration.

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

          After I checkout rainboy's submission, the tricky about segment contribution is applying the monotonic stack for right point, but use the left point to calculate the answer...

          I was so obsess on calculate the right segment (like editorial), which result as using data structure is the only choice :(

          I see where I went wrong, thanks for sticking with me.

          → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Finally accepted, my last rant is the problem time limit is too strict for python users :(

          (I got TLE because I sort one more time too many)

          → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the solution of problem C, or someone give a different approach to problem C

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

    read the comment I wrote above

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

    we can use suffix sums for the same. check out my solution for it

    → Reply
»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Copy of problem C: 1175D - Array Splitting

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem-C, you should use int64.

→ Reply
»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem E can be solved in $$$\Theta(n)$$$ without requiring an $$$O(1)$$$ LCA computation. Instead, we precompute two properties for each subtree: (1) whether it contains all $$$n$$$ distinct values, and (2) whether it contains duplicate values. Using these properties, we can decide whether to select a vertex directly in order.

To facilitate the precomputation, we use the DFS order to represent each subtree as a range and then translate the constraints for a subtree into constraints for its corresponding range. Both properties can be checked in $$$\Theta(n)$$$ using a simple two-pointer technique on the range.

294738728

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i tried c using binary search, but couldn't figure out the mistake.. :(

https://shorturl.at/043Sb

→ Reply
»
5 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.

Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)

Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D: What is the reason of the tle ?

void solve(){
    int n;
    cin>>n;

    vector<array<int, 2>> v(n);
    for(auto &curr: v)
        for(auto &it: curr)
            cin>>it;

    vector<array<int, 3>> a(n);
    map<array<int, 2>, int> m;
    for(int i=0; i<n; ++i)
        a[i][0] = v[i][0], a[i][1] = v[i][1], a[i][2] = i, ++m[v[i]];

    vector<int> ans(n);
    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[0] < a2[0]) return true;
        if(a1[0] > a2[0]) return false;
        return a1[1] >= a2[1];
    });

    set<int> s;
    s.insert(a[0][1]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.lower_bound(currE);
        if(it == s.end()){
            s.insert(currE);
            continue;
        }

        ans[idx] += (*it - currE);
        s.insert(currE);
    }

    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[1] < a2[1]) return false;
        if(a1[1] > a2[1]) return true;
        return a1[0] <= a2[0];
    });

    s.clear();
    s.insert(a[0][0]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.upper_bound(currS);
        if(it == s.begin()){
            s.insert(currS);
            continue;
        }
        --it;

        ans[idx] += (currS - *it);
        s.insert(currS);
    }

    for(int i=0; i<n; ++i)
        if(m[v[i]] > 1)
            ans[i] = 0;

    for(int i=0; i<n; ++i)
        cout<<ans[i]<<"\n";
}
→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems like D are often convenient to implement in a way when we group intervals by the beginning of the interval and by the end of the interval and then iterate through all positions:

  1. Add all intervals that begin at this position to our data structure
  2. Calculate answer
  3. Remove all intervals that end at this position from our data structure

For this problem it would look like this:

for (const auto& [pos, event] : q) {
    for (int i : event.open) {
        open_by_l.insert(l[i]);
        open_by_r.insert(r[i]);
    }
    for (int i : event.open) {
        auto it = open_by_r.lower_bound(r[i]);
        if (it != open_by_r.end() && next(it) != open_by_r.end()) {
            ans[i] += *next(it) - r[i];
        }
    }
    for (int i : event.close) {
        auto it = open_by_l.upper_bound(l[i]);
        if (it != open_by_l.begin() && prev(it) != open_by_l.begin()) {
            ans[i] += l[i] - *prev(prev(it));
        }
    }
    for (int i : event.close) {
        open_by_l.extract(l[i]);
        open_by_r.extract(r[i]);
    }
}

I hope someone finds this useful.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope TL of D have to be atleast 4s because if we use segment tree/Fenwick tree instead of ordered set it runs in like 2.2s. so is this tight TL is intended?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain solution to problem E, with dsu? (saw it in jiangly`s code)

→ Reply
»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem-E is a very beautiful problem. I like it.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

problem E is interesting, thanks you!

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you are asked to find out starting and ending index of each group in problem C then how to do that ?

From the given editorial explanation

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the editorial's solution of Problem C in a bit more intuitive way?

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You should learn how to create problem: don't worry i will teach you for free

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello. I need help in problem D. I am having a Time Complexity of O(NlogN) but I am getting TLE. Can someone please point me out -> TLE Test case 5.

My login: { 1. Sort by start time 2. On every index ask the question, what is time just greater than current(this is our end) and what time is just greater than current that I saw recently(this is our start) 3. Due to the data we have already sorted by start, we get start from Monotonic stack and end from a set or someplace where we can do a query like: give me just greater than the current element 4. Do a difference and that is the answer for that index 5. Put it into our Monotonic stack }

Additional problems: 1. If I use endl or flush at the end I am getting Runtime error: STATUS_ACCESS_VIOLATION -> Runtime error Test case 4 2. If I use endl I am getting WA (weird but OK)

PS: I tried to made my code readable before posting. I hope it helps.

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

    std::lower_bound is only O(log(n)) over random access iterators. Set iterators are NOT random access, so your std::lower_bound call is actually O(n). You probably want to use set::lower_bound instead.

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

      Thank you. Got AC.

      → Reply
    • »
      »
      »
      25 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, I spent 2 hours trying to figure out why I was getting TLE... thought aswell that lower_bound was O(log(n)) on set

      → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, I am wondering how So, each "border" between two groups increases the value of every fish after the border by 1 . leads to thinking about difference between Alice's fishes and Bob's fishes at every index i.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the coloured marble question, following this logic, wouldnt the input [1 3 1 3 4] result in output 6?

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope. If she plays optimally, Alice will take marble '4' first (+2 points), then Bob takes marble '3' or '1', let's say Bob takes '3'. So, Alice can take marble '1' or '3' also, let's say she takes '1'(+1 point) . And to make a counter from being get +1 point from taking the all colors of marbles '1', so Bob takes '1', and lastly, alice takes '3' (+1 point) . So, Alice get 4 points.

    → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For the tutorial of C, shouldn't it be sum is greater than or equal to k

→ Reply