CodeJam 2019 1C

2019.05.04 coding codejam cpp algo

I haven’t been working on these problem for a really long time, therefore, it took be quite some time to hammer out some of the bugs I had.

Problem A: Robot Rock Paper Scissors

This was a rather easy problem, but I made some wrong assumption that the start, which caused me quite a lot of headache to debug.

But the general idea is as such

for the first move, look at all the first moves of all the other robots.
if all 3 moves exist, it is impossible to have a sure winning move.
in other cases, it is always possible to eliminate some of the other robots.
repeat the same steps for the other robots still alive. looping the entries if needed.
end when all the other robots are dead.

Solution in CPP:

#include <bits/stdc++.h>
#define let const auto
#define REP(var, i) for (int var = 0; var < i; ++var)
using namespace std;
using Int = int;
//using Int = long long;
using vi = vector<Int>;
using vvi = vector< vector<Int> >;

#define O_R 4
#define O_P 2
#define O_S 1 
#define N 5 

void solve() { 
    int A; cin >> A; 
    vector<string> seq; string s;
    char *mask = (char*) calloc(N, sizeof(char));

    REP(i, A){ 
        cin >> s; seq.push_back(s);
    }

    char *ans = (char*) calloc(501, sizeof(char));
    char *dead = (char*) calloc(A, sizeof(char));

    char c, m; char impossible = 0;
    for (int p=0; p<500; p++) {
        c = 0;

        REP(i, A){
            if (!dead[i]) {
                s = seq[i];
                m = seq[i][p%s.size()];

                if (m == 'R') c |= O_R;
                if (m == 'P') c |= O_P;
                if (m == 'S') c |= O_S;
            }
        }

        if (c == 7) {
            impossible = 1; break;
        }

        if (c == O_R) { ans[p] = 'P'; break; }
        if (c == O_P) { ans[p] = 'S'; break; }
        if (c == O_S) { ans[p] = 'R'; break; }

        c = c^7;
        if (c == O_R) ans[p] = 'S';
        if (c == O_P) ans[p] = 'R';
        if (c == O_S) ans[p] = 'P';

        REP(i, A){
            if (!dead[i]) {
                s = seq[i]; 
                if (ans[p] != seq[i][p%s.size()]) dead[i] = 1;
            }
        }
    }

    if (impossible) printf("IMPOSSIBLE");
    else printf("%s", ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T; cin >> T;
    REP(t, T) {
        printf("Case #%d: ", t+1);
        solve();
        printf("\n");
    }
}

Problem B: Power Arrangers, finding missing permutation

This is a really cool problem. I wrote out quite a bit to finally see the pattern. And once you realize the pattern, it is a rather easy problem to tackle.

The solution can be briefly explained as so:

If you list down all the first characters of each different set, we will have 24 counts of each letter (120/5 = 24), except for one, this will give us the 1st letter of the missing set
Doing the same for the second character, we should have (24/4 = 6) counts of each letter
Then the third and forth character. And by elimination, we get the last character.
This will take us a total of (120-1) + (24-1) + (6-1) + (2-1) <= 150 moves

#include <bits/stdc++.h>
#define let const auto
#define REP(var, i) for (int var = 0; var < i; ++var)
using namespace std;
using Int = int;
//using Int = long long;
using vi = vector<Int>;
using vvi = vector< vector<Int> >;

void solve() {
    char *out = (char*) calloc(119, sizeof(char));
    vector<vector<int>> heros;

    REP(i, 5){
        heros.push_back(vector<int>());
    }
    
    char left = 0;
    char ans[6] = {'A', 'A', 'A', 'A', 'A', 0}; 
    char used[5] = {0, 0, 0, 0, 0};
    int counts[4] = {24, 6, 2, 1};

    char c; 
    int n; vector<int> outed;

    int i, p;
    for(p=0; p<4; p++){
        for(i=0; i<119; i++){
            if (out[i]==p) {
                cout << i*5 + p+1 << endl; 
                cin >> c; 

                heros[c-'A'].push_back(i);
            } 
        }
        
        for(i=0; i<5; i++){
            if(!used[i] && heros[i].size()<counts[p]){
                used[i] = 1;
                ans[p] += i; 
                left += i;

                outed = heros[i];
                n = outed.size();

                REP(ii, n){
                    out[outed[ii]] += 1; 
                }
            }
        }

        for(i=0; i<5; i++){
            heros[i].clear();
        }

    }

    ans[4] += 10-left;
    cout << ans << endl; 
    cin >> c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T, F; cin >> T >> F;

    REP(t, T) {
        solve();
    }
}