โมบาย: ยุบกิ่งทั้งกิ่งให้เหลือป้ายสามแบบ จนไม่เหลือทางให้ตัดสินใจผิด

ตั้งชื่อชั้นลึกที่สุดของของเล่นทั้งโมบายว่า D จากตอนที่แล้วเรารู้แล้วว่าถ้าจะมีคำตอบ ของเล่นทุกชิ้นต้องอยู่ที่ชั้น D หรือชั้น D - 1 เท่านั้น ทีนี้กิ่งที่ผ่านเงื่อนไขของไอค์แล้ว มีหน้าตาได้แค่สามแบบ

• เต็มลึก ของเล่นในกิ่งนี้อยู่ชั้น D ทุกชิ้น มันเป็นกิ่งที่แน่นเต็มถึงชั้นล่างสุด
• เต็มตื้น ของเล่นในกิ่งนี้อยู่ชั้น D - 1 ทุกชิ้น มันเป็นกิ่งที่จบก่อนหนึ่งชั้น
• ครึ่ง ในกิ่งนี้มีทั้งของชั้น D และชั้น D - 1 ปนกัน โดยของลึกอยู่ซ้ายของของตื้นเรียบร้อยแล้ว

ที่มันมีแค่สามแบบเพราะมีแค่สองชั้นให้เลือก กิ่งหนึ่งจะมีของชั้นลึกอย่างเดียว ชั้นตื้นอย่างเดียว หรือมีทั้งสอง ไม่มีทางเลือกที่สี่ และของเล่นหนึ่งชิ้นก็นับเป็นกิ่งเล็กที่สุด ถ้ามันอยู่ชั้น D มันคือเต็มลึก ถ้าอยู่ชั้น D - 1 มันคือเต็มตื้น

ประเด็นสำคัญคือเรารู้แค่ป้ายสามแบบนี้ก็พอ ไม่ต้องรู้เลยว่าข้างในกิ่งมีแกนกี่อันหรือหน้าตายังไง เพราะสิ่งเดียวที่แกนด้านบนต้องตัดสินใจคือ "เอากิ่งไหนไว้ซ้าย" ซึ่งขึ้นกับป้ายเท่านั้น

แล้วเงื่อนไข "ของลึกอยู่ทางซ้าย" ก็แปลเป็นลำดับของป้ายได้ตรง ๆ เต็มลึกต้องอยู่ซ้ายสุด เต็มตื้นต้องอยู่ขวาสุด ส่วนครึ่งอยู่ตรงกลาง เขียนเป็นลำดับได้ว่า เต็มลึก ก่อน ครึ่ง ก่อน เต็มตื้น

แกนหนึ่งอันเห็นป้ายของกิ่งซ้ายกับกิ่งขวา รวมเป็นเก้าคู่ ไล่ให้ครบแล้วจะเห็นว่าแทบทุกคู่บังคับคำตอบมาให้แล้ว ไม่ใช่ปัญหาที่ต้องเลือก

อ่านตารางนี้ทีเดียวได้กฎสามข้อ ข้อแรก ถ้าทั้งสองข้างเป็นครึ่ง จบเลย ตอบ -1 ข้อสอง ถ้าป้ายเรียงผิดลำดับ ก็สลับหนึ่งครั้ง ไม่มีทางเลือกอื่น ข้อสาม ป้ายของแกนนี้คือเต็มลึกเมื่อลูกเป็นเต็มลึกทั้งคู่ เต็มตื้นเมื่อลูกเป็นเต็มตื้นทั้งคู่ นอกนั้นเป็นครึ่ง

เพราะทุกช่องในตารางบังคับมาให้หมด จึงไม่มีการเลือกที่ผิดพลาดได้เลย จำนวนครั้งที่สลับจึงไม่ใช่ค่าที่ต้องไปหา ค่าที่น้อยที่สุด มันเป็นค่าเดียวที่เป็นไปได้ นับไปตามทางแล้วได้เท่าไรก็คือคำตอบ

สังเกตรูปของวิธีนี้ให้ดี เพราะมันมีสองท่าที่จะเจอซ้ำไปทั้งคลัง ท่าแรกคือเราตัดสินใจที่แกนหนึ่งอัน โดยดูแค่ป้ายของลูกสองกิ่ง ไม่มองไปข้างหน้าและไม่ย้อนกลับมาแก้ การตัดสินใจแบบเห็นอะไรดีตรงหน้าก็เอาเลย เรียกว่าท่าโลภ (greedy) ท่าที่สองคือลำดับที่เราเดิน คือต้องรู้ป้ายของลูกให้ครบก่อนจึงตัดสินใจที่พ่อได้ การไล่ลงไปให้สุดก่อนแล้วค่อยเก็บผลย้อนขึ้นมาแบบนี้เรียกว่าการไล่ลึก (DFS) โครงสร้างที่เราไล่อยู่ก็คือต้นไม้ ที่มีแกนบนสุดเป็นราก

