aloobukhara's blog

Help Needed!!
By aloobukhara, history, 5 years ago, In English

we have an array of size n. we have to maximize a variable "sum" which is initialized to 0 . for this we can do the following operation as many time as we can (including 0). operation : consider any subsequence of size m<=n . update sum value by the total sum of subsequence and update value of each element of the subsequence by multiplying it by -1. M is given to us. We have to take subsequence ofsize exactly m Thanks in advance !! array elemets can be in between -1000000000 to 1000000000

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Answer to this problem will be the sum of all positive elements in the array!!
Once you apply the operation to the subsequence with all positive elements, all elements in the array will become negative and choosing any subsequence now will lead to a reduction in the answer. Hope this helps :)

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

    Take this . m=5 n= 7 2 1 0 -1 -3 -3 -3 m is given to us. I am sorry for not to be clear with the question.

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

      DELETED Sorry for the wrong algorithm

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

        i am not able to handle number of zeroes . I am stuck in this from last two three days. i think greedy is the solution for it. Any hint ??

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

          Can you share the question link so I can understand better and help you better?

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

According to me, answer should simply be sum of some number of groups of m elements in descending order. You should stop when last such group of m elements has an overall negative sum. I don't see why you will convert a negative value to positive, because that will reduce as much as it will add.

Also, I would recommend that you always provide a source for your problems because no one would want to help you in a problem from ongoing contest. I made a mistake in sharing my thoughts with you ( even though it may be wrong ). If you want people to help better, you should always provide a source. More here.

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

    Thanks friend .. I will take care of it next time .. for your solution I have a counter test case M= 5 n = 6 9 -1 -2 -3 -4 -5 Answer should be 4. Take first five .. sum equals -1 make them negative .. then pick last 5 . Sum would be -1+5 i.e 4.

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

      Okay, I understand now.

      BTW, there exists even better solution than what you gave.

      First choose {9,-2,-3,-4,-5} , which gives sum = -5 and new array = {-9,-1,2,3,4,5} Then choose {-1,2,3,4,5} , which gives sum = -5 + (13) = 8, and new array = {-9,1,-2,-3,-4,-5}

      I could even make 7 with another operation. Who knows, maybe if you keep doing you'll get even better answer. I am very curious as to what the real solution is.

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

        So, I think in this case, since $$$n-m = 1$$$, we can make all possible values that have $$$a[i] + a[j]$$$ for different $$$i,j$$$ in original array. Take all but one, say $$$j$$$, then take all except $$$i$$$, then you get $$$a[i] + a[j]$$$ ( NOTE : This only works here, as $$$n-m=1$$$ ). Hence with one of numbers as $$$9$$$, we can make $$$8,7,6,5,4$$$.

        I am getting a feeling there is $$$gcd$$$ of $$$n,m$$$ involved. You could call it intuition, but maybe it is not so. Just expressing my thoughts.

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

This is a Dynamic Programming problem. I'm not sure if you got it from Codeforces, but there was a similar problem on an Educational Round two months ago.

Problem: 1155D - Beautiful Array

Editorial: https://mirror.codeforces.com/blog/entry/66687

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

This question is similar to one of the questions asked in a contest that is currently going on (i can't share the link of the contest because that will be a hint for others on how to solve the problem) Please don't help this guy cheat!!

→ Reply