Brukhovich and Exams (Codeforces 1891E)
Tags: Math, sortings

The boy Smilo is learning algorithms with a teacher named Brukhovich.Over the course of the year, Brukhovich will administer $$$n$$$ exams. For each exam, its difficulty $$$a_i$$$ is known, which is a non-negative integer.Smilo doesn't like when the greatest common divisor of the difficulties of two consecutive exams is equal to $$$1$$$. Therefore, he considers the sadness of the academic year to be the number of such pairs of exams. More formally, the sadness is the number of indices $$$i$$$ ($$$1 \leq i \leq n - 1$$$) such that $$$gcd(a_i, a_{i+1}) = 1$$$, where $$$gcd(x, y)$$$ is the greatest common divisor of integers $$$x$$$ and $$$y$$$.Brukhovich wants to minimize the sadness of the year of Smilo. To do this, he can set the difficulty of any exam to $$$0$$$. However, Brukhovich doesn't want to make his students' lives too easy. Therefore, he will perform this action no more than $$$k$$$ times.Help Smilo determine the minimum sadness that Brukhovich can achieve if he performs no more than $$$k$$$ operations.As a reminder, the greatest common divisor (GCD) of two non-negative integers $$$x$$$ and $$$y$$$ is the maximum integer that is a divisor of both $$$x$$$ and $$$y$$$ and is denoted as $$$gcd(x, y)$$$. In particular, $$$gcd(x, 0) = gcd(0, x) = x$$$ for any non-negative integer $$$x$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The descriptions of the test cases follow.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 10^5$$$) — the total number of exams and the maximum number of exams that can be simplified, respectively. The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ — the elements of array $$$a$$$, which are the difficulties of the exams ($$$0 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output: For each test case, output the minimum possible sadness that can be achieved by performing no more than $$$k$$$ operations.

Note: In the first test case, a sadness of $$$1$$$ can be achieved. To this, you can simplify the second and fourth exams. After this, there will be only one pair of adjacent exams with a greatest common divisor (GCD) equal to one, which is the first and second exams.In the second test case, a sadness of $$$0$$$ can be achieved by simplifying the second and fourth exams.

Sample Inputs:
9
5 2
1 3 5 7 9
5 2
3 5 7 9 11
8 2
17 15 10 1 1 5 14 8
5 3
1 1 1 1 1
5 5
1 1 1 1 1
19 7
1 1 2 3 4 5 5 6 6 7 8 9 10 1 1 1 2 3 1
15 6
2 1 1 1 1 2 1 1 2 1 1 1 2 1 2
5 2
1 1 1 1 2
5 2
1 0 1 0 1

Sample Outputs:
1
0
2
2
0
5
5
2
1

Solution (Python):
import sys
import heapq
import math

def solute():
    (n, k) = map(int, sys.stdin.readline().strip().split())
    a_list = list(map(int, sys.stdin.readline().split()))

    def coprime(a, b):
        return math.gcd(a, b) == 1
    con_pairs = []
    con_ones = []
    special_con_ones = []
    curr = 0
    prev = 1
    con_one = 0
    (divs, rems) = (0, 0)
    for (i, num) in enumerate(a_list):
        if con_one:
            if num == 1:
                con_one += 1
                continue
            else:
                con_ones.append(con_one)
                con_one = 0
                prev = num
                continue
        if num == 1:
            con_one = 1
            if curr:
                con_pairs.append(curr)
                curr = 0
            prev = 1
            continue
        if i == 0:
            prev = num
            continue
        if coprime(num, prev):
            curr += 1
        else:
            if curr:
                con_pairs.append(curr)
            curr = 0
        prev = num
    if curr:
        con_pairs.append(curr)
    if con_one:
        rems += con_one
        if all((num == 1 for num in a_list)):
            return max(0, con_one - k)
    if a_list[0] == 1:
        rems += con_ones.pop(0)
    con_ones.sort()
    special_con_ones.sort()
    ans = 0
    divs += sum((i >> 1 for i in con_pairs))
    rems += sum((i & 1 for i in con_pairs))
    r_divs = min(divs, k)
    divs -= r_divs
    k -= r_divs
    for i in range(len(con_ones)):
        if k >= con_ones[i]:
            k -= con_ones[i]
        else:
            ans += con_ones[i] + 1
    r_rems = min(rems, k)
    rems -= r_rems
    k -= r_rems
    ans = ans + 2 * divs + rems
    if ans and k:
        ans = max(0, ans - k)
    return ans
t = int(sys.stdin.readline())
for _ in range(t):
    print(solute())

Solution (Python):
import sys
import heapq
import math

def solute():
    (n, k) = map(int, sys.stdin.readline().strip().split())
    a_list = list(map(int, sys.stdin.readline().split()))

    def coprime(a, b):
        return math.gcd(a, b) == 1
    con_pairs = []
    con_ones = []
    special_con_ones = []
    curr = 0
    prev = 1
    con_one = 0
    (divs, rems) = (0, 0)
    for (i, num) in enumerate(a_list):
        if con_one:
            if num == 1:
                con_one += 1
                continue
            else:
                con_ones.append(con_one)
                con_one = 0
                prev = num
                continue
        if num == 1:
            con_one = 1
            if curr:
                con_pairs.append(curr)
                curr = 0
            prev = 1
            continue
        if i == 0:
            prev = num
            continue
        if coprime(num, prev):
            curr += 1
        else:
            if curr:
                con_pairs.append(curr)
            curr = 0
        prev = num
    if curr:
        con_pairs.append(curr)
    if con_one:
        rems += con_one
        if all((num == 1 for num in a_list)):
            return max(0, con_one - k)
    if a_list[0] == 1:
        rems += con_ones.pop(0)
    con_ones.sort()
    special_con_ones.sort()
    ans = 0
    divs += sum((i >> 1 for i in con_pairs))
    rems += sum((i & 1 for i in con_pairs))
    r_divs = min(divs, k)
    divs -= r_divs
    k -= r_divs
    for i in range(len(con_ones)):
        if k >= con_ones[i]:
            k -= con_ones[i]
        else:
            ans += con_ones[i] + 1
    r_rems = min(rems, k)
    rems -= r_rems
    k -= r_rems
    ans = ans + 2 * divs + rems
    if ans and k:
        ans = max(0, ans - k)
    return ans
t = int(sys.stdin.readline())
for _ in range(t):
    print(solute())

Solution (Python):
from math import gcd
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    s = p = f = l = 0
    arr = []
    for i in range(n - 1):
        if gcd(a[i], a[i + 1]) == 1:
            s += 1
            if p == 2 and a[i + 1] != 1 and k:
                (s, k, p) = (s - 2, k - 1, 0)
            elif a[i] == 1:
                if p == 1:
                    arr[-1] += 1
                else:
                    p = 1
                    arr.append(1)
            else:
                p = 2
        else:
            p = 0
    if a[-2:] == [1, 1]:
        if arr.pop() + 1 == n and k < n:
            s += 1
    if arr != [] and a[0] == 1:
        arr.pop(0)
    arr.sort()
    for i in arr:
        if k < i:
            break
        s -= i + 1
        k -= i
    print(max(0, s - k))