Problem:


Score : 700 points

Problem Statement

Snuke is buying a lamp.
The light of the lamp can be adjusted to m levels of brightness, represented by integers from 1 through m, by the two buttons on the remote control.

The first button is a "forward" button. When this button is pressed, the brightness level is increased by 1, except when the brightness level is m, in which case the brightness level becomes 1.

The second button is a "favorite" button. When this button is pressed, the brightness level becomes the favorite brightness level x, which is set when the lamp is purchased.

Snuke is thinking of setting the favorite brightness level x so that he can efficiently adjust the brightness.
He is planning to change the brightness n-1 times. In the i-th change, the brightness level is changed from a_i to a_{i+1}. The initial brightness level is a_1.
Find the number of times Snuke needs to press the buttons when x is set to minimize this number.

Constraints

2 \leq n,m \leq 10^5

1 \leq a_i\leq m

a_i \neq a_{i+1}

n, m and a_i are integers.

Input

Input is given from Standard Input in the following format:

n m
a_1 a_2 … a_n

Output

Print the minimum number of times Snuke needs to press the buttons.

Sample Input 1

4 6
1 5 1 4

Sample Output 1

5

When the favorite brightness level is set to 1, 2, 3, 4, 5 and 6, Snuke needs to press the buttons 8, 9, 7, 5, 6 and 9 times, respectively.
Thus, Snuke should set the favorite brightness level to 4.
In this case, the brightness is adjusted as follows:

In the first change, press the favorite button once, then press the forward button once.

In the second change, press the forward button twice.

In the third change, press the favorite button once.

Sample Input 2

10 10
10 9 8 7 6 5 4 3 2 1

Sample Output 2

45



Sample input:
4 6
1 5 1 4


Sample output:
5

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N, M = map(int, input().split())
A = list(map(int, input().split()))

cnt = [0] * (2 * M + 1)
memo = []

ans = 0
for s, t in zip(A[:-1], A[1:]):
    s += 1
    if s <= t:
        cnt[s] += 1
        cnt[t] -= 1
        cnt[s + M] += 1
        cnt[t + M] -= 1
        memo.append((t, t - s))
        memo.append((t + M, t - s))
        ans += t - s + 1
    else:
        t += M
        cnt[s] += 1
        cnt[t] -= 1
        memo.append((t, t - s))
        ans += t - s + 1


cnt = list(accumulate(cnt))
for i, d in memo:
    cnt[i] -= d
cnt = list(accumulate(cnt))

print(ans - max(cnt))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]
ps = [0]*(m+2)  # 0,1,2,...,m,m+1

for i in range(n-1):
    if a[i] < a[i+1]:
        ps[a[i]+1] += 1
        ps[a[i+1]] -= 1
    else:
        ps[0] += 1
        ps[a[i+1]] -= 1
        ps[a[i]+1] += 1
        ps[m+1] -= 1

aps = [0]
for x in ps[:-1]:
    aps.append(aps[-1]+x)
aps = aps[2:]


def dist(src, tar):
    return (m+tar-src) % m


freq = [0]*m
for i, x in enumerate(a):
    if i == 0:
        continue
    freq[x-1] += dist(a[i-1], a[i])-1


ans = [0]*m
for i in range(n-1):
    ans[0] += min(dist(a[i], a[i+1]), 1+dist(1, a[i+1]))

for i in range(1, m):
    ans[i] = ans[i-1] + freq[i-1] - aps[i-1]

