Problem:


Score : 300 points

Problem Statement

Snuke has an integer sequence A of length N.

He will freely choose an integer b.
Here, he will get sad if A_i and b+i are far from each other.
More specifically, the sadness of Snuke is calculated as follows:

abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))

Here, abs(x) is a function that returns the absolute value of x.

Find the minimum possible sadness of Snuke.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the minimum possible sadness of Snuke.

Sample Input 1

5
2 2 3 5 5

Sample Output 1

2

If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2.
Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.

Sample Input 2

9
1 2 3 4 5 6 7 8 9

Sample Output 2

0

Sample Input 3

6
6 5 4 3 2 1

Sample Output 3

18

Sample Input 4

7
1 1 1 1 2 3 4

Sample Output 4

6



Sample input:
5
2 2 3 5 5


Sample output:
2

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

for i in range(len(a)):
    a[i] -= i + 1

a.sort()
b = [a[0]]
for i in a[1:]:
    b.append(b[-1] + i)
hi = len(a)
lo = 0


def score(index):
    return abs((lft * a[index] - b[index]) - (b[-1] - b[index] - (len(a) - index) * a[index]))


for i in range(10000):
    lft = (hi + 2 * lo) // 3
    rgt = (2 * hi + lo) // 3
    ltmp = score(lft)
    rtmp = score(rgt)
    if ltmp <= rtmp:
        lo = lft
    else:
        hi = rgt

printmin([(score(lo), score(lo + 1)]))

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
nums = sorted([num - i for i, num in enumerate(list(map(int,input().split())), 1)])


sums = [None for i in range(n)]
sums[0] = nums[0]
allv = sum(nums)

minv = nums[0] * (2 - n) - 2 * sums[0] + allv
for i in range(n-1):
    sums[i+1] = sums[i] + nums[i+1]
    p = sum[i] * (2*(i+1) - n) -2 * sums[i] + allv
    minv = min(minv,p)

print(minv)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_ = []

for i in range(n):
    a_.append(a[i] - i)
b = round((sum(a_))/n)

ans0 = 0
for i in range(n):
    ans0 += abs(a[i] - (b + i))

ansp = 0
for i in range(n):
    ansp += abs(a[i] - (b + i+1))

ansm = 0
for i in range(n):
    ansm += abs(a[i] - (b + i-1))

ans = min(ans0, ansp, ansm)

if ans == ans0:
    print(ans)
else:
    if ans == ansp:
        p = 1
        while 1:
            ansp = 0
            for i in range(n):
                ansp += abs(a[i] - (b + i+p))
            if ansp > ans:
                break
            ans = ansp
            p += 1
    if ans == ansm:
        m = 1
        while 1:
            ansm = 0
            for i in range(n):
                ansm += abs(a[i] - (b + i-m))
            if ansm > ans:
                break
            ans = ansm
            p -= 1
    print(min(ansp, ansm))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
check = np.arange(1, n+1)
c = sorted(list(a - check))
b1 = c[int(n/2)]
b2 = c[int(n/2)+1]
count1 = 0
count2 = 0
for i in range(1, n+1):
    count1 += abs(a[i-1] - i - b1)
    count2 += abs(a[i-1] - i - b2)
print(min(count1, count2))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

for i in range(N):
    A[i] = A[i]-i
A.sort()

S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]

sumA = sum(A)
maxA,minA = max(A),min(A)

Ans = 10**9
for i in range(3z00):
    l = bisect_left(A,minA)
    low  = abs(minA*l - S[l]) + abs(S[N]-S[l] - minA*(N-l))
    h = bisect_left(A,maxA)
    high  = abs(maxA*h - S[h]) + abs(S[N]-S[h] - maxA*(N-h))
    if low==high:
        minA += 1
    elif low < high:
        maxA = (maxA+minA)//2
    else:
        minA = (maxA+minA)//2
    #print(Ans,low,high,minA,maxA)
    Ans = min(Ans,low,high)

print(Ans)

Submission status: Runtime Error

Solution code:
def Asum(A,b):
    sumA = 0
    for i in range(len(A)):
        sumA += abs(A[i] - i - b - 1)
    return sumA



N = int(input())
ip = input().split()

A = []
for i in ip:
    A.append(int(i))

buf = Asum(A,max(A))
for i in range(max(A)-1,min(A)-N,-1):
    if buf > Asum(A,i):
        buf = Asum(A,i)
    else:
        break

print(Asum(A,i-1))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

lru_cache
def sunuke(b):
  return sum(abs(a-i-1-b) for i,a in enumerate(A))

