20240507

1869A. Make It Zero

My friend once talked about his recent interview, where he was asked to utilize the fact that XOR turns bits off if they have the same value.

I forgot the exact problem he mentioned, but as I recall, the problem might be

• You are given a sequence of integers. Count the bits where their occurance count are odd for the given numbers.

The optimal answer for that problem is to calculate the XOR of all numbers, and the resulting number only contains bits with odd occurrences.

The memory guided me to the idea

s XOR s XOR s XOR ... = 0 when the count of s is even

solution

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

// > Note that you do not have to minimize k.
// > If there are multiple solutions, you may output any of them.

// It's known that XOR of the same numbers results in 0
// <=> If all the counts of elements in a sequence are even, XOR of all elements is 0

// 1. The number of elements is even
//  1. replace all elements (1 <= i <= n) with s (The number of s does not matter).
//  2. replace all elements (1 <= i <= n) with 0. s XOR s XOR, ... = 0 because all elements can find a pair to make 0

// 2. The number of elements is odd (thinking about leveraging the "even" case)
//  1, 2. replace elements (2 <= i <= n) with 0, used the operations mentioned above
//  3. replace first two elements with s e.g., [3, 0, 0, ...] => [3, 3, 0, 0, ...]
//  4. replace first two elements with 0. s XOR s = 0

// This approach does not exceed the cap "8 operations in total"

func solve(n int, a []int) {
    if n%2 == 0 {
        fmt.Println(2)
        fmt.Println(1, n)
        fmt.Println(1, n)
    } else {
        fmt.Println(4)
        fmt.Println(2, n)
        fmt.Println(2, n)
        fmt.Println(1, 2)
        fmt.Println(1, 2)
    }
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    scanner.Scan()
    t, _ := strconv.Atoi(scanner.Text())

    for tc := 0; tc < t; tc++ {
        scanner.Scan()
        n, _ := strconv.Atoi(scanner.Text())

        a := make([]int, n)
        scanner.Scan()
        for i, aStr := range strings.Split(scanner.Text(), " ") {
            ai, _ := strconv.Atoi(aStr)
            a[i] = ai
        }

        solve(n, a)
    }
}

1954A. Painting the Ribbon

package main

import (
    "fmt"
)

// My thoughts
// Alice's optimal approach is to paint the ribbon with all colors and as evenly as possible.
// With the ribbon painted, we can split the ribbon into two parts, a color with the largest count (a) and the remaining (b).
// If Bob can paint the (b) part with color (a), Alice won't be satisfied.
// <=> If the (b) part is larger than k, Aliec won't complain.

func canSatisfyAlice(n int, m int, k int) bool {
    if n%m == 0 {
        return n-n/m > k
    } else {
        return n-(n/m+1) > k
    }
}

func main() {
    var t int
    fmt.Scan(&t)

    for tc := 0; tc < t; tc++ {
        var n, m, k int
        fmt.Scan(&n, &m, &k)
        if canSatisfyAlice(n, m, k) {
            fmt.Println("YES")
        } else {
            fmt.Println("NO")
        }
    }
}

TODO: Understand the editorial

Kombucha 100 Snacks 200 Avocado rolls 300 Sushi bowl 600 Chips 500 Yogurt 200

Total 1900 kcal

index 20240506 20240508