Hi everyone!

During the last three days I focused almost entirely on BFS on grids. Instead of solving many unrelated problems, I tried to understand why the algorithm works, where TLE comes from, and why some implementations are much faster despite using the same idea.

multi-source BFS instead of many separate searches

The biggest takeaway was that if there are multiple sources, you should not run BFS from each of them independently.

My initial idea was to launch a separate BFS every time I found a new source. This may traverse the same cells many times.

If there are $$$k$$$ sources, the worst-case complexity becomes

The correct approach is to put all sources into the queue at once, assign distance 0 to each of them, and run a single BFS.

from collections import deque

q = deque()

for i in range(n):
    for j in range(m):
        if a[i][j] == 2:
            dist[i][j] = 0
            q.append((i, j))

Now all waves expand simultaneously from every source.

The complexity becomes

where this technique is useful

This pattern appears in many problems:

• multiple exits;
• multiple infection sources;
• multiple fires;
• multiple starting vertices;
• distance to the nearest object.

Whenever a statement contains several equivalent starting points, multi-source BFS is often the right idea.

why the first discovered distance is already optimal

Another concept I finally understood is why BFS never needs to improve distances later.

BFS processes vertices layer by layer.

First all vertices with distance 0.

Then all vertices with distance 1.

Then distance 2, and so on.

Therefore, if a vertex first receives

dist[nx][ny] = dist[x][y] + 1

no shorter path can appear afterwards.

That is why checking only unvisited vertices is enough.

if dist[nx][ny] == -1:
    dist[nx][ny] = dist[x][y] + 1
    q.append((nx, ny))

This is much simpler than repeatedly trying to improve distances.

a common mistake

During implementation I used logic similar to

if dist[nx][ny] > dist[x][y] + 1:
    ...
elif dist[nx][ny] == -1:
    ...

For a standard BFS this is unnecessary.

If the queue is processed correctly, the first assigned distance is already optimal.

Extra checks only make the implementation harder to read and debug.

a small diagnostic problem

After finishing this BFS block I started reviewing some basic algorithmic skills.

One of the tasks was to find the longest non-decreasing contiguous subarray.

I produced several Wrong Answers before getting it right.

A useful lesson was to manually test edge cases before changing the implementation:

• the whole array is non-decreasing;
• the whole array is decreasing;
• the answer ends at the last element;
• several longest segments have the same length.

These cases often reveal indexing mistakes and incorrect answer updates.

what's next

The next topic we have already started discussing is problems where you first compute the spreading time with a multi-source BFS and then use those distances in a second traversal (for example, a person escaping from a fire).

These problems require not only BFS itself but also careful reasoning about arrival times for every cell.

Hi everyone!

Over the last few days, I focused almost entirely on recursion. Before that, I could sometimes write a recursive function by following a familiar pattern, but I did not always understand why it worked or how to discover the recursive idea in a new problem.

Now I have started approaching these problems differently. Instead of writing code immediately or trying to imagine every function call, I first define the meaning of the state.

What I now do before writing recursion

Before coding, I try to answer four questions:

• what exactly the function should do or return;
• what the simplest possible case is;
• how the answer can be expressed using a smaller problem;
• why every recursive call moves closer to termination.

For example, if a function solves a problem for $$$n$$$, the next call usually works with a smaller value such as $$$n-1$$$, $$$n/2$$$, or another simpler state.

The most important thing is that recursion must not call itself forever. That is why every recursive function needs a base case.

A simple example:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

The function solves the problem for $$$n$$$ using the smaller problem for $$$n-1$$$.

The recurrence is:

The base case is:

Before, I mostly memorized code like this. Now I understand the purpose of every part much better.

Branching recursion

I also understood the difference between a single chain of recursive calls and a situation where one state creates several new states.

A good example is the binomial coefficient recurrence:

The base cases are:

• $$$k=0$$$;
• $$$k=n$$$.

In both cases, the answer is $$$1$$$.

def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

