Submission Code How many moves are needed in the vertical and horizontal directions respectively. Vertical Direction Simply moving downward, so it takes $k$ moves. Horizontal Direction Let $a_x$ be the information about where you originally came from when you moved to cell $x$. In other words, you start from $a_x$ in the 1st row and move to $x$ in the $k$-th row. For each $k$, think of starting from one of the cells in the forbidden area and moving to $b_i+1$....

Submitted Code After watching the explanation broadcast, I understood the approach, but it took a while from there. I think this is a problem with relatively heavy implementation. Consider dividing the answer palindrome LR into string L and string R. Initialize both as empty strings. When adding $s_i$, add it to the right side of L or to the left side of R. Suppose after adding $s_i$ several times, we have L="abcde" and R="cba"....

Submission It was a red difficulty problem. Reading the problem statement made it seem approachable, but it wasn’t that simple. First, I considered an $O(N^3)$ DP, then approached it by reducing the computational complexity based on that. We look at $i = 2, 5, 8, 11, \dots$ at intervals of 3 characters. Let dp[i][x][y] be the maximum score when we’ve examined up to the $i$-th position and the previous two characters are $x$ and $y$....

Submitted Code If $n \ge 4$ and $m \ge 4$, it’s impossible to satisfy condition A (the number of 1s contained in a square with even vertical and horizontal lengths is odd). For example, when a $2 \times 2$ square satisfies condition A, if you connect four such squares, the sum becomes even. That is, a $4 \times 4$ square cannot satisfy condition A. In all other cases, you can always satisfy condition A by performing operations several times....

It’s sufficiently mature and rarely causes trouble, but since it’s a technology that will continue to be used, knowing its behavior is meaningful. Full Virtualization and Paravirtualization of NICs A quick review. Full virtualization is a type of virtualization where the guest itself cannot recognize that it is running in a virtual environment. The host needs to completely emulate the behavior of devices used by the guest. To emulate devices, a large number of traps occur, and the CPU is used for host-side processing....

I purchased Ubiquiti Networks’ router EdgeRouter X (ER-X) a few years ago but left it unused, so this time I tried using it as an L2 switch. Since ER-X runs on a Debian-based OS, monitoring programs like Node exporter for Prometheus can be used. Prometheus itself was run on a Raspberry Pi. I wanted to run ElastiFlow too, but it seemed too demanding for the Raspberry Pi’s specs. Installing Prometheus and Grafana Install Prometheus and Grafana on the Raspberry Pi....

Submitted Code Given a string $t$, we want to make the string after cyclic left shift and cyclic right shift equal. When removing some characters from $t$ to satisfy this condition, what is the minimum number of characters to remove? Let $n$ be the length of string $t$, and consider separately for even and odd cases. When $n$ is odd Take $t = t_1 t_2 t_3 t_4 t_5$ as an example....

I tried https://github.com/kelseyhightower/kubernetes-the-hard-way on QEMU/KVM, so I’ll leave a log here. The original text assumes GCP, but this time I built it on local QEMU/KVM. Version List kubernetes-the-hard-way bf2850974e19c118d04fdc0809ce2ae8a0026a27 Kubernetes 1.12.0 containerd Container Runtime 1.2.0-rc.0 gVisor 50c283b9f56bb7200938d9e207355f05f79f0d17 CNI Container Networking 0.6.0 etcd v3.3.9 CoreDNS v1.2.2 1. Preparation Until getting the VM image and starting it. # Prepare VM image $ http_dir=http://ftp.jaist.ac.jp/pub/Linux/Fedora/releases/30/Cloud/x86_64/images $ wget $http_dir/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 $ virt-customize -a /var/lib/libvirt/images/Fedora-Cloud-Base-30-1.2.x86_64.qcow2 \ --run-command 'yum remove cloud-init* -y' \ --root-password password:root $ cd /var/lib/libvirt/images/ $ for i in 0 1 2 ; do \ sudo cp ....

Submitted Code Given an integer $a \ge 2$, we want to find a pair $(d_1, d_2)$ that satisfies $gcd(d_1+d_2, a)=1$. However, $d_1 \ge 2$ and $d_2 \ge 2$. Repeat this $n$ times. First, perform prime factorization as $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$. If $m = 1$ or $a$ is prime, the answer is $(-1, -1)$. If $m \ge 2$, the answer is $(p_1, p_2 \cdot p_3 \cdots p_m)$....

Submitted Code Focus on the fact that in a tree, “number of connected components = number of vertices - number of edges”. Intuitively, it can be understood as: when vertices increase, the number of connected components increases by 1, and when edges increase, the number of connected components decreases by 1. $f(L, R)$ can also be found using this. $$ \begin{aligned} &f(L, R) \\ &= Number of points contained in interval [L \ R] \\ &- Number of edges with both endpoints in interval [L \ R] \\ \end{aligned} $$...

