Editorial for ptit022: Cuộc đấu trí của Daisy và Louis

Hiểu bài toán

Trò chơi giữa Daisy và Louis xoay quanh một xâu ký tự. Daisy chơi trước, họ thay nhau loại bỏ một ký tự khỏi xâu. Người chơi nào tại lượt của mình có thể sắp xếp lại các ký tự còn lại để tạo thành một xâu đối xứng (palindrome) thì thắng. Cả hai đều chơi tối ưu. Xâu đối xứng có thể được tạo ra khi số lượng ký tự có tần suất lẻ (odd frequency) trong xâu không vượt quá 1 (nếu độ dài xâu chẵn thì phải bằng 0, nếu lẻ thì bằng 1). Bài toán quy về game theory đơn giản: Người chơi muốn là người tạo ra trạng thái thắng (tức là sau khi bỏ đi 1 ký tự, số ký tự lẻ <= 1). Nếu không thể thắng ngay, người chơi sẽ cố gắng ép đối thủ vào thế thua. Phân tích cho thấy Daisy thắng nếu số ký tự lẻ ban đầu là số chẵn (0, 2, 4...) hoặc bằng 1, còn Louis thắng nếu số ký tự lẻ ban đầu là số lẻ lớn hơn 1 (3, 5...).

Các cách tiếp cận

Cách Hash Map

#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    string s;
    cin>>s;
    unordered_map<char,int> mp;
    for(char x : s){
        mp[x]++;
    }
    int cntodd = 0;
    auto x : mp){
        if(x.second % 2 == 1){
            ++cntodd;
        }
    }
    if(cntodd == 0 || cntodd%2 == 1){
        cout<<"Daisy";
    }
    else{
        cout<<"Louis";
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(K) (K là số ký tự khác nhau)

Sử dụng hash map để đếm tần suất của từng ký tự. Duyệt qua bản đồ để đếm số lượng ký tự có tần suất lẻ (cntodd). Áp dụng quy tắc thắng/thua: Daisy thắng nếu cntodd là 0 hoặc là số lẻ, Louis thắng nếu cntodd là số chẵn và lớn hơn 0.

Cách Mảng Count (Fixed Array)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    if (!(cin >> s)) return 0;
    vector<int> f(26, 0);
    for (char c : s) if ('a' <= c && c <= 'z') ++f[c - 'a'];
    int odd = 0;
    for (int x : f) if (x % 2) ++odd;
    if (odd == 0 || (odd % 2 == 1)) cout << "Daisy";
    else cout << "Louis";
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Vì đầu vào chỉ chứa các ký tự tiếng Anh viết thường, ta có thể dùng mảng kích thước 26 thay vì hash map để tối ưu không gian bộ nhớ và tốc độ truy cập. Logic tính toán giống Approach 1.

Cách Logic Game Theory (Phân tích luật chơi)

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

int main() {
    string s;
    cin >> s;
    int cnt[26] = {0};
    for (char c: s) cnt[c - 'a']++;
    int d = 0;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] % 2) d++;
    }
    if (d <= 1) cout << "Daisy";
    else {
        if (d % 2 == 1) cout << "Daisy";
        else cout << "Louis";
    }
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(1)

Đây là biến thể của logic mảng count. Code kiểm tra điều kiện đặc biệt 'd <= 1' (Daisy thắng ngay nếu trạng thái ban đầu đã thắng hoặc chỉ cần 1 bước để thắng). Nếu d > 1, kết quả phụ thuộc vào tính chẵn lẻ của d. Louis thắng khi d là số chẵn (vì Daisy phải di chuyển trước, chuyển d từ chẵn sang lẻ, Louis sẽ chuyển lại về chẵn cho đến khi Louis thắng). Daisy thắng khi d là số lẻ (vì Daisy có thể chiến thắng bằng cách đi nước đầu tiên.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là một trò chơi thông thường (Impartial Game) với trạng thái thắng/thua phụ thuộc hoàn vào số lượng ký tự có tần suất lẻ (odd count).
• Daisy (người đi trước) thắng nếu số ký tự lẻ ban đầu là số chẵn (bao gồm 0) hoặc số lẻ.
• Louis (người đi sau) chỉ thắng khi số ký tự lẻ ban đầu là một số lẻ lớn hơn 1 (ví dụ: 3, 5...). Có thể tóm tắt bằng công thức: Louis thắng nếu (odd > 1 và odd % 2 == 0), ngược lại Daisy thắng.
• Việc sắp xếp lại xâu để thành palindrome chỉ cần kiểm tra số lượng ký tự lẻ.

Lỗi thường gặp

• Lầm tưởng rằng cần phải thực hiện các bước di chuyển mô phỏng (simulate) từng nước đi, dẫn đến thuật toán phức tạp O(2^N). Cần nhận ra đây là bài toán Logic Game.
• Quên rằng nếu ban đầu xâu đã là palindrome (odd = 0) thì Daisy thắng ngay lập tức.
• Sử dụng cấu trúc dữ liệu quá nặng (như map) khi có thể dùng mảng固定 size cho ký tự viết thường.