เดินตารางนี้จากล่างขึ้นบนกับตัวอย่างในโจทย์ ได้ผลตามนี้ (ชั้นลึกที่สุดของตัวอย่างคือ D = 3)

เงื่อนไข "ครึ่งประกบครึ่ง" ในตารางไม่ใช่ของประดับ มันเกิดขึ้นจริงได้ และเกิดกับโมบายที่ผ่านการตรวจชั้นตั้งแต่ต้นมาแล้วด้วย ตัวอย่างข้างล่างมีของเล่น 6 ชิ้น ชั้นของมันคือ 2 3 3 2 3 3 ซึ่งอยู่แค่สองชั้นติดกัน ผ่านเงื่อนไขข้อแรกสบาย ๆ

กิ่งซ้ายของแกน 1 เป็นครึ่ง กิ่งขวาก็เป็นครึ่ง สลับยังไงก็ยังมีของชั้นตื้นของกิ่งหนึ่งไปยืนคั่นหน้าของชั้นลึกของอีกกิ่งอยู่ดี โปรแกรมจึงตอบ -1 ทั้งที่ตรวจชั้นตอนต้นผ่านฉลุย นี่คือเหตุผลที่การเช็กชั้น อย่างเดียวไม่พอ ต้องเดินตารางจนถึงแกนบนสุดจริง ๆ

ทั้งข้อคือสามบรรทัดนี้ วนบนทุกแกนจากล่างขึ้นบน อ่านป้ายของลูกสองข้าง แล้วทำตามตาราง

if (a == 1 && b == 1) { bad = true; break; }   // ครึ่งสองอันประกบกันไม่ได้
if (a > b) { cost++; swap(a, b); }             // ลำดับที่ถูกคือ เต็มลึก ครึ่ง เต็มตื้น
shape[v] = (a == 0 && b == 0) ? 0 : (a == 2 && b == 2) ? 2 : 1;

กับดักที่ทำให้โค้ดถูกแต่ตกรอบคือความลึกของการเรียกซ้ำ โจทย์ไม่ได้รับประกันว่าโมบายจะสมดุล อินพุตที่แกนแต่ละอันมีแกนลูกข้างเดียวยาวติดกันหนึ่งแสนอันเป็นอินพุตที่ถูกกติกาทุกประการ ถ้าเขียนเป็นฟังก์ชันเรียกตัวเอง สแต็กจะล้นก่อนได้คำตอบ ที่นี่จึงเดินด้วยสแต็กที่ประกาศเอง แล้วเก็บลำดับที่พ่ออยู่ก่อนลูกไว้ใน order พออ่านย้อนกลับก็ได้ลูกก่อนพ่อพอดี

อีกจุดที่ต้องอ่านให้ครบคือ -1 มีสองที่มา ที่แรกคือชั้นของของเล่นห่างกันเกินหนึ่งชั้น ซึ่งตรวจได้ก่อนเริ่มเลย ที่สองคือครึ่งประกบครึ่งระหว่างทาง ซึ่งรู้ตอนเดินไปแล้วเท่านั้น โค้ดที่ตรวจแค่ที่แรกจะผ่านตัวอย่างในโจทย์ แล้วไปตกกับเทสที่ซ่อนไว้

#include <bits/stdc++.h>
using namespace std;

