Facebook Hacker Cup 2020 qualification

0.md

https://twitter.com/kusano_k/status/1287800292612780032

A.py

T = input()
for t in range(T):
  N = input()
  I = raw_input()
  O = raw_input()
  P = [["N"]*N for _ in range(N)]
  for i in range(N):
    for j in range(N):
      if i==j or O[i]=="Y" and I[j]=="Y" and abs(i-j)==1:
        P[i][j] = "Y"
  for i in range(N):
    for j in range(N):
      for k in range(N):
        if P[j][i]=="Y" and P[i][k]=="Y":
          P[j][k] = "Y"
  print "Case #%d: "%(t+1)
  for i in range(N):
    print "".join(P[i])

B.py

T = input()
for t in range(T):
  N = input()
  C = raw_input()
  ans = "Y" if abs(C.count("A")-C.count("B"))==1 else "N"
  print "Case #%s: %s"%(t+1, ans)

C.py

from collections import *

T = input()
for t in range(T):
  N = input()
  PH = [map(int, raw_input().split()) for i in range(N)]
  PH.sort()
  L = defaultdict(int)
  for p, h in PH[::-1]:
    if p in L:
      L[p-h] = max(L[p-h], L[p]+h)
    else:
      L[p-h] = max(L[p-h], h)
  R = defaultdict(int)
  for p, h in PH:
    if p in R:
      R[p+h] = max(R[p+h], R[p]+h)
    else:
      R[p+h] = max(R[p+h], h)
  ans = 0
  for l in L:
    ans = max(ans, L[l])
  for r in R:
    ans = max(ans, R[r])
  for c in L:
    if c in R:
      ans = max(ans, L[c]+R[c])
  print "Case #%d: %d"%(t+1, ans)

D1.cpp

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

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, M;
        cin>>N>>M;
        vector<long long> C(N);
        for (int i=0; i<N; i++)
            cin>>C[i];

        M = min(M, N-1);
        vector<long long> D(N, -1);
        //  (D[p]+C[p], p)
        set<pair<long long, int>> S;

        for (int i=1; i<=M; i++)
        {
            D[i] = 0;
            if (C[i]>0)
                S.insert(make_pair(D[i]+C[i], i));
        }

        for (int i=M+1; i<N; i++)
        {
            if (C[i-M-1]>0)
                S.erase(make_pair(D[i-M-1]+C[i-M-1], i-M-1));
            if (S.empty())
                break;
            D[i] = S.begin()->first;
            if (C[i]>0)
                S.insert(make_pair(D[i]+C[i], i));
        }
        cout<<"Case #"<<t<<": "<<D[N-1]<<endl;
    }
}

D2.cpp

//  時間切れで出せなかったので、合っているかどうかは不明

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

//  last common ancestor
class LCA
{
public:
    int n;
    vector<vector<int>> P;
    vector<int> D;

    //  a in E[b] <=> b in E[a]
    LCA(vector<vector<int>> E, int root)
    {
        n = (int)E.size();
        P = vector<vector<int>>(n);
        D = vector<int>(n);

        function<void (int, int, int)> f = [&](int c, int p, int d)
        {
            D[c] = d;

            if (d>0)
                P[c].push_back(p);
            for (int i=1; 1<<i<=d; i++)
                P[c].push_back(P[P[c][i-1]][i-1]);

            for (int e: E[c])
                if (e != p)
                    f(e, c, d+1);
        };
        f(root, -1, 0);
    }

    int query(int a, int b)
    {
        if (D[a]>D[b])
            swap(a, b);

        int d = D[b]-D[a];
        for (int i=0; d>0; i++)
        {
            if (d&1)
                b = P[b][i];
            d >>= 1;
        }

        if (a==b)
            return a;

        int i = 0;
        while (1<<(i+1)<=D[a])
            i++;
        for (; i>=0; i--)
            if (1<<i<=D[a] && P[a][i]!=P[b][i])
            {
                a = P[a][i];
                b = P[b][i];
            }

        if (D[a]>0)
            a = P[a][0];
        return a;
    }
};


long long solve(int N, int M, int A, int B, vector<int> P, vector<int> C)
{
    A--;
    B--;
    C[A] = 0;

    vector<vector<int>> E(N);
    for (int i=1; i<N; i++)
    {
        E[i].push_back(P[i]-1);
        E[P[i]-1].push_back(i);
    }

    LCA lca(E, A);
    auto dist = [&](int x, int y)
    {
        return lca.D[x] + lca.D[y] - 2*lca.D[lca.query(x, y)];
    };

    vector<long long> D(N, -1);
    vector<int> prev(N, -1);
    vector<vector<pair<int, int>>> F(N+1);
    //  (D[p]+C[p], p)
    set<pair<long long, int>> S;

    D[A] = 0;
    prev[A] = N;
    S.insert(make_pair(0, A));
    F[N].push_back(make_pair(A, -1));

    function<void(int, int, int, int)> f = [&](int d, int c, int p, int r)
    {
        if (D[c]==-1 || D[r]+C[r]<D[c])
        {
            long long old = D[c];

            D[c] = D[r]+C[r];
            prev[c] = r;
            S.erase(make_pair(old+C[c], c));
            S.insert(make_pair(D[c]+C[c], c));
        }

        if (d==0)
        {
            F[r].push_back(make_pair(c, p));
            return;
        }

        for (int e: E[c])
            if (e!=p)
                f(d-1, e, c, r);
    };

    while (!S.empty())
    {
        int r = S.begin()->second;
        S.erase(S.begin());

        if (r==A || C[r]>0)
            for (auto cp: F[prev[r]])
            {
                int c = cp.first;
                int p = cp.second;
                int d = c==r ? M : M - dist(c, r);
                if (d>0)
                    f(d, c, p, r);
            }
    }

    return D[B]>=0 ? D[B] : -1;
}

void D2()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, M, A, B;
        cin>>N>>M>>A>>B;
        vector<int> P(N), C(N);
        for (int i=0; i<N; i++)
            cin>>P[i]>>C[i];
        long long ans = solve(N, M, A, B, P, C);
        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}

int main()
{
    D2();
}