E - Hierarchical Majority Vote
Source: atcoder
Difficulty: 450

Problem Statement
For a binary string
B = B_1 B_2 \dots B_{3^n}
of length
3^n
(
n \geq 1
), we define an operation to obtain a binary string
C = C_1 C_2 \dots C_{3^{n-1}}
of length
3^{n-1}
as follows:
Partition the elements of
B
into groups of
3
and take the majority value from each group. That is, for
i=1,2,\dots,3^{n-1}
, let
C_i
be the value that appears most frequently among
B_{3i-2}
,
B_{3i-1}
, and
B_{3i}
.
You are given a binary string
A = A_1 A_2 \dots A_{3^N}
of length
3^N
. Let
A' = A'_1
be the length-
1
string obtained by applying the above operation
N
times to
A
.
Determine the minimum number of elements of
A
that must be changed (from
0
to
1
or from
1
to
0
) in order to change the value of
A'_1
.
Constraints
N
is an integer with
1 \leq N \leq 13
.
A
is a string of length
3^N
consisting of
0
and
1
.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_{3^N}
Output
Print the answer.
Sample Input 1
2
010011101
Sample Output 1
1
For example, with
A=010011101
, after applying the operation twice, we obtain:
First operation: The majority of
010
is
0
, of
011
is
1
, and of
101
is
1
, resulting in
011
.
Second operation: The majority of
011
is
1
, yielding
1
.
To change the final value from
1
to
0
, one way is to change the 5th character of
A
from
1
to
0
, yielding
A=010001101
. After the change, the operations yield:
First operation: The majority of
010
is
0
, of
001
is
0
, and of
101
is
1
, resulting in
001
.
Second operation: The majority of
001
is
0
, yielding
0
.
Thus, the minimum number of changes required is
1
.
Sample Input 2
1
000
Sample Output 2
2

C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;

    // array[0]: the cost of changing the value to `0`
    // array[1]: the cost of changing the value to `1`
    auto calc = [&](auto &&self, int l, int r) -> array<int, 2>
    {
        if (r - l == 1)
        {
            if (s[l] == '0')
            {
                // value = 0
                // the cost of `0` -> `0`: 0
                // the cost of `0` -> `1`: 1
                return {0, 1};
            }
            else
            {
                // value = 1
                // the cost of `1` -> `0`: 1
                // the cost of `1` -> `1`: 0
                return {1, 0};
            }
        }

        int len = r - l;
        int m1 = l + len / 3;
        int m2 = r - len / 3;

        auto a = self(self, l, m1);
        auto b = self(self, m1, m2);
        auto c = self(self, m2, r);

        // we only need to change at most two of three to change the value
        return {min({a[0] + b[0], b[0] + c[0], a[0] + c[0]}), min({a[1] + b[1], b[1] + c[1], a[1] + c[1]})};
    };

    auto ans = calc(calc, 0, s.size());

    cout << max(ans[0], ans[1]) << endl;

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func f(l, r int) (int, int) {
	if l+1 == r {
		return int(a[l] - '0'), 1
	}

	m1 := (2*l + r) / 3
	m2 := (l + 2*r) / 3
	val1, cnt1 := f(l, m1)
	val2, cnt2 := f(m1, m2)
	val3, cnt3 := f(m2, r)

	if val1 == val2 && val2 == val3 {
		return val1, cnt1 + cnt2 + cnt3 - nmax(cnt1, cnt2, cnt3)
	} else if val1 == val2 {
		return val1, min(cnt1, cnt2)
	} else if val1 == val3 {
		return val1, min(cnt1, cnt3)
	} else if val2 == val3 {
		return val2, min(cnt2, cnt3)
	}
	return 0, 0
}

var a string
var N int

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	N = getI()
	a = getS()

	n := 1
	for i := 0; i < N; i++ {
		n *= 3
	}
	_, y := f(0, n)
	out(y)

}