Submitted Code Failed on test case after_contest01.txt added after the contest. Since I passed everything else on my own, my consideration was insufficient. First, divide into cases (A) where the answer is negative and (B) where the answer is non-negative. For (A), greedily take in order of smallest absolute value. Let’s think about case (B). First, prepare two queues. Non-negative values sorted in descending order (e.g., 9 6 5 2 1 0 0) Negative values sorted in ascending order (e....

Submitted Code As prerequisite knowledge, it’s good to know that this is a game called Nim. Nim has a winning strategy: take XOR of the number of stones in all piles $A_i$, and if the result is anything other than 0, the person whose turn it is can always win with optimal moves. When your turn comes in a winning state with XOR != 0, by cleverly removing a certain number of stones from a certain pile, you can transition to a state with XOR = 0....

Notes on Towards a more Scalable KVM Hypervisor presented at KVM FORUM 2018. [PATCH v8 0/4] KVM: X86: Add Paravirt TLB Shootdown Guest OSes are affected by the host OS scheduler during OS-level synchronization mechanisms such as TLB shoot down and RCU processing. Operations that would complete immediately in a bare-metal environment cannot ignore delays in a virtual environment. TLB (Translation Lookaside Buffer) is used to cache mappings between virtual memory addresses and physical memory addresses....

After playing Civilization VI once with a friend, it seems I won’t be able to win as is, so I’ll do some research. This game is a series of choices, so if you proceed casually without knowing the mechanism, it seems difficult to win. This is just notes that a beginner is writing for themselves, so please understand. If you want to know more details, please see CIVILIZATION VI wiki....

Submitted Code Looking at the explanations, it seems that if we think of inserting alphabets arbitrarily $K$ times and consider the positions of each character in $S$ as fixed in a string of length $N+K$, it works well. Thinking that way, we just need to consider how to insert $K$ characters in a string of length $N+K$. Let’s think using Example Input 1. S = “oof” N = len(“oof”) = 3 K = 5 For example, place ‘o’ at position 1, ‘o’ at position 3, and ‘f’ at position 5....

Submitted Code I think reflecting after solving is important. Find the shortest path from the start position to the goal position on a 2D plane. However, there are some blocks on the plane, and those cells cannot be passed through. Furthermore, in one move, you can advance an arbitrary number of cells from $1 … K$ in the same direction. Consider the graph with vertices as $(y, x, dir)$ and calculate the shortest path using Dijkstra’s algorithm....

I completed all problems in EDPC. This is a miscellaneous memo, not a cleanly organized solution guide. W - intervals Let $dp_i$ be the final score when some bits are set to 1 and the rightmost 1 is at position $i$. Here, $dp_i$ can be calculated as the sum of $ max_{j=0 … i-1} dp_j$ and the score obtained when setting the $i$-th character to 1. Let $block_i$ be the set of blocks whose right end $r$ is $i$....

I read Linux Observability with BPF, so I’ll leave some notes. This month, Brendan Gregg’s BPF book is also coming out, so I’d like to read that too. Using BPF allows hooking kernel events and safely executing code BPF verifies that the code won’t destroy or crash the system Unlike kernel modules, BPF programs don’t require kernel recompilation After BPF code is verified, BPF bytecode is JIT-compiled to machine instructions BPF programs are loaded into the BPF VM by the bpf syscall Alexei Starovoitov introduced eBPF in early 2014 Old BPF only allowed 2 32-bit registers, but eBPF allows up to 10 64-bit registers In June 2014, eBPF was also extended to user space BPF program types: Can be broadly classified into tracing and networking Socket Filter: First program type to enter the kernel....

I read Kubernetes Complete Guide and will leave some notes here. I’m summarizing commands and mechanisms that I wasn’t usually conscious of. If you want to create small images, base them on scratch or alpine When both ENTRYPOINT and CMD are set, $ENTRYPOINT $CMD is executed Multi-stage build: You can process only in a build-specific container and copy the artifacts to an execution-specific container CNCF sets project maturity in three stages: “Graduated”, “Incubating”, and “Sandbox” When building on-premises, instance sizes on AWS or GCP can be used as a guide Flannel: Configures an overlay network between nodes There is a kubernetes playground provided by Docker, Inc....

I managed to get the USB wireless LAN adapter TP-Link Archer T3U AC1300 working on a Thinkpad X1 Carbon 2015 (Fedora release 29 (Twenty Nine), linux 5.3.6-100.fc29.x86_64), so I’m documenting the procedure. # The official website didn't distribute drivers, so I used rtl88x2bu git clone https://github.com/cilynx/rtl88x2bu cd rtl88x2bu/ git rev-parse HEAD # 962cd6b1660d3dae996f0bde545f641372c28e12 VER=$(sed -n 's/\PACKAGE_VERSION="\(.*\)"/\1/p' dkms.conf) sudo rsync -rvhP ./ /usr/src/rtl88x2bu-${VER} # Move to /usr/src/<module_name>_<module_version> and manage with dkms sudo dkms add -m rtl88x2bu -v ${VER} sudo dkms build -m rtl88x2bu -v ${VER} sudo dkms install -m rtl88x2bu -v ${VER} sudo dkms status sudo modprobe 88x2bu When connecting two types of adapters (onboard adapter and TP-Link adapter) to the same network, priority is determined by metric....