Introductory Problems - CSES Problem Set Solutions

I solved all problems on this page without any hints/spoilers (not even reading the CSES recommended book).

Visit https://cses.fi/problemset/ for the full problem set.

I don't provide the full problem specifications on this page due to possible copyright issues. Links to the original problem specs are provided below along with the date accessed, which should allow you to use Internet Archive if the original URL hosting a problem specification ever meaningfully changes.

Weird Algorithm [Spec] (2023-12-31)

#!/usr/bin/env python3

n = int(input())
while n > 1:
    print(n, end=" ")
    if n % 2:
        n = (n * 3) + 1
    else:
        n //= 2
print(n)

Missing Number [Spec] (2023-01-02)

We take the expected sum of all numbers sum_all, calculated using Arithmetic Series, and subtract the numbers we have to get the missing number.

#!/usr/bin/env python3
 
n = int(input())
nums = [int(s) for s in input().split()]
 
sum_all = (n * (1 + n)) // 2
print(sum_all - sum(nums))

TODO: There’s a cool bit manipulation solution for this that I should study.

Repetitions [Spec] (2023-01-02)

#!/usr/bin/env python3

s = input()

prev = None
cur_len = 0
solution = 0
for c in s:
    if c == prev:
        cur_len += 1
    else:
        prev = c
        cur_len = 1
    solution = max(solution, cur_len)

print(solution)

Increasing Array [Spec] (2023-01-02)

#!/usr/bin/env python3

input()
nums = [int(s) for s in input().split()]

cur = 0
solution = 0
for n in nums:
    if n < cur:
        solution += cur - n
    else:
        cur = n

print(solution)

Permutations [Spec] (2023-01-02)

y initial solution was unnecessarily messy because I was sorting out the edge cases.

#!/usr/bin/env python3 n = int(input()) if n == 1: print("1") elif n <= 3: print("NO SOLUTION") elif n == 4: print("2 4 1 3") else: for i in range(1, n + 1, 2): print(i, end=" ") for i in range(2, n + 1, 2): print(i, end=" ") print()

I improved on my initial solution by swapping the loop order and cutting the branches:

#!/usr/bin/env python3
 
n = int(input())

if (n == 2) or (n == 3):
    print("NO SOLUTION")
else:
    for i in range(2, n + 1, 2):
        print(i, end=" ")
    for i in range(1, n + 1, 2):
        print(i, end=" ")
    print()

Number Spiral [Spec] (2023-01-03)

Let’s work with the same $5 \times 5$ grid shown in the spec to get a feel for how this works, and let’s query for $y = 3$ and $x = 4$ .

1	2	9	10	25
4	3	8	11	24
5	6	7	12	23
16	15	14	13	22
17	18	19	20	21

I arbitrarily chose to zero-index the coordinates, so the new zero-indexed coordinates are $y' = 2$ and $x' = 3$ .

I started by calculating the “layer number” of the queried coordinates, and recognizing that the only information you need about the previous layers is the total number of cells in all previous layers (excluding the aforementioned layer number):

1	2	9	10	25
4	3	8	11	24
5	6	7	12	23
16	15	14	13	22
17	18	19	20	21

In the figure above, we see that there are $9$ cells in the previous layers.

Therefore, the largest number in all the previous layers is $9$ , and the current layer will start with $10$ . All we need now is to index within the layer.

First, we need to know the direction of counting:

Layer:	0	1	2	3	4
	↗	↓	↑	↓	↑
	←	↙	↑	↓	↑
	→	→	↗	↓	↑
	←	←	←	↙	↑
	→	→	→	→	↗

We notice here that odd-numbered layers count “downward” while even-numbered layers count “upward”. Therefore, for the example query, the layer counts downwards.

This should be sufficient background to understand my initial solution:

#!/usr/bin/env python3

from sys import stdin

stdin.readline()
tests = [s.strip().split() for s in stdin.readlines()]

for y, x in tests:
    (y, x) = (int(y) - 1, int(x) - 1)
    layer = max(y, x)
    count_prev_layers = layer * layer

    if layer % 2:
        # odd layer --> downwards
        if y < x:
            # vertical section
            print(count_prev_layers + 1 + y)
        else:
            # horizontal section
            print(count_prev_layers + (layer * 2) + 1 - x)
    else:
        # even layer --> upwards
        if y < x:
            # vertical section
            print(count_prev_layers + (layer * 2) + 1 - y)
        else:
            # horizontal section
            print(count_prev_layers + 1 + x)

