Submission #1080557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080557		eyalz	Magic Show (APIO24_show)	C++17	100 / 100	2 ms	1028 KiB

Alice

#include"Alice.h"
#include<bits/stdc++.h>
using namespace std;
using llong = long long;
using vpii = vector<pair<int,int>>;

constexpr int N = 101;
constexpr int q = 9;
constexpr int s = 25;

int Q[q],S[s];
bool I[N];
vpii Alice()
{
    // init
    for(int i = 0; i < N; ++i) I[i] = false;
    // get X
    llong X = setN(N + 1) - 1;
    // represent X in base N (resulting in q numbers). store in Q.
    for(int i = 0; i < q; ++i)
    {
        Q[i] = X % N;
        X /= N;
    }
    // make a polynomial with coefficents from Q, and calculate it at s points, storing the result in S.
    // I indicates which numbers are in S.
    for(int i = 0; i < s; ++i)
    {
        int r = 0;
        int p = 1;
        for(int f : Q)
        {
            r = (r + (p * f) % N) % N;
            p = p * i % N;
        }
        S[i] = r;
        I[r] = true;
    }
    // create tree
    vpii T; T.reserve(N);
    for(int i = 0; i < N; ++i)
    {
        if(!I[i])
            T.push_back({i + 1, S[i%s] + 1});
        else
            T.push_back({i + 1, N + 1});
    }
    return T;
}

Bob

#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
using llong = long long;
using vpii = vector<pair<int,int>>;

constexpr int N = 101;
constexpr int q = 9;
constexpr int s = 25;

int V[q][q], Y[q], S[s];
bool I[N], M[N][s];
llong Bob(vpii T)
{
    // clear arrays
    for(int i = 0; i < N; ++i)
    {
        I[i] = false;
        for(int j = 0; j < s; ++j)
            M[i][j] = false;
    }
    // find I - which numbers are in S, and M - what indices in S a number is at.
    for(auto[a,b] : T)
    {
        --a; --b;
        I[b] |= a == N; I[a] |= b == N;
        if(a != N && b != N)
        {
            // if already has a neighbor with this rem, this is an important node.
            I[b] |= M[b][a%s]; I[a] |= M[a][b%s];
            M[a][b%s] = M[b][a%s] = true;
        }
    }
    // use I and M to restore S. -1 indicates the number is unknown.
    // N and s are picked such that atleast q = logN(maxX-1) numbers are recoverable.
    for(int m = 0; m < s; ++m)
    {
        S[m] = -1;
        for(int i = 0; i < N; ++i)
        {
            if(I[i] && M[i][m])
            {
                S[m] = i;
                break;
            }
        }
    }
    // polynomial interpolation over mod N field.
    // create vandermont matrix (V) and result vector (Y).
    int c = 0;
    for(int i = 0; i < s; ++i)
    {
        if(c >= q) break;
        if(S[i] != -1)
        {
            int p = 1;
            for(int j = 0; j < q; ++j)
            {
                V[c][j] = p;
                p = p * i % N;
            }
            Y[c] = S[i];
            ++c;
        }
    }
    // using elimination, calculate V^-1 * Y to get the vector of the polynomial coefficients, stored in Y as an optimization.
    for(int i = 0; i < q; ++i)
    {
        int e = 1;
        int a = V[i][i];
        // e = inverse of V[i][i]
        for(int p = N-2; p; p>>=1)
        {
            if(p&1) e = e*a%N;
            a = a*a%N;
        }

        //step 1:
        for(int j = i; j < q; ++j)
            V[i][j] = e*V[i][j]%N;
        Y[i] = e*Y[i]%N;
        //V[i][i] is now 1

        //step 2:
        for(int j = 0; j < q; ++j)if(i != j)
        {
            int ej = N - V[j][i];
            for(int k = 0; k < q; ++k)
                V[j][k] = (V[j][k] + ej*V[i][k]%N)%N;
            Y[j] = (Y[j] + ej*Y[i]%N)%N;
        }
        //V[j][i] is now 0 for all j != i.
    }
    // restore X through the new Y.
    llong X = 0;
    llong a = 1;
    for(int i = 0; i < q; ++i)
    {
        X += a*Y[i];
        a *= N;
    }
    return X+1;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65