Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

pikmike's blog

By pikmike, history, 12 months ago, translation, In English,

1197A - DIY Wooden Ladder

Idea: adedalic

Tutorial
Solution (adedalic)

1197B - Pillars

Idea: BledDest

Tutorial
Solution (BledDest)

1197C - Array Splitting

Idea: Roms

Tutorial
Solution (Roms)

1197D - Yet Another Subarray Problem

Idea: BledDest

Tutorial
Solution (Roms)

1197E - Culture Code

Idea: adedalic

Tutorial
Solution (adedalic)

1197F - Coloring Game

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +68
  • Vote: I do not like it

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

I challenge you to write D in $$$O(n)$$$

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

What's the intuition behind D?

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

    I can explain a different (easier) solution. Let's define $$$dp_i$$$ as answer, such that $$$i$$$ is the last used element. Now $$$dp_i = max(0, a_i - k, max(dp[j] - k + \sum_{j + 1}^{i} a_t)$$$, where $$$i - j \leq m$$$. The intuition is as follows: we need to divide all the segment, into subsegments, each length $$$\leq m$$$.

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

      I used the technique but the it fails on test case 19 here is the link to it.

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

      Can you explain a bit more the meaning of each term in the recursive formula in terms of the decision it represents?

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

        Basically we want to find the best segment, such that after splitting it into $$$cnt$$$ subsegments each length $$$\leq m$$$, $$$\sum_{l}^{r} a_i - cnt \cdot k$$$ is maximum. So when we want to count $$$dp_i$$$, we take all lengths $$$1$$$ to $$$m$$$ and try to make $$$[i - len + 1, i]$$$ the last of subsegments. That's how we update dp. This solution relies on the fact that $$$k \geq 0$$$.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it
          length ≤m, ∑rlai−cnt⋅k is maximum.
          

          Can you plz explain this

          Edit-ok i got that and you are very smart:)

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

            I'm glad you did it by yourself =)

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

            Can you explain $$$best_i = \max\limits_{0 \le len, i - len \cdot m \ge 0} (sum(i-len \cdot m + 1, i) - len * k)$$$

            What is this the "best" of? How comes this formular?

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
              Rev. 2   Vote: I like it +5 Vote: I do not like it

              i will explain my solution which is similar to that solution (my sol https://codeforces.com/contest/1197/submission/80940806)

              1.dp[i] will represent the subarray with max cost ending at i

              2.now we will iterate from the last index 'i' up to when the length becomes m because the greatest integer of length less than m will be 1 so after that we don't have to because it will be same as dp[i-j] where j is the starting index

              3.now we will just maintain 'sum' of value let say we are at jth index from the last index i so sum =a[j]+a[j+1]...a[i] now we dp[i]=max(dp[i],sum-k) 'sum-k' because the length i-j+1 is less than or equal m also we have to do dp[i]=max(dp[i],dp[j-1]+sum-k)

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

                What is the key idea, or key observation to come up with that solution?

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

      so for this solution, how does it take into account segments with length > m?

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

        Every segment consists of subsegments of length $$$\leq m$$$. For each small subsegment you have to subtract $$$k$$$. So each segment is just continuous merge of small subsegments. That's why we can apply DP. Each segment is either a small segment or a merge of segment and a small segment.

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

      This easier solution is O(m*n) right?

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

      You can check my solution, Only $$$j = i - m$$$ needs to be considered, Otherwise just take max subarray ending at $$$i$$$ with length $$$\leq m$$$.

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

        Yes, your solution is actually the same, I simply don't differ those cases. It still works in $$$O(n\cdot m)$$$.

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

          It can actually be improved to $$$O(n)$$$ easily by also storing the 2 best subarrays of length $$$\leq m$$$ for $$$i - 1$$$ so you don't have to do a for loop.

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

      consider this case: say $$$j = i - 1, dp_j = a_j - k$$$, when you try to update the value for $$$dp_i$$$ using $$$dp_j - k + a_i$$$, $$$k$$$ will be deducted twice when you calculate $$$dp_i$$$. Is that the case or am I misunderstanding something?

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

        Yes, in this case it subtracts twice, but we will find the best answer anyway.

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

          Is it ok for you to explain why this is the case?

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

            I assume that [i, i] is the last small segment. It means that before i there were small segments only of length m. This leads to another subtraction as [i, i] is a different segment.

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

              I mean why we can still find the optimal answer despite that k is subtracted twice

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

                This is the situation, where length is x * m + 1, we have to subtract k x + 1 times.

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

                  I kindda get your idea after re-reading your comments. In your method, although $$$dp[i]$$$ is miscalculated when we try to update it using $$$dp[i-1]$$$, the optimal answer will surface out when we try to update it using $$$dp[i-2]$$$, is that the case?

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

                  Yes, we choose the maximal value of all, so we will get the best answer.

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

                  I think I finally get it. Thanks for answering my questions patiently!

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

      Thanks for clear explanation!

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

      When you use the transition $$$dp[j] - k + \sum_{j+1}^{i} a_t$$$ , then you extend the optimal segment ending at $$$j$$$. How do we decide the $$$-k$$$ part here?

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

        Consider it this way: adding a segment of length $$$\leq m$$$ costs you $$$k$$$ money.

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

          But may be when we add the segment, then the number of segments doesn't increase....Suppose $$$m = 5$$$ and $$$dp[j]$$$ comprises of segments of size $$$3,5,5,5$$$. If we use one more element to update $$$dp[i]$$$ then the segments will be $$$4,5,5,5$$$ . Here $$$-k$$$ won't be there.

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

            We will overlook both $$$4, 5, 5, 5$$$ and $$$3, 5, 5, 5$$$. I do not understand your usage of word "segment". We'll just try and add every last possible segment $$$[j+1, i]$$$ and update $$$dp[i]$$$, which is the best answer for all segments ending at position $$$i$$$.

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

              In the above example with $$$m = 5$$$, I meant that since $$$dp[j]$$$ means the answer for position $$$j$$$ ,let's say optimal value is for the interval $$$[j - 17, j]$$$ which means value of $$$dp[j]$$$ is $$$\sum_{j-17}^{j} a_t - 4k$$$ . When we update something like $$$dp[j+1]$$$ using $$$dp[j]$$$ then we will take $$$dp[j] - k + a[j+1]$$$ , but it should only be $$$dp[j] - a[j+1]$$$ because now the interval becomes of size 19 and we have already paid $$$4k$$$ in $$$dp[j]$$$...

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

I don't understand the solution for C, I guess this solution works because the initial array is sorted? Is there known algorithm that leads to this solution using differences between adjacent elements?

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

    Let a[1], a[2].. a[n] be the elements in the array. Let 1 <= i < j < k < l....< n be the k-1 indices we choose for dividing the array into k segments. So, cost of division = (a[i] — a[1]) + (a[j] — a[i+1]) + .... + (a[k] — a[j+1]) + (a[n] — a[k+1]), on rearranging : (a[n] — a[1]) — ((a[i+1] — a[i]) + (a[j+1] — a[j]) +.....+ (a[k+1] — a[k])). So, we will store the difference of a[i+1]-a[i] for each 1<=i<n , sort them in decreasing order and take first k-1 differences and finally subtract from (a[n]-a[1]).

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

    lol

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

Can someone explain how to solve E problem. Why do we need a segment tree. And how do we find the value of the minimum for the whole set of the dolls?

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

    If there is no $$$j$$$, that $$$matryoshka_j.in \ge matryoshka_i.out$$$, then $$$d_i = (matryoshka_i.in, 1)$$$

    else

    $$$d_i.first = min[pos,n] - (matryoshka_i.out - matryoshka_i.in)$$$, where $$$pos$$$ is the first $$$j$$$, that $$$matryoshka_j.in \ge matryoshka_i.out$$$ (It means that we can put matryoshka $$$i$$$ inside matryoshka $$$j$$$)

    $$$d_i.second = numberOfMinimums[pos,n]$$$

    And $$$d$$$ — is our segment tree, so we need it to calculate minimum and number of minimums on suffix!

    You can check my solution, I think it's clear enought.

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

    I haven't mastered segment trees yet (did an object-pointer based one for practice but probably need to learn how to do it with bitwise-math and array indices for better efficiency) but I managed to solve this one using only a priority queue; code here if interested:

    https://codeforces.com/contest/1197/submission/57589994

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

What does len mean in the editorial of D? And how does that expression len * m come?

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

    I suppose len is the number of segments that are fully covered. So $$$best_i$$$ is the answer if only segments of length divisible by m are considered.

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

    len means the mutiple of m u r checking backwards from your current position as u need to check only multiples of m for the correct answer from any given position

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

I come with something for problem D but I can't develop it to a solution if anyone solves it by the help of the following please tell me:

we deal with the array as the blocks, we try each possible one let's call it j from 1 to m, and for every j we try to start from 0 to j — 1 and move by j step to partition the array.

it does nothing but I think it could be developed in some way.

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

Very nice explanation of problem E. Thank you so much)

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

