Problem A: A?C

Check the element at 1st index and print “ARC” or “ABC” accordingly.

Code

 
/**
 * The code below is just a snippet of solution code.
*/
string s;
cin >> s;

if (s[1] == 'B') {
	cout << "ARC" << endl;
} else {
	cout << "ABC" << endl;
}

Problem B: Trick or Treat

Simplified problem:

  • Given N bins and K type of balls, each type of ball is present in some bins.
  • Find the count of bins in which no there is no ball.

Hint
  • Just build a count array denoting the no. of balls present in a particular bin.
  • The answer is just the count of bins having ZERO balls present in them.

Code

 
void solve() {
    int n, k;
    cin >> n >> k;

    int d, x;
    vector<int> cnt(n, 0);
    for (int i = 0; i < k; ++i) {
        cin >> d;
        for (int j = 0; j < d; ++j) {
            cin >> x;
            ++cnt[x-1]; // 0-based
        }
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (cnt[i] == 0) {
            ++res;
        }
    }
    cout << res << endl;
}

Problem C: Peaks

Simplified problem:

  • Given a graph with N nodes and M undirected edges, and each node has a value H[i] associated with it.
  • Find the count of nodes which either do not have any adjacent nodes, or whose value is more than all of its adjacent nodes.

Hint
  • Create an adjacency list and the answer is the sum of nodes with no element in this list or
  • the nodes whose all elements in the adjacency list have a value less than the node's value.

Code

 
void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> h(n);
    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    int a, b;
    vector<int> adj[n];
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        --a; --b; // 0-based
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (adj[i].size() == 0) {
            ++res;
            continue;
        }
        int curval = h[i];
        bool possible = true;
        for (auto next: adj[i]) {
            if (h[next] >= curval) {
                possible = false;
                break;
            }
        }
        if (possible) {
            ++res;
        }
    }
    cout << res << endl;
}

Problem D: I hate factorization

Simplified problem: Given an integer X find integers A and B such that

Hint
  • Since X is an integer, can we somehow brute force over values of A and B?
  • Can A and B ever exceed 1000? (The limit can be further narrowed)

Code

 
typedef long long ll;
void solve() {
    ll x;
    cin >> x;
    ll res_a = 0, res_b = 0;
    bool done = false;
    for (int a = -1000; a <= 1000; ++a) {
        for (int b = -1000; b <= 1000; ++b) {
            ll v1 = pow(a, 5);
            ll v2 = pow(b, 5);
            if (v1 - v2 == x) {
                res_a = a;
                res_b = b;
                done = true;
                break;
            }
        }
        if (done) {
            break;
        }
    }
    cout << res_a << " " << res_b << endl;
}

Problem E: This Message Will Self-Destruct in 5s

Simplified problem: Given an array arr containing N integers, find the no. of pairs

where and

Hint
  • Try to rearrange the expression to bring terms containing i and j separately. $$ j - arr[j] = i + arr[i] $$
  • So, you need to count the pair of indices in the array for which the above expression holds true.
  • As you iterate over the array, store the count of say (i + arr[i]) in a map (say cnt), also add $$ cnt[i - arr[i]] $$ to the result before adding to count of (i + arr[i]). This will count the pairs where the current index is the second one in the pair. It will be more clear in the code below.

Code

 
void solve() {
    int n;
    cin >> n;

    vector<ll> a(n);
    for (auto &x: a) {
        cin >> x;
    }

    ll res = 0;
    map<ll, ll> cnt;
    for (int i = 0; i < n; ++i) {
        ll cur = i - a[i];
        res += cnt[cur];
        ++cnt[i + a[i]];
    }
    cout << res << endl;
}

Problem F: Three Variables Game

Simplified problem:

Hint

Code