HackerRank Combinatorics – Introduction to Representation Theory – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

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

Cerinta

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\times n$ complex matrix $M$. He calculated $Tr(M^0), \ldots,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\times n$ identity matrix.)
However, the dark side of the world destroyed $M$, and only $n, m, Tr(M^0), \ldots, 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 \cdot b_k$, where $i$ is the imaginary unit.  

**Constraints**  
$1\leqslant n \leqslant 10000$  
$1 \leqslant m \leqslant 2000$  
$|a_k|, |b_k| \leqslant 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\cdot 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 sursa

#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