Google Code Jam Farewell Round

A_A.py

T = int(input())
for t in range(T):
    D = list(map(int, input().split()))
    N = int(input())
    S = set()
    for i in range(N):
        s = input()
        s = "".join(str(D[ord(c)-ord("A")]) for c in s)
        S.add(s)
    if len(S)==N:
        ans = "NO"
    else:
        ans = "YES"
    print(f"Case #{t+1}: {ans}")

A_B.py

T = int(input())
for t in range(T):
    M, R, N = map(int, input().split())
    X = list(map(int, input().split()))
    ans = 0
    x = 0
    p = 0
    while p<N:
        if x<X[p]-R:
            ans = "IMPOSSIBLE"
            break
        if p==N-1 or x<X[p+1]-R:
            ans += 1
            x = X[p]+R
            if x>=M:
                break
        p += 1
    if x<M:
        ans = "IMPOSSIBLE"
    print(f"Case #{t+1}: {ans}")

A_C.py

T = int(input())
for t in range(T):
    N = int(input())
    S = list(map(int, input().split()))
    S2 = [S[0]]
    for i in range(1, N):
        if S[i]!=S[i-1]:
            S2 += [S[i]]
    if len(set(S2))==len(S2):
        ans = " ".join(map(str, S2))
    else:
        ans = "IMPOSSIBLE"
    print(f"Case #{t+1}: {ans}")

A_D.py