print(min(ans[1:]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

ps = [0]*(m+2)  # 0,1,2,...,m,m+1

for i in range(n-1):
    if a[i] < a[i+1]:
        ps[a[i]+1] += 1
        ps[a[i+1]+1] -= 1
    else:
        ps[0] += 1
        ps[a[i+1]+1] -= 1
        ps[a[i]+1] += 1
        ps[m+1] -= 1

aps = [0]
for x in ps[:-1]:
    aps.append(aps[-1]+x)

aps = aps[2:]
mx = 0
okini = 0
for i, x in enumerate(aps):
    if mx <= x:
        okini = i+1
        mx = x


def dist(a, b):
    if a <= b:
        return b-a
    else:
        return m+b-a


ans2 = 10**12
for o in [aps.index(mx)+1, okini]:
    ans = 0
    for i in range(n-1):
        ans += min(dist(a[i], a[i+1]), 1 + dist(o, a[i+1]))
    ans2 = min(ans, ans2)

print(ans2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

ps = [0]*(m+2)  # 0,1,2,...,m,m+1

for i in range(n-1):
    if a[i] < a[i+1]:
        ps[a[i]+1] += 1
        ps[a[i+1]+1] -= 1
    else:
        ps[0] += 1
        ps[a[i+1]+1] -= 1
        ps[a[i]+1] += 1
        ps[m+1] -= 1

aps = [0]
for x in ps[:-1]:
    aps.append(aps[-1]+x)

aps = aps[2:]
mx = 0
okini = 0
for i, x in enumerate(aps):
    if mx <= x:
        okini = i+1
        mx = x


def dist(a, b):
    if a <= b:
        return b-a
    else:
        return m+b-a


ans = 0
for i in range(n-1):
    ans += min(dist(a[i], a[i+1]), 1 + dist(okini, a[i+1]))

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
imos1=[0]*(m*2+2)
imos2=[0]*(m*2+2)
imos3=[0]*(m*2+2)
for i in range(n-1):
  cost=(m+arr[i+1]-arr[i])%m
  if arr[i]<arr[i+1]:
    imos1[arr[i]]+=1+cost
    imos1[arr[i+1]+1]-=1+cost
    imos2[arr[i]+1]+=-1
    imos2[arr[i+1]+1]+=1
    imos3[arr[i+1]+1]+=cost
    if arr[i]!=1:
      imos1[1]+=cost
      imos1[arr[i]]-=cost
    if arr[i+1]!=m:
      imos1[arr[i+1]+1]+=cost
      imos1[m+1]-=cost    
  else:
    imos1[arr[i]]+=1+cost
    imos1[m+arr[i+1]+1]-=1+cost
    imos2[arr[i]+1]+=-1
    imos2[m+arr[i+1]+1]+=1
    imos3[m+arr[i+1]+1]+=cost
    imos1[arr[i+1]+1]+=cost
    imos1[arr[i]]-=cost
for i in range(1,m*2+2):
  imos2[i]+=imos2[i-1]
for i in range(m*2+2):
  imos1[i]+=imos2[i]
  imos1[i]+=imos3[i]
for i in range(1,m*2+2):
  imos1[i]+=imos1[i-1]
xs=[0]*(m+1)
xs[0]=10**18
for i in range(1,m+1):
  xs[i]=imos1[i]+imos1[m+i]
print(min(xs))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0]*(2*m)
B = []
cnt = 0
for i in range(n-1):
  a, b = A[i], A[i+1]
  a -= 1
  b -= 1
  if a < b:
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
    a += m
    b += m
    L[a+2] += 1
    if b < 2*m-1:
      L[b+1] += -1
      B.append((b+1, -(b-a-1)))
  else:
    b += m
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
L = list(accumulate(L))
for i, b in B:
  L[i] += b
L = list(accumulate(L))
ans = cnt - max(L)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(n)]

imos=[0 for i in range(m+1)]
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    val=(g-s)%m
    if val>1:
        s=(s+2)%m
        if s>g:
            imos[s]+=-1
            imos[m]+=1
            imos[0]+=-1
            imos[g+1]+=1
        else:
            imos[s]+=-1
            imos[g+1]+=1
        imos[(g+1)%m]+=val-1
        imos[(g+1)%m+1]+=-(val-1)

for i in range(1,m+1):
    imos[i]+=imos[i-1]

for i in range(1,m+1):
    imos[i]+=imos[i-1]

ans=-1
val=0
for i in range(m):
    if val>imos[i]:
        ans=i
        val=imos[i]

val=0
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    if (g-s)%m>1:
        if g>=s:
            if ans>s:
                val+=1+(g-ans)%m
            else:
                val+=(g-ans)%m
        else:
            if ans>s or g>=ans:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
    else:
        val+=(g-s)%m


print(val)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(n)]

