Read problems statements in Mandarin Chinese  and Russian. 
You are given an array that consists of n integer numbers. You have to change at most K elements of this array, so that the resulting array will be a arithmetic progression. From all the possible arithmetic progressions, you should choose most beautiful. 
You can uniquely define the arithmetic progression by two numbers a_{0} and d - the first element of the given progression and the step that defines next element. (a_{i} = a_{0}+i * d). The progression A(a_{0} , d_{0}) is more beautiful than the progression B(b_{0}, d_{1}) iff (a_{0} < b_{0} or (a_{0} = b_{0} and d_{0} < d_{1}))  

------ Input ------ 

The first line contains two integers N and K denoting the number of elements in the given array and the number of elements that you can change
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the given array.

------ Output ------ 

Output a single line containing the resulting array with at most K changes. Mind that among all the arithmetic sequences you have to choose the most beautiful.

In the given test data, it is always possible to recover at least one arithmetic progression under the constraints of the problem.

------ Constraints ------ 

$2 ≤ N ≤ 100000$
$0 ≤ K ≤ min(10, N-2)$
$-10^{9} ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
4 2
1 2 1 4
----- Sample Output 1 ------ 
-5 -2 1 4

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc


Solutions:
from collections import defaultdict

def eval(A, dictR, r):
	l = dictR[r]
	nbToChange = 0
	newVal = A[l[-1]]
	for iR in range(l[-1], len(A) - 1):
		newVal += r
		if newVal != A[iR + 1]:
			nbToChange += 1
	lastVal = newVal
	newVal = A[l[0]]
	for iR in range(l[0], 0, -1):
		newVal -= r
		if newVal != A[iR - 1]:
			nbToChange += 1
	return (newVal, r, lastVal, nbToChange)

def solve(A, K):
	dictR = defaultdict(list)
	for i in range(1, len(A)):
		r = A[i] - A[i - 1]
		dictR[r].append(i)
	maxEff = max((len(v) for v in dictR.values()))
	rMaxEff = [key for key in dictR if len(dictR[key]) == maxEff]
	results = []
	for r in dictR:
		results.append(eval(A, dictR, r))
	possibles = [t for t in results if t[3] <= K]
	possibles.sort(key=lambda x: (x[0], x[1]), reverse=False)
	(a0, r, an, _) = possibles[0]
	return ' '.join(list(map(str, range(a0, an + 1, r))))
(N, K) = map(int, input().split())
A = list(map(int, input().split()))
print(solve(A, K))


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def alg(L, K):
	length = len(L)
	cur_best = None
	best_res = []
	for fixed1 in range(K + 2):
		for fixed2 in range(fixed1 + 1, K + 2):
			dnum = L[fixed2] - L[fixed1]
			dden = fixed2 - fixed1
			if dnum % dden != 0:
				continue
			d = dnum // dden
			a0 = L[fixed1] - d * fixed1
			if cur_best is None or cur_best[0] > a0 or (cur_best[0] == a0 and cur_best[1] > d):
				changes = 0
				i_list = 0
				a = a0
				valid = True
				cur_res = []
				while True:
					if a != L[i_list]:
						changes += 1
						if changes > K:
							valid = False
							break
					cur_res.append(a)
					a += d
					i_list += 1
					if i_list == length:
						break
				if valid:
					cur_best = (a0, d)
					best_res = cur_res
	if len(best_res) == 0:
		print('invalid case')
	return ' '.join((str(a) for a in best_res))

def main():
	data = sys.stdin
	(n, k) = map(int, data.readline().split())
	L = list(map(int, data.readline().split()))
	res = alg(L, k)
	print(res)
main()


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
w1 = float('inf')
w2 = float('inf')
for i in range(0, k + 1):
	for j in range(n - 1, n - 2 - k + i, -1):
		l = i
		r = j
		d = int((a[r] - a[l]) / (r - l))
		s = a[l] - d * l
		c = 0
		for z in range(n):
			if a[z] != s + d * z:
				c += 1
		if c <= k:
			if s < w1 or (s == w1 and d < w2):
				w1 = int(s)
				w2 = int(d)
for x in range(n):
	a[x] = str(w1 + x * w2)
print(' '.join(a))


def main():
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	w_a = float('inf')
	w_d = float('inf')
	for i in range(0, k + 1):
		for j in range(n - 1, n - 2 - k + i, -1):
			L = i
			R = j
			D = int((a[R] - a[L]) / (R - L))
			a_0 = a[L] - D * L
			chg = 0
			for l in range(0, n):
				if a[l] != a_0 + D * l:
					chg += 1
			if chg <= k:
				if a_0 < w_a or (a_0 == w_a and D < w_d):
					w_a = int(a_0)
					w_d = int(D)
	for i in range(n):
		a[i] = str(w_a + i * w_d)
	print(' '.join(a))
main()


(n, k) = map(int, input().split())
l = [int(i) for i in input().split()]
cds = [0] * n
for i in range(1, n):
	cds[i] = l[i] - l[i - 1]
from collections import Counter
c = Counter(cds)
maxi = 0
maxic = 0
for i in c:
	if c[i] > maxic:
		maxic = c[i]
		maxi = i
	elif c[i] == maxic:
		if i > maxi:
			maxi = i
req = 0
for i in range(1, n):
	if l[i] - l[i - 1] != maxi:
		curr = maxi - (l[i] - l[i - 1])
		req += curr
st = l[0] - req
l = [0] * n
l[0] = st
for i in range(1, n):
	l[i] = l[i - 1] + maxi
print(*l)