Hướng dẫn giải bài tập Interactive

Bài tập interactive (tương tác) là dạng bài đặc biệt trong competitive programming, nơi chương trình của bạn phải "giao tiếp" với máy chấm trong quá trình chạy.

1. Bài tập Interactive là gì?

Khác với bài thông thường (đọc input → xử lý → in output), bài interactive yêu cầu:

1. Đọc một phần dữ liệu ban đầu
2. Gửi truy vấn (query) đến máy chấm
3. Nhận phản hồi từ máy chấm
4. Lặp lại bước 2-3 cho đến khi tìm ra đáp án
5. In kết quả cuối cùng

┌─────────────┐         ┌─────────────┐
│  Chương     │ ──?──▶  │   Máy       │
│  trình      │ ◀─────  │   chấm      │
│  của bạn    │ ──!──▶  │ (interactor)│
└─────────────┘         └─────────────┘

2. Flush Output - Điều quan trọng nhất

Vấn đề: Mặc định, output được lưu trong buffer và chỉ gửi đi khi buffer đầy hoặc chương trình kết thúc. Trong bài interactive, nếu không flush, máy chấm sẽ không nhận được query của bạn → deadlock → TLE.

C++

#include <iostream>
using namespace std;

// Cách 1: endl (tự động flush)
cout << "? " << x << endl;

// Cách 2: flush thủ công
cout << "? " << x << "\n";
cout.flush();

// Cách 3: Tắt sync (nhanh hơn nhưng cẩn thận)
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << "? " << x << "\n" << flush;

Python

# Cách 1: flush=True
print(f"? {x}", flush=True)

# Cách 2: import sys
import sys
print(f"? {x}")
sys.stdout.flush()

Java

import java.io.*;

PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println("? " + x);
out.flush();

3. Các dạng bài Interactive phổ biến

3.1. Binary Search (Tìm kiếm nhị phân)

Mẫu: Tìm số $x$ trong $[1,n]$, mỗi query hỏi so sánh.

int lo = 1, hi = n;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    cout << "? " << mid << endl;
    string resp; cin >> resp;
    if (resp == "<=") hi = mid;
    else lo = mid + 1;
}
cout << "! " << lo << endl;

Số query: $O(\log n)$

3.2. Chia hết (Divisibility)

Mẫu: Tìm số $x$, query ? y trả lời $x$ có chia hết cho $y$ không.

Chiến lược:

• Hỏi các số nguyên tố nhỏ: 2, 3, 5, 7, 11, ...
• Hỏi các lũy thừa nguyên tố: 4, 8, 9, 16, ...
• Xác định "chữ ký chia hết" của $x$

3.3. Định lý Thặng dư Trung Hoa (CRT)

Mẫu: Tìm số $x$, query ? y trả lời $x\mathrm{mod}y$.

Chiến lược:

• Hỏi $x\mathrm{mod}p$ cho các số nguyên tố $p_1,p_2,\dots ,p_k$
• Dùng CRT ghép lại: nếu $\prod p_i>n$ thì $x$ duy nhất

// Ghép hai đồng dư bằng CRT
pair<ll, ll> crt2(ll r1, ll m1, ll r2, ll m2) {
    ll g, x, y;
    g = extgcd(m1, m2, x, y);
    ll lcm = m1 / g * m2;
    ll t = (r2 - r1) / g * x % (m2 / g);
    ll ans = ((r1 + m1 * t) % lcm + lcm) % lcm;
    return {ans, lcm};
}

3.4. Khoảng cách Manhattan

Mẫu: Tìm điểm $(x,y)$ trên lưới, query trả lời khoảng cách Manhattan.

Chiến lược:

• Query 4 góc: $(1,1),(n,1),(1,n),(n,n)$
• Giải hệ phương trình để tìm $(x,y)$

4. Xử lý máy chấm "nói dối" (Lie)

Một số bài cho phép máy chấm nói dối tối đa $k$ lần.

Chiến lược với 1 lie:

1. Hỏi mỗi query 2 lần:

   • Nếu 2 câu trả lời giống nhau → tin tưởng
   • Nếu khác nhau → hỏi lần 3, dùng đa số (2/3)

2. Đếm mismatch:

   • Với mỗi ứng viên $x$, đếm số câu trả lời không khớp
   • Ứng viên hợp lệ nếu mismatch $\le k$

int count_mismatch(int x) {
    int cnt = 0;
    for (auto& [q, ans] : queries) {
        bool expected = /* x thỏa query q */;
        if (expected != ans) cnt++;
    }
    return cnt;
}

vector<int> get_candidates() {
    vector<int> cands;
    for (int x = 1; x <= n; x++)
        if (count_mismatch(x) <= k) // k = số lie tối đa
            cands.push_back(x);
    return cands;
}

5. Máy chấm biến hóa (Adaptive)

Máy chấm adaptive không cố định đáp án từ đầu. Sau mỗi query, máy chấm có thể thay đổi đáp án, miễn là vẫn nhất quán với các câu trả lời trước.

Hậu quả:

• Bạn không thể dựa vào may mắn
• Phải đảm bảo sau tất cả query, chỉ còn duy nhất 1 đáp án khả thi
• Máy chấm sẽ luôn chọn đáp án bất lợi nhất cho bạn

Chiến lược:

• Chọn query chia đều tập ứng viên
• Mục tiêu: minimize(max(nhánh YES, nhánh NO))

int best_query(vector<int>& candidates) {
    int best_y = -1, best_score = INT_MAX;
    for (int y = 2; y <= n; y++) {
        int yes_cnt = 0, no_cnt = 0;
        for (int x : candidates) {
            if (/* x thỏa query y */) yes_cnt++;
            else no_cnt++;
        }
        if (yes_cnt == 0 || no_cnt == 0) continue;
        int score = max(yes_cnt, no_cnt);
        if (score < best_score) {
            best_score = score;
            best_y = y;
        }
    }
    return best_y;
}

6. Template cơ bản

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

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

    int n;
    cin >> n;

    auto ask = [&](int y) -> string {
        cout << "? " << y << endl;
        string resp;
        cin >> resp;
        return resp;
    };

    // Thuật toán của bạn ở đây
    // ...

    cout << "! " << answer << endl;
    return 0;
}

7. Debug bài Interactive

1. Test local: Viết interactor giả để test
2. In ra stderr: cerr << "debug: " << x << endl; (không ảnh hưởng đến giao tiếp)
3. Kiểm tra flush: Đảm bảo mọi output đều được flush
4. Đọc kỹ format: YES/yes, >=/>/<=/<, có newline không?

8. Các bài tập thực hành

9. Lỗi thường gặp

10. Tổng kết

1. Luôn flush sau mỗi query
2. Đếm số query để không vượt giới hạn
3. Với adaptive: đảm bảo duy nhất 1 đáp án sau tất cả query
4. Với lie: dùng mismatch counting hoặc majority voting
5. Test kỹ trước khi submit