imos=[0 for i in range(m+1)]
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    val=(g-s)%m
    if val>2:
        s=(s+2)%m
        if s>g:
            imos[s]+=-1
            imos[m]+=1
            imos[0]+=-1
            imos[g+1]+=1
        else:
            imos[s]+=-1
            imos[g+1]+=1
        imos[(g+1)%m]+=val-1
        imos[(g+1)%m+1]+=-(val-1)

for i in range(1,m+1):
    imos[i]+=imos[i-1]

for i in range(1,m+1):
    imos[i]+=imos[i-1]

ans=-1
val=0
for i in range(m):
    if val>imos[i]:
        ans=i
        val=imos[i]

val=0
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    if (g-s)%m>2:
        if g>=s:
            if ans>s:
                val+=1+(g-ans)%m
            else:
                val+=(g-ans)%m
        else:
            if ans>s or g>=ans:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
    else:
        val+=(g-s)%m


print(val)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(n)]

imos=[0 for i in range(m+1)]
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    val=(g-s)%m
    if val>2:
        s=(s+2)%m
        if s>g:
            imos[s]+=-1
            imos[m]+=1
            imos[0]+=-1
            imos[g+1]+=1
        else:
            imos[s]+=-1
            imos[g+1]+=1
        imos[(g+1)%m]+=val-1
        imos[(g+1)%m+1]+=-(val-1)

for i in range(1,m+1):
    imos[i]+=imos[i-1]

for i in range(1,m+1):
    imos[i]+=imos[i-1]

ans=-1
val=0
for i in range(m):
    if val>imos[i]:
        ans=i
        val=imos[i]

val=0
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    if g>=s:
        if ans>s:
            val+=1+(g-ans)%m
        else:
            val+=(g-ans)%m
    else:
        if ans>s or g>=ans:
            val+=1+(g-ans)%m
        else:
            val+=(g-s)%m

print(val)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x-1, a))
lr = []
cnt = 0

for i in range(n-1):
    ai, aj = a[i], a[i+1]
    
    if ai<aj:
        lr.append((ai, aj))
        cnt += aj-ai
    else:
        lr.append((ai-m, aj))
        lr.append((ai, m-1))
        cnt += m+aj-ai
    
lr.sort(key=lambda t: t[0])
idx = 0
ans = cnt
decre = 0
pq = []

for i in range(m):
    while len(pq)>0 and pq[0][0]<i:
        r, l = heappop(pq)
        decre -= r-l
        
    while idx<len(lr) and i>=lr[idx][0]:
        decre += i-lr[idx][0]-1
        heappush(pq, (lr[idx][1], lr[idx][0]))
        idx += 1
    
    ans = min(ans, cnt-decre)
    decre += len(pq)

print(ans)

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

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

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    allsum += (a[i+1]-a[i]) % m
    if a[i+1] == (a[i]+1)%m:
        continue

    start[a[i] % m].append(i)
    end[(a[i+1]-1) % m].append(i)

    


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

if (allsum - max(lis) < 0):
    print (asxacscd)
#print (lis)
print (allsum - max(lis))

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

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

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    if a[i+1] == (a[i]+1)%m:
        continue

    start[a[i] % m].append(i)
    end[(a[i+1]-1) % m].append(i)

    allsum += (a[i+1]-a[i]) % m


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

print (allsum - max(lis))

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

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

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    if a[i+1] == a[i]+1:
        continue

    start[a[i] % m].append(i)
    end[(a[i+1]-1) % m].append(i)

    allsum += (a[i+1]-a[i]) % m


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

print (allsum - max(lis))

Submission status: Wrong Answer

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

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

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    start[a[i] % m].append(i)
    end[(a[i+1]-1) % m].append(i)

    allsum += (a[i+1]-a[i]) % m


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-a[j])%m-1)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

print (allsum - max(lis))

Submission status: Wrong Answer

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

