23 August 2018: ANZAC Round 1 2017 Problems C & D

From UMCPC Wiki
Jump to navigation Jump to search

This week, in preparation for next weekend, we will discuss some questions from ANZAC Round 1 of last year.

You may want to look at problem D first, as it is a bit easier. You can take a look at problems E and F if you get through these quickly.

Problem C. Crazy Email Chains

#include <bits/stdc++.h>

using namespace std;

#define UNVISITED -1
#define EXPLORED -2
#define NOT_WORTH 0
#define WORTH 1
#define MAXN 100000

unordered_map<string, string> parent(MAXN);
unordered_map<string, int> state(MAXN);

int dfs(const string& name) {
    if (state[name] == EXPLORED) return state[name] = 0;
    if (state[name] != UNVISITED) return state[name];
    state[name] = EXPLORED;
    return state[name] = dfs(parent[name]);
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        string s0, s1, s2;
        cin >> s0 >> s1 >> s2;
        if (s1 == "->") {
            parent[s0] = s2;
            state[s0] = UNVISITED;
        } else {
            parent[s0] = s0;
            state[s0] = WORTH;
        }
    }
    for (auto& kv : state) {
        if (kv.second == UNVISITED) {
            dfs(kv.first);
        }
    }
    int count = 0;
    for (auto& kv : state) {
        count += kv.second;
    }
    cout << count << endl;
    return 0;
}

Problem D. Deconstructed Password

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200000

int N;
int code[MAXN];
char s[MAXN];

bool dfs(int i, char ch) {
    if (i == N) return true;
    if (i > N || i < 0 || s[i]) return false;
    s[i] = ch;
    return dfs(code[i]-1, ch);
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> code[i];
    }
    char next = 'a';
    for (int i = 0; i < N; i++) {
        if (!s[i] && (next > 'z' || !dfs(i, next++))) {
            cout << -1 << endl; 
            return 0;
        }
    }
    cout << s << endl;
    return 0;
}