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 ??
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.
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.
Yep, this is even simpler! Until there no negative robots :) Then we should do the opposite :)
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.)
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.
I think there are three possibilities:-
When all are non-negative integer then ans will be sum — 2*min_element.
When all are negative integer then ans will be -1*sum + 2*max_element.
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.
I implemented the solution that i have mentioned above and it got accepted, u can check out the solution here submission link
Read the editorial of this problem :
https://mirror.codeforces.com/problemset/problem/1038/D
If you couldn't understand it then reply back.