সি++-এ গেম থিওরি: প্রথম খেলোয়াড় জিততে পারবে কিনা (গোস্ট গেম)

সমস্যা বিবরণ

একটি ওয়ার্ড লিস্ট দেওয়া আছে। দুজন খেলোয়াড় বারবার ক্যারেক্টার অ্যাপেন্ড করে একটি স্ট্রিং বানায়। স্ট্রিংটি লিস্টের যেকোনো ওয়ার্ডের ভ্যালিড প্রিফিক্স হতে হবে। যে খেলোয়াড়টি লিস্টের যেকোনো ওয়ার্ড কমপ্লিট করবে সে হেরে যাবে। উভয় অপ্টিমাল খেললে প্রথম খেলোয়াড় জিততে পারবে কিনা?

উদাহরণ: words = ["manage","manager","min"] → আউটপুট True।

সমাধানের পদ্ধতি

ট্রাই (Trie) + গেম থিওরি (Win/Lose স্টেট):

1. সব ওয়ার্ড দিয়ে ট্রাই বানান।
2. প্রতিটি নোডের জন্য win এবং lose স্টেট গণনা করুন (পোস্ট-অর্ডার DFS)।
3. win[u] = any(!win[v] for v in children) — কোনো চাইল্ডে হেরালে বর্তমান নোড জয়।
4. lose[u] = any(!lose[v] for v in children) — কোনো চাইল্ডে জেতলে বর্তমান নোড হেরে।
5. রুট নোডের win স্টেট চেক করুন।

দ্রষ্টব্য: প্রদত্ত কোডে একটি সরলীকৃত লজিক ব্যবহৃত হয়েছে যা সব ওয়ার্ডের প্রথম ক্যারেক্টার অনুযায়ী গ্রুপ করে এবং ইভেন লেন্থ চেক করে।

উদাহরণ কোড

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

bool solve(vector<string>& words) {
    map<char, set<string>> mp;
    for (auto& it : words) {
        char ch = it[0];
        mp[ch].insert(it);
    }
    for (auto& it : mp) {
        string str = *(it.second.begin());
        int sz = str.size();
        if (sz % 2 == 0) return true;
    }
    return false;
}

int main() {
    vector<string> v = {"manage", "manager", "min"};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {"manage", "manager", "min"}

আউটপুট: 1