Google Code Jam 2022 Round 2

A.py

T = int(input())
for t in range(1, T+1):
  N, K = map(int, input().split())
  V = [1]
  for i in range(2, N, 2)[::-1]:
    for j in range(4):
      V += [V[-1]+i]
  V += [N*N, N*N]
  d = N*N-1-K
  c = 0
  ans = []
  #print(V)
  while d>0 and c<len(V)-4:
    if V[c+4]-V[c]-2<=d:
      d -= V[c+4]-V[c]-2
      ans += [(V[c]+1, V[c+4])]
      c += 4
    else:
      c += 1
  if d>0:
    print(f"Case #{t}: IMPOSSIBLE")
  else:
    print(f"Case #{t}: {len(ans)}")
    for a in ans:
      print(*a)

B.py

def draw_circle_perimeter(A, R, r):
  for x in range(-r, r+1):
    y = int((r*r-x*x)**.5+.5)
    A[R+y][R+x] = "#"
    A[R-y][R+x] = "#"
    A[R+x][R+y] = "#"
    A[R+x][R-y] = "#"

def draw_circle_filled(A, R):
  for x in range(-R, R+1):
    for y in range(-R, R+1):
      if int((x*x+y*y)**.5+.5)<=R:
        A[R+y][R+x] = "#"

def draw_circle_filled_wrong(A, R):
  for r in range(0, R+1):
    draw_circle_perimeter(A, R, r)

def naive(R):
  A = [["."]*(2*R+1) for _ in range(2*R+1)]
  B = [["."]*(2*R+1) for _ in range(2*R+1)]

  draw_circle_filled(A, R)
  draw_circle_filled_wrong(B, R)

  for a in A:
    print("".join(a))
  for b in B:
    print("".join(b))

  ans = 0
  for y in range(2*R+1):
    for x in range(2*R+1):
      if A[y][x]!=B[y][x]:
        ans += 1
  return ans

T = int(input())
for t in range(1, T+1):
  R = int(input())
  ans = naive(R)
  print(f"Case #{t}: {ans}")

C.cpp

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int maxflow(vector<vector<int>> E_, vector<vector<int>> F_, vector<vector<int>> *FF, int s, int t)
{
    int n = (int)E_.size();

    vector<vector<int>> E(n), F(n), R(n), FI(n);
    for (int i=0; i<n; i++)
    for (int j=0; j<(int)E_[i].size(); j++)
    {
        int v = E_[i][j];
        R[i].push_back(int(E[v].size()));
        R[v].push_back(int(E[i].size()));
        E[i].push_back(v);
        E[v].push_back(i);
        F[i].push_back(F_[i][j]);
        F[v].push_back(0);
        FI[i].push_back(j);
        FI[v].push_back(-1);
    }
    vector<bool> U(n);
    function<int (int, int)> dfs = [&](int p, int f)
    {
        if (p==t)
            return f;
        U[p] = true;
        for (int i=0; i<(int)E[p].size(); i++)
        if (!U[E[p][i]] && F[p][i]>0)
        {
            int t = dfs(E[p][i], min(f, F[p][i]));
            if (t>0)
            {
                F[p][i] -= t;
                if (FI[p][i]>=0)
                    (*FF)[p][FI[p][i]] = 1;
                F[E[p][i]][R[p][i]] += t;
                if (FI[E[p][i]][R[p][i]]>=0)
                    (*FF)[E[p][i]][FI[E[p][i]][R[p][i]]] = 0;
                return t;
            }
        }
        return 0;
    };

    int flow = 0;
    while (true)
    {
        for (int i=0; i<n; i++)
            U[i] = false;
        int f = dfs(s, 0x7fffffff);
        if (f==0)
            break;
        flow += f;
    }

    return flow;
}

int bipartite(vector<vector<int>> M, vector<int> *R)
{
    int n = (int)M.size();
    int m = 0;
    for (int i=0; i<n; i++)
        for (int j=0; j<(int)M[i].size(); j++)
            m = max(m, M[i][j]+1);

    vector<vector<int>> E(n+m+2), F(n+m+2), FF(n+m+2);

    for (int i=0; i<n; i++)
    for (int j=0; j<(int)M[i].size(); j++)
        E[i].push_back(n+M[i][j]),
        F[i].push_back(1),
        FF[i].push_back(0);
    for (int i=0; i<n; i++)
        E[n+m].push_back(i),
        F[n+m].push_back(1),
        FF[n+m].push_back(0);
    for (int i=0; i<m; i++)
        E[n+i].push_back(n+m+1),
        F[n+i].push_back(1),
        FF[n+i].push_back(0);

    int ret = maxflow(E, F, &FF, n+m, n+m+1);
    if (ret==n)
    {
        for (int i=0; i<n; i++)
            for (int j=0; j<(int)E[i].size(); j++)
                if (FF[i][j]>0)
                    (*R)[i] = E[i][j]-n;
    }

    return ret;
}

