Facebook Hacker Cup 2019 Round 2

1_on_the_run.py

T = input()
for t in range(T):
  N, M, K = map(int, raw_input().split())
  A, B = map(int, raw_input().split())
  A -= 1
  B -= 1
  R = [0]*K
  C = [0]*K
  for i in range(K):
    R[i], C[i] = map(int, raw_input().split())
    R[i] -= 1
    C[i] -= 1
  if K==1:
    ans = "N"
  else:
    if (A+B)%2==(R[0]+C[0])%2==(R[1]+C[1])%2:
      ans = "Y"
    else:
      ans = "N"
  print "Case #%s: %s"%(t+1, ans)

2_bitstrings_as_a_service.cpp

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

class UnionFind
{
public:
    vector<int> parent;
    vector<int> sz;
    
    UnionFind(int n): parent(n), sz(n)
    {
        for(int i=0;i<n;i++)
        {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    int root(int x)
    {
        return parent[x]==x ? x : parent[x] = root(parent[x]);
    }

    bool same(int x, int y)
    {
        return root(x)==root(y);
    }

    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x != y)
        {
            if (sz[x] < sz[y])
            {
                parent[x] = y;
                sz[y] += sz[x];
            }
            else
            {
                parent[y] = x;
                sz[x] += sz[y];
            }
        }
    }

    int size(int x)
    {
        return sz[root(x)];
    }
};

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, M;
        cin>>N>>M;
        UnionFind UF(N);
        for (int i=0; i<M; i++)
        {
            int X, Y;
            cin>>X>>Y;
            X--;
            Y--;
            for (int j=0; j<(Y-X+1)/2; j++)
                UF.unite(X+j, Y-j);
        }
        vector<vector<int>> V(N);
        for (int i=0; i<N; i++)
            V[UF.root(i)].push_back(i);

        vector<vector<int>> X(N, vector<int>(N+1, -1));
        X[0][0] = 0;
        X[0][V[0].size()] = 1;
        for (int i=1; i<N; i++)
        {
            for (int j=0; j<=N; j++)
            if (X[i-1][j] != -1)
            {
                X[i][j] = 0;
                X[i][j+V[i].size()] = 1;
            }
        }

        int best = 0;
        for (int i=0; i<=N; i++)
            if (X[N-1][i]!=-1 && abs(2*i-N)<abs(2*best-N))
                best = i;
        //cout<<"--"<<endl;
        //cout<<best<<" "<<abs(best-(N-best))<<endl;
        string ans(N, '_');
        for (int i=N-1; i>=0; i--)
        {
            for (int v: V[i])
                ans[v] = '0'+X[i][best];
            if (X[i][best]==1)
                best -= (int)V[i].size();
        }
        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}

3_grading.cpp

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

//  ans[s]: minimum number of loses for at most s context switces
vector<int> solve3(int H, string S)
{
    vector<int> TA(H+2, H+1), TB(H+2, H+1);
    vector<int> PA(H+2), PB(H+2);

    if (S[0]=='A')
    {
        TA[1] = 0;
        TB[2] = 1;
    }
    else
    {
        TA[1] = 1;
        TB[2] = 0;
    }

    for (int h=1; h<H; h++)
    {
        for (int i=0; i<=H+1; i++)
        {
            PA[i] = TA[i];
            PB[i] = TB[i];
            TA[i] = H;
            TB[i] = H;
        }

        if (S[h]=='A')
        {
            //  no context switch
            for (int i=0; i<=H+1; i++)
                TA[i] = min(TA[i], PA[i]);
            for (int i=0; i<=H+1; i++)
                TB[i] = min(TB[i], PB[i]+1);
            //  with context switch
            for (int i=0; i<=H; i++)
                TA[i+1] = min(TA[i+1], PB[i]);
        }
        else
        {
            //  no context switch
            for (int i=0; i<=H+1; i++)
                TB[i] = min(TB[i], PB[i]);
            for (int i=0; i<=H+1; i++)
                TA[i] = min(TA[i], PA[i]+1);
            //  with context switch
            for (int i=0; i<=H; i++)
                TB[i+1] = min(TB[i+1], PA[i]);
        }
    }

    vector<int> ans(H+2);
    for (int h=0; h<=H+1; h++)
        ans[h] = min(TA[h], TB[h]);
    for (int h=1; h<=H+1; h++)
        ans[h] = min(ans[h], ans[h-1]);
    return ans;
}

//  ans[l]: minimum number of context switches with at most l loses
vector<int> solve2(int H, int S, int K, vector<string> P)
{
    vector<vector<int>> T;
    for (int s=0; s<S; s++)
    {
        string p = "";
        for (int h=0; h<H; h++)
            p += P[h][s];
        T.push_back(solve3(H, p));
    }
    vector<int> ans(H*S+1, H*S);
    for (int h=1; h<=H+1; h++)
    {
        int a = 0;
        for (int s=0; s<S; s++)
            a += T[s][h];
        ans[a] = min(ans[a], h);
    }
    for (int a=1; a<=H*S; a++)
        ans[a] = min(ans[a-1], ans[a]);
    return ans;
}

vector<int> solve1(int H, int S, int K, vector<string> P, vector<int> L)
{
    vector<int> a1 = solve2(H, S, K, P);
    for (int h=0; h<H; h++)
        for (int s=0; s<S; s++)
            P[h][s] = P[h][s]=='A' ? 'B' : 'A';
    vector<int> a2 = solve2(H, S, K, P);

    vector<int> ans;
    for (int l: L)
        ans.push_back(min(a1[l], a2[l]));
    return ans;
}

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int H, S, K;
        cin>>H>>S>>K;
        vector<string> P(H);
        for (string &p: P)
            cin>>p;
        vector<int> L(K);
        for (int &l: L)
            cin>>l;

        vector<int> ans = solve1(H, S, K, P, L);
        cout<<"Case #"<<t<<":";
        for (int a: ans)
            cout<<" "<<a;
        cout<<endl;
    }
}