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.