Here, one call creates two more calls, so the number of computations grows very quickly.

This helped me understand that a correct recurrence does not automatically mean an efficient solution.

Memoization and repeated states

Some of my recursive solutions received TLE, even though the main idea was correct.

The problem was that the program calculated the same state many times.

For example, while computing binomial coefficients, the same pair of values n and k can appear again and again.

Memoization solves this problem:

from functools import cache

@cache
def combinations(n, k):
    if k == 0 or k == n:
        return 1
    return combinations(n - 1, k - 1) + combinations(n - 1, k)

Now the result of every state is stored.

When the function is called again with the same arguments, Python returns the saved result instead of calculating everything again.

After learning this, I started asking myself an important question:

Am I solving the same small problem more than once?

If the answer is yes, memoization or dynamic programming may be needed.

Tower of Hanoi

For a long time, I could not properly understand the Tower of Hanoi problem.

The code is short, but the recursive transition initially felt almost magical.

A visual explanation on YouTube finally helped me see the three main steps:

1. move $$$n-1$$$ disks from the starting rod to the auxiliary rod;
2. move the largest disk to the destination rod;
3. move the $$$n-1$$$ disks from the auxiliary rod to the destination rod.

So the problem for $$$n$$$ disks is reduced to two problems for $$$n-1$$$ disks.

The number of moves satisfies:

The final number of moves is:

Once I understood these three steps, the code became much clearer:

def hanoi(n, start, finish, auxiliary):
    if n == 1:
        print(start, finish)
        return

    hanoi(n - 1, start, auxiliary, finish)
    print(start, finish)
    hanoi(n - 1, auxiliary, finish, start)

My main lesson was that one good visualization can sometimes teach more than repeatedly reading finished code.

My first real understanding of DFS

After basic recursion, I started learning graph traversal.

One of the problems involved a room or maze represented by a grid.

At first, I only saw it as a two-dimensional array. Then I found a more useful model:

• every available cell is a graph vertex;
• moving to a neighboring cell is an edge;
• the entire reachable area is a connected component.

A DFS function works approximately like this:

1. check whether the cell is valid;
2. mark it as visited;
3. recursively visit neighboring cells.

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:
        return 0

    if grid[x][y] == '#':
        return 0

    if visited[x][y]:
        return 0

    visited[x][y] = True

    result = 1
    result += dfs(x + 1, y)
    result += dfs(x - 1, y)
    result += dfs(x, y + 1)
    result += dfs(x, y - 1)

    return result

The idea can be written as:

where $$$u$$$ represents the unvisited neighbors of vertex $$$v$$$.

Why visited cells must be marked

Previously, I did not fully understand why the visited array was so important.

Now I see two clear reasons.

First, without visited marks, the algorithm can move in a cycle:

A -> B -> A -> B -> ...

Second, the same cell may be counted several times.

That is why a vertex should be marked as visited immediately after entering it, not after processing all of its neighbors.

This is a small implementation detail, but without it DFS may produce a wrong answer or never terminate.

Trees and choosing the right representation

I also solved a problem where a message had to be deleted together with all of its replies.

The input was naturally represented as:

message -> parent

However, this representation is inconvenient when we need to find every descendant.

A better structure is:

parent -> list of children

For example:

children = [[] for _ in range(n)]

for child, parent in relations:
    children[parent].append(child)

After that, deleting every reply becomes a normal subtree traversal:

def remove_subtree(v):
    removed[v] = True

    for child in children[v]:
        remove_subtree(child)

This helped me understand an important principle:

Sometimes the main difficulty is not the algorithm itself, but the way the input data is represented.

With the correct representation, the final solution can become very short.

Mistakes I fixed

During these days, I noticed several mistakes that appeared repeatedly in my code.

1. Printing instead of returning a value

Sometimes I wrote a recursive function that immediately printed something, even though I later needed its result in another calculation.

Now I try to separate:

• calculating the result with return;
• displaying the result with print.

For example:

