Soluție HackerRank pentru Introduction to Representation Theory, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația…

  • Problemă: Introduction to Representation Theory
  • Domeniu: Combinatorics
  • Limbaj: C++14

Challenge: Introduction to Representation Theory

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464815178

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/introduction-to-representation-theory/problem

Cerință

Welcome to Sevenkplus' perfect math class! In this class, you will learn about representation theory. And this class is in a different format than before: Learning by doing! You need to solve a problem, which can be solved elegantly using (really elementary) representation theory. (Of course you can solve this problem without representation theory. But learning more is helpful!)

Sevenkplus had an n× n complex matrix M. He calculated Tr(M^0), …,Tr(M^m-1) and found that M^m=I. (For a square matrix A, Tr(A) is the trace of A. I is the n× n identity matrix.)
However, the dark side of the world destroyed M, and only n, m, Tr(M^0), …, Tr(M^m-1) remained.

Sevenkplus wants to recover his beloved M. However, this is impossible.
Nevertheless, doing something weaker is possible: Only recover the eigenvalues of M. Here the eigenvalues are defined to be the entries on the diagonal of the Jordan normal form of M. For a fixed M, they are unique up to permutation.

Input Format

The first line contains two space separated integers, n and m.
Followed by m lines where for each value of k in [0,m) line contains two real numbers a_k, b_k, which means that Tr(M^k) = a_k + i · b_k, where i is the imaginary unit.

Constraints
1≤ n ≤ 10000
1 ≤ m ≤ 2000
|a_k|, |b_k| ≤ 10000
It is guaranteed that there is an M that satisfies the relations.

Output Format

Print n lines where for each value of k in [0,m) line contains two real numbers c_k, d_k.
The multi-set of c_k+i· d_k should be the multi-set of eigenvalues of M.

You can output the eigenvalues in any order.
In case of multiple answers output any of them, your answer is considered correct if your answer satisfies the input, within absolute error 10^-6.

Cod sursă

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    const long double PI = acosl(-1.0L);

    vector<complex<long double>> s(m);
    for (int k = 0; k < m; ++k) {
        long double a, b;
        cin >> a >> b;
        s[k] = {a, b};
    }

    vector<long long> cnt(m, 0);
    vector<long double> residue(m, 0.0L);

    for (int t = 0; t < m; ++t) {
        complex<long double> acc = 0;
        for (int k = 0; k < m; ++k) {
            long double ang = -2.0L * PI * (long double)t * (long double)k / (long double)m;
            complex<long double> w = {cosl(ang), sinl(ang)};
            acc += s[k] * w;
        }
        acc /= (long double)m;
        long double x = acc.real();
        long long r = llround(x);
        if (r < 0 && fabsl(x) < 1e-6L) r = 0;
        cnt[t] = r;
        residue[t] = x - (long double)r;
    }

    long long total = 0;
    for (long long v : cnt) total += v;

    // Small numerical correction so total multiplicity equals n.
    while (total < n) {
        int best = 0;
        for (int i = 1; i < m; ++i) {
            if (residue[i] > residue[best]) best = i;
        }
        ++cnt[best];
        residue[best] -= 1.0L;
        ++total;
    }
    while (total > n) {
        int best = -1;
        for (int i = 0; i < m; ++i) {
            if (cnt[i] <= 0) continue;
            if (best == -1 || residue[i] < residue[best]) best = i;
        }
        if (best == -1) break;
        --cnt[best];
        residue[best] += 1.0L;
        --total;
    }

    cout.setf(std::ios::fixed);
    cout << setprecision(12);

    int printed = 0;
    for (int t = 0; t < m; ++t) {
        long long c = cnt[t];
        if (c <= 0) continue;
        long double ang = 2.0L * PI * (long double)t / (long double)m;
        long double re = cosl(ang), im = sinl(ang);
        if (fabsl(re) < 1e-15L) re = 0;
        if (fabsl(im) < 1e-15L) im = 0;
        for (long long z = 0; z < c; ++z) {
            cout << (double)re << ' ' << (double)im << '\n';
            ++printed;
        }
    }

    // Fallback safety: if due severe input noise we printed fewer, pad with 1+0i.
    while (printed < n) {
        cout << "1.000000000000 0.000000000000\n";
        ++printed;
    }
    return 0;
}
HackerRank Combinatorics – Introduction to Representation Theory