1806

A_Walking_Master

Explanation

This problem involves a character, YunQian, who can move on a Cartesian coordinate system. She can either move diagonally to the top-right or horizontally to the left. Given her initial position (a, b) and her desired destination (c, d), the task is to determine the minimum number of moves she needs to make to get there, or to state if it's impossible for her to reach that point.

Logic:

The logic to solve the problem is as follows:

If the destination's y-coordinate (d) is less than the starting y-coordinate (b), YunQian can't reach the destination, so output "-1".

If the difference between the destination's x-coordinate (c) and the starting x-coordinate (a) is greater than the difference between the y-coordinates (d-b), YunQian can't reach the destination, so output "-1".

Otherwise, the minimum number of steps is the difference between the y-coordinates (d-b) plus the absolute difference between this value and the difference between the x-coordinates.

Naive Approach:

A naive approach might involve trying to simulate every possible step YunQian could make from the starting point to the end point. However, this would be very inefficient as the number of possible paths can be very large.

def solve():
    a, b, c, d = list(map(int, input().split()))
    if d < b or a + d - b - c < 0:
        print(-1)
    else:
        result = d - b + abs(a + d - b - c)
        print(result)


for _ in range(int(input())):
    solve()

B_Mex_Master

Explanation

This problem involves an array of integers. The score of this array is calculated as follows: you add up each pair of adjacent numbers in the array to create a new array, and then find the MEX (minimum excluded number) of this new array. The MEX is the smallest non-negative integer that is not in the array. Your task is to rearrange the original array in such a way that its score (the MEX of the new array) is minimized.

Logic:

The logic to solve this problem is based on counting the number of zeros in the array and comparing it with the half of the array length. If the number of zeros is equal to the length of the array, the minimum score will be 1. If the number of zeros is less than or equal to half of the array length, the minimum score will be 0. Otherwise, it depends on the maximum number in the array: if it's greater than 1, the minimum score will be 1, otherwise, it will be 2.

Naive Approach:

A naive approach would be to generate all possible permutations of the array and calculate the score for each permutation. However, this approach would be very time-consuming and impractical for large arrays.

from collections import Counter


def solve():
    n = int(input())
    a = list(map(int, input().split()))

    counts = Counter(a)
    zeros = counts[0]
    max_value = max(a)

    if zeros == n:
        print(1)
    elif zeros <= (n + 1) // 2:
        print(0)
    else:
        print(1 if max_value > 1 else 2)


for _ in range(int(input())):
    solve()

C_Sequence_Master

Explanation

The problem requires us to analyze an array with 2n integers and find a new array q which satisfies certain conditions. The conditions are such that for every subsequence of length n in q, the product of the elements in the subsequence is equal to the sum of the remaining elements. We are asked to find the minimum possible "distance" between our original array and this q array. The "distance" is defined as the absolute difference between corresponding elements in the two arrays.

Logic:

We can approach this problem by considering three possible arrays q: an array of zeros, an array of twos (if n=2), and an array with n-1 elements as -1 and one element as n (if n is even). We calculate the "distance" from the original array to each of these possible arrays q and return the smallest distance.

Naive Approach:

A naive approach to this problem would be to generate all possible arrays q, calculate the "distance" to each, and return the minimum distance. This approach would be computationally expensive and impractical for larger inputs.

def solve():
    n = int(input())
    a = sorted(map(int, input().split()))
    res = float("inf")

    if n == 1:
        res = abs(a[0] - a[1])
    else:
        if n == 2:
            res = min(res, sum(abs(x - 2) for x in a))
        if n % 2 == 0:
            res = min(res, sum(abs(x + 1) for x in a[:-1]) + abs(a[-1] - n))
        res = min(res, sum(abs(x) for x in a))

    print(res)


for _ in range(int(input())):
    solve()