def sum_digits(n):
    if n == 0:
        return 0
    return n % 10 + sum_digits(n // 10)

print(sum_digits(12345))

2. Unnecessary global variables

Global variables can make a solution harder to understand and debug.

Now I try to pass the necessary data through function arguments or return the result from the function.

3. Choosing the wrong data structure

When fast membership checks are needed, set is usually better.

used = set()

if value in used:
    ...

On average, a set membership check works in $$$O(1)$$$, while searching in a list takes $$$O(n)$$$.

4. Trying to modify a string

I also reinforced the fact that Python strings are immutable.

This does not work:

s[0] = 'a'

Instead, we need to create a new string or convert it into a list first:

s = list(s)
s[0] = 'a'
s = ''.join(s)

5. Writing code too early

Sometimes I started implementing a solution before deciding:

• what the vertices are;
• which transitions are possible;
• what the function stores or returns;
• which states have already been visited.

Now I try to build the model first and write the implementation only after that.

Practical advice for other beginners

Here are a few things that really helped me understand recursion better.

Define the meaning of the function first

Do not start with the first line of code.

First, describe the function in words:

dfs(v) returns the size of the area reachable from vertex v.

Or:

solve(n) returns the answer for a problem of size n.

After that, the base case and transition usually become much easier to find.

Do not try to hold the entire recursion tree in your head

A recursive function only needs to correctly solve the current problem while assuming that the smaller problem is already solved correctly.

This is much easier than manually imagining hundreds of calls.

Check that the problem becomes smaller

Every recursive call must move closer to the base case.

For example:

solve(n - 1)

is usually safer than:

solve(n)

The second version may create infinite recursion.

Draw small examples

For $$$n=3$$$ or for a small grid, drawing the recursion tree on paper is very useful.

It helps reveal:

• repeated states;
• the order of calls;
• when the function returns;
• why visited is needed.

Always estimate complexity

Even correct recursion may be too slow.

If every state creates two new calls, the complexity may be close to $$$O(2^n)$$$.

If every state is stored and calculated only once, the solution may improve to $$$O(n)$$$ or $$$O(nk)$$$.

What I want to study next

Over the next few days, I want to practice:

• DFS on graphs;
• DFS on two-dimensional grids;
• connected components;
• tree traversal;
• BFS and queues;
• first dynamic programming problems.

I especially want to become faster at identifying the correct problem model before writing code:

• array;
• graph;
• tree;
• grid;
• dynamic programming state.

My main conclusion from these three days is:

Recursion becomes much easier when you stop treating it like magic and start understanding the exact meaning of every call, the base case, and the transition to a smaller problem.

functions, sets, and why a correct solution is sometimes not enough

over the last three days, i continued learning python and solving problems on informatics and atcoder. my main topics were functions, sets, floating-point numbers, sorting, and algorithmic complexity.

during one of these study days, i solved 11 problems and spent more than eight hours working at my computer. previously, i might have called it “only 11 problems,” but now i understand that the number of accepted solutions does not show all the work.

a lot of time was spent on:

• finding mistakes;
• understanding problem statements;
• learning new python constructions;
• fixing WA;
• optimizing solutions after TLE.

functions in python

i studied functions in more detail and understood that a function is not only a way to shorten a program. it also separates one logical part of a solution from another.

the general structure is:

def function_name(parameters):
    # actions
    return result

it is especially important to understand the difference between print() and return.

print() only displays a value, while return sends the result back to the place where the function was called.

for example, a primality-testing function can return prime or composite, and the main part of the program can print that result.

i also learned that a problem from a functions section does not necessarily require recursion. a normal loop can be used inside a function. recursion is useful when a problem naturally reduces to a smaller version of itself.

my first serious tle in a primality test

in a primality-testing problem, my first solution checked every possible divisor from 2 to n - 1.

the logic was correct, but the solution exceeded the time limit for large values.

the original complexity was:

when the number can be close to two billion, this approach performs far too many operations.

then i learned that it is enough to check divisors only up to the square root of the number.

if a number is composite, it can be represented as:

if both conditions were true:

and

then:

which is impossible.

therefore, at least one divisor of a composite number does not exceed $$$\sqrt{n}$$$.

the optimized complexity becomes:

for a number close to two billion, this means about 45,000 checks instead of billions.

it is also better not to calculate the square root using float. the loop condition can be written as:

divisor * divisor <= n

this keeps the whole algorithm integer-based.

sets and fast membership checks

another important topic was Python’s set.

i used sets for:

• finding the intersection of two collections;
• counting distinct elements;
• checking whether a value had appeared before;
• removing duplicates.

the intersection of two sets:

common = first & second

the number of common distinct elements:

len(first & second)

an important detail is that a set does not store its elements in sorted order.

when the statement requires increasing order, the result must be sorted:

print(*sorted(common))

here, sorted() creates a sorted list, while * unpacks its elements and passes them to print() as separate arguments.

i also received a TLE in a problem where i checked whether every value existed in a normal list.

membership testing in a list may take:

doing it for every element produces:

the correct idea is to move from left to right and store previously seen values in an initially empty set called seen.

membership testing in a set takes, on average:

therefore, the whole algorithm becomes linear:

this was a good example of why fixing a TLE often requires changing the approach instead of changing one line.

floating-point numbers and precision errors

in a body mass index problem, i initially used ordinary float calculations.

the bmi formula is:

on a boundary test where the bmi is mathematically exactly 25, the program could produce:

24.999999999999996

because of floating-point representation. the condition bmi >= 25 then returned the wrong answer.

in this problem, it was better to remove floating-point calculations completely.

the condition:

can be transformed into:

now only integers are compared, so the precision problem disappears.

i also studied floating-point comparison using eps.

two numbers may be considered equal when:

in python:

abs(a - b) <= eps

however, before using eps, i now check whether the formula can be transformed into an integer comparison.

stable sorting

i also learned more about sorted() and .sort().

both use stable sorting. this means that elements with equal keys keep their relative order.

for example, if two students have the same average score, the one who appeared earlier in the input remains earlier after sorting.

the difference is:

• sorted() creates a new list;
• .sort() modifies the existing list;
• .sort() returns None.

i also learned how to sort objects by several fields using a tuple:

key=lambda student: (
    student.class_number,
    student.class_letter,
    student.surname
)

python first compares the class number, then the class letter, and finally the surname.

what i learned

my main conclusion is that writing a logically correct solution is not enough.

i also need to check:

• how many operations it performs;
• whether the complexity fits the constraints;
• whether nested loops can be replaced with a set;
• whether floating-point precision can cause an error;
• whether equal elements must keep their original order;
• whether i understood the statement correctly.

previously, i often started coding immediately. now i try to formulate the idea first and estimate its complexity.

advice for other beginners

1. read the constraints before writing code.

when $$$n$$$ is around $$$10^5$$$, an $$$O(n^2)$$$ solution will almost certainly be too slow.

1. do not use a list for many x in collection checks.

when order is not important, a set is usually better for fast membership checks.

1. do not use recursion only because the problem is in a functions section.

first ask whether the problem naturally reduces to a smaller version of itself.

1. test boundary cases when working with float.

a value that is mathematically equal to 25 may be stored as a slightly smaller number.

1. use integer transformations whenever possible.

rewriting a formula can make a solution more reliable.

1. after receiving tle, find the expensive repeated operation.

faster input will not save an algorithm with the wrong complexity.

1. separate correctness from efficiency.

a solution may be correct on small tests but still fail the maximum constraints.

plans for the next few days

• finish the problems on functions;
• understand recursion more deeply;
• solve problems on binary exponentiation;
• study recursive and iterative fibonacci implementations;
• learn to estimate complexity before writing code;
• continue trying to solve problems independently before asking for a hint.

i am gradually realizing that competitive programming is not only about knowing syntax. the more important skill is seeing the structure of a problem and understanding which algorithm can handle the constraints.