T = int(input())
for t in range(T):
    N = int(input())
    N -= 1
    i = 1
    while True:
        if N<i*26:
            ans = chr(ord("A")+N//i)
            break
        N -= i*26
        i += 1
    print(f"Case #{t+1}: {ans}")

A_E.py

T = int(input())
for t in range(T):
    C = input()
    CC = []
    n = 1
    for i in range(1, len(C)):
        if C[i]!=C[i-1]:
            CC += [n]
            n = 1
        else:
            n += 1
    CC += [n]
    if len(CC)>1 and C[0]==C[-1]:
        CC[0] += CC[-1]
        CC.pop()
    ans = 0
    if len(CC)>1:
        for c in CC:
            ans += c//2
    else:
        ans += (CC[0]+1)//2
    print(f"Case #{t+1}: {ans}")

B_A.py

def f(a, b):
    if a<b:
        return S[a+(b-a)//2+1]
    else:
        return S[-1]-S[b+(a-b+1)//2]

T = int(input())
for tt in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    La, Ra, Lb, Rb = map(int, input().split())
    La -= 1
    Lb -= 1

    S = [0]*(len(A)+1)
    for i in range(len(A)):
        S[i+1] = S[i]+A[i]
    if Ra<=Lb:
        ans = f(Ra-1, Lb)
    elif Rb<=La:
        ans = f(La, Rb-1)
    else:
        ans = 0
        for a in range(La, Ra):
            if a<Lb:
                t = f(a, Lb)
            elif Rb<=a:
                t = f(a, Rb-1)
            else:
                t = S[-1]
                if Lb<=a-1<Rb:
                    t = min(t, f(a, a-1))
                if Lb<=a+1<Rb:
                    t = min(t, f(a, a+1))
            ans = max(ans, t)
    print(f"Case #{tt+1}: {ans}")

B_B.py

import math

def exgcd(m, n):
    if n>0:
        y,x,d = exgcd(n, m%n)
        return x, y-m//n*x, d
    else:
        return 1, 0, m

T = int(input())
for t in range(T):
    W, N, D = map(int, input().split())
    X = [int(x)-1 for x in input().split()]
    ans = 0
    oo = 10**20
    for i in range(W//2):
        d = X[i]-X[-i-1]
        g = math.gcd(N, D)
        if d%g!=0:
            ans += oo
        else:
            d //= g
            #a = d*pow(D//g, -1, N//g)%(N//g)
            x, y, _ = exgcd(D//g, N//g)
            a = d*x%(N//g)
            ans += min(a, (N//g)-a)
    if ans>=oo:
        ans = "IMPOSSIBLE"
    print(f"Case #{t+1}: {ans}")

B_C.cpp

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

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, K;
        cin>>N>>K;
        vector<int> A(N);
        for (int &a: A)
            cin>>a;

        vector<int> A1 = A;
        sort(A1.begin(), A1.end());
        vector<int> T1(N);
        for (int i=N-1; i>=0; i--)
        {
            auto it = lower_bound(A1.begin(), A1.end(), A1[i]+K);
            T1[i] = 1+(it==A1.end()?0:T1[it-A1.begin()]);
        }

        vector<int> A2(N);
        for (int i=0; i<N; i++)
            A2[i] = -A[i];
        sort(A2.begin(), A2.end());
        vector<int> T2(N);
        for (int i=N-1; i>=0; i--)
        {
            auto it = lower_bound(A2.begin(), A2.end(), A2[i]+K);
            T2[i] = 1+(it==A2.end()?0:T2[it-A2.begin()]);
        }
        reverse(T2.begin(), T2.end());

        map<int,int> M;
        for (int i=0; i<N; i++)
            M[A1[i]] = T1[i]+T2[i]-1;
        cout<<"Case #"<<t<<":";
        for (int a: A)
            cout<<" "<<M[a];
        cout<<endl;
    }
}

B_D.cpp

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

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N, L;
        cin>>N>>L;
        vector<vector<int>> S(L);
        for (int i=0; i<L; i++)
        {
            int K;
            cin>>K;
            S[i] = vector<int>(K);
            for (int &s: S[i])
            {
                cin>>s;
                s--;
            }
        }

        vector<vector<int>> E(N+L);
        for (int i=0; i<L; i++)
            for (int s: S[i])
            {
                E[N+i].push_back(s);
                E[s].push_back(N+i);
            }

        // https://algo-logic.info/articulation-points/
        vector<int> ord(N+L, -1);
        vector<int> low(N+L);
        int d = 0;
        int ans = 0;
        function<void(int, int)> f = [&](int c, int p)
        {
            ord[c] = d++;
            low[c] = ord[c];
            bool x = false;
            for (int e: E[c])
                if (e!=p)
                {
                    if (ord[e]==-1)
                    {
                        f(e, c);
                        low[c] = min(low[c], low[e]);
                        if (ord[c]<=low[e])
                            x = true;
                    }
                    else
                        low[c] = min(low[c], ord[e]);
                }
            if (x && c>=N)
                ans++;
        };
        f(0, -1);

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

B_E.cpp

#include <vector>
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)];
    }
};


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

int main()
{
    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N;
        cin>>N;
        vector<int> D(N);
        for (int &d: D)
            cin>>d, d--;
        vector<long long> C(N);
        for (long long &c: C)
            cin>>c;

        vector<int> P(N);
        for (int d: D)
            P[d]++;

        vector<int> Q;
        for (int i=0; i<N; i++)
            if (P[i]==0)
                Q.push_back(i);

        vector<long long> C2(N);

        long long ans = 0;
        while (!Q.empty())
        {
            int i = Q.back();
            Q.pop_back();

            ans += max(0LL, C[i]-C2[i]);
            C2[D[i]] += C[i];
            if (--P[D[i]]==0)
                Q.push_back(D[i]);
        }

        vector<long long> C3(N);
        for (int i=0; i<N; i++)
            if (P[i]>0)
                C3[D[i]] = C[i];

        //long long a2 = 1000000000LL;
        UnionFind UF(N);
        map<int, long long> M;
        for (int i=0; i<N; i++)
            if (P[i]>0)
                UF.unite(i, D[i]);

        for (int i=0; i<N; i++)
            if (P[i]>0)
                M[UF.root(i)] = 1000000000LL;

        for (int i=0; i<N; i++)
            if (P[i]>0)
            {
                ans += max(0LL, C[i]-C2[i]-C3[i]);
                M[UF.root(i)] = min(M[UF.root(i)], max(0LL, C[i]-C2[i]));
            }

        for (auto m: M)
            ans += m.second;
        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}