# функции, множества и почему правильного решения иногда недостаточно↵
↵
за последние три дня я продолжил изучать python и решать задачи на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. основными темами стали функции, множества, работа с вещественными числами, сортировка и оценка сложности алгоритмов.↵
↵
за один из учебных дней я решил **11 задач** и провёл за компьютером больше восьми часов. раньше я мог бы сказать, что это «только 11 задач», но сейчас понимаю, что количество принятых решений показывает далеко не всю работу.↵
↵
много времени ушло на:↵
↵
- поиск ошибок;↵
- чтение и понимание условий;↵
- разбор новых конструкций python;↵
- исправление `WA`;↵
- оптимизацию решений после `TLE`.↵
↵
## функции в python↵
↵
я подробнее разобрал функции и понял, что функция — это не просто способ сократить программу. она помогает отделить одну логическую часть решения от другой.↵
↵
общий вид функции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()`только выводит значение на экран, а `return` возвращает результат туда, откуда была вызвана функция.↵
↵
например, функция проверки числа на простоту может вернуть строку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`, после чего основная часть программы выведет этот результат.↵
↵
ещё я понял, что задача из раздела про функции не обязательно должна решаться рекурсией. внутри функции может находиться обычный цикл. рекурсия нужна только тогда, когда задача естественно сводится к своей уменьшенной версии.↵
↵
## мой первый серьёзный tle на проверке простого числа↵
↵
в задаче на проверку простоты числа моё первое решение перебирало все возможные делители от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`.↵
↵
логически оно было правильным, но на больших значениях не укладывалось в ограничение времени.↵
↵
первоначальная сложность была:↵
↵
$$↵
O(n)↵
$$↵
↵
если число может достигать примерно двух миллиардов, такой перебор выполняет слишком много операций.↵
↵
потом я узнал, что достаточно проверять делители только до квадратного корня из числа.↵
↵
если число составное, его можно представить в виде:↵
↵
$$↵
n = a \cdot b↵
$$↵
↵
если бы одновременно выполнялось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,↵
$$↵
↵
что невозможно.↵
↵
значит, хотя бы один делитель составного числа не превышает $\sqrt{n}$.↵
↵
после такой оптимизации сложность становится:↵
↵
$$↵
O(\sqrt{n})↵
$$↵
↵
для числа около двух миллиардов это примерно 45 тысяч проверок вместо миллиардов.↵
↵
ещё удобнее не вычислять квадратный корень через `float`, а использовать условие:↵
↵
```python↵
divisor * divisor <= n↵
```↵
↵
так алгоритм остаётся полностью целочисленным.↵
↵
## множества и быстрый поиск↵
↵
ещё одной важной темой стали множества `set`.↵
↵
я использовал их для:↵
↵
- поиска пересечения двух наборов чисел;↵
- подсчёта различных элементов;↵
- проверки, встречалось ли число раньше;↵
- удаления повторов.↵
↵
пересечение двух множеств:↵
↵
```python↵
common = first & second↵
```↵
↵
количество общих различных элементов:↵
↵
```python↵
len(first & second)↵
```↵
↵
важный момент: множество не хранит элементы в отсортированном порядке.↵
↵
если по условию общие элементы нужно вывести по возрастанию, требуется:↵
↵
```python↵
print(*sorted(common))↵
```↵
↵
здесь `sorted()` создаёт отсортированный список, а `*` распаковывает его элементы и передаёт их в `print()` как отдельные аргументы.↵
↵
ещё я получил `TLE` в задаче, где для каждого числа проверял его наличие в обычном списке.↵
↵
поиск в списке в худшем случае работает за:↵
↵
$$↵
O(n)↵
$$↵
↵
если делать его для каждого элемента, общая сложность становится:↵
↵
$$↵
O(n^2)↵
$$↵
↵
правильная идея — идти слева направо и хранить уже встреченные значения в пустом множестве `seen`.↵
↵
проверка наличия элемента в `set` в среднем работает за:↵
↵
$$↵
O(1)↵
$$↵
↵
поэтому весь алгоритм становится линейным:↵
↵
$$↵
O(n)↵
$$↵
↵
это был хороший пример того, что после `TLE` нужно менять не отдельную строку, а сам подход.↵
↵
## вещественные числа и погрешность↵
↵
в задаче про индекс массы тела я сначала использовал обычные вычисления с `float`.↵
↵
формула bmi:↵
↵
$$↵
\mathrm{BMI} = \frac{W}{(H/100)^2}↵
$$↵
↵
на граничном тесте, где bmi математически равен ровно `25`, программа могла получить значение:↵
↵
```text↵
24.999999999999996↵
```↵
↵
из-за этого условие `bmi >= 25` давало неправильный ответ.↵
↵
в этой задаче оказалось лучше полностью убрать вещественные числа.↵
↵
условие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↵
$$↵
↵
после этого сравниваются только целые числа, поэтому погрешность исчезает.↵
↵
я также разобрал сравнение вещественных чисел через `eps`.↵
↵
два числа можно считать равными, если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↵
```↵
↵
но теперь перед использованием `eps` я сначала проверяю, нельзя ли преобразовать формулу и перейти к целым числам.↵
↵
## стабильная сортировка↵
↵
ещё я подробнее разобрал `sorted()` и `.sort()`.↵
↵
оба способа используют стабильную сортировку. это означает, что элементы с одинаковым ключом сохраняют взаимный порядок.↵
↵
например, если два ученика имеют одинаковый средний балл, тот, кто находился раньше во входных данных, останется раньше и после сортировки.↵
↵
разница между способами:↵
↵
- `sorted()` создаёт новый список;↵
- `.sort()` изменяет существующий список;↵
- `.sort()` возвращает `None`.↵
↵
я также научился сортировать объекты сразу по нескольким признакам с помощью кортежа:↵
↵
```python↵
key=lambda student: (↵
student.class_number,↵
student.class_letter,↵
student.surname↵
)↵
```↵
↵
python сначала сравнивает номер класса, затем букву и только потом фамилию.↵
↵
## что я понял за эти дни↵
↵
главный вывод — написать логически правильное решение недостаточно.↵
↵
нужно ещё проверить:↵
↵
- сколько операций оно выполнит;↵
- подходит ли сложность под ограничения;↵
- можно ли заменить вложенные циклы множеством;↵
- не возникает ли погрешность из-за `float`;↵
- требуется ли сохранять порядок равных элементов;↵
- правильно ли я понял формулировку задачи.↵
↵
раньше я чаще сразу начинал писать код. теперь стараюсь сначала сформулировать идею и оценить её сложность.↵
↵
## советы другим новичкам↵
↵
1. **смотрите на ограничения до написания кода.**↵
↵
если $n$ около $10^5$, решение за $O(n^2)$ почти наверняка не пройдёт.↵
↵
2. **не используйте список для большого количества проверок `x in collection`.**↵
↵
когда порядок не важен, для быстрых проверок обычно лучше подходит `set`.↵
↵
3. **не применяйте рекурсию только потому, что задача находится в разделе про функции.**↵
↵
сначала подумайте, действительно ли задача сводится к своей уменьшенной версии.↵
↵
4. **проверяйте граничные случаи при работе с `float`.**↵
↵
число, которое математически равно `25`, в памяти может оказаться немного меньше.↵
↵
5. **по возможности переходите к целым вычислениям.**↵
↵
преобразование формулы часто делает решение надёжнее.↵
↵
6. **после tle ищите повторяющуюся дорогую операцию.**↵
↵
ускорение ввода не спасёт алгоритм с неправильной асимптотикой.↵
↵
7. **различайте правильность и эффективность.**↵
↵
решение может давать правильный ответ на маленьких тестах, но не выдерживать максимальные ограничения.↵
↵
## планы на следующие дни↵
↵
- закончить задачи по функциям;↵
- лучше разобраться с рекурсией;↵
- решить задачи на быстрое возведение в степень;↵
- изучить рекурсивный и итеративный варианты чисел фибоначчи;↵
- научиться оценивать сложность решения до написания кода;↵
- продолжать сначала пытаться решить задачу самостоятельно и только потом брать подсказку.↵
↵
постепенно начинаю понимать, что олимпиадное программирование — это не только знание синтаксиса. намного важнее видеть структуру задачи и заранее понимать, какой алгоритм выдержит ограничения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.
↵
за последние три дня я продолжил изучать python и решать задачи на
↵
over the last three days, i continued learning python and solving problems on informatics
↵
за один из учебных дней я решил **11 задач** и провёл за компьютером больше восьми часов. раньше я мог бы сказать, что это «только 11 задач», но сейчас понимаю, что количество принятых решений показывает далеко не всю работу.↵
↵
много времени ушло на:↵
↵
- поиск ошибок;↵
- чтение и понимание условий;↵
- разбор новых конструкций python;↵
- исправление `WA`;↵
- оптимизацию решений после `TLE`.↵
↵
## функции в python↵
↵
я подробнее разобрал функции и понял, что функция — это не просто способ сократить программу. она помогает отделить одну логическую часть решения от другой.↵
↵
общий вид функции
↵
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):↵
#
return result↵
```↵
↵
↵
`print()`
↵
например, функция проверки числа на простоту может вернуть строку
↵
for example, a primality-testing function can return `prime`
↵
ещё я понял, что задача из раздела про функции не обязательно должна решаться рекурсией. внутри функции может находиться обычный цикл. рекурсия нужна только тогда, когда задача естественно сводится к своей уменьшенной версии.↵
↵
## мой первый серьёзный tle на проверке простого числа↵
↵
в задаче на проверку простоты числа моё первое решение перебирало все возможные делители от
↵
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`
↵
↵
первоначальная сложность была:↵
↵
$$↵
O(n)↵
$$↵
↵
если число может достигать примерно двух миллиардов, такой перебор выполняет слишком много операций.↵
↵
потом я узнал, что достаточно проверять делители только до квадратного корня из числа.↵
↵
если число составное, его можно представить в виде:↵
↵
$$↵
n = a \cdot b↵
$$↵
↵
если бы одновременно выполнялось
↵
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}↵
$$↵
↵
↵
$$↵
b > \sqrt{n},↵
$$↵
↵
↵
$$↵
a \cdot b > n,↵
$$↵
↵
↵
значит, хотя бы один делитель составного числа не превышает $\sqrt{n}$.↵
↵
после такой оптимизации сложность становится:↵
↵
$$↵
O(\sqrt{n})↵
$$↵
↵
для числа около двух миллиардов это примерно 45 тысяч проверок вместо миллиардов.↵
↵
ещё удобнее не вычислять квадратный корень через `float`, а использовать условие:↵
↵
```python↵
divisor * divisor <= n↵
```↵
↵
так алгоритм остаётся полностью целочисленным.↵
↵
## множества и быстрый поиск↵
↵
ещё одной важной темой стали множества `set`.↵
↵
я использовал их для:↵
↵
- поиска пересечения двух наборов чисел;↵
- подсчёта различных элементов;↵
- проверки, встречалось ли число раньше;↵
- удаления повторов.↵
↵
пересечение двух множеств:↵
↵
```python↵
common = first & second↵
```↵
↵
количество общих различных элементов:↵
↵
```python↵
len(first & second)↵
```↵
↵
важный момент: множество не хранит элементы в отсортированном порядке.↵
↵
если по условию общие элементы нужно вывести по возрастанию, требуется:↵
↵
```python↵
print(*sorted(common))↵
```↵
↵
здесь `sorted()` создаёт отсортированный список, а `*` распаковывает его элементы и передаёт их в `print()` как отдельные аргументы.↵
↵
ещё я получил `TLE` в задаче, где для каждого числа проверял его наличие в обычном списке.↵
↵
поиск в списке в худшем случае работает за:↵
↵
$$↵
O(n)↵
$$↵
↵
если делать его для каждого элемента, общая сложность становится:↵
↵
$$↵
O(n^2)↵
$$↵
↵
правильная идея — идти слева направо и хранить уже встреченные значения в пустом множестве `seen`.↵
↵
проверка наличия элемента в `set` в среднем работает за:↵
↵
$$↵
O(1)↵
$$↵
↵
поэтому весь алгоритм становится линейным:↵
↵
$$↵
O(n)↵
$$↵
↵
это был хороший пример того, что после `TLE` нужно менять не отдельную строку, а сам подход.↵
↵
## вещественные числа и погрешность↵
↵
в задаче про индекс массы тела я сначала использовал обычные вычисления с `float`.↵
↵
формула bmi:↵
↵
$$↵
\mathrm{BMI} = \frac{W}{(H/100)^2}↵
$$↵
↵
на граничном тесте, где bmi математически равен ровно `25`, программа могла получить значение:↵
↵
```text↵
24.999999999999996↵
```↵
↵
из-за этого условие `bmi >= 25` давало неправильный ответ.↵
↵
в этой задаче оказалось лучше полностью убрать вещественные числа.↵
↵
условие
↵
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↵
$$↵
↵
↵
$$↵
W \cdot 10000 \ge 25 \cdot H^2↵
$$↵
↵
↵
я также разобрал сравнение вещественных чисел через `eps`.↵
↵
два числа можно считать равными, если
↵
i also studied floating-point comparison using `eps`.↵
↵
two numbers may be considered equal when:↵
↵
$$↵
|a-b| \le \varepsilon↵
$$↵
↵
↵
```python↵
abs(a - b) <= eps↵
```↵
↵
↵
## стабильная сортировка↵
↵
ещё я подробнее разобрал `sorted()` и `.sort()`.↵
↵
оба способа используют стабильную сортировку. это означает, что элементы с одинаковым ключом сохраняют взаимный порядок.↵
↵
например, если два ученика имеют одинаковый средний балл, тот, кто находился раньше во входных данных, останется раньше и после сортировки.↵
↵
разница между способами:↵
↵
- `sorted()` создаёт новый список;↵
- `.sort()` изменяет существующий список;↵
- `.sort()` возвращает `None`.↵
↵
я также научился сортировать объекты сразу по нескольким признакам с помощью кортежа:↵
↵
```python↵
key=lambda student: (↵
student.class_number,↵
student.class_letter,↵
student.surname↵
)↵
```↵
↵
python сначала сравнивает номер класса, затем букву и только потом фамилию.↵
↵
## что я понял за эти дни↵
↵
главный вывод — написать логически правильное решение недостаточно.↵
↵
нужно ещё проверить:↵
↵
- сколько операций оно выполнит;↵
- подходит ли сложность под ограничения;↵
- можно ли заменить вложенные циклы множеством;↵
- не возникает ли погрешность из-за `float`;↵
- требуется ли сохранять порядок равных элементов;↵
- правильно ли я понял формулировку задачи.↵
↵
раньше я чаще сразу начинал писать код. теперь стараюсь сначала сформулировать идею и оценить её сложность.↵
↵
## советы другим новичкам↵
↵
1. **смотрите на ограничения до написания кода.**↵
↵
если $n$ около $10^5$, решение за $O(n^2)$ почти наверняка не пройдёт.↵
↵
2. **не используйте список для большого количества проверок `x in collection`.**↵
↵
когда порядок не важен, для быстрых проверок обычно лучше подходит `set`.↵
↵
3. **не применяйте рекурсию только потому, что задача находится в разделе про функции.**↵
↵
сначала подумайте, действительно ли задача сводится к своей уменьшенной версии.↵
↵
4. **проверяйте граничные случаи при работе с `float`.**↵
↵
число, которое математически равно `25`, в памяти может оказаться немного меньше.↵
↵
5. **по возможности переходите к целым вычислениям.**↵
↵
преобразование формулы часто делает решение надёжнее.↵
↵
6. **после tle ищите повторяющуюся дорогую операцию.**↵
↵
ускорение ввода не спасёт алгоритм с неправильной асимптотикой.↵
↵
7. **различайте правильность и эффективность.**↵
↵
решение может давать правильный ответ на маленьких тестах, но не выдерживать максимальные ограничения.↵
↵
## планы на следующие дни↵
↵
- закончить задачи по функциям;↵
- лучше разобраться с рекурсией;↵
- решить задачи на быстрое возведение в степень;↵
- изучить рекурсивный и итеративный варианты чисел фибоначчи;↵
- научиться оценивать сложность решения до написания кода;↵
- продолжать сначала пытаться решить задачу самостоятельно и только потом брать подсказку.↵
↵
постепенно начинаю понимать, что олимпиадное программирование — это не только знание синтаксиса. намного важнее видеть структуру задачи и заранее понимать, какой алгоритм выдержит ограничения
↵
## 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.