why is it besti+sum(i−len,i−1)−k. in the end and not besti + sum(i-len+1,i) — k ?

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

I was discussing problem E with my friend SparklingRa1n and after he solved it we read the editorial. And we noticed this part ( It's because not big enough subsets are not optimal in terms of minimality of extra space.)

However, we are not sure if the part that adedalic says is true, please correct us if we're wrong.

Take this example with 2 dolls {4, 1} {6, 5}

The minimum extra space of big enough is 2, but if you take the first doll only, the extra space is 1

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

    Let's extend your example as {2,1} {4,2} {6,5}

    $$$d[3] = (5, 1)$$$ — it should be obvious. When we try to calculate $$$d[2]$$$ we can see, that the second matryoshka can be nested inside the third one — so "we must put it inside". Then $$$d[2] = (5-2=3, 1)$$$.

    The first doll can be nested both in the second and third dolls, but putting it inside the third doll will lead us to not big enough subset. But! it also makes the extra space not optimal since $$$d[2].first < d[3].first$$$. Then $$$d[1] = (3-1=2, 1)$$$ and it's correct.

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

      Ohh, I understand, I was a little confused, but now is totally clear. Thanks.

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

Can someone explain the intution behind D and as to how are we connecting the maximum sum subarray problem to this problem in greater depth. Also I'm not able to understand the intuition behind the idea of introducing len (as done in the editorial) Please help.

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

This is an alternate Solution 57537548 of Problem 1197C - Array Splitting

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

In problem E, Why cann't we add subset {4,7} as one of good subsets in Test Case 1.

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

can someone give me some further explanations about problem c? more specific: why should we "add up the k−1 minimal ones to the answer"?

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

In the solution given for D why do we fix some elements of best_i with best_i + sum(i-len,i-1) — k ?

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

Can someone explain in more details solution of C, with proofs? Thanks

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

I don't see why we need a segment tree for E since all queries are suffix queries and all updates are at the position we are currently at. We can just maintain a suffix minimum as we go along.

Solution with editorial's approach minus segment tree: 57644319

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

So, I actually got hacked on problem A because of exceeded time limit. How do you know if your solution needs to be O(n) or O(nlogn) given the time constraint? Would you just assume 2 seconds means my solution needs to be O(n)?

Sorry for too many questions, I'm just new to CP.

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

    The rule of thumb I use is to plug the maximum input size into the big O, and look for something $$$\le 10^8$$$.

    So for $$$n=10^3$$$ for example, $$$O(n^2)$$$ is fine ($$$10^6 < 10^8$$$), but for $$$n=10^5$$$, it'd be too slow ($$$10^{10}>10^8$$$).

    In your solution you used quicksort, which is usually $$$O(n \log n)$$$, fast enough, but you were hacked by an input that causes it to become $$$O(n^2)$$$, which is too slow.

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

Could somebody explain me, if we want to calc T(i, j), we must know colors of r1, r2, r3. But I can't find any mention of it in the tutorial.

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

Logic behind soulution of C?

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

I think problem F can be solved simply by reducing the number of states. The number of states that are possible to reach is actually way lower than 64, it's 25. Then I don't think there's any need for optimization, just brute 25^3*1000*log2(10^9) will work. (Correct me if I'm wrong).

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

