Problem A: Registration

Given two strings S and T, check if T can be obtained by appending exactly one letter to the end of S.

Code

 
void solve() {
    string s, t;
    cin >> s >> t;
    for (char ch = 'a'; ch <= 'z'; ++ch) {
        if (s + ch == t) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

Problem B: Easy Linear Programming

Problem Statement:

  • There are A cards with value 1, B cards with value 0 and C cards with value -1.
  • You need to pick up exactly K cards so that the sum of numbers on the cards is maximized.

Hint
  • Try to pick as many as cards with value 1 possible, next with 0 and finally with value -1.

Code

 
void solve() {
    ll a, b, c, k;
    cin >> a >> b >> c >> k;

    ll res = 0;
    // pick cards with value 1
    res += min(a, k);
    k -= min(a, k);

    if (k == 0) {
        cout << res << endl;
        return;
    }

    // pick cards with value 0
    k -= min(b, k);
    if (k == 0) {
        cout << res << endl;
        return;
    }

    // pick cards with value -1
    res -= min(c, k);
    k -= min(c, k);
    cout << res << endl;
}

Problem C: Skill Up

Problem Statement:

  • There are M algorithms, for each of them, you have an understanding level of 0 initially.
  • There are N books, each of them costing some value, say C[i] for i-th book, and by reading the i-th book, the level of understanding of j-th algorithm gets increased by A[i][j].
  • You need to make the understanding level of each algorithm greater or equal to X.
  • Tell whether it is possible to do so by buying some subset of the books and if so, print the minimum cost of books which will achieve it.

Constraints:

Hints
  • Check the constraints of the values of N and M in the problem statement.
  • For every book, you have 2 choices to make, either buy it or don't.
  • Apply standard recursion to check for cost in each possibility, and take the minimum one, and also check that level of understanding for each book must be greater or equal to X in the end!

Code

 
int n, m, x;
int res;

void rec_solve(int cur, int cost, vector<pair<int, vector<int>>>& books, vector<int> levels) {
    if (cur == books.size()) {
        for (int i = 0; i < m; ++i) {
            if (levels[i] < x) {
                return;
            }
        }
        res = min(res, cost);
        return;
    }
    // don't pick the book
    rec_solve(cur + 1, cost, books, levels);
    // pick the book
    for (int i = 0; i < m; ++i) {
        levels[i] += books[cur].second[i];
    }
    rec_solve(cur + 1, cost + books[cur].first, books, levels);
}

void solve() {
    cin >> n >> m >> x;

    int c;
    vector<pair<int, vector<int>>> books;
    for (int i = 0; i < n; ++i) {
        cin >> c;
        vector<int> level(m);
        for (auto &l: level) {
            cin >> l;
        }
        books.push_back({c, level});
    }

    res = INT_MAX;
    vector<int> levels(m, 0);
    rec_solve(0, 0, books, levels);
    
    if (res == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << res << endl;
    }
}

Problem D: Teleporter

Problem Statement:

  • You are given an array contains N values, each in the range of 1 to N, (may not be all distinct).
  • You are currently at position 1 in the array. (consider 1-based indexing).
  • At each step, if you are position pos, you get to arr[pos].
  • You need to find out the position where you will be after K steps.

Constraints:

Hints
  • Since K is very large, we cannot simulate the entire process. So there must be some mathematics involved since we just need the final position.
  • We are at position 1 initially, and in atmost N steps, we will reach a position which is already visited earlier (why?). So, what happens next?
  • We will keep on looping over from the start of the cycle, to the same positions visited earlier from the cycle start.
  • Consider the example arr = [3, 2, 4, 3]. We go from 1 -> 3 -> 4 -> 3. After this, we will keep on looping between 3 and 4.
  • See what all do we need to compute the final position after K steps, we will need the start of the cycle and when it is reached (steps) and also the length of the cycle.
  • We will cover some steps before cycle start, say done, and remaining steps will be k - done. We can find remainder of it when divided by cycle length and then simulate the process that many times to get the final position, see code for details.

Code

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

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

    vector<int> next(n, -1);
    int cur = 0;
    vector<int> steps;
    while (next[cur] == -1) {
        next[cur] = arr[cur] - 1; // 0-based indexing
        cur = next[cur];
        steps.push_back(cur);
    }
    int cycle = cur; // start of cycle
    int len = 1; // length of cycle
    cur = next[cycle];
    while (cur != cycle) {
        cur = next[cur];
        ++len;
    }
    
    // already covered before cycle start
    int done = steps.size() - len;
    // remaining steps
    int rem = (k - done) % len;

    if (k <= steps.size()) { // if before cycle starts
        cout << 1 + steps[k - 1] << endl; // 1-based indexing
    } else { // simulate for remaining steps
        cur = cycle;
        while (rem) {
            cur = next[cur];
            --rem;
        }
        cout << 1 + cur << endl; // 1-based indexing
    }
}