Congratulations ChatGPT for obtaining a total score of $602$ out of $600$ in SEATST! Here is its distribution:↵
↵
Day 1: $100 + 100 + 100 = 300$↵
↵
Day 2: $102 + 100 + 100 = 302$↵
↵
# Explanation↵
↵
ChatGPT managed to solve [BugabooProblem 2A: Triple Circuit](https://tlx.toki.id/bugabooproblems/seatst-2026/2A) using just $213$ logic gates (you needed to use $\leq 215$ logic gates to obtain full score). If we use the scoring function $f(K) = 1 - 0.40 \times \frac{K - 215}{41}$ (since no one expected $K < 215$ to be within the domain of $f$), this gives $f(213) = 1.0195$, which is a score of $102$ (TLX rounds scores to the nearest integer).↵
↵
<spoiler summary="ChatGPT's solution">↵
First pair the $128$ bits into $64$ pairs and calculate the OR of each pair. If there is an anomaly, at least $2$ pairs will have an OR of $1$.↵
↵
Construct a tripartite graph, where the three parts have sizes $4$, $5$ and $5$ respectively. Call the parts $A$, $B$, $C$. This graph has a total of $4 \times 5 + 4 \times 5 + 5 \times 5 = 65$ edges. Assign each bit to one of these edges, so there is $1$ unused edge.↵
↵
For each vertex, calculate the OR of all edges that include it. Define a vertex to be active if this OR is equal to $1$. Then, we either have:↵
↵
- All three parts have active nodes, or↵
- There exists a part with two active nodes↵
↵
if and only if there is an anomaly.↵
↵
Given a part with $X$ nodes, we can check both:↵
↵
- whether it has an active node↵
- whether it has $\geq 2$ active nodes↵
↵
using $3X - 4$ operations as follows. Suppose the nodes are $A_1, A_2, \cdots, A_X$.↵
↵
1. Calculate $P_i = A_1 \bigvee A_2 \bigvee \cdots \bigvee A_i$. This can be done by letting $P_1 = A_1$ and $P_i = P_{i-1} \bigvee A_i$. Note $P_X$ is $1$ if and only if there is at least one active node.↵
↵
2. Calculate $P_i \bigwedge A_{i+1}$ for each $1 \leq i < X$. Note that if the component has at least two active nodes, $P_i \bigwedge A_{i+1} = 1$ for some $i$.↵
↵
3. Take the OR of these $X-1$ values.↵
↵
Step $1$ requires $X-1$ gates, step $2$ requires $X-1$, and step $3$ requires $X-2$ gates, for a total of $3X - 4$.↵
↵
Overall, we need:↵
↵
- $64$ gates to compute the ORs of pairs↵
- $\sum_{\text{node } v} (\text{deg}(v) - 1) = 2 E - V = 2 \times 64 - 14 = 114$ gates to compute whether each node is active↵
- $3 \times |A| - 4 = 8$ gates to compute $f_A$, which is $1$ if $A$ has at least one active node, and $g_A$, which is $1$ if $A$ has at least two active nodes↵
- $3 \times |B| - 4 = 11$ and $3 \times |C| - 4 = 11$ gates to do the same for $B$ and $C$↵
- $5$ gates for the expression $g_A \bigvee g_B \bigvee g_C \bigvee (f_A \bigwedge f_B \bigwedge f_C)$↵
↵
Which adds up to $64 + 114 + 8 + 11 + 11 + 5 = 213$ gates.↵
↵
Once again, congratulations ChatGPT!↵
</spoiler>↵
↵
↵
Day 1: $100 + 100 + 100 = 300$↵
↵
Day 2: $102 + 100 + 100 = 302$↵
↵
# Explanation↵
↵
ChatGPT managed to solve [
↵
<spoiler summary="ChatGPT's solution">↵
First pair the $128$ bits into $64$ pairs and calculate the OR of each pair. If there is an anomaly, at least $2$ pairs will have an OR of $1$.↵
↵
Construct a tripartite graph, where the three parts have sizes $4$, $5$ and $5$ respectively. Call the parts $A$, $B$, $C$. This graph has a total of $4 \times 5 + 4 \times 5 + 5 \times 5 = 65$ edges. Assign each bit to one of these edges, so there is $1$ unused edge.↵
↵
For each vertex, calculate the OR of all edges that include it. Define a vertex to be active if this OR is equal to $1$. Then, we either have:↵
↵
- All three parts have active nodes, or↵
- There exists a part with two active nodes↵
↵
if and only if there is an anomaly.↵
↵
Given a part with $X$ nodes, we can check both:↵
↵
- whether it has an active node↵
- whether it has $\geq 2$ active nodes↵
↵
using $3X - 4$ operations as follows. Suppose the nodes are $A_1, A_2, \cdots, A_X$.↵
↵
1. Calculate $P_i = A_1 \bigvee A_2 \bigvee \cdots \bigvee A_i$. This can be done by letting $P_1 = A_1$ and $P_i = P_{i-1} \bigvee A_i$. Note $P_X$ is $1$ if and only if there is at least one active node.↵
↵
2. Calculate $P_i \bigwedge A_{i+1}$ for each $1 \leq i < X$. Note that if the component has at least two active nodes, $P_i \bigwedge A_{i+1} = 1$ for some $i$.↵
↵
3. Take the OR of these $X-1$ values.↵
↵
Step $1$ requires $X-1$ gates, step $2$ requires $X-1$, and step $3$ requires $X-2$ gates, for a total of $3X - 4$.↵
↵
Overall, we need:↵
↵
- $64$ gates to compute the ORs of pairs↵
- $\sum_{\text{node } v} (\text{deg}(v) - 1) = 2 E - V = 2 \times 64 - 14 = 114$ gates to compute whether each node is active↵
- $3 \times |A| - 4 = 8$ gates to compute $f_A$, which is $1$ if $A$ has at least one active node, and $g_A$, which is $1$ if $A$ has at least two active nodes↵
- $3 \times |B| - 4 = 11$ and $3 \times |C| - 4 = 11$ gates to do the same for $B$ and $C$↵
- $5$ gates for the expression $g_A \bigvee g_B \bigvee g_C \bigvee (f_A \bigwedge f_B \bigwedge f_C)$↵
↵
Which adds up to $64 + 114 + 8 + 11 + 11 + 5 = 213$ gates.↵
↵
Once again, congratulations ChatGPT!↵
</spoiler>↵
↵
