Codeforces: B. Roma and Changing Signs

The problem is from codeforces: http://www.codeforces.com/problemset/problem/262/B

Two hints used to solve this problem are greedy and sorted numbers. The greedy approach turns negative numbers one by one in non-decreasing order (the absolute value is decreasing for negative numbers). After k changes, if there are still zero or more non-negative numbers, then the answer would be the sum of these numbers. However, if there are less than k negative numbers, we should change all non-negative numbers and thus we have an array of all non-negative integers. We still have k’ changes, which can be easily computed by subtracting k – c where c is the number of non-positive numbers in the first place.

Now, the next is simple, if k’ is even, we can keep flipping any numbers so the total sum won’t change. if k’ is odd, then we can flip the last time the smallest number (with the absolute value). The answer will be the sum minus two times the number.

#!/usr/bin/env python
# acm.steakovercooked.com

n, k = map(int, raw_input().split())
num = map(int, raw_input().split())

cnt = len([i for i in num if i <= 0])
ans = 0

if cnt >= k:
    for i in xrange(len(num)):
        if num[i] <= 0:
            if k > 0:
                num[i] = -num[i]
                k -= 1
            else:
                break
    print sum(num)
else:
    y = abs(num[0])
    for i in xrange(len(num)):
        if num[i] <= 0:
            num[i] = -num[i]
        if num[i] < y:
            y = num[i]            
    k -= cnt
    if (k & 1) == 0:
        print sum(num)
    else:        
        print sum(num) - 2 * y

In python, always there are shorter versions, for example,

N,K=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()))
for i in xrange(N):
	if a[i]<0 and K:
		a[i]*= -1
		K-= 1
a.sort()
a[0]*= (-1)**K
print sum(a)

Or

n,k=map(int,raw_input().split())
ns=map(int,raw_input().split())
for i in range(n):
  if k>0 and ns[i]<0:
    ns[i]*=-1
    k-=1
print sum(ns)-(0 if k%2*min(ns)==0 else 2*min(ns) )

Both present the same ideas.
--EOF (The Ultimate Computing & Technology Blog) --