For fun, I decided to refactor into smaller code:

#!/usr/bin/env python3 from sys import stdin stdin.readline() tests = [s.strip().split() for s in stdin.readlines()] for y, x in tests: (y, x) = (int(y) - 1, int(x) - 1) layer = max(y, x) count_prev_layers = layer * layer if not (layer % 2): (y, x) = (x, y) if y < x: print(count_prev_layers + 1 + y) else: print(count_prev_layers + (layer * 2) + 1 - x)

#!/usr/bin/env python3 from sys import stdin stdin.readline() tests = [s.strip().split() for s in stdin.readlines()] for y, x in tests: (y, x) = (int(y) - 1, int(x) - 1) layer = max(y, x) if not (layer % 2): (y, x) = (x, y) print((layer * layer) + 1 + (y if (y < x) else ((layer * 2) - x)))

Though, these refactorings start becoming less intuitive and comprehensible.

Two Knights [Spec] (2023-01-03)

The approach I went with was terribly lazy. I imagine there are some fancy combinatorics solutions? But I wasn’t too sure how to incorporate the knight movements and board geometry. But hey, whatever works!

I started with a hardcoded table for $k \le 7$ to get past some edge cases for low values of $k$ . I chose $7$ arbitrarily and didn’t think too deeply about what the smallest hardcoded table I can get away with is. It would’ve been tough to calculate up to $k = 7$ by hand, but I just used the example solution in the spec. How convenient!

My solution considers “layers” in a vaguely similar way my Number Spiral solution did.

Let’s suppose a solution for layer $k = 7$ is already known to have $1056$ ways to place two knights. Therefore, we have “seen” a $7 \times 7$ grid of cells ( $49$ cells):

We seek to add another “layer” to this known square to get a solution for layer $k = 8$ :

To do this, we take the approach of adding one more square at a time, and after adding each square, we recalculate the solution.

Let’s start by placing one new square at the bottom-left corner. The new square is labelled K while the squares that a knight placed on K can attack are labelled #:






	#
		#
K

So now, how many times can we place two knights in these $50$ cells? We find that there are $1056 + 49 - 2 = 1103$ ways to place two knights in these $50$ cells. The $-2$ in that calculation comes from accounting for the two squares that a knight in the new square can attack.

Formula:

new_solution = prev_solution + prev_number_of_squares - ways_new_knight_can_attack_old_squares

Next, we add another square in the new layer. With the new square, there are now $1103 + 50 - 3 = 1150$ ways to place two knights in these $51$ squares:






#		#
			#
	K

We simply keep going until the whole layer has been added and a solution for the whole layer has been calculated.

#!/usr/bin/env python3

n = int(input())

for k in range(1, min(8, n + 1)):
    print({1: 0, 2: 6, 3: 28, 4: 96, 5: 252, 6: 550, 7: 1056}[k])

acc = 1056
seen = 7 * 7
for k in range(8, n + 1):
    # corner
    acc += seen - 2
    seen += 1
    # next square
    acc += seen - 3
    seen += 1
    # continue until near corner
    # -1 since we're skipping the very corner
    # -2 since we've already done two squares
    # -2 since we're also going to hardcode the final two squares
    for _ in range(k - 1 - 2 - 2):
        acc += seen - 4
        seen += 1
    # more hardcodes
    acc += seen - 3
    seen += 1
    acc += seen - 2
    seen += 1
    # start again
    # corner
    acc += seen - 2
    seen += 1
    # next square
    acc += seen - 3
    seen += 1
    # this time, we're not skipping the very corner, so just -2 -2
    for _ in range(k - 2 - 2):
        acc += seen - 4
        seen += 1
    # more hardcodes
    acc += seen - 3
    seen += 1
    acc += seen - 2
    seen += 1
    print(acc)

Two Sets [Spec] (2023-01-03)

#!/usr/bin/env python3

n = int(input())

def print_set(lst):
    print(len(lst))
    print(" ".join(str(x) for x in lst))

