কন্টেস্ট ম্যাচ আউটপুট জেনারেট করা C++-এ

সমস্যা বিবরণ

n টিম আছে (১ থেকে n র‍্যাঙ্ক, ১ = সবচেয়ে শক্তিশালী)। প্রতিটি রাউন্ডে সবচেয়ে শক্তিশালী টিম সবচেয়ে দুর্বল টিমের সাথে খেলবে। পেয়ারিং স্ট্রিং আকারে আউটপুট করতে হবে প্যারেনথেসিস ও কমা দিয়ে।

উদাহরণ

n = 4

রাউন্ড ১: (1,4), (2,3) → স্ট্রিং: ((1,4),(2,3))

রাউন্ড ২: ((1,4),(2,3)) — একটিমাত্র রয়ে গেলে ফাইনাল।

অ্যালগরিদম: রিকার্সিভ পেয়ারিং

1. টিমের লিস্ট v1 = ["1", "2", ..., "n"] বানান।
2. যখন v1.size() > 1:
   • নতুন লিস্ট v2 বানান: v2[i] = "(" + v1[i] + "," + v1[n-1-i] + ")"।
   • v1 = v2।
3. শেষে v1[0] রিটার্ন করুন।

C++ বাস্তবায়ন

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

class Solution {
public:
    void create(int low, int high, vector<string>& v2, vector<string>& v1) {
        if (low >= high) return;
        v2.push_back("(" + v1[low] + "," + v1[high] + ")");
        create(low + 1, high - 1, v2, v1);
    }

    string findContestMatch(int n) {
        vector<string> v1, v2;
        for (int i = 1; i <= n; i++) v1.push_back(to_string(i));
        while (v1.size() > 1) {
            create(0, v1.size() - 1, v2, v1);
            v1 = v2;
            v2.clear();
        }
        return v1.back();
    }
};

int main() {
    Solution ob;
    cout << ob.findContestMatch(4); // ((1,4),(2,3))
    return 0;
}

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

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n log n) — প্রতিটি রাউন্ডে n/2 পেয়ার, log n রাউন্ড।
• স্থান জটিলতা: O(n log n) — স্ট্রিং সংরক্ষণ (আউটপুট সাইজ)।