In the tutorial for D, last line, you wrote: $$$best_i + sum(i - len, i - 1) - k$$$. But in the code posted below it seems that you are calculating $$$best_i + sum(i + 1, i + len)$$$. I think that is a typo in your tutorial.

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Best solution for B. Your text to link here...

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

Can E be solved by Graph Theory? Just saw the "Shortest Path" tag.

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

    There's an edge from i to j with length $$$in_i-out_j$$$ ,if and only if $$$in_i\ge out_j$$$ holds. Sort the matryoshkas by $$$out_i$$$ ,then we can use segment tree to build the graph. To solve the problem more easily,we use two more nodes,S and T. For all node i with indeg=0,add an edge from S to i with length 0. For all node i with outdeg=0,add an edge from i to T with length $$$in_i$$$ . The answer is the number of shortest paths from S to T. Since the graph is a DAG,the solution above works in $$$O(n\log n)$$$ time.

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

whats is the idea behind F solution? and is there any easier way to solve F? thanks

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

Here is an easier $$$O(n \log m)$$$ solution for D:

Let $$$p$$$ be the prefix sum of $$$a$$$. Then maximum cost of subarray ending at $$$i$$$ is $$$ \max_{j < i} \left\lbrace p_i - p_j - k\left \lceil \frac{i - j}{m} \right\rceil\right\rbrace$$$

Main observation is --

$$$\left\lceil \frac{i - j}{m} \right\rceil = \begin{cases}\left\lfloor \frac{i}{m} \right\rfloor - \left\lfloor \frac{j}{m} \right\rfloor + 1, & \text{if }(j \text{ mod } m) < (i \text{ mod } m) \\ \left\lfloor \frac{i}{m} \right\rfloor - \left\lfloor \frac{j}{m} \right\rfloor, & \text{if } (j \text{ mod } m) \geq (i \text{ mod } m) \end{cases}$$$

So, our formula becomes --