def s(ran):
  l = 0
  r = len(ran)-1
  while l < r:
    su_l = sunuke(ran[l])
    su_r = sunuke(ran[r])
    d = (r-l)//2
    if d == 0:
      d = 1
    if su_l > su_r:
      l += d
    else:
      r -= d
  return sunuke(ran[l])
  
print(s(list(range(min(ary),max(ary)+1))))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

lru_cache
def sunuke(b):
  return sum(abs(a-i-1-b) for i,a in enumerate(A))

def s(ran):
  l = 0
  r = len(ran)-1
  while l != r:
    su_l = sunuke(ran[l])
    su_r = sunuke(ran[r])
    d = (r-l)//2
    if d == 0:
      d = 1
    if su_l > su_r:
      l += d
    else:
      r -= d
  return sunuke(ran[l])
  
print(s(list(range(min(ary),max(ary)+1))))

Submission status: Runtime Error

Solution code:
from math import ceil,floor
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  a[i]-=(i+1)
a.sort()

b1=a[ceil(n/2)]
b2=a[floor(n/2)]

def c1(x):
    return abs(x-b1)
def c2(x):
    return abs(x-b2)
print(min(sum(list(map(c1,a))),sum(list(map(c2,a)))))

Submission status: Runtime Error

Solution code:
import math
def f(a, n):
    b = sum(a) / n
    b2 = (1+n) / 2 
    
    res = []
    for x in [b, b2, b-b2, b2-b, ceil(b), ceil(b2), floor(b), floor(b2), ceil(b-b2), ceil(b2 - b), floor(b-b2), floor(b2-b)]:
        s = (int(x+i) for i in range(1, n+1))
        sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
        res.append(sadness)
        
    return min(res)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Runtime Error

Solution code:
import math
def f(a, n):
    b = sum(a) / n
    b2 = (1+n) / 2 
    
    res = []
    for x in [b, b2, b-b2, b2-b, ceil(b), ceil(b2), floor(b), floor(b2), ceil(b-b2), ceil(b2 - b), floor(b-b2), floor(b2-b)]:
        s = (x+i for i in range(1, n+1))
        sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
        res.append(sadness)
        
    return min(res)
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

lru_cache
def sunuke(b):
  return sum(abs(a-i-1-b) for i,a in enumerate(A))