int n;
int L[100005], R[100005], dep[100005];
int shape[100005];      // 0 = เต็มลึก, 1 = ครึ่ง, 2 = เต็มตื้น

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &L[i], &R[i]);

    // เดินหาความลึกด้วยสแต็กของตัวเอง ไม่ใช้การเรียกซ้ำ เพราะโมบายอาจลึกถึงแสนชั้น
    vector<int> order;
    order.reserve(n);
    {
        vector<int> st{1};
        dep[1] = 0;
        while (!st.empty()) {
            int v = st.back(); st.pop_back();
            order.push_back(v);
            if (L[v] != -1) { dep[L[v]] = dep[v] + 1; st.push_back(L[v]); }
            if (R[v] != -1) { dep[R[v]] = dep[v] + 1; st.push_back(R[v]); }
        }
    }

    // ชั้นของของเล่นเปลี่ยนไม่ได้ ถ้ามันห่างกันเกินหนึ่งชั้นก็จบตั้งแต่ยังไม่เริ่ม
    int deep = 0, shallow = INT_MAX;
    for (int i = 1; i <= n; i++)
        if (L[i] == -1 || R[i] == -1) {
            deep = max(deep, dep[i] + 1);
            shallow = min(shallow, dep[i] + 1);
        }
    if (deep - shallow > 1) { puts("-1"); return 0; }

    // order เป็นลำดับที่พ่ออยู่ก่อนลูกเสมอ อ่านย้อนกลับจึงได้ลูกก่อนพ่อ
    long long cost = 0;
    bool bad = false;
    for (int idx = (int)order.size() - 1; idx >= 0 && !bad; idx--) {
        int v = order[idx];
        int a = (L[v] == -1) ? (dep[v] + 1 == deep ? 0 : 2) : shape[L[v]];
        int b = (R[v] == -1) ? (dep[v] + 1 == deep ? 0 : 2) : shape[R[v]];

        if (a == 1 && b == 1) { bad = true; break; }   // ครึ่งสองอันประกบกันไม่ได้
        if (a > b) { cost++; swap(a, b); }             // ลำดับที่ถูกคือ เต็มลึก ครึ่ง เต็มตื้น
        shape[v] = (a == 0 && b == 0) ? 0 : (a == 2 && b == 2) ? 2 : 1;
    }

    if (bad) puts("-1");
    else printf("%lld\n", cost);
    return 0;
}

# ตัวตรวจสอบแบบซื่อ ๆ ลองสลับทุกแบบด้วยบิตมาสก์ ใช้ได้แค่ n ราว ๆ 10
# เอาไว้สุ่มเทียบกับโค้ดจริงก่อนส่ง ไม่ใช่โค้ดที่ส่งเข้าระบบตัดสิน
import sys
sys.setrecursionlimit(10000)

d = sys.stdin.read().split()
n = int(d[0])
L = [0] * (n + 1)
R = [0] * (n + 1)
for i in range(1, n + 1):
    L[i] = int(d[2 * i - 1])
    R[i] = int(d[2 * i])

best = None
for mask in range(1 << n):
    l, r = L[:], R[:]
    for i in range(1, n + 1):
        if mask >> (i - 1) & 1:
            l[i], r[i] = r[i], l[i]

    seq = []
    def go(v, dp):
        for c in (l[v], r[v]):
            if c == -1: seq.append(dp + 1)
            else: go(c, dp + 1)
    go(1, 0)

    D = max(seq)
    if min(seq) < D - 1: continue                                  # ชั้นห่างกันเกินหนึ่ง
    if any(seq[i] < seq[i + 1] for i in range(len(seq) - 1)): continue  # ของลึกต้องอยู่ซ้ายเสมอ
    c = bin(mask).count('1')
    if best is None or c < best: best = c

print(-1 if best is None else best)

งานทั้งหมดคือเดินต้นไม้สองรอบ รอบแรกหาความลึก รอบที่สองไล่ป้าย จึงเป็น O(n) เวลาที่วัดได้บนเครื่องผมกับโมบายหนึ่งแสนแกนคือ 60 มิลลิวินาที จากลิมิตหนึ่งวินาที โดยกรณีที่ผมกลัวที่สุด (โซ่ยาวหนึ่งแสนแกน) จบเร็วที่สุดเพราะตรวจชั้นแล้วตอบ -1 ตั้งแต่ต้น

ท่าที่ติดมือกลับไปใช้ได้ทุกครั้งที่โจทย์ให้ทำอะไรบางอย่างกี่ครั้งก็ได้ ก่อนจะเริ่มไล่ว่าจะทำตรงไหนบ้าง ให้ถามก่อนว่าการกระทำนั้นเปลี่ยนอะไรไม่ได้เลย ของที่มันเปลี่ยนไม่ได้ถูกตัดสินไปแล้ว ตั้งแต่ก่อนเราลงมือ จึงตรวจได้ทันทีและมักตัดคำตอบทิ้งได้ก้อนใหญ่ ส่วนของที่มันเปลี่ยนได้คือทั้งหมด ที่เหลือให้ค้นจริง ๆ แล้วถ้าของก้อนนั้นยุบลงเหลือป้ายไม่กี่แบบได้อีก ตารางของคู่ป้ายก็จะเล็กพอจะกางดู ด้วยมือทั้งตาราง ซึ่งเป็นวิธีที่ถูกที่สุดในการรู้ว่ายังเหลือจุดให้ตัดสินใจผิดอยู่ไหม เกณฑ์ตัดสินว่ากิ่งหนึ่งกิ่ง ควรส่งค่าขึ้นไปให้พ่อกี่ค่าอยู่ในบทปูพื้นฐาน DP บนต้นไม้