$$$\begin{cases}p_i - k\left\lfloor \frac{i}{m} \right\rfloor + \left(k\left\lfloor \frac{j}{m} \right\rfloor - p_j\right) - k, & \text{if }(j \text{ mod } m) < (i \text{ mod } m) \\ p_i - k\left\lfloor \frac{i}{m} \right\rfloor + \left(k\left\lfloor \frac{j}{m} \right\rfloor - p_j\right), & \text{if }(j \text{ mod } m) \geq (i \text{ mod } m) \end{cases}$$$

To evaluate the formula quickly, we can keep the maximum of $$$\left\lbrace k\left\lfloor \frac{i}{m} \right\rfloor - p_i\right\rbrace$$$ at index $$$(i\text{ mod } m)$$$ of a segment tree. Which enables us to get the prefix/suffix maximum in $$$O(\log m)$$$ resulting in total complexity $$$O(n \log m)$$$.

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

    do you mean that i should be kept at such place where it is totally divisible by m and same condition applies for j too ..

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

    Hello Sir
    can u give me a formal proof how did u come up with the formula so quick during the contest

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

the second example of B: 3 1 2. why it is NO?we can move it like this.

-------------------------1------------------1---------------1-------------------------------2
3-1-2 ——> 3-null-2 ——> null-3-2 ——> null-3-2 ——> 1-3-2 ——> 1-3-null ——> finished and yes

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

    Please notice the second condition among the three in the problem statement:

    2.pillar i contains exactly one disk

    According to this, you won't be able to perform your third (also fourth) move.

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

hello everybody, I tried to solve problem D using Kadane algorithm. I got WA at test 19

I can't figure out why it fails at test 19 and I don't understand the editorial for the problem any help is appreciated

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

I m not able to understand the logic for Problem-C. Please explain??

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

In problem B,what happens when there are two discs of same radius , doesn't it affect the answer? My both solutions taking the case of equal radii discs and ignoring that case are accepted. I'm little confuse here ,help me out.

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

    "The second line contains n integers a1, a2, ..., ai (1≤ai≤n), where ai is the radius of the disk initially placed on the i-th pillar. All numbers ai are distinct." — As the problem statement says.

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

I've devised a non-dp-based solution for D, taking advantage that the m is only up to 10.

Mark the array elements in 0, m, 2m, ... . Treat these elements as having k less cost than their original. Then calculate the max sum of the array but you may only start from a marked element.

Start with the leftmost marked element and traverse right, adding to the sum as you do so, and every time you visit a marked element, if it's better to start from that element instead, do so (if sum < cost of current marked element, already reduced by k from original, then set sum to that cost instead)

Then do the next rotation, that is, instead of marking 0, m, 2m, ..., you mark 1, m+1, 2m+1, ... . Doing m rotation ensures that all the elements got marked in one of the rotations, so you cover the cases of starting from every element.

The whole point of this is to take advantage of the fact that, if you mark every m element, the multiple of k that you have to "pay" is exactly as many as the marked elements included in your subarray, as long as you start your subarray in one of the marked elements.

Takes O(n*m) but very little memory.

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

Can Anyone Explain Problem C.I am confused that how we come up with the solution. Thanks in Advance.

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

    Idea is simple, we need to pick the starting point of the k subarrays. Of course the first subarray must have starting point 0. The other k - 1 starting points must be distinct indices in the range 1 .. n - 1 but there is no other restriction on them.

    When you pick a starting point i, it adds a[i - 1] - a[i] to the total cost because a[i - 1] becomes an end point and a[i] becomes a starting point.

    Thus we can just make a vector 'starts' with starts[i] = a[i - 1] - a[i], sort it, and take the sum of the first k - 1 elements. Then add a[n - 1] - a[0] to the sum to account for the fact that a[0] is a start point and a[n - 1] is an end point.

    My code: 82349539

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

      Thanks for the beautiful explaination AQZZ,

      because a[i — 1] becomes a max and a[i] becomes a min.
      

      What does it mean?

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

        I edited it. I mean a[i — 1] becomes an end point (since it is the max of a subarray) and a[i] becomes a start point (since it is the min of a subarray).

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

          Shouldn't it be that:

          a[i] - end point
          
          a[i-1]-starting point
          

          If not , then whats the reason? AQZZ

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

            In my approach we are picking the starting points of the subarray. If we make index i a starting point then a[i - 1] becomes the endpoint of a subarray and a[i] becomes the starting point of a subarray.

            Let k = 2 and a = {1, 2, 5, 6, 7}. Then if we pick i = 2 to start a subarray it means the subarrays will be {1, 2} and {5, 6, 7}.

            Starting point and minimum element of a subarray are exactly the same because the array is sorted. Same with end point and maximum.

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

              Okay Thanks for the beautiful explaination dude.

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

can anyone tell me mistake in my code 84062159