Блог пользователя aloobukhara

Help Needed!!
Автор aloobukhara, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

→ Ответить
»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.net/blog/entry/66687

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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!!

→ Ответить