imos = [0] * (2 * m)
diff = [0] * (2 * m)
res = 0
for i in range(n - 1):
    l = a[i] - 1
    r = a[i + 1] - 1
    if l > r:
        r += m
    imos[l + 2] += 1
    imos[r + 1] -= 1
    diff[r + 1] = r - l - 1
    res += r - l

ans = [0] * (2 * m)
tmp = 0

for i in range(2 * m):
    tmp += imos[i]
    if i - 1 >= 0:
        ans[i] += ans[i - 1] + tmp
    else:
        ans[i] += tmp
    ans[i] -= diff[i]
    
max_ = 0
for i in range(m):
    max_ = max(max_, ans[i] + ans[i + m])
print(res - max_)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

def calc(l, m1, m2, r):
    val = [0] * 4
    for a1, a2 in zip(a, a[1:]):
        diff = (a2 - a1 + m) % m
        val[0] += min(diff, (a2 - l + m) % m + 1)
        val[1] += min(diff, (a2 - m1 + m) % m + 1)
        val[2] += min(diff, (a2 - m2 + m) % m + 1)
        val[3] += min(diff, (a2 - r + m) % m + 1)
    return val.index(min(val)), min(val)

l = 1; r = m
while r - l > 2:
    m1 = (l * 2 + r) // 3
    m2 = (l + r * 2) // 3
    ret, _ = calc(l, m1, m2, r)
    if ret == 0:
        r = m1
    elif ret == 1:
        r = m2
    elif ret == 2:
        l = m1
    else:
        l = m2
m1 = (l * 2 + r) // 3
m2 = (l + r * 2) // 3
_, ans = calc(l, m1, m2, r)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

def calc(l, m1, m2, r):
    val = [0] * 4
    for a1, a2 in zip(a, a[1:]):
        diff = (a2 - a1 + m) % m
        val[0] += min(diff, (a2 - l + m) % m + 1)
        val[1] += min(diff, (a2 - m1 + m) % m + 1)
        val[2] += min(diff, (a2 - m2 + m) % m + 1)
        val[3] += min(diff, (a2 - r + m) % m + 1)
    return val.index(min(val)), min(val)

l = 0; r = m+1
while r - l > 2:
    m1 = (l * 2 + r) // 3
    m2 = (l + r * 2) // 3
    ret, _ = calc(l, m1, m2, r)
    if ret == 0:
        r = m1
    elif ret == 1:
        r = m2
    elif ret == 2:
        l = m1
    else:
        l = m2
_, ans = calc(l, m1, m2, r)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


n, m = map(int, input().split())
light_list = list(map(int, input().split()))
ret = 0

diff_dict = defaultdict(int)
cnt=0
for i in range(n-1):
    if light_list[i+1] > light_list[i]:
        diff_dict[light_list[i+1]+1] += light_list[i+1] - light_list[i]
        ret += light_list[i+1] - light_list[i]
    else:
        diff_dict[light_list[i+1]+1] += m - (light_list[i] - light_list[i+1])
        ret += light_list[i+1]
        cnt += 1


ret_min = float('inf')
for i in range(1, m+1):
    if i-1 == 1:
        cnt += 1
    if i-1 == light_list[-1]:
        cnt -= 1
    if diff_dict[i]:
        ret += diff_dict[i]
    ret -= cnt
    ret_min = min(ret+cnt, ret_min)



print(ret_min)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import itertools

"""
(a_i+1,a_{i+1}] に x がある間は...使う。傾き-1
a_{i+1} -> a_{i+1} + 1 のところでがくっと下がる
そこからa_iまでは傾き0
""" 

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
FROM = A[:-1]
TO = A[1:]

d_slope = [0] * (M+1) # 傾きの差分

"""
5,4,3,2,1,5,5,5,5
0,-1,-1,-1,-1,4,0,0,0
0,-1,0,0,0,0,5,-4,0,0
"""

for x,y in zip(FROM,TO):
    if y < x:
        y += M
    z = y - x
    if z == 1:
        continue
    d_slope[1+(x+1)%M] += -1
    d_slope[1+y%M] += z # 1回で行けたのがz回かかるようになる
    d_slope[1+(y+1)%M] += 1-z