def s(r):
  if len(r) == 1:
    return sunuke(r[0])
  r1 = sunuke(r[0])
  r2 = sunuke(r[-1])
  if len(r) == 2:
    return min((r1,r2))
  d = 1
  if len(r) == 3:
    d = 0
  if r1 > r2:
    return s(r[len(r)//2-d:])
  else:
    return s(r[:len(r)//2+d])
  

ret = sum(abs(a) for a in ary)
print(s(list(range(min(ary),max(ary)+1))))

Submission status: Runtime Error

Solution code:
N = int(input())
a = [0]*N
sum = 0
for i in range(N):
    a[i] = int(input()) - i - 1
    sum += a[i]
mean = sum / N
sad1 = 0
sad2 = 0
for i in range(N):
    sad1 += (a[i] - mean)
    sad2 += (a[i] - mean + 1)
print(min([sad1, sad2]))

Submission status: Runtime Error

Solution code:
import collections
import numpy as np
n=int(input())
a=np.array(sorted([int(x)-i for (x,i) in zip(input().split(), range(1,n+1))]))
if np.sum(a > 0) > np.sum(a < 0):
  b = a[a>0][np.sum(a > 0)-np.sum(a < 0)-1]
  a-=b
elif np.sum(a > 0) < np.sum(a < 0):
  b = a[a<0][-(np.sum(a > 0)-np.sum(a < 0))]
  a-=b
a=abs(a)
print(a.sum())

Submission status: Runtime Error

Solution code:
_ = input()
aa = list(map(int, input().split()))

normalized = [aa[i-1] - i for i in range(1, len(aa) + 1)]


def search(aa, b_bottom, b_up):
    if b_up == b_bottom:
        return b_bottom

    b_mid = (b_up + b_bottom) // 2
    total_up = sum([abs(a - b_up) for a in aa])
    total_bottom = sum([abs(a - b_bottom) for a in aa])
    total_mid = sum([abs(a - b_mid) for a in aa])
    if total_bottom < total_up and total_mid < total_up:
        return search(aa, b_bottom, b_mid)
    else:
        return search(aa, b_mid, b_up)


bottom = min(normalized)
up = max(normalized)
b = search(normalized, bottom, up)
moved = [abs(a - b) for a in normalized]
print(sum(moved))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

lru_cache
def sunuke(b):
  return sum(abs(a-i-1-b) for i,a in enumerate(A))

def s(r):
  if len(r) == 1:
    return sunuke(r[0])
  pp(r)
  r1 = sunuke(r[0])
  r2 = sunuke(r[-1])
  if len(r) == 2:
    return min((r1,r2))
  d = 1
  if len(r) == 3:
    d = 0
  if r1 > r2:
    return s(r[len(r)//2-d:])
  else:
    return s(r[:len(r)//2+d])
  

ret = sum(abs(a) for a in ary)
print(s(list(range(min(ary),max(ary)+1))))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
from pprint import pprint as pp
import itertools as it
from functools import lru_cache

YN = {True: 'Yes', False: 'No'}
ri = lambda: int(input())
ria = lambda: list(map(int, input().split()))
rian = lambda n: [ria() for _ in range(n)]
rs = lambda: input()
rsa = lambda: input().split()
rsn = lambda n: [rs() for _ in range(n)]

N = ri()
A = ria()

ret = None
ary = [a-i-1 for i,a in enumerate(A)]

lru_cache
def sunuke(b):
  return sum(abs(a-i-1-b) for i,a in enumerate(A))

def s(r):
  if len(r) == 1:
    return sunuke(r[0])
  r1 = sunuke(r[0])
  r2 = sunuke(r[-1])
  if len(r) == 2:
    return min((r1,r2))
  if r1 > r2:
    return s(r[len(r)//2-1:])
  else:
    return s(r[:len(r)//2+1])
  

ret = sum(abs(a) for a in ary)
print(s(list(range(min(ary),max(ary)+1))))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    A[i] -= i + 1

sortA = sorted(A)
b1 = sortA[(N-1)//2]
b2 = sortA[(N-1)//2+1]

ans1 = 0
ans2 = 0
for i in range(N):
    ans1 += abs(b1-A[i])
    ans2 += abs(b2-A[i])

print(min(ans1, ans2))

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = [int(i) for i in input().split()]
dif = calc(A,0)
if dif > calc(A,1):
    d = 1
    b = 1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
elif dif > calc(A,-1):
    d = -1
    b = -1
    while(True):
        if calc(A,b) > calc(A,b+d):
            dif = calc(A,b+d)
            b+=d
        else:
            break
ans = dif
print(ans)

Submission status: Runtime Error

Solution code:
import math

def f(a, n):
    res = math.inf
    for b in range(-n-1, n+1):
        s = (b+i for i in range(1, n+1))
        sadness = sum(abs(ai - xi) for (ai, xi) in zip(a, s))
        res = min(res, sadness)
    
    return res
    
n = int(input())
a = [int(i) for i in input().split()]
print(f(a, n))

Submission status: Runtime Error

Solution code:
def main():
    N= input()
    list = map(int, raw_input().split())
    list = [i - list[i] for i in range(len(list))]
    # print(list)
    mini = min(list)
    maxi = max(list)
    # print(mini)
    # print(maxi)
    beforesumm = float('inf')
    for b in range(-abs(maxi), abs(maxi)+1):
        blist = [abs(b+list[i]) for i in range(len(list))]
        # print(blist)
        summ = sum(blist)
        # print(summ)
        if beforesumm >= summ:
            beforesumm = summ
        else:
            break
    print(int(beforesumm))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

vector<int> a;
int n, x;
long long lo, hi, mid, y, z, ans;

long long eval (long long b) {
  long long r = 0;
  for (int i = 0; i < n; i++) {
    r += abs(a[i] - b - i+1);
  }
  return r;
}
int main() {
  cin >> n;
  for (int i= 0; i < n; i++) {
    cin >> x;
    a.push_back(x);
  }

  lo = -1000000000;
  hi = 1000000000;
  ans = 	9223372036854775807;
  while (hi - lo > 1) {
    mid = (hi+lo)/2;
    y = eval(mid);
    z = eval(mid+1);
    ans = min(ans, min(y, z));
    if (y > z) {
      lo = mid;
    } else {
      hi = mid;
    }
  }

  cout << ans << endl;

  return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list2 = sorted([a - (i + 1) for i, a in enumerate(a_list)])

s = 0
b = math.floor(sum(a_list2) / n)

for a in a_list2:
    s += abs(a - b)
    
print(s)

Submission status: Runtime Error

Solution code:
n = map(int, input().split())

a = list(map(int, input().split()))

for i in range(len(a)):
    a[i] -= i + 1

a.sort()

d1, d2 = a[len(a) // 2], a[len(a) // 2 + 1]
print(sum([abs(i - d1) for i in a]))