# 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:↵
↵
```python↵
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:↵
↵
$$↵
O(n)↵
$$↵
↵
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:↵
↵
$$↵
n = a \cdot b↵
$$↵
↵
if both conditions were true:↵
↵
$$↵
a > \sqrt{n}↵
$$↵
↵
and↵
↵
$$↵
b > \sqrt{n},↵
$$↵
↵
then:↵
↵
$$↵
a \cdot b > n,↵
$$↵
↵
which is impossible.↵
↵
therefore, at least one divisor of a composite number does not exceed $\sqrt{n}$.↵
↵
the optimized complexity becomes:↵
↵
$$↵
O(\sqrt{n})↵
$$↵
↵
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:↵
↵
```python↵
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:↵
↵
```python↵
common = first & second↵
```↵
↵
the number of common distinct elements:↵
↵
```python↵
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:↵
↵
```python↵
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:↵
↵
$$↵
O(n)↵
$$↵
↵
doing it for every element produces:↵
↵
$$↵
O(n^2)↵
$$↵
↵
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:↵
↵
$$↵
O(1)↵
$$↵
↵
therefore, the whole algorithm becomes linear:↵
↵
$$↵
O(n)↵
$$↵
↵
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:↵
↵
$$↵
\mathrm{BMI} = \frac{W}{(H/100)^2}↵
$$↵
↵
on a boundary test where the bmi is mathematically exactly `25`, the program could produce:↵
↵
```text↵
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:↵
↵
$$↵
\frac{W}{(H/100)^2} \ge 25↵
$$↵
↵
can be transformed into:↵
↵
$$↵
W \cdot 10000 \ge 25 \cdot H^2↵
$$↵
↵
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:↵
↵
$$↵
|a-b| \le \varepsilon↵
$$↵
↵
in python:↵
↵
```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:↵
↵
```python↵
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.↵
↵
2. **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.↵
↵
3. **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.↵
↵
4. **test boundary cases when working with `float`.**↵
↵
a value that is mathematically equal to `25` may be stored as a slightly smaller number.↵
↵
5. **use integer transformations whenever possible.**↵
↵
rewriting a formula can make a solution more reliable.↵
↵
6. **after receiving tle, find the expensive repeated operation.**↵
↵
faster input will not save an algorithm with the wrong complexity.↵
↵
7. **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.
↵
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:↵
↵
```python↵
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:↵
↵
$$↵
O(n)↵
$$↵
↵
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:↵
↵
$$↵
n = a \cdot b↵
$$↵
↵
if both conditions were true:↵
↵
$$↵
a > \sqrt{n}↵
$$↵
↵
and↵
↵
$$↵
b > \sqrt{n},↵
$$↵
↵
then:↵
↵
$$↵
a \cdot b > n,↵
$$↵
↵
which is impossible.↵
↵
therefore, at least one divisor of a composite number does not exceed $\sqrt{n}$.↵
↵
the optimized complexity becomes:↵
↵
$$↵
O(\sqrt{n})↵
$$↵
↵
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:↵
↵
```python↵
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:↵
↵
```python↵
common = first & second↵
```↵
↵
the number of common distinct elements:↵
↵
```python↵
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:↵
↵
```python↵
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:↵
↵
$$↵
O(n)↵
$$↵
↵
doing it for every element produces:↵
↵
$$↵
O(n^2)↵
$$↵
↵
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:↵
↵
$$↵
O(1)↵
$$↵
↵
therefore, the whole algorithm becomes linear:↵
↵
$$↵
O(n)↵
$$↵
↵
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:↵
↵
$$↵
\mathrm{BMI} = \frac{W}{(H/100)^2}↵
$$↵
↵
on a boundary test where the bmi is mathematically exactly `25`, the program could produce:↵
↵
```text↵
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:↵
↵
$$↵
\frac{W}{(H/100)^2} \ge 25↵
$$↵
↵
can be transformed into:↵
↵
$$↵
W \cdot 10000 \ge 25 \cdot H^2↵
$$↵
↵
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:↵
↵
$$↵
|a-b| \le \varepsilon↵
$$↵
↵
in python:↵
↵
```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:↵
↵
```python↵
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.↵
↵
2. **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.↵
↵
3. **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.↵
↵
4. **test boundary cases when working with `float`.**↵
↵
a value that is mathematically equal to `25` may be stored as a slightly smaller number.↵
↵
5. **use integer transformations whenever possible.**↵
↵
rewriting a formula can make a solution more reliable.↵
↵
6. **after receiving tle, find the expensive repeated operation.**↵
↵
faster input will not save an algorithm with the wrong complexity.↵
↵
7. **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.