slope = list(itertools.accumulate(d_slope))
S = sum(slope)
slope = [x - S//M for x in slope]
slope[0] = 0

# 1番をお気に入りにしたときのスコアを求める
cnt = 0
for x,y in zip(FROM,TO):
    if x < y:
        cnt += (y-x)
    else:
        cnt += y

answer = cnt + min(itertools.accumulate(slope[2:]))
print(answer)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(m):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(m):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def acc(X): return list(accumulate(X))

N, M = map(int, input().split())
A = [int(a)-1 for a in input().split()]

X = [0] * M # 1,1,1,...
Y = [0] * M # 1,2,3,...

def tri(l, r, a = 1):
    if l < M:
        Y[l] += a
    if r + 1 < M:
        Y[r+1] -= a
        X[r+1] -= (r-l+1) * a

def box(l, r, a = 1):
    if l < M:
        X[l] += a
    if r + 1< M:
        X[r+1] -= a
    
def calc(a, b):
    if a <= b - 2:
        tri(a+2, b)
    elif a > b and a <= b + M - 2:
        tri(a+1, M-1)
        tri(0, b)
        box(0, b, b-a)
        
    # print(a, b, X, Y, rev())

def rev():
    ret = acc(Y)
    ret = [X[i] + ret[i] for i in range(M)]
    return acc(ret)
    
ans = 0
for i in range(1, N):
    ans += (A[i] - A[i-1]) % M
    calc(A[i-1], A[i])

X = rev()
# print(X)
ans -= max(X)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
def acc(X): return list(accumulate(X))

N, M = map(int, input().split())
A = [int(a)-1 for a in input().split()]

X = [0] * M # 1,1,1,...
Y = [0] * M # 1,2,3,...

def tri(l, r, a = 1):
    if l < M:
        Y[l] += a
    if r + 1 < M:
        Y[r+1] -= a
        X[r+1] -= (r-l+1) * a

def box(l, r, a = 1):
    if l < M:
        X[l] += a
    if r + 1< M:
        X[r+1] -= a
    
def calc(a, b):
    if a <= b - 2:
        tri(a+2, b)
    elif a > b and a <= b + M - 2:
        tri(a+1, M-1)
        tri(0, b)
        box(0, b, b-a-1)

ans = 0
for i in range(1, N):
    ans += (A[i] - A[i-1]) % M
    calc(A[i-1], A[i])

Y = acc(Y)
X = [X[i] + Y[i] for i in range(M)]
X = acc(X)

ans -= max(X)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
aa = inpl()
for i in range(N):
	aa[i] -= 1

yama_height = [0]*(2*M)
yama_num = [0]*(2*M)
SUM = 0
for i in range(1,N):
	na = aa[i]
	ba = aa[i-1]
	if na < ba:
		na += M
	SUM += (na-ba)
	yama_height[na] = na - (ba + 1)
	yama_num[na] -= 1
	yama_num[ba+1] += 1

tmp = 0
for i in range(2*M):
	tmp += yama_num[i]
	yama_num[i] = tmp

ans_list = [0]*(M)
tmp = 0
for i in reversed(range(2*M)):
	tmp += yama_height[i]
	tmp -= yama_num[i]
	ans_list[i%M] += tmp

print(SUM-max(ans_list))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
aa = inpl()

yama_height = [0]*(2*M)
yama_num = [0]*(2*M)
SUM = 0
for i in range(1,N):
	na = aa[i]
	ba = aa[i-1]
	if na < ba:
		na += M
	SUM += (na-ba)
	yama_height[na] = na - (ba + 1)
	yama_num[na] -= 1
	yama_num[ba+1] += 1

tmp = 0
for i in range(2*M):
	tmp += yama_num[i]
	yama_num[i] = tmp

ans_list = [0]*(M)
tmp = 0
for i in reversed(range(2*M)):
	tmp += yama_height[i]
	tmp -= yama_num[i]
	ans_list[i%M] += tmp

print(SUM-max(ans_list))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
src = list(map(lambda x:int(x)-1,input().split()))

imos = [0] * (2*M+1)
ends = [0] * (2*M+1)
max_press = 0
for a,b in zip(src,src[1:]):
    if a > b:
        b += M
    if b-a == 1: continue
    imos[a+2] += 1
    imos[b+1] -= 1
    ends[b+1] += b-a-1
    max_press += b-a

for i in range(2*M):
    imos[i+1] += imos[i]

press = [max_press] * M
d = 0
for i,(dec,inc) in enumerate(zip(imos, ends)):
    d += inc - dec
    press[i%M] += d
print(min(press))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
src = list(map(lambda x:int(x)-1,input().split()))

imos = [0] * (2*M+1)
ends = [0] * (2*M+1)
max_press = 0
for a,b in zip(src,src[1:]):
    if a > b:
        b += M
    if b-a == 1: continue
    imos[a+2] += 1
    imos[b+1] -= 1
    ends[b+1] += b-a-1
    max_press += b-a

for i in range(2*M):
    imos[i+1] += imos[i]

ans = tmp = max_press
for dec,inc in zip(imos, ends):
    tmp -= dec
    tmp += inc
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,*a=map(int,open(0).read().split())
s=[0]*(2*m+2)
tot=0
for l,r in zip(a,a[1:]):
	tot+=(r-l)%m
	if l>r:
		r+=m
	dif=r-l
	if dif>1:
		s[l+2]+=1
		s[r+1]-=dif
		s[r+2]+=dif-1
s=list(itertools.accumulate(list(itertools.accumulate(s))))
print(tot-max(s[i]+s[m+i] for i in range(1,m)))

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*(2*m+2)
tot=0
for l,r in zip(a,a[1:]):
	tot+=(r-l)%m
	if l>r:
		r+=m
	dif=r-l
	if dif>1:
		s[l+2]+=1
		s[r+1]-=dif
		s[r+2]+=dif-1
s=list(itertools.accumulate(list(itertools.accumulate(s))))
print(tot-max(s[i]+s[m+i] for i in range(1,m)))

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*(2*m+2)
tot=0
for l,r in zip(a,a[1:]):
	tot+=(r-l)%m
	if l>r:
		r+=m
	dif=r-l
	if dif>1:
		s[l+2]+=1
		s[r+1]-=dif
		s[r+2]+=dif-1
s=list(itertools.accumulate(s))
s=list(itertools.accumulate(s))
print(tot-max(s[i]+s[m+i] for i in range(1,m)))

Submission status: Wrong Answer

Solution code:
import operator
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros(2 * M)
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
base_result = sum(diff_array[diff_2 <= 0]) + sum(input_array[1:][diff_2 > 0])

for index in xrange(len(diff_array)):
	index_dict[input_array[index+1]] += (diff_array[index] - 1)
	index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 


best_result = base_result

for base_val in xrange(1,M):
	diff = sum(index_dict[[base_val,base_val + M]])
	best_result = min(base_result,best_result) 

print int(best_result)

Submission status: Wrong Answer

Solution code:
import operator
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros(2 * M)
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
base_result = sum(diff_array[diff_2 <= 0]) + sum(input_array[1:][diff_2 > 0])

for index in xrange(len(diff_array)):
	index_dict[input_array[index+1]] += (diff_array[index] - 1)
	index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 


best_result = base_result

for base_val in xrange(1,M):
	diff = sum(index_dict[[base_val,base_val + M]])
	base_result += diff
	if diff <= 0:
		best_result = base_result

print int(best_result)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros(2 * M)
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
True_False = (diff_2 <= 0)
base_result = sum(diff_array[True_False]) + sum(input_array[1:][np.logical_not(True_False)])

for index in xrange(len(diff_array)):
	index_dict[input_array[index+1]] += (diff_array[index] - 1)
	index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 


best_result = base_result

for base_val in xrange(1,M):
	diff = sum(index_dict[[base_val,base_val + M]])
	base_result += diff
	if diff < 0:
		best_result = base_result

print int(best_result)

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0

index_dict = [0] * M
s = [0] * (2 * M + 1)
now_val = input_array[0]
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	diff = val - now_val
	base_result += min(diff % M, val + 1)
	index_dict[val % M] += (diff % M - 1)
	#next_val = (now_val + diff % M)
	#if now_val + 1 >= next_val:
		#continue
	#else:
		#for val_2 in xrange(now_val + 1, next_val):
			#index_dict[val_2 % M] -= 1
	#now_val = next_val
"""
for i in xrange(N - 1):
    s[input_array[i] + 1] += 1
    if input_array[i + 1] < input_array[i]:
        s[input_array[i + 1] + M] -= 1
    else:
        s[input_array[i + 1]] -= 1
 
for i in xrange(2 * M):
    s[i + 1] += s[i]
for i in xrange(1, M + 1):
    s[i] = s[i] + s[i + M]
"""
best_result = base_result

for base_val in xrange(M):
	base_result += index_dict[base_val % M]
	#base_result -= s[base_val]
	best_result = min(base_result,best_result) 
	
print best_result

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
n, m = list(map(int, input().split()))
ary = list(map(int, input().split()))

def calcMinNum(frm, to, m, fav):
	return(min(forwardNum(frm, to, m), favNum(to, m, fav)))

def forwardNum(frm, to, m):
	if frm <= to:
		return(to - frm)
	else:
		return(to - frm + m)

def favNum(to, m, fav):
	return(forwardNum(fav, to, m) + 1)

def findMin(n, m, ary):
	nums = []
	for i1 in range(1, m):
		kari = 0
		for i2 in range(0, n-1):
			kari += calcMinNum(ary[i2], ary[i2 + 1], m, i1)
		nums.append(kari)
	return(min(nums))

print(findMin(n, m, ary))

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0
if len(input_array) == 0:
	print 0
else:
	index_dict = [0] * M
	now_val = input_array[0]
	for index in xrange(len(input_array)- 1):
		val = input_array[index + 1]
		diff = val - now_val
		base_result += min(diff % M,
			val + 1)
		index_dict[val % M] += (diff % M - 1)
		next_val = (now_val + diff % M)
		if now_val + 1 >= next_val:
			continue
		else:
			for val_2 in xrange(now_val + 1, next_val):
				index_dict[val_2 % M] -= 1
		now_val = next_val

	best_result = base_result

	for base_val in xrange(M):
		base_result += index_dict[base_val % M]
		best_result = min(base_result,best_result) 
 	
	print best_result

Submission status: Wrong Answer

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
input_array = [int(i) for i in input_line_2.split(" ")]
M = int(input_line_1.split(" ")[1])
def count(base_val, input_array, M):
	return sum([min((input_array[i + 1] - input_array[i]) % M,
		 (input_array[i + 1] - base_val) % M + 1
		)
	 for i in range(len(input_array) - 1)])

#base_result = [(input_array[i + 1] - input_array[i]) % M for i in range(len(input_array) - 1)]
def count_2(base_val, input_array, M):
	return sum([min(base_result[i],(input_array[i + 1] - base_val) % M + 1)
	for i in range(len(input_array)-1)])

def count_3(base_val, input_array, M, base_result_i):
	diff_result = 0
	for index in range(len(input_array)-1):
		if ((input_array[index] < base_val) & (base_val < input_array[index + 1])):
			diff_result -= 1
			#print "p1", input_array[index], base_val,  input_array[index + 1]
		#elif ((input_array[index] < base_val) & 
			  #(base_val < (input_array[index + 1] + M)) & 
			  #(input_array[index + 1] < input_array[index] < 0)
			  #):
			#diff_result -= 1
			#print "p2", input_array[index], base_val,  input_array[index + 1]
		elif input_array[index + 1] == base_val:
			diff_result += (input_array[index + 1] - input_array[index] - 1) % M
			#print "p3", input_array[index], base_val,  input_array[index + 1]
	return base_result_i + diff_result

base_result = count(1, input_array, M)
best_result = base_result
for base_val in range(M + 1)[1:-1]:
	#print base_val,base_result,best_result 
	base_result = count_3(base_val, input_array, M, base_result)
	best_result = min(base_result,best_result) 


print best_result