 # 1778A - Flip Flop Sum - 800

Updated: 2023-09-01

1778A - Flip Flop Sum (greedy, implementation, 800)

There are three possible conditions:

1. -1 -1 - all negative. In this case sum -2 becomes sum 2. Plus 4.
2. -1 1 - different, no sum change.
3. 1 1 - all positive. 2 becomes -2. Diff is -4.

## Solution

def solve():
n = int(input())
ar = list(map(int, input().split()))

s = 0 # sum

# three conditions: all 1, all -1, at least one -1
has_diff = False
has2_positive = 0
has2_negative = 0

s += ar
for idx in range(1, n):
if ar[idx] == ar[idx-1]:
if ar[idx] == -1:
has2_negative = 4 # -2 -> +2, diff 4
else:
has2_positive = -4 # +2 => +1, diff 1
else:
has_diff = True
s += ar[idx]

if has2_negative:
s += has2_negative
elif has_diff:
...
elif has2_positive:
s += has2_positive
print(s)

for _ in range(int(input())):
solve()


Optimized solution:

def solve():
n = int(input())
ar = list(map(int, input().split()))
res = sum(ar)

for i in range(n-1):
if ar[i] == ar[i+1] == -1:
print(res + 4)
return
if res == n:
res -= 4
print(res)

for _ in range(int(input())):
solve()