Representative Edges (Codeforces 1616C)
Tags: Math, geometry

An array $$$a_1, a_2, \ldots, a_n$$$ is good if and only if for every subsegment $$$1 \leq l \leq r \leq n$$$, the following holds: $$$a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$$$. You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$. In one operation, you can replace any one element of this array with any real number. Find the minimum number of operations you need to make this array good.

Input: The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 100$$$): the number of test cases.Each of the next $$$t$$$ lines contains the description of a test case.In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 70$$$): the number of integers in the array.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$): the initial array.

Output: For each test case, print one integer: the minimum number of elements that you need to replace to make the given array good.

Note: In the first test case, the array is good already.In the second test case, one of the possible good arrays is $$$[1, 1, \underline{1}, \underline{1}]$$$ (replaced elements are underlined).In the third test case, the array is good already.In the fourth test case, one of the possible good arrays is $$$[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$$$.

Sample Inputs:
5
4
1 2 3 4
4
1 1 2 2
2
0 -1
6
3 -2 4 -1 -4 0
1
-100

Sample Outputs:
0
2
0
3
0

Solution (Python):
from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
ls = lambda : list(input())
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)
''
''

def solve():
    for _ in range(inp()):
        n = inp()
        a = li()
        m = 0
        for i in range(n - 1):
            d = {}
            for j in range(i + 1, n):
                t = (a[j] - a[i]) / (j - i)
                if t not in d:
                    d[t] = 1
                else:
                    d[t] += 1
            m = max(m, *d.values())
        print(n - m - 1)
solve()

Solution (Python):
from collections import Counter
for _ in range(int(input())):
    n = int(input())
    arr = list(map(float, input().split()))
    if n == 1:
        print(0)
    else:
        ans = float('inf')
        for i in range(n):
            ht = {}
            for j in range(i + 1, n):
                d = (arr[i] - arr[j]) / (i - j)
                if d in ht:
                    ht[d] += 1
                else:
                    ht[d] = 1
            if ht:
                ans = min(ans, n - 1 - max(ht.values()))
        print(ans)

Solution (Python):
import sys
import os
from math import ceil, floor, sqrt, gcd, factorial, log, log2
from io import BytesIO, IOBase
from collections import Counter, deque
from bisect import bisect
inf = int(10000000000.0)
BUFSIZE = 8192
inp = lambda : int(input())
mp = lambda : map(int, input().split())
lst = lambda : list(map(int, input().split()))
alp = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
d = {alp[i]: i for i in range(26)}

def rev(a):
    return a[::-1]

def main():
    for _ in range(inp()):
        n = inp()
        a = lst()
        if n == 1 or n == 2:
            print(0)
        else:
            d = a[1] - a[0]
            f = True
            for i in range(2, n):
                if a[i] - a[i - 1] == d:
                    continue
                else:
                    f = False
                    break
            if f:
                print(0)
            else:
                blen = -1
                bpos = 0
                bs = 0
                for i in range(1, n):
                    d = {}
                    for j in range(i):
                        s = (a[i] - a[j]) / (i - j)
                        if s * (i - j) == a[i] - a[j]:
                            if s in d:
                                d[s] += 1
                            else:
                                d[s] = 1
                            l = d[s]
                            if l > blen:
                                blen = l
                                bpos = i
                                bs = s
                blen += 1
                ans = n - blen
                print(ans)

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()