def walk(lst, i, j):
    while i > j:
        lst.extend((i, j))
        (i, j) = (i - 2, j + 2)
    return lst

if n <= 2:
    print("NO")
elif n % 2:
    if (((n - 1) // 2) % 2):
        print("YES")
        print_set(walk([n], n - 2, 2))
        print_set(walk([], n - 1, 1))
    else:
        print("NO")
elif not ((n // 2) % 2):
    print("YES")
    print_set(walk([], n, 1))
    print_set(walk([], n - 1, 2))
else:
    print("NO")

Bit Strings [Spec] (2023-01-04)

This problem is boring in Python. Maybe they should’ve pushed the input bounds a couple orders of magnitude larger?

#!/usr/bin/env python3
 
n = int(input())
print((1 << n) % ((10**9) + 7))

TODO: How to do it with fixed-size integers?

Trailing Zeros [UNFINISHED] [Spec] (2023-01-13)

The first thing that comes to mind is to consider the conditions where trailing zeroes appear. Let’s start by considering the multiplication definition of factorial:

n! = \prod_{k = 1}^n{k}, \qquad\qquad \forall n \in \mathbb{Z} : n > 0. \qquad\qquad 0! = 1.

Trivially, $k$ being a multiple of $10$ will yield a trailing zero, but so will a trailing $5$ multiplied by a trailing $2$ , among other combinations like $4$ and $5$ .

A possible naive algorithm that comes to mind at this point might be to incrementally calculate the factorial, including a new term of $k$ at each step while also truncating (and recording) trailing zeroes that appear. However, this approach is flawed since the number of non-zero digits is expected to explode.

A better approach might involve something like truncating the left side of a $k$ -term to get only the least-significant non-zero and all the zeroes to its right. However, is it possible that this least-significant non-zero digit is ever entirely consumed?

Let’s enumerate all possible pairs of non-zero digits:

$a$	$b$	$ab$
$1$	$1$	$1$
$1$	$2$	$2$
$1$	$3$	$3$
$1$	$4$	$4$
$1$	$5$	$5$
$1$	$6$	$6$
$1$	$7$	$7$
$1$	$8$	$8$
$1$	$9$	$9$

$a$	$b$	$ab$
$2$	$2$	$4$
$2$	$3$	$6$
$2$	$4$	$8$
$2$	$5$	$10$
$2$	$6$	$12$
$2$	$7$	$14$
$2$	$8$	$16$
$2$	$9$	$18$

$a$	$b$	$ab$
$3$	$3$	$9$
$3$	$4$	$12$
$3$	$5$	$15$
$3$	$6$	$18$
$3$	$7$	$21$
$3$	$8$	$24$
$3$	$9$	$27$

$a$	$b$	$ab$
$4$	$4$	$16$
$4$	$5$	$20$
$4$	$6$	$24$
$4$	$7$	$28$
$4$	$8$	$32$
$4$	$9$	$36$
$5$	$5$	$25$
$5$	$6$	$30$
$5$	$7$	$35$
$5$	$8$	$40$
$5$	$9$	$45$

$a$	$b$	$ab$
$6$	$6$	$36$
$6$	$7$	$42$
$6$	$8$	$48$
$6$	$9$	$54$
$7$	$7$	$49$
$7$	$8$	$56$
$7$	$9$	$63$
$8$	$8$	$64$
$8$	$9$	$72$
$9$	$9$	$81$

We notice that no pair ever generates purely zeroes, therefore we can design an algorithm that ignores all digits beyond this least-significant non-zero digit.

Our next issue is to scale the algorithm for the $n \le {10}^9$ bound. Processing all ${10}^9$ terms of $k$ will be a very expensive operation.

My first idea is to try batching cycles where the least-significant non-zero digit goes through digits $1, \dots, 9$ in a cycle. For example, for $31!$ , we can batch the following terms of $k$ together (with factorial calculations truncated to relevant digits):

\begin{align*} \braces{1, 2, 3, 4, 5, 6, 7, 8, 9} &\quad\Longrightarrow\quad 9! = 362880 \\ \braces{11, 12, 13, 14, 15, 16, 17, 18, 19} &\quad\Longrightarrow\quad 19! / 10! = \dots 40 \\ \braces{21, 22, 23, 24, 25, 26, 27, 28, 29} &\quad\Longrightarrow\quad 29! / 20! = \dots 400 \\ \braces{31}& \\ \braces{10, 20, 30}& \end{align*}

A couple more calculations I made while exploring the pattern:

\begin{align*} \braces{31, 32, 33, 34, 35, 36, 37, 38, 39} &\quad\Longrightarrow\quad 39! / 30! = \dots 60 \\ \braces{41, 42, 43, 44, 45, 46, 47, 48, 49} &\quad\Longrightarrow\quad 49! / 40! = \dots 20 \end{align*}

I used an online factorial table and a web-based large decimal calculator to explore this pattern. However, the pattern isn’t clear. There could be a pattern, but I doubt that it’s necessary to explore it for an introductory CSES problem.

TODO: Continue!

Coin Piles [Spec] (2024-02-02)

The first thing that comes to mind is the observation that you take exactly three coins at a time, therefore the total coins must be a multiple of 3.

One pile also can never have more than double of the other pile. The reason for that should be trivial.

Let’s work through what we know as candidate passing instances of the probem to see if a pattern emerges.

2 4 -> 1 2 -> 0 0 3 3 -> 2 1 -> 0 0 3 6 -> trivial 0 0 4 5 -> 3 3 -> trivial 0 0 4 8 -> trivial 0 0 5 7 -> 3 6 -> trivial 0 0 6 6 -> 4 5 -> trivial 0 0 5 10 -> trivial 0 0 6 9 -> 4 8 -> trivial 0 0 7 8 -> 5 7 -> trivial 0 0 6 12 -> trivial 0 0 7 11 -> 5 10 -> trivial 0 0 8 10 -> 6 9 -> trivial 0 0 9 9 -> 7 8 -> trivial 0 0 7 14 -> trivial 0 0 8 13 -> 6 12 -> trivial 0 0 9 12 -> 7 11 -> trivial 0 0 10 11 -> 8 10 -> trivial 0 0

Naively, it seems reasonable that the solution is to simply check for the conditions described earlier:

#!/usr/bin/env python3

from sys import stdin

stdin.readline()
test_cases = [[int(x) for x in s.strip().split()] for s in stdin.readlines()]

for a, b in test_cases:
    print("YES" if (((a + b) % 3 == 0) and (max(a, b) <= 2 * min(a, b))) else "NO")

This solution passes all tests.

Palindrome Reorder [Spec] (2024-02-02)

#!/usr/bin/env python3

from collections import Counter
 
s = input().strip()

cnt = Counter(s)
odds = [(c, v) for c, v in cnt.items() if (v % 2)]
evens = [(c, v) for c, v in cnt.items() if (v % 2 == 0)]

if len(odds) > 1:
    print("NO SOLUTION")
else:
    left = [c*(v // 2) for c, v in evens]
    mid = (odds[0][0]*odds[0][1]) if len(odds) else ""
    print("".join([*left, mid, *reversed(left)]))

Gray Code [Spec] (2024-02-02)

This is a classic code number encoding scheme that was covered a few times during my university career. I went for a very simple Python solution:

#!/usr/bin/env python3
 
n = int(input())

codes = [""]
for _ in range(n):
    codes = ["0" + s for s in codes] + ["1" + s for s in reversed(codes)]
print("\n".join(codes))

TODO: Try some other algorithms?

$a$	$b$	$ab$
$1$	$1$	$1$
$1$	$2$	$2$
$1$	$3$	$3$
$1$	$4$	$4$
$1$	$5$	$5$
$1$	$6$	$6$
$1$	$7$	$7$
$1$	$8$	$8$
$1$	$9$	$9$

$a$	$b$	$ab$
$1$	$1$	$1$
$1$	$2$	$2$
$1$	$3$	$3$
$1$	$4$	$4$
$1$	$5$	$5$
$1$	$6$	$6$
$1$	$7$	$7$
$1$	$8$	$8$
$1$	$9$	$9$

$a$	$b$	$ab$
$1$	$1$	$1$
$1$	$2$	$2$
$1$	$3$	$3$
$1$	$4$	$4$
$1$	$5$	$5$
$1$	$6$	$6$
$1$	$7$	$7$
$1$	$8$	$8$
$1$	$9$	$9$