Repainting Street (Codeforces 1415B)
Tags: Greedy, brute force

There is a street with $$$n$$$ houses in a line, numbered from $$$1$$$ to $$$n$$$. The house $$$i$$$ is initially painted in color $$$c_i$$$. The street is considered beautiful if all houses are painted in the same color. Tom, the painter, is in charge of making the street beautiful. Tom's painting capacity is defined by an integer, let's call it $$$k$$$.On one day, Tom can do the following repainting process that consists of two steps:   He chooses two integers $$$l$$$ and $$$r$$$ such that $$$ 1 \le l \le r \le n $$$ and $$$ r - l + 1 = k $$$.  For each house $$$i$$$ such that $$$l \le i \le r$$$, he can either repaint it with any color he wants, or ignore it and let it keep its current color. Note that in the same day Tom can use different colors to repaint different houses.Tom wants to know the minimum number of days needed to repaint the street so that it becomes beautiful.

Input: The first line of input contains a single integer $$$t$$$ ($$$ 1 \le t \le 10^4$$$), the number of test cases. Description of test cases follows.In the first line of a test case description there are two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).The second line contains $$$n$$$ space-separated integers. The $$$i$$$-th of these integers represents $$$c_i$$$ ($$$1 \le c_i \le 100$$$), the color which house $$$i$$$ is initially painted in.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: Print $$$t$$$ lines, each with one integer: the minimum number of days Tom needs to make the street beautiful for each test case. 

Note: In the first test case Tom should paint houses 1 and 2 in the first day in color 2, houses 5 and 6 in the second day in color 2, and the last house in color 2 on the third day.In the second test case Tom can, for example, spend 6 days to paint houses 1, 2, 4, 5, 6, 7 in color 3.In the third test case Tom can paint the first house in the first day and houses 6, 7, and 8 in the second day in color 3.

Sample Inputs:
3
10 2
1 1 2 2 1 1 2 2 2 1
7 1
1 2 3 4 5 6 7
10 3
1 3 3 3 3 1 2 1 3 3

Sample Outputs:
3
6
2

Solution (Python):
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
import math
import random
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def main():

    def solve():
        (n, k) = map(int, input().split())
        arr = list(map(int, input().split()))
        dist = set(arr)
        ans = math.inf
        for i in dist:
            j = 0
            temp = 0
            while j < n:
                if arr[j] != i:
                    temp += 1
                    j += k
                else:
                    j += 1
            ans = min(ans, temp)
        return ans
    t = int(input())
    for i in range(t):
        print(solve())
BUFSIZE = 8192

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')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    w = list(map(int, input().split()))
    if k == 1:
        print(n - max(Counter(w).values()))
    else:
        (d, m) = (set(w), 10 ** 5)
        for i in d:
            (a, b) = (0, 0)
            while a < n:
                if w[a] != i:
                    a += k
                    b += 1
                else:
                    a += 1
            m = min(m, b)
        print(m)

Solution (Python):
t = int(input())
for i in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    s = set(a)
    l = []
    for i in s:
        j = 0
        c = 0
        while j < n:
            if a[j] != i:
                c = c + 1
                j = j + k
            else:
                j = j + 1
        l.append(c)
    print(min(l))