#include <iostream>

#if 0
int main()
{
    /*
    0---0
      X
    1   1
      \
    2---2
    */
    vector<int> R(3);
    cout<<bipartite({
        {0, 1},
        {0, 2},
        {2},
    }, &R)<<endl;   //  3
    for (int r: R)
        cout<<" "<<r;
    cout<<endl;
}
#endif

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N;
        cin>>N;
        vector<long long> CX(N), CY(N);
        vector<long long> JX(N+1), JY(N+1);
        for (int i=0; i<N; i++)
            cin>>CX[i]>>CY[i];
        for (int i=0; i<N+1; i++)
            cin>>JX[i]>>JY[i];

        vector<vector<long long>> D(N, vector<long long>(N+1));
        for (int i=0; i<N; i++)
            for (int j=0; j<N+1; j++)
                D[i][j] = (CX[i]-JX[j])*(CX[i]-JX[j])+(CY[i]-JY[j])*(CY[i]-JY[j]);

        vector<vector<int>> E(N);
        for (int i=0; i<N; i++)
            for (int j=1; j<N+1; j++)
            {
                if (D[i][j]<=D[i][0])
                    E[i].push_back(j);
                sort(E[i].begin(), E[i].end(), [&](int a, int b){return D[i][a]<D[i][b];});
            }

        cout<<"Case #"<<t<<": ";
        vector<int> R(N);
        int n = bipartite(E, &R);
        if (n==N)
        {
            cout<<"POSSIBLE"<<endl;
            vector<int> P(N);
            vector<bool> UC(N);
            vector<bool> UJ(N+1);
            for (int i=0; i<N; i++)
            {
                for (int j=0; j<N; j++)
                    if (!UC[j])
                    {
                        while (UJ[E[j][P[j]]])
                            P[j]++;
                        if (E[j][P[j]]==R[j])
                        {
                            cout<<j+1<<" "<<R[j]+1<<endl;
                            UC[j] = UJ[R[j]] = true;
                            goto end;
                        }
                    }
                end:;
            }
        }
        else
            cout<<"IMPOSSIBLE"<<endl;

    }
}

D.cpp

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

long long solve(vector<long long> X, vector<int> S, long long C)
{
    int n = (int)X.size();
    vector<pair<long long, int>> XS(n);
    for (int i=0; i<n; i++)
        XS[i] = make_pair(-X[i], S[i]);
    sort(XS.begin(), XS.end());
    for (int i=0; i<n; i++)
    {
        X[i] = -XS[i].first;
        S[i] = XS[i].second;
    }

    long long oo = 1'000'000'000'000'000'000LL;
    vector<long long> T0(n+1, oo);
    vector<long long> T1(n+1, oo);
    T0[0] = T1[0] = 0;
    for (int i=0; i<n; i++)
    {
        vector<long long> P0(n+1, oo);
        vector<long long> P1(n+1, oo);
        P0.swap(T0);
        P1.swap(T1);
        for (int j=0; j<=n; j++)
        {
            if (j>0)
            {
                T0[j] = min(T0[j], P0[j-1]+2*X[i]+(S[i]==1?0:C));
                T1[j] = min(T1[j], P1[j-1]+2*X[i]+(S[i]==0?0:C));
            }
            if (j<n)
            {
                T0[j] = min(T0[j], P0[j+1]+(S[i]==0?0:C));
                T1[j] = min(T1[j], P1[j+1]+(S[i]==1?0:C));
            }
        }
        long long m = min(T0[0], T1[0]);
        T0[0] = T1[0] = m;
    }

    long long ans = oo;
    for (int i=0; i<=n; i++)
    {
        ans = min(ans, T0[i]);
        ans = min(ans, T1[i]);
    }

    return ans;
}

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

        vector<long long> XL, XR;
        vector<int> SL, SR;
        for (int i=0; i<N; i++)
        {
            if (X[i]>0)
            {
                XR.push_back(X[i]);
                SR.push_back(S[i]);
            }
            else
            {
                XL.push_back(-X[i]);
                SL.push_back(S[i]);
            }
        }
        long long ans = solve(XL, SL, C)+solve(XR, SR, C);
        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}