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

Автор electro177, история, 3 года назад, По-английски

There are N robots in a single row each having an integer value assigned to them.Each robot can terminate the closest robot (either left or right) if there is any When a robot with a value x terminates another robot with value y, then terminated robot vanishes and the value of the robot which terminated changes to x-y. The robots will destroy each other until one remains Find the maximum possible value of the last robot.

First line contains integer N and the next line contains N integers where ith element denotes the value of ith robot and these values are given in the same order in which those robots appear in the row.

CONSTRAINTS: 1<N<500000

-10^9 <= A, < 10^9 where A, is the value of ith robot

Example:

Input: 4

2 1 2 1

Output:

4

Explanation:

Second robot terminates third making array 2,-1,1 then second terminates the third one in this new array making the new array as 2,-2 and finally first terminate second leaving with value 4

I thought of doing range dp but it will be O(n^3),and also in the i had a doubt whether to find maximum value or minimum value Any ideas ??

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

»
3 года назад, # |
Rev. 8   Проголосовать: нравится +10 Проголосовать: не нравится

This is not a dp. And you should not think of O(n^3) when you see N = 500'000. Even O(n^2) would need to run like for a few days to finish, so O(n^3) wouldn't do it in your life time.

This is a one of strangest problems I've seen: basically, cheapest value robots destroying all higher value robots around and going almost to -inf "karma", just to be "eaten" by some-high-value-troll-robot in the end, to gain him some gigantic "karma". This looks like some karma-fraud scheme.

It's a greedy linear problem. If the highest rated robot stands at one of the ends of queue, then answer is: highest_value — (lowest_value — sum_of_all_other_values). If it stands in the middle — it may be not the best candidate (you should also consider others) + you need to consider left_cheapest and right_cheapest separately.

ps. Ooops, I missed the negative numbers. If there is a negative numbers — they just eat all except 1 non-negative (or negative closest to 0), and then it eats all the negatives.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    I think the lowest robot can kill everyone except one robot and in the end the robot that wasn't killed by the lowest value robot can kill the lowest robot. So final answer will be sum of all robots -2*lowest_value_robot.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Yep, this is even simpler! Until there no negative robots :) Then we should do the opposite :)

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

Since each element will mutiply 1 or -1 and appear at the final answer,we can assign -1 and 1 to each element in the array.However,there are also special cases.There must at least one A will mutiply 1 and at least one and at least one A will mutiply -1 when they appear in final answer.(The construction is easy to find when you think about the explanation in the statement.)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    You can sort the array.And then,you should caculate the sum of array and the sum of nagtive element.If all elements in array is non-negtive,the final result is sum of array minus the lowest number.If some elements in array is negtive,the final result is the sum of array minus the sum of negtive element.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

I think there are three possibilities:-

  1. When all are non-negative integer then ans will be sum — 2*min_element.

  2. When all are negative integer then ans will be -1*sum + 2*max_element.

  3. When both negative and non-negative integers are present then ans is sum of abs(a[i]).

Also handle the corner case of N=1.

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

Read the editorial of this problem :
https://codeforces.com/problemset/problem/1038/D
If you couldn't understand it then reply back.