Facebook Hacker Cup 2020 Round 2

A.py

def read_array(N, K):
  X = list(map(int, input().split()))
  A, B, C, D = map(int, input().split())
  for i in range(K, N):
    X += [(A*X[i-2]+B*X[i-1]+C)%D]
  return X

T = int(input())
for t in range(T):
  N, K = map(int, input().split())
  S = read_array(N, K)
  X = read_array(N, K)
  Y = read_array(N, K)
  if sum(X)<=sum(S)<=sum(X)+sum(Y):
    n = 0
    p = 0
    for i in range(N):
      if S[i]<X[i]:
        n += X[i]-S[i]
      if X[i]+Y[i]<S[i]:
        p += S[i]-(X[i]+Y[i])
    ans = max(n, p)
  else:
    ans = -1
  print(f"Case #{t+1}: {ans}")

B.cpp

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N;
        double P;
        cin>>N>>P;
        vector<double> A = {1.0, 1.0};
        for (int i=3; i<=N; i++)
        {
            vector<double> B(i, 1.0);
            int a = i*(i-1)/2;
            for (int j=0; j<i; j++)
            {
                if (j>=2)
                    B[j] += A[j-1]*(j*(j-1)/2)/a;
                if (j>=1)
                    B[j] += A[j-1]*j/a*P;
                if (j<i-1)
                    B[j] += A[j]*(i-j-1)/a*(1-P);
                if (j<i-2)
                {
                    int x = i-j-1;
                    B[j] += A[j]*(x*(x-1)/2)/a;
                }
                if (1<=j && j<i-1)
                {
                    B[j] += A[j-1]*(j*(i-j-1))/a*P;
                    B[j] += A[j]*(j*(i-j-1))/a*(1-P);
                }
            }
            A = B;
        }
        printf("Case #%d:\n", t);
        for (double a: A)
            printf("%.10f\n", a);
    }
}

C.cpp

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<long long> read_array(int N, int K, long long M)
{
    vector<long long> X(N);
    for (int i=0; i<K; i++)
        cin>>X[i];
    long long A, B, C;
    cin>>A>>B>>C;
    for (int i=K; i<N; i++)
        X[i] = (A*X[i-2]+B*X[i-1]+C)%M;
    return X;
}

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, M, E, K;
        cin>>N>>M>>E>>K;
        vector<long long> X = read_array(N, K, M);
        vector<long long> Y = read_array(N, K, M);
        vector<long long> I = read_array(E, K, N*M+N);
        vector<long long> W = read_array(E, K, 1'000'000'000LL);

        for (int i=0; i<N; i++)
            if (X[i]>Y[i])
                swap(X[i], Y[i]);

        vector<long long> ER(N, 1);
        multiset<long long> SR;
        for (int i=0; i<N; i++)
            SR.insert(1);
        for (int i=0; i<N; i++)
            if (X[i]<Y[i])
                SR.insert(1);

        vector<int> B2R(N);
        vector<vector<long long>> EB(N, vector<long long>(M, 1));
        vector<multiset<long long>> SB(2*N);
        for (int i=0; i<N; i++)
        {
            int n = Y[i]-X[i];
            for (int j=0; j<n; j++)
                SB[i*2].insert(1);
            for (int j=n; j<M; j++)
                SB[i*2+1].insert(1);
        }
        long long V = N*M-1;
        long long ans = 1;
        long long MOD = 1'000'000'007;

        for (int i=0; i<E; i++)
        {
            if (I[i]>=N*M)
            {
                long long e = I[i]-N*M;
                V += *SR.rbegin();
                V -= ER[e];
                SR.erase(SR.find(ER[e]));
                ER[e] = W[i];
                SR.insert(ER[e]);
                V += ER[e];
                V -= *SR.rbegin();
            }
            else
            {
                long long ci = I[i]/M;
                long long e = I[i]%M;
                if (X[ci]==Y[ci])
                {
                    V += *SB[2*ci+1].rbegin();
                    V -= EB[ci][e];
                    SB[2*ci+1].erase(SB[2*ci+1].find(EB[ci][e]));
                    EB[ci][e] = W[i];
                    SB[2*ci+1].insert(EB[ci][e]);
                    V += EB[ci][e];
                    V -= *SB[2*ci+1].rbegin();
                }
                else
                {
                    //  remove from SR
                    int b2ri = B2R[ci];
                    V += *SR.rbegin();
                    V -= *SB[2*ci+b2ri].rbegin();
                    SR.erase(SR.find(*SB[2*ci+b2ri].rbegin()));

                    V += *SB[2*ci].rbegin();
                    V += *SB[2*ci+1].rbegin();

                    int ei = X[ci]<=e && e<Y[ci] ? 0 : 1;
                    V -= EB[ci][e];
                    SB[2*ci+ei].erase(SB[2*ci+ei].find(EB[ci][e]));
                    EB[ci][e] = W[i];
                    SB[2*ci+ei].insert(EB[ci][e]);
                    V += EB[ci][e];

                    V -= *SB[2*ci].rbegin();
                    V -= *SB[2*ci+1].rbegin();

                    //  add to SR
                    b2ri = *SB[2*ci].rbegin() > *SB[2*ci+1].rbegin() ? 1 : 0;
                    SR.insert(*SB[2*ci+b2ri].rbegin());
                    V += *SB[2*ci+b2ri].rbegin();
                    V -= *SR.rbegin();
                    B2R[ci] = b2ri;
                }
            }
            ans *= V%MOD;
            ans %= MOD;
            //cout<<" "<<V<<endl;
        }

        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}