Monday, April 18, 2016

Google Code Jam 2016 Round 1A 2016 Problem B. Rank and File

// Google Code Jam 2016 Round 1A 2016 Problem B. Rank and File
// Problem URL: https://code.google.com/codejam/contest/4304486/dashboard#s=p1&a=0

#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <limits>

using namespace std;

typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;

//==================================
void solve()
{
    int numCases = 1;
    cin >> numCases;

    for ( int ncase=1; ncase <= numCases; ncase++ )
    {
        //===== start case
        int N;
        cin >> N;
        int num[2501];
        for (int i=0; i<=2500; i++)
            num[i]=0;
        int x;
        for (int i=0; i<2*N-1; i++) {
            for (int j=0; j<N; j++) {
                cin >> x;
                num[x]+=1;
            }
        }
        vector<int> v;
        for (int i=1; i<=2500; i++) {
            if (num[i]%2==1)
                v.push_back(i);
        }

        sort(v.begin(),v.end());

        cout << "Case #" << ncase << ": ";
        for (int i=0; i<N; i++) {
            cout << v[i] << " ";
        }
        cout << endl;

        //===== end case

    }
}

int main()
{
    solve();
    return 0;

}



Google Code Jam 2016 Round 1A 2016 A. The Last Word

// Google Code Jam 2016 Round 1A 2016
// Problem A. The Last Word
// Problem URL: https://code.google.com/codejam/contest/4304486/dashboard#s=p0&a=0


#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <limits>

using namespace std;

typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<long long> vll;

void solve()
{
    int numCases = 1;
    cin >> numCases;

    for ( int ncase=1; ncase <= numCases; ncase++ )
    {
        //===== start case
        string S;
        cin >> S;

        string ans=S.substr(0,1);
        for ( int i=1; i<S.size(); i++ )
        {
            if (S[i]>=ans[0])
                ans = S.substr(i,1) + ans;
            else
                ans = ans + S.substr(i,1);
        }
        cout << "Case #" << ncase << ": ";
        cout << ans << endl;

        //===== end case
    }
}

int main()
{
    solve();
    return 0;

}

Friday, January 22, 2016

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Facebook Hacker Cup 2015 Qualification Round, Cooking the Books

Problem Statements:
https://www.facebook.com/hackercup/problem/582062045257424/

Solution:
We could solve the problem by testing all possible numbers when any 2 digits are swapped.
We swap position i and j for every possible i and j where 1<i<9 and 1<j<9, so the number of all possible combination is small enough for brute force attack.

Example codes:

            long T = inp.NextInt ( );
            for ( int t = 0; t < T; t++ )
            {
                long N = inp.NextLong ( );
                string sn = N.ToString ( );
                char[] cn = sn.ToCharArray ( );
                string ans = "";
                if ( N < 10 )
                {
                    ans = string.Format ( "{0} {1}", N, N );
                }
                else
                {
                    string snmin = sn;
                    string snmax = sn;
                    for ( int i = 0; i < sn.Length; i++ )
                    {
                        for ( int j = i + 1; j < sn.Length; j++ )
                        {
                            //swap then test
                            char[] cc = cn.ToArray ( );
                            char tmp = cc[i];
                            cc[i] = cc[j];
                            cc[j] = tmp;
                            string st = new string ( cc );
                            if ( st.CompareTo ( snmin ) < 0 && st[0] != '0' )
                                snmin = st;
                            if ( st.CompareTo ( snmax ) > 0 )
                                snmax = st;
                        }
                    }

                    ans = string.Format ( "{0} {1}", snmin, snmax );
                }

                Console.WriteLine ( "Case #{0}: {1}", t + 1, ans );
            }