Java solution:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n;
        n = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer tokenizer = new StringTokenizer(bufferedReader.readLine());
        char []bits = tokenizer.nextToken().toCharArray();
        int [][]dp = new int[2][bits.length + 1];
        for(int i = 0; i < bits.length; ++i) {
            dp[0][i] = dp[1][i] = bits[i] == '1' ? 1 : 0;
            if ((i + 1) % 3 == 0) {
                for(int k = 0; k < 2; ++k) {
                    dp[k][i - 2] = Math.min(calc(k, dp[k][i - 1], dp[k][i - 2]), 
                    Math.min(calc(k, dp[k][i], dp[k][i - 1]), calc(k, dp[k][i], dp[k][i - 2])));
                    //System.out.print(dp[k][i] + " ");
                }
                //System.out.println();
            }
        }
        for(int k = 0; k < 2; ++k) {
            for(int i = 1, level = 3; i < n; level *= 3, ++i) {
                for(int j = 0; j < bits.length; j += (3 * level)) {
                    int a = dp[k][j] + dp[k][j + level];
                    int b = dp[k][j] + dp[k][j + 2 * level];
                    int c = dp[k][j + level] + dp[k][j + 2 * level];

                    dp[k][j] = Math.min(a, Math.min(b, c));

                    //System.out.print(dp[k][j] + " ");
                }
                //System.out.println();
            }
        }
        System.out.println(Math.max(dp[1][0], dp[0][0]));
        // System.out.println(dp[1][0]);
    }

    private static int calc(int bit, int a, int b) {
        int count = (a == bit ? 0 : 1) + (b == bit ? 0 : 1);
        return count;
    }
}

JavaScript solution:
const main = function(input) {
    const N = Number(input[0]);
    const An = input[1].trim();
    const arr = [];
    arr[0] = [];
    for (var i = 0; i < 3 ** (N - 1); i++) {
        const a = Number(An[3 * i]);
        const b = Number(An[3 * i + 1]);
        const c = Number(An[3 * i + 2]);
        if (a == b && b == c) {
            arr[0][i] = [a, 2];
        } else {
            arr[0][i] = [a + b + c - 1, 1]
        }
    }
    for (var i = 1; i < N; i++) {
        arr[i] = [];
        for (var k = 0; k < 3 ** (N - i - 1); k++) {
            const a = arr[i - 1][3 * k];
            const b = arr[i - 1][3 * k + 1];
            const c = arr[i - 1][3 * k + 2];
            if (a[0] == b[0] && b[0] == c[0]) {
                arr[i][k] = [a[0], Math.min(a[1] + b[1], b[1] + c[1], c[1] + a[1])];
            } else if (a[0] == b[0]) {
                arr[i][k] = [a[0], Math.min(a[1], b[1])];
            } else if (b[0] == c[0]) {
                arr[i][k] = [b[0], Math.min(b[1], c[1])];
            } else {
                arr[i][k] = [c[0], Math.min(c[1], a[1])];
            }
        }
    }
    console.log(arr[N - 1][0][1])
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));

Python solution:
import sys

sys.setrecursionlimit(10**8)
N = int(input())
A = input()


def func(k, i):
    if k == 0:
        return A[i], 1
    v1, c1 = func(k - 1, 3 * i)
    v2, c2 = func(k - 1, 3 * i + 1)
    v3, c3 = func(k - 1, 3 * i + 2)
    if v1 == v2 == v3:
        return v1, c1 + c2 + c3 - max(c1, c2, c3)
    elif v1 == v2:
        return v1, min(c1, c2)
    elif v2 == v3:
        return v2, min(c2, c3)
    elif v3 == v1:
        return v3, min(c3, c1)


print(func(N, 0)[1])

Ruby solution:
END { load __FILE__ unless $stdin.eof? }

n = gets.to_i
a = gets.chomp.bytes.map! { |b| b - 0x30 }

b0 = a.dup             # change to 0
b1 = a.map { _1 ^ 1 }  # change to 1

n3 = 3**n
n.times do
  n3 /= 3
  na = Array.new(n3)
  nb0 = Array.new(n3)
  nb1 = Array.new(n3)

  n3.times do |i|
    v = a[i*3,3]
    vote = v.sum
    na[i] = vote / 2

    case vote
    when 0
      nb0[i] = 0
      nb1[i] = b1[i*3,3].then { |b| b.sum - b.max }
    when 1
      nb0[i] = 0
      nb1[i] = (
        x = 1_000_000_000
        x = b1[i*3+0] if v[0] == 0 && b1[i*3+0] < x
        x = b1[i*3+1] if v[1] == 0 && b1[i*3+1] < x
        x = b1[i*3+2] if v[2] == 0 && b1[i*3+2] < x
        x
      )
    when 2
      nb0[i] = (
        x = 1_000_000_000
        x = b0[i*3+0] if v[0] == 1 && b0[i*3+0] < x
        x = b0[i*3+1] if v[1] == 1 && b0[i*3+1] < x
        x = b0[i*3+2] if v[2] == 1 && b0[i*3+2] < x
        x
      )
      nb1[i] = 0
    else
      nb0[i] = b0[i*3,3].then { |b| b.sum - b.max }
      nb1[i] = 0
    end
  end

  a = na
  b0 = nb0
  b1 = nb1
end

puts a[0] == 0 ? b1[0] : b0[0]

__END__