Solutions to CSES Problemset

Problem

First of all we need to check whether we can divide numbers 1 to n into two groups with equal sum. This means that we need to be able to divide the sum of 1 to n into two, in other words the sum of 1 to n is even. \[ S_n = n * (n + 1) / 2 \]

Later we need to divide them into two groups with equal sum.

    vll s1, s2;
    vll visited(n+1, 0);

    ll sum = n*(n+1)/4;
    ll sum_s1 = 0;
    ll max = n;

    while (sum > sum_s1) {
        ll remaining = sum - sum_s1;

        if (remaining > max) {
            s1.pb(max);
            visited[max] = 1;
            sum_s1 += max;
            max--;
        } else {
            s1.pb(remaining);
            visited[remaining] = 1;
            sum_s1 = sum;
        }
    }

    for (ll i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            s2.push_back(i);
        }
    }

Although not directly related, there is a similar problem in number theory named partition problem.

keywords: parity, partition problem, greedy algorithm

Problem

The solution to this problem is pretty simple and straight forward. All we need to do is to calculate \(2^n\). The problem is that for large n’s the solution takes a long time to compute. Therefore we have to implemented an algorithm called Binary Exponentiation to compute this power in O(log n).

Problem

Gray Code on Wikipedia

Problem One of the most famous problems in computer science. This is can be solved through recursion.

void Hanoi(int n, int i, int j, int k) {
    if (n == 0) {
        return;
    }

    Hanoi(n - 1, i, k, j);
    cout << i << " " << j << "\n";
    Hanoi(n - 1, k, j, i);
}

This basically means that the solution to the whole problem is the same as the solution to a sub-problem of this. Note: Recursion and induction have something fundamental in common.

Recursion on Wikipedia Tower of Hanoi on Wikipedia

Problem

This was a pretty straight forward problem to solve. All you need to do is to use the recursive technique you have learned before:

set<string> P(string str) {
    set<string> sol;
    if (str.length() == 1) {
        sol.insert(str);
        return sol;
    }

    for (int i = 0; i < str.length(); i++) {
        char c1 = str[i];
        string r = rest(str, i);
        for (auto s : P(r)) {
            sol.insert(c1 + s);
        }
    }
    return sol;
}

Problem

A fantastic problem known as “N Queens problem”. The goal is to compute the number of ways we can place n queens on a n by n chessboard such that they do not attack each other. This problem is solved through a technique called Backtracking. To put it simply, we check all the possible solutions one by one. The only challenge we have here is that some squares are already reserved so we need to check for them while putting the queens on the board.

#define N 8

int counter = 0;
vector<int> col(N*N);
vector<int> diag1(N*N);
vector<int> diag2(N*N);
char board[N][N];

void solve(int y) {
    if (y == N) {
        counter++;
        return;
    }

    for (int x = 0; x < N; x++) {
        if (board[y][x] == '*' || col[x] || diag1[x+y] || diag2[x-y+N-1]) continue;
        col[x] = diag1[x+y] = diag2[x-y+N-1] = 1;
        solve(y+1);
        col[x] = diag1[x+y] = diag2[x-y+N-1] = 0;
    }
}