As you can guess from the increase in the number of shitposting blogs in the recent actions section, last week was that time of the year again for Turkish winter training camp to commence. I was also honored to be one of the instructors and did a lecture on number theory. I tried to give a bit more rigorous understanding to the experienced students from my point of understanding of the topic while also providing a good basis for students that had less experience so they could derive more advanced stuff on their own.

I think I didn't do a very good job, since most students lost their interest very quickly. Nevertheless, I think that my material (the slides I've used) was not that bad, and I've realized that we don't have an ample amount of resources for an introduction to the topic for competitive programming specifically. Therefore, I hope for it to be useful for people and maybe pique the interest of some of you.

Since the target audience's experience with mathematical notation and concepts was kind of a mixed bag, you'll notice that there are some obscure cases on parts that I've chosen to explain and to not. (For example, I've assumed that most students had some understanding of the equivalence relations and used the concept while making proofs and to skip some examples without any prior explanation, while giving the definitions very briefly for sets and functions.) A similar case also occurs for the explanation of algorithms and proofs, since I've elaborated on the details on the board and tried to provide the essential ideas on the slides to let the students explore the possibilities on their own and ask questions on the more ambiguous parts. The same applies to the parts I've chosen to explain and ones that I've omitted, like multiplicative functions.

But enough excuses for the imperfections and my choices. Regardless of them, I hope it can prove to be useful for you. Also, huge thanks to Mert Akarca for providing a concise proof for one of the lemmas that I've skipped and allowing me to incorporate it on the final version of the slides.

The Problem

You are given a tree with $$$N$$$ ($$$1 \le N \le 10^5$$$) vertices.

You need to partition the vertices into minimum number of sets, such that every set has a maximum size of $$$S$$$ ($$$1 \le S \le N$$$) and maximum distance between any of the two vertices, that are in the same set is less than $$$2K$$$ ($$$1 \le K \le 20$$$).

With a more formal statement, assuming vertices in the tree are labeled $$$[1, N]$$$ and $$$dist(v, u)$$$ is defined as the distance between two vertices in the tree, you need to find a partition $$$ \{ P_0,\, P_1,\, \dots ,\, P_{C-1} \} $$$ with minimum $$$C$$$, such that:

• for every $$$\displaystyle P_i, \ max_{\ \forall v,\ u \ \in P_i} \{dist(v, u)\} \le 2K$$$

• for every $$$\displaystyle P_i, \ |P_i| \le S$$$

• for every $$$\displaystyle 1 \le x \le N, \ x \in \bigcup P_i$$$

The problem doesn't want you to print the partition, you only need to print it's size (number of sets) and note that it's not necesseary for vertices in a set to form a connected component.

$$$ \ $$$

Hi everyone,

Our team selection test will be in a month probably and I'm bad at olympiad style competitive programming, I mean I'm bad at Codeforces style but olympiad style is the next level, I have no training and solved hardly any olympiad problems, according to my friends and blogs I have seen, problem styles can be very different, I looked up for the blogs like this and either they were old, or they had no information, so which problems should I solve, from which olympiads and assuming I get selected, how should I train for IOI ?

(Also please don't cyberbully me, I know my English is trash.)