CSES Editorials

Introduction

CSES Problemset is a collection of competitive programming problems that are frequently used in contests. This blog post contains a collection of editorials for the problems in CSES Problemset. The solutions are written in C++ and are intended to be teach you the concept of the problem. Problems may be accessed at CSES Problemset.

Template I will be using

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4#define ff(i, a, b) for (int i = a; i <= b; i++)
 5#define fb(i, b, a) for (int i = b; i >= a; i--)
 6#define loop(a, b) for (auto &a : b)
 7#define nl '\n'
 8#define sp ' '
 9#define ll long long
10
11void solve() {
12    // code here
13}
14
15signed main()
16{
17    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
18    cout << fixed << setprecision(10);
19    int tt = 1;
20    // cin >> tt;
21    while (tt--) solve();
22}

Introductory Problems

1. Weird Algorithm

This problem is fairly simple, just apply the algorithm as stated and output the result. This problem is the Collatz Conjecture, which states that for any positive integer n, the sequence will eventually reach 1. The sequence is defined as follows:

• If n is even, divide it by 2.
• If n is odd, multiply it by 3 and add 1.

Code:

1void solve() {
2    ll n; cin >> n;
3    cout << n << sp;
4    while (n != 1) {
5        if (n % 2 == 0) n /= 2;
6        else n = 3 * n + 1;
7        cout << n << sp;
8    }
9}

Note the use of ll which represents long long, if you use int, the number will overflow and cause WA.

2. Missing Number

This problem is also simple, just take the sum of all the provided numbers (accumulate(a.begin(), a.end(), 0ll)) and subtract it from the expected sum. You can find the expected sum using the formula \(S_n = \frac{n(n+1)}{2}\).

Code:

1void solve() {
2    ll n; cin >> n;
3    vector<ll> a(n-1);
4    loop(x, a) cin >> x;
5    cout << (n * (n + 1ll) / 2ll) - accumulate(a.begin(), a.end(), 0ll) << nl;
6}

1ll stands for 1 as a long long integer

3. Repetitions

This problem can be solved using a simple loop, for each position i, check if it a[i] == a[i-1], if it is, increment the count. If not, update the global maximum.

 1void solve() {
 2    string s; cin >> s;
 3    int n = s.size();
 4    int max_count = 1, count = 1;
 5    ff(i, 1, n-1) {
 6        if (s[i] == s[i-1]) count++;
 7        else {
 8            max_count = max(max_count, count);
 9            count = 1;
10        }
11    }
12    cout << max(max_count, count) << nl;
13}

Note that max_count is updated after the loop, in case the longest repetition is at the end of the string.

4. Increasing Array

This problem introduces the concept of greedy, which is common by taking the local optimum. This problem can be solved by increasing each element to the maximum of the previous element.

 1void solve() {
 2    int n; cin >> n;
 3    vector<int> a(n);
 4    loop(x, a) cin >> x;
 5    ll ans = 0;
 6    ff(i, 1, n-1) {
 7        ans += max(0, a[i-1] - a[i]);
 8        a[i] = max(a[i], a[i-1]);
 9    }
10    cout << ans << nl;
11}

Remember to update the current element to the maximum of the previous element, otherwise the next element will not be correct.

5. Permutations

This problem can be solved by trying out the first few test cases. For example:

• For n = 1, the only permutation is 1.
• For n = 2, the only permutation is 1 2 or 2 1.
• For n = 3, the only permutation is 1 2 3 or 3 1 2 or 2 1 3. All of which are invalid per the condition of the statement.
• However, for n = 4, we can arrange it in this way: 2 4 1 3
• Similarly, for n = 5, we can arrange it in this way: 2 4 1 3 5, notice the pattern?

Code:

1void solve() {
2    int n; cin >> n;
3    if (n == 1) cout << 1;
4    else if (n == 2 || n == 3) cout << "NO SOLUTION";
5    else {
6        for (int i = 2; i <= n; i += 2) cout << i << sp;
7        for (int i = 1; i <= n; i += 2) cout << i << sp;
8    }
9}

6. Number Spiral

This problem starts to get tricky and needed a little bit of observation. If you draw out the first few numbers as such:

Observation 1: Notice the pattern, for each number, it is always in the square of its larger square number closest to it. For example, 3’s closest greater square is 4, and you can find 3 on Row 2 and Column 2. Similarly, 5’s closest greater square is 9, and you can find 5 on Row 3 and Column 1.

Since we are given the x and y coordinates, we can find the maximum of x and y, and find the inner square of it. This means we find the starting point of our square, a quick example: if we are given x = 3 and y = 2, the maximum is 3, and the inner square is \((3-1)^2 = 4\). We start the search from 5, since the inner square contains numbers up to 4.

Observation 2: The numbers starts either from the column downwards or the row to the right. If it is even (0-based indexing), it starts from the row to the right, otherwise it starts from the column downwards. An example would be x = 3 and y = 2, x-1 is even, so it starts from the row to the right.

After we know its starting point, just add the difference between the coordinate and the starting point.

 1void solve() {
 2    ll y, x; 
 3    cin >> y >> x;
 4    ll n = max(y, x);
 5    if (n % 2 == 0) {
 6        // even layer
 7        if (y == n) {
 8            cout << n*n - (x - 1) << nl;
 9        } else {
10            cout << (n - 1)*(n - 1) + y << nl;
11        }
12    } else {
13        // odd layer
14        if (x == n) {
15            cout << n*n - (y - 1) << nl;
16        } else {
17            cout << (n - 1)*(n - 1) + x << nl;
18        }
19    }
20}

Mathematics Problems

2. Exponentiation

If the algorithm is done naively, the multiplication will take O(nb) time, where n is the number of test cases and b is the number of exponentiation needed to be done on a. We can do better. We can do better.

\(a^{b+c} = a^b \cdot a^c\) is a simple bit of exponentiation math, and we can make \(a^{2b} = a^b \cdot a^b = (a^b)^2\). Then we can apply the following algorithm:

The solution is as follows:

 1int MOD = 1e9+7;
 2
 3int fastExp(int a, int b) {
 4    if (b == 0) return 1;
 5    int res = fastExp(a, b/2);
 6    int res_square = (res * res) % MOD;
 7    if (b % 2 == 0) return res_square;
 8    else return (res_square * a) % MOD;
 9}
10
11void solve() {
12    int a, b; cin >> a >> b;
13    cout << fastExp(a,b) << nl;
14}

Note that MOD is used after every multiplication process, you can read more about it here.