When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

TheScrasse's blog

By TheScrasse, history, 3 months ago, In English

Hello everyone,

in this blog I'm trying to convince you that editorials are useful, especially if you read them "correctly".

"Algorithm $$$1$$$" vs "Algorithm $$$2$$$"

This is what many users do when reading the editorial for one problem (let's call it "algorithm $$$1$$$"):

  • Read it.
  • Repeat until able to implement the solution.
  • Implement the solution; possibly forget about any previous attempt to solve that problem without editorial, and any detail in the editorial that seems unrelated to the implementation of the solution.
  • Possibly, read the comments trying to find out how it is possible to come up with the solution in the editorial.

This is what you should do in my opinion (let's call it "algorithm $$$2$$$"):

  • Keep the editorial open until you are able to implement the solution, using both your ideas and editorial's ideas: sometimes, this just means opening the editorial for $$$1$$$ second, because you had already found most of the ideas on your own.
  • Implement the solution.
  • Re-read the editorial carefully, and pretend you can modify it; ask yourself which parts of the editorial you would modify.
  • Possibly, read the comments to find additional insights / ideas.

(I'm not saying "algorithm $$$2$$$" is the best way to use editorials. It's just a method that works for me, and seems strictly better than "algorithm $$$1$$$". Feel free to find your own way to use editorials.)

Examples:

1909B - Make Almost Equal With Mod

Algorithm $$$1$$$:

  • Read the editorial.
  • Understand that, for some unintuitive reason (i.e., some math formulas), you only need to check $$$k = 2^i$$$.
  • Implement the solution.
  • Read the comments; find out that an alternative solution is printing $$$k = 2 \cdot \gcd(|a_i - a_{i+1}|)$$$. Convince yourself that you could come up with that by trial and error, and lots of small examples on paper (i.e., do some "proof by examples").

Algorithm $$$2$$$:

  • Look at the picture for some time (between $$$1$$$ second and $$$5$$$ minutes), understand what's going on, understand the solution.
  • Implement the solution.
  • Re-read the editorial carefully. Read the comments and find out that an alternative solution is printing $$$k = 2 \cdot \gcd(|a_i - a_{i+1}|) =: 2g$$$. This seems a completely different solution, but let's check if you can use the editorial to prove it fast.
  • We have to prove $$$f(2g) = 2$$$. But $$$f(g) = 1$$$ because all the $$$a_i$$$ modulo $$$g$$$ are the same. Then, either $$$f(2g) = 1$$$ or $$$f(2g) = 2$$$ (according to the editorial). But $$$f(2g) \neq 1$$$ because otherwise $$$\gcd(|a_i - a_{i+1}|)$$$ would be a multiple of $$$2g$$$.

With both algorithm $$$1$$$ and algorithm $$$2$$$ you would learn two solutions, but only with algorithm $$$2$$$ you would have a "full" understanding of them.

  • With algorithm $$$1$$$, you could get conclusions such as "when number $$$2$$$ appears in the statement, consider binary representation" or "when $$$\text{mod}$$$ appears in the statement, consider $$$\text{gcd}$$$" which seem random and not so practical.
  • With algorithm $$$2$$$, you have an intuitive visualization and an actual proof of the solution. You have also used the proof in the editorial to prove another (seemingly unrelated) solution (so proofs are not useless!). You learned the "binary" trick, but you also got better at proving stuff.

1909C - Heavy Intervals

Algorithm $$$1$$$:

  • Read the editorial.
  • Understand that, for some unintuitive reason (i.e., a proof which seems unnecessarily long), you need a bracket matching.
  • Implement the solution.
  • Read the comments; find out that many people tried to sort $$$l$$$ and $$$r$$$ in ascending order, but somehow it does not work.

Algorithm $$$2$$$:

  • Look at the picture for some time (between $$$1$$$ second and $$$5$$$ minutes), understand what's going on, understand the solution.
  • Implement the solution.
  • Re-read the editorial carefully. Ask yourself why the proof is so long. In particular, why do we need "Keep swapping endpoints until you get the "regular" bracket matching. You can show that the process ends in a finite number of steps"? Can't you just swap a single pair of endpoints to show that intersecting segments are never optimal?
Spoiler
  • Read the comments; find out that many people tried to sort $$$l$$$ and $$$r$$$ in ascending order. Realize a fun fact: sorting $$$l$$$ and $$$r$$$ in ascending order is the worst possible ordering (assuming you sort $$$c$$$ correctly).

Conclusions

Editorials are not evil! But, if you are not improving, ask yourself if you are reading them correctly.

Full text and comments »

  • Vote: I like it
  • +172
  • Vote: I do not like it

By TheScrasse, history, 3 months ago, In English

Sorry for weak tests in 1917C - Watering an Array.

Initially, the statement had the array $$$b$$$ in input, and we had to do these three things simultaneously:

  • make $$$O(n^2)$$$ pass;
  • make $$$O(nd)$$$ fail;
  • make $$$d$$$ small enough (i.e., $$$\leq 10^6$$$), so that the input could be read fast in any language.

But $$$O(nd)$$$ was too fast, so (on Dec 22) we decided to use $$$d \leq 10^9$$$ and compress the array. But testers had already tested the old version of the problem, and I can't expect testers to reset their memory and retry the problem, so no one found the wrong $$$O(nk)$$$ solution.

I'm sorry for making at least two mistakes:

  • Modifications 2 days before the contest may be ok, but they must be checked very carefully because fewer testers will see them.
  • I should have checked the existence of a pretest with all small cases. Maybe in this problem such test is not so comfortable to make, but you can achieve a similar effect by using a pretest with many random cases where every value in the input is small.

Please downvote this blog (instead of the announcement).

Full text and comments »

  • Vote: I like it
  • +515
  • Vote: I do not like it

By TheScrasse, 3 months ago, In English

text Ciao, Codeforces! We're glad to invite you to take part in Pinely Round 3 (Div. 1 + Div. 2), which will start on Dec/23/2023 17:35 (Moscow time). You will be given 9 problems and 3 hours to solve them. One of the problems will be divided into two subtasks.

The problems were authored and prepared by me.

Spoiler

We would like to thank

Score distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - (1500 + 1500) - 4000 - 6000 - 6000$$$

We hope you'll like the problemset!

Update 1: the editorial is here.

Update 2: congratulations to the winners!

This round is made possible with the support of Pinely!

Pinely is an algorithmic trading firm, with its main focus set on high-frequency and ultra-low-latency trading. They have offices in Amsterdam, Limassol, Singapore, and Shanghai and are open for job discussions. Pinely is a team of winners, awardees, and medalists of various competitions in respective fields such as ICPC, IMC, HITB PRO CTF, and Google HashCode, etc. They constantly face various challenges such as developing strategies for trading, optimizing trading systems to achieve the lowest latency reactions to various market events, and saving and processing large volumes of historical data.

You can find out more about Pinely on their website or from their employees registered here on Codeforces. If you want to join the Pinely team, please send your CV to [email protected] or fill in the form:

Apply

Prizes: top 30 contestants and 10 random contestants placed 31-100 will receive a branded Pinely hoodie :)

Full text and comments »

  • Vote: I like it
  • +797
  • Vote: I do not like it

By TheScrasse, history, 3 months ago, In English

The official implementations of all the problems are here.

Timeline of the round proposal (may contain spoilers)

1909A - Distinct Buttons

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

1909B - Make Almost Equal With Mod

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909C - Heavy Intervals

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909D - Split Plus K

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

1909E - Multiple Lamps

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1909F1 - Small Permutation Problem (Easy Version), 1909F2 - Small Permutation Problem (Hard Version)

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1909G - Pumping Lemma

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

1909H - Parallel Swaps Sort

Author: TheScrasse
Full solution: Endagorion, errorgorn
Preparation: TheScrasse, franv

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Hint 10
Hint 11
Hint 12
Solution

1909I - Short Permutation Problem

Author: TheScrasse
Full solution: errorgorn
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution

Full text and comments »

  • Vote: I like it
  • +354
  • Vote: I do not like it

By TheScrasse, history, 3 months ago, In English

This problem was going to be used in Pinely round...

Problem

but it has exactly the same solution as 1913D - Схлопывание массива.

A while ago I invented another problem, but my coordinator rejected it because the authors of Hello 2024 (whose coordinator is the same) had just invented the same exact problem!

:(

Full text and comments »

Tags sad
  • Vote: I like it
  • +329
  • Vote: I do not like it

By TheScrasse, history, 6 months ago, In English

For the eighth time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate! There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

  1. The problem statements will be available in both English and Italian.
  2. Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
  3. The only language allowed is C++.
  4. The time window for the practice contest (featuring original problems) will start on 2023 September 30th, 00:00 CET and will end on 2023 October 10th, 23:59 CET.
  5. The time window for the main contest will start on 2023 October 13th, 10:00 CET and will end on 2023 October 14th, 15:00 CET.

The contests' timing will be USACO-like: you can decide when to start your 5-hours time window (after the login), but the contest will end at the given time regardless of your time window.

If you want to participate, you must:

  1. Visit the contest website: https://mirror.oii.olinfo.it
  2. Click the link "register", fill out the form and then click on the register button and then "back to login"
  3. You can now log in with the same username and password you used to sign up
  4. If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  5. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  6. Good luck and have fun!

Ranking: The ranking of the online contest will be available at https://mirror.oii.olinfo.it/ranking when the contest starts.

Upsolving: After the end of the contest, tasks will be uploaded in the Italian training website https://training.olinfo.it (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).

Full text and comments »

  • Vote: I like it
  • +106
  • Vote: I do not like it

By TheScrasse, history, 8 months ago, In English

Hi everyone,

after Codeforces Round 889 (Div. 1), maybe it's time to collect all my problems here. For now, I've mainly invented easy-ish problems. I wish to invent a very hard problem sooner or later :)

I'm putting the story of each problem under spoiler, because it may contain parts of the solution. I invented many problems by just trying random setups until I came up with something solvable, but some problems (especially the harder ones, for example 1854D - Майкл и отель) may have more interesting stories.

Fun facts:

Authored (roughly sorted by difficulty)

preoii_vm - Aggiornamento della macchina virtuale

Story

cc PATHPAR - Path Parity

Story

cc XORPERM - Xor Permutation

1485A - Add and Divide

Story

cc SUMPRODSEG - Sum Product Segments

Story

cc MXMODSUM - Maximum Pairwise Modular Sum

Story

1855B - Наибольший интервал делителей

Story

terry 2023/3 - Dipingere i muri

Story

1485B - Replace and Keep Sorted

Story

cc SEGFAULT - Segmentation Fault

Story

cc SUBARRAYLEN - Subarrays with length

Story

terry 2023/4 - Viaggio intrigante

Story

cc ANTIKNAPSACK - Anti-knapsack

Story

cc THROWTAKE - Throw and Take

Story

1854A2 - Dual (сложная версия)

Story

1485D - Multiples and Power Differences

Story

1854B - Заработать или разблокировать

Story

preoii_armadio - Evasione dall'armadio

Story

UOI 2023/7 - Add Again

Story

1485E - Move and Swap

Story

1485F - Copy or Prefix Sum

Story

cc NDANDANDOR - Non-decreasing AND and OR

Story

1854C - Ожидаемое разрушение

Story

preoii_allenamento - Allenamento su ChinaForces

Story

cc PERMSEGMENTS - Permutation Segments

Story

1854D - Майкл и отель

Story

Partially authored (roughly sorted by difficulty)

1654A - Maximum Cake Tastiness

Story

preoii_triplets - Comune di Alleib

Story

1485C - Floor and Mod

Story

arc147_c - Min Diff Sum

Story

preoii_permutazione2 - Trova la permutazione

Story

preoii_sets - Insiemi nell'armadio

Story

1762E - Tree Sum

Story

preoii_statue - Galleria d'arte

Story

UOI 2023/4 - Array and prefix sums

Story

1654H - Three Minimums

Story

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

By TheScrasse, history, 8 months ago, In English

Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 889 (Div. 1) and Codeforces Round 889 (Div. 2), which will start on Jul/29/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions.

  • One of the problems will be divided into two subtasks.
  • One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

The problems were authored and prepared by akifpatel, dario2994, Kaey and me.

We would like to thank

Score distribution:

  • Div. 1: $$$(750 + 750) - 1500 - 1500 - 2000 - 2750 - 3250$$$
  • Div. 2: $$$500 - 1000 - (1250 + 1250) - 2500 - 2500 - 3000$$$

We hope you'll like the problemset!

Update 1: the editorial is out.

Update 2: congratulations to the winners!

Winners and first solves

Full text and comments »

  • Vote: I like it
  • +377
  • Vote: I do not like it

By TheScrasse, 8 months ago, In English

The official implementations of all the problems are here.

1855A - Dalton the Teacher

Author: Kaey
Preparation: akifpatel

Hint 1
Hint 2
Solution

1855B - Longest Divisors Interval

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854A1 - Dual (Easy Version)

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854A2 - Dual (Hard Version)

Author: TheScrasse
Preparation: akifpatel, dario2994

The hints and the solution continue from the easy version.

Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Solution

1854B - Earn or Unlock

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution

1854C - Expected Destruction

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution

1854D - Michael and Hotel

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854E - Game Bundles

Author: dario2994
Preparation: akifpatel, dario2994

Hint 1
Hint 2
Hint 3
Solution

1854F - Mark and Spaceship

Author: dario2994
Preparation: akifpatel, dario2994

Hint 1
Hint 2
Hint 3
Solution

Full text and comments »

  • Vote: I like it
  • +196
  • Vote: I do not like it

By TheScrasse, history, 9 months ago, In English

Hello, Codeforces! We're glad to invite you to take part in WPF Sudoku GP7.

  • Authors: Giulia Franceschini, Stefano Forcolin, Valeria Losasso, Valerio Stancanelli (TheScrasse).
  • The time window is USACO-style: you can choose any time window of $$$90$$$ minutes from Jul 7th to Jul 10th.
  • The instruction booklet with the score distribution is available here.

Why should you join?

  • If you are good at competitive programming, expect to be good at sudoku.
  • There are $$$13$$$ grids of different difficulties: anyone can find something to solve.
  • You will compete against tourist!

We hope you'll like the round!

Full text and comments »

  • Vote: I like it
  • +90
  • Vote: I do not like it

By TheScrasse, history, 10 months ago, In English

A while ago, I posted this blog. I was wrong.

In CodeRush May '23 (a contest with prizes), problem E was copied from yukicoder. The sample input is also almost the same: the CodeRush organizers just made it weaker by removing the last 2 queries!

Problemsetters, please stop.

Full text and comments »

  • Vote: I like it
  • +101
  • Vote: I do not like it

By TheScrasse, history, 11 months ago, In English

We will hold a duel (Dominater069 vs TheScrasse), with live streaming.

The problem will be chosen from past AtCoder Regular Contests.

We are looking forward to your participation!

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

By TheScrasse, history, 13 months ago, In English

Hello everyone,

yesterday I hacked the following submission: 195599340. It wasn't trivial for me (I found it more difficult than solving the problem itself), but it doesn't require any weird mathematical knowledge. So, if you've never hacked before, you may want to try to hack that submission by yourself. Anyway, I wanted to share the hack as a tutorial (since I have not found similar blogs on Codeforces). Here is the "solution":

Solution

Let's read the submission. It calculates two hashes (stored in val[x]). We would like to generate a collision (= two non-isomorphic subtrees that have the same hashes). Let's notice some details:

  • The hash is deterministic (it doesn't rely on random variables), so it's potentially vulnerable.
  • The hash of small trees looks "manageable" (= it doesn't grow very fast), so it may be possible to find a collision just using small trees.

So, let's start printing the hashes of small trees. Actually it doesn't work (all those hashes are distinct). However, we can try merging those trees. In particular, if we attach a subtree with hash val[x] to node r, val[r] becomes {val[r].first * val[x].first * treeSize[x], val[r].second + (val[x].second * (treeSize[x] + 1))} (in modulo).

Now we want to attach subtrees to two nodes r, s, in such a way that their hashes become the same. So, we are interested in products of $$$a_i =$$$ val[x].first * treeSize[x] and sums of $$$b_i =$$$ val[x].second * (treeSize[x] + 1). Let's print their values for small trees $$$T_i$$$:

  • $$$T_1 = \{(1, 2)\}$$$, $$$a_1 = 6$$$, $$$b_1 = 4$$$
  • $$$T_2 = \{(1, 2), (1, 3)\}$$$, $$$a_2 = 16$$$, $$$b_2 = 9$$$
  • $$$T_3 = \{(1, 2), (2, 3)\}$$$, $$$a_3 = 24$$$, $$$b_3 = 15$$$
  • $$$T_4 = \{(1, 2), (1, 3), (1, 4)\}$$$, $$$a_4 = 40$$$, $$$b_4 = 16$$$
  • $$$T_5 = \{(1, 2), (1, 3), (2, 4)\}$$$, $$$a_5 = 60$$$, $$$b_5 = 24$$$
  • $$$T_6 = \{(1, 2), (2, 3), (2, 4)\}$$$, $$$a_6 = 80$$$, $$$b_6 = 40$$$
  • $$$T_7 = \{(1, 2), (2, 3), (3, 4)\}$$$, $$$a_7 = 120$$$, $$$b_7 = 64$$$

Let's find two distinct multisets of trees with equal $$$\prod a_i$$$ and $$$\sum b_i$$$. That's equivalent to finding non-zero coefficients $$$e_i$$$ such that $$$\prod a_i^{e_i} = 1$$$ and $$$\sum b_ie_i = 0$$$ (if $$$e_i$$$ is positive, it contributes to a multiset; if it's negative, it contributes to the other multiset).

$$$\prod a_i^{e_i} = 1$$$ if the multiplicity of each prime factor is $$$0$$$. For example, we can get rid of factors $$$\neq 2$$$ by enforcing $$$e_3 = -e_1$$$, $$$e_6 = -e_4$$$, $$$e_7 = -e_5$$$ (so, we get $$$a_1^{e_1} \cdot a_3^{e_3} = (a_3/a_1)^{e_3} = 2^{2e_3}$$$, etc.).

Now we have only $$$2$$$ equations (one for the multiplicity of $$$2$$$, one for the sum), and more than $$$2$$$ unknowns, so we can find a non-zero solution. One example is $$$[16, 0, -16, -69, 37, 69, -37]$$$. The total number of nodes is smaller than $$$2 \cdot 10^5$$$, so we have found a hack.

Conclusions

In the next div3 / educational round, it's up to you to hack such submissions!

Bonus

Can you hack 195587728? It's still deterministic, but the hash function seems stronger. Maybe we can generate random trees with $$$> 10^9$$$ nodes in total and hope that a collision happens (birthday paradox), but I have not tried.

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

By TheScrasse, history, 14 months ago, In English

tl;dr

Read this comment.

It's good to know that segment tree exists

  • You can learn basic segment tree (Fenwick tree may be enough) if you want to overkill some problems. Just don't try to solve hard segment tree problems like this and this if you are cyan, because there are better ways to practice and learn something. This comment hits the spot: you can "be aware of the segment tree", but it shouldn't be your main weapon as a cyan / blue.
  • If you take part to OI / ICPC, segment tree can be very useful (especially at regional level). Unlike on Codeforces, there may be easy-ish but not trivial segment tree problems (let's say with a rating around 2200). So, if you want to practice segment tree for some reason (e.g., you love segment trees, or you are practicing for OI), start with OI problems.

Should you master segment tree problems?

If you want to solve non-trivial segment tree problems, you should

  1. actually understand how segment tree works (including time complexity);
  2. have decent implementation skills;
  3. be able to convert the given problem into a segment tree problem.

If you are able to learn all these things, you already have purple skills. Conversely, if you are not purple, most probably you won't manage to actually learn segment tree.

Examples

  • Blog 1: the author asks how to solve a problem. Someone replies, linking a comment about another problem whose solution is almost identical to the original problem. The comment contains a detailed explanation of the solution and an AC code.
    The author of the blog replies that he wants an AC code of his problem because he can't implement the solution. It turns out it's because the provided AC code uses a segment tree as a struct.
  • Blog 2: the author is "confused" about the time and space complexity of his solution using a segment tree. It turns out his solution is worse than the naive solution.

Comments

  • Blog 1: if you understand the explanation of the solution, and you say you know segment tree, you should have no problems implementing the solution from scratch (point 2 above). If not, it means that you don't understand the solution, so the problem is too hard for you (3). Then, why would you need to solve it? Also, copy-pasting others' code without understanding it does not count as solving the problem. Then, why are you asking for the code?
  • Blog 2: I guess someone told you that the problem is solved "using segment tree" and you tried to implement a solution without even calculating the complexity (1). Please note that there may be multiple ways, both correct and wrong, to use segment tree in a problem (similarly, in other problems there may be multiple greedy solutions, both correct and wrong). So, if you are using segment tree, it doesn't mean that the code is "magically" efficient. Finding an actually correct solution can be hard (3).

Conclusion

It's fine not to be good at points 1, 2, 3 above if you are blue or below. There are other (more important?) things to learn at that level.

Side note: when I first became yellow, I had no clue about how to solve the linked problems. Now I can solve them, but I'm still yellow.

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

By TheScrasse, history, 14 months ago, In English

tl;dr

  • Competitive programming roadmap here.
  • It should be suitable both for newcomers and for people with some experience with CP: let's say, up to blue on Codeforces.
  • It contains ~ 100 "must-know" problems about various topics: ad-hoc, STL, binary search, DP, number theory, graphs.
  • There are solution sketches at the bottom, don't feel guilty reading them if stuck.

Why?

Many people new to Codeforces seek advice about how to get better / which problems to try. Other people are stuck on gray / green even after solving a lot of problems. This roadmap aims to be a solution.

My take: to be good at competitive programming, you have to know "what to think" and "how to think" when you try a problem.

  • "What to think": you have to know a decent amount of standard problems / techniques. Sometimes, a problem requires steps / observations that seem obvious if you've already seen them. Other times, you may solve a problem by reducing it to a well-known sub-problem. On the other hand, you may realize you've done something wrong if you "reduce" the problem to something that you know it's unsolvable under the given constraints. All this isn't possible if you don't know those standard problems.
  • "How to think": it comes down to "building" a path to the solution. Sometimes, you need to find new insights / observations by analyzing the process in the statement, manipulating math equations, etc. Other times, you need to find a twist to a well-known technique. You can practice "how to think" by solving ad-hoc / non-standard problems.

So, how to practice?

  • Using the Codeforces problemset is quite good for experienced people, but it may turn out to be harmful for beginners. Surely, recent contests on Codeforces have a very good quality, and even the easiest problems are often original and can't be googled. However, this means there are no easy standard problems, so you don't really improve in "what to think" when you solve them.
    Also, even the easiest problems are supposed to require an "idea" that often turns out to be nontrivial to find / prove without looking at the sample input / output. So, in most cases, the most convenient way to solve easy problems is to find a pattern in the samples, and this does not actually teach you "how to think" to solve harder problems. For example, in problem 1768A - Greatest Convex it's way easier to observe that the solution is $$$k-1$$$ from the samples than to actually find it out. (Note: this doesn't mean it's a bad problem, but only practicing with this kind of problems may be a bad practice).
  • CSES mainly contains standard problems, so it doesn't really teach "how to think".
  • AtCoder problemset contains a lot of educational problems, and AtCoder Beginner Contests problems are quite good for practice. However, most of them are "trivial" if you already know the underlying idea and "impossible" otherwise.
  • USACO Guide is very good, but it's more oriented to OI (Olympiads in Informatics) and it contains some problems with very long statements and where the bottleneck is the implementation.

How does the roadmap work?

The roadmap contains ~ 100 problems, mainly from AtCoder, Codeforces and an Italian online judge.

  • "What to think": the problems are "standard-ish", and they cover most of the ideas required in problems ranging from easy (div2A) to medium (div2D-E). In other words, given a problem of such difficulty, there is a high chance it has at least one idea in common with a problem in the roadmap.
  • "How to think": the problems are "not so standard", and most of them also require ad-hoc ideas or twists to standard ideas.
  • The statements are short, and they require no "unnecessary" implementation details. Try to make your implementation as simple and short as possible.
  • The problems are split into topics. However, sections $$$5$$$ and $$$6$$$ contain "summary problems" with no topic, so that you don't get used to solve problems knowing the topic in advance.
  • The roadmap includes problems with various levels of difficulty, indicated by the number of stars (from $$$0$$$ to $$$6$$$).
  • If you are stuck on a problem for a long time, you may want to read the solution sketch at the end of the document. These sketches are written in such a way that only new ideas (= not used in the previous problems in the roadmap) are highlighted. So, you may want to think again about the problem. If you are still stuck, you may want to read the editorial (available on Codeforces and AtCoder). Of course, you shouldn't always use the solution sketch or the editorial. Ideally, you should use the solution sketch in less than half of the problems above your level, and read the complete editorial few times. However, reading the solution sketch and the editorial after solving the problem is often useful, as they can contain tips, alternative solutions or variants of the problem.

Then?

After finishing the roadmap (excluding the "Final problems" in section $$$14$$$), probably you have built a small "database" of standard-ish problems in your head and you're much better in the "what to think" part. "How to think" is more complex and it requires more time / experience to be mastered. Anyway, there are many ways to make further progress.

  • If you want to practice on a specific topic, you can use USACO Guide, or try the "bonus mashups" in the last section.
  • You can try harder problems on the Codeforces problemset (guessing from the samples doesn't work on harder problems) and on AtCoder problemset (they are not "impossible" anymore, since you know more tools to solve them).

Conclusion

Of course, feedback / suggestions / corrections are welcome. The roadmap may contain a lot of typos or the solutions may be unclear, let me know and I will try to fix.

If you're starting the roadmap, good luck! I hope it will be useful.

Full text and comments »

  • Vote: I like it
  • +283
  • Vote: I do not like it

By TheScrasse, history, 16 months ago, In English

[title inspired by this blog]

Hello everyone,

today, during a NEERC virtual contest, I found an unintended solution for problem 1089I - Interval-Free Permutations. I've checked all the official submissions and no one of them uses my solution, so I think it's worth sharing it.

Abridged statement: count the permutations of $$$[1, \dots, n]$$$ such that there are no subarrays of length between $$$2$$$ and $$$n-1$$$ where all the values are contiguous. For example, the permutation $$$[2,8,4,6,3,5,1,7]$$$ is bad because it contains $$$[4,6,3,5]$$$ as a subarray. Output the answer (modulo a prime, given in the input) for all $$$1 \leq n \leq 400$$$.

My solution:

  • Let's use PIE (inclusion-exclusion principle) on minimal bad subarrays.
  • Let's use Connected Components DP, somehow keeping track of minimal bad subarrays.

  • Let $$$dp_{i,j,k}$$$ be the number of ordered sets of $$$j$$$ connected components with total length $$$i$$$, and $$$k =$$$ parity of minimal bad subarrays. Then, the number of good permutations of length $$$i$$$ is $$$dp_{i,1,0} - dp_{i,1,1}$$$.
    Instead of adding elements one at a time to the permutation, let's consider two cases:
    - We add only one element (using the standard Connected Components DP transitions);
    - We add a minimal bad subarray of length $$$2 \leq l \leq i-1$$$ (the transitions are similar, but using $$$dp_{i-l,*,k \oplus 1}$$$ instead of $$$dp_{i-1, *, k}$$$. Note that the number of ways to add a minimal bad subarray of length $$$l$$$ is equal to the number of good permutations of length $$$l$$$.
  • When we calculate $$$dp_{i,*,*}$$$, we assume that $$$dp_{j,1,*} = 0$$$ ($$$j < i$$$), because the corresponding elements are good as arrays but bad as subarrays.

This solution is actually wrong: in most cases, it produces the correct output $$$\pm 2$$$! It turns out it's enough to add $$$-2 \cdot (-1)^n$$$ to the result, for $$$n \geq 3$$$. (AC code: 181878668)

So my questions are:

  • Why is the initial solution wrong?
Hint
  • Why is the solution with $$$-2 \cdot (-1)^n$$$ correct? Actually I don't know, I've just found the formula using the samples.
  • Can this solution be generalized to solve harder problems? For example,
    "An array is weird if the local minimums are bitonic (i.e., decreasing, then increasing). Count the weird permutations of $$$[1, \dots, n]$$$ such that there are no weird subarrays of length between $$$2$$$ and $$$n-1$$$ where all the values are contiguous."

Full text and comments »

  • Vote: I like it
  • +125
  • Vote: I do not like it

By TheScrasse, history, 18 months ago, In English

For the seventh time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate! There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

  1. The problem statements will be available in both English and Italian.
  2. Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
  3. The only language allowed is C++.
  4. The time window for the practice contest (featuring original problems) will start on 2022 September 13th, 00:01 CET and will end on 2022 September 17th, 23:59 CET.
  5. The time window for the main contest will start on 2022 September 23th, 10:00 CET and will end on 2022 September 24th, 15:00 CET.

The contests' timing will be USACO-like: you can decide when to start your 5-hours time window (after the login), but the contest will end at the given time regardless of your time window.

If you want to participate, you must:

  1. Visit the contest website: https://mirror.oii.olinfo.it
  2. Click the link "register", fill out the form and then click on the register button and then "back to login"
  3. You can now log in with the same username and password you used to sign up
  4. If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  5. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  6. Good luck and have fun!

Ranking: The ranking of the online contest will be available at https://mirror.oii.olinfo.it/ranking when the contest starts.

Upsolving: After the end of the contest, tasks will be uploaded in the Italian training website https://training.olinfo.it (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).

Full text and comments »

  • Vote: I like it
  • +181
  • Vote: I do not like it

By TheScrasse, history, 23 months ago, In English

Hello everyone,

I'm asking for some help about how to train my schoolmates for Regional OI. Most of them have a fairly good MO background, so they are supposed to get good even if they don't practice at home (i.e., I think the $$$2$$$ hours a week at school should be enough to qualify to National OI). However, the results so far are quite disappointing: I feel I'm doing something really wrong.

Format of Regional OI

The statements are here (requires registration). Each year, there are usually

  • $$$2$$$ easy problems (let's say A, B);
  • $$$1$$$ standard DP with a twist (C);
  • $$$1$$$ standard graph problem with a twist (D).

A < B < C < D (in order of difficulty and points). They are similar to Div. 3 C, D, E, F. Solving A and C is enough to go to National OI.

Schedule of this year

The training started in October 2021.

  • October - November: introduction to C++ and STL (in the CPH, they correspond to chapters $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, part of $$$5$$$, part of $$$6$$$)
  • December - January: dynamic programming (chapter $$$7$$$)
  • end of January: ad-hoc, number theory (chapter $$$21$$$)
  • February - April: graphs (chapters $$$11$$$, $$$12$$$, part of $$$13$$$, part of $$$14$$$, part of $$$15$$$)
  • May: Regional OI.

Results

  • Initially, there were at least $$$20$$$ participants. Many of them dropped out of the training very soon. I actually expected this: the background of the participants was quite heterogeneous, and maybe it would have been better to hold two parallel training sessions ("basic" and "advanced"), but there was no other "trainer". Maybe this issue can be solved next year. Currently, there are $$$7$$$ participants.
  • $$$2$$$ of them got a silver medal at National OI last year. The tasks I propose to the rest of the group are too easy for them, so they try harder tasks (but I can't pay much attention to them).
  • About (most of) the others, I think they still struggle too much with implementation. More specifically, they don't have a clear understanding of what they are implementing. Examples:

    Q. "Now you have to pick the unprocessed node with the smallest distance [in Dijkstra's algorithm], how to do that?"
    A. "Adjacency lists?"

    Q. "So, what's the time complexity?"
    no one answers
    I explain why the complexity is $$$O(n + m \cdot \log n)$$$
    A. "This time complexity is so weird"

    Result: at the end of the meeting ($$$2$$$ hours), there is someone who still hasn't finished implementing Dijkstra.
    Of course, I can't blame the participants. In fact, the same "lack of understanding" happens to me when I try to solve physics problems.

Why does it happen?

I suspect the main reason is that most participants solved too few problems, but I haven't find a way to avoid this issue.

  1. I don't want to force them to do homework or train on their own. They have something better to do.
  2. I don't think solving a lot of *800 rated problems is a good strategy.
  3. When they can't solve a problem, I feel they just wait for the explanation and they don't strive to learn something new from the solution.
  4. It's difficult to find easy DP and graphs problems (i.e., I feel there is almost always a huge difficulty gap between "count connected components" and "realize that, after this modification, the problem reduces to counting connected components").

Examples:

Seeking for help

Regional OI is in $$$1$$$ month. I'm quite sure that all the participants to the training have the potential to qualify to National OI, but I feel I wasted that potential. Moreover, I don't want to repeat the same mistakes next year.

If you have suggestions to fix the "coaching" method, please write them in the comments. Thanks!

Full text and comments »

  • Vote: I like it
  • +186
  • Vote: I do not like it

By TheScrasse, history, 2 years ago, In English

Hello everyone,
finding the diameter is one of the most frequent ways to solve problems about trees. In this tutorial we will see how to find a diameter and some of its properties, and we will use them to solve some problems of increasing difficulty.
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.

Target: rating $$$[1400, 2300]$$$ on CF
Prerequisites: basic graph theory, greedy

The diameter

Given an unweighted tree, let's define $$$\text{dist}(a, b) =$$$ the number of edges in the simple path $$$a \rightarrow b$$$.

A diameter of the tree $$$a \rightarrow b$$$ is the longest path, i.e., the one that maximizes $$$\text{dist}(a, b)$$$ over all pairs of nodes. If there are multiple diameters, let's pick any of them.

The same definition is valid for a weighted tree with nonnegative weights (with $$$\text{dist}(a, b) =$$$ the sum of the weights of the edges in the simple path $$$a \rightarrow b$$$).

Finding a diameter

Given a tree with $$$n$$$ nodes are multiple ways to find a diameter. Here is one of the simplest ways:

Run a DFS from any node $$$p$$$. Let $$$a$$$ be a node whose distance from node $$$p$$$ is maximized. Run another DFS from node $$$a$$$. Let $$$b$$$ be a node whose distance from node $$$a$$$ is maximized. $$$a \rightarrow b$$$ is a diameter.

Tree = edges of a diameter + forest

Before proving the previous algorithm, let's analyze the structure of the tree (we will mention the diameter, but we will not use the fact that $$$a \rightarrow b$$$ is actually a diameter before proving it).

We started a DFS from node $$$p = 16$$$, and we got that node $$$a = 1$$$ is the farthest from $$$p$$$, and node $$$b = 7$$$ is the farthest from $$$a$$$.

Let's represent the diameter on a line. If you remove the edges of the diameter, you get a forest (i.e., several trees). Let's root each tree at the node in the diameter. What's the height (i.e., the maximum distance from the root to any node) of each component?

Let $$$q$$$ be the root of the component of $$$p$$$. Let's consider any component whose root $$$d$$$ is between $$$a$$$ (included) and $$$q$$$ (excluded), and one of its nodes $$$c$$$.

We get

$$$\text{dist}(p, a) \geq \text{dist}(p, c) \implies \text{dist}(p, a) - \text{dist}(p, d) \geq \text{dist}(p, c) - \text{dist}(p, d) \implies \text{dist}(a, d) \geq \text{dist}(c, d)$$$.

In other words, the height of each component with root in the left half of the diameter (i.e., $$$\text{dist}(a, d) < \text{dist}(d, b)$$$) is at most the distance of the root of the component from the left end of the diameter.

You can prove the same statement for the right half of the diameter (i.e., $$$\text{dist}(a, d) \geq \text{dist}(d, b)$$$), using that $$$b$$$ is the farthest node from $$$a$$$.

Farthest node for each node

For each node $$$i$$$, let's find a node $$$j$$$ such that $$$\text{dist}(i, j)$$$ is maximum.

Claim: $$$j = a$$$ or $$$j = b$$$ always works.

Proof:

  • If $$$j = j_1$$$ works ($$$j_1$$$ is not in the same component of $$$i$$$; let's assume without loss of generality that $$$j_1$$$ is closer to $$$a$$$ than to $$$b$$$), $$$\text{dist}(i, j_1) = \text{dist}(i, r) + \text{dist}(r, j_1) \leq \text{dist}(i, r) + \text{dist}(r, a) = \text{dist}(i, a)$$$. Then, $$$j = a$$$ also works.
  • If $$$j = j_2$$$ works ($$$j_2$$$ is in the same component of $$$i$$$), $$$\text{dist}(i, j_2) \leq \text{dist}(i, r) + \text{dist}(r, j_2) \leq \text{dist}(i, r) + \text{dist}(r, a) = \text{dist}(i, a)$$$. Then, $$$j = a$$$ also works.

Proof that $$$a \rightarrow b$$$ is a diameter

Now we can finish the proof.

Suppose that $$$u \rightarrow v$$$ is a diameter. We have either $$$\text{dist}(u, a) \geq \text{dist}(u, v)$$$ or $$$\text{dist}(u, b) \geq \text{dist}(u, v)$$$ (see "Farthest node for each node").

Let's assume without loss of generality that $$$\text{dist}(u, b) \geq \text{dist}(u, v)$$$. We get $$$\text{dist}(a, b) \geq \text{dist}(u, b) \geq \text{dist}(u, v)$$$, so $$$a \rightarrow b$$$ is a diameter.

Observations

The algorithm also works in a weighted tree with positive edges (we've never used that the weights are $$$1$$$).

However, it doesn't work on general graphs (discussion).

How to use the diameter

Most of the times, spamming "the farthest node from each node is one end of the diameter" and "the height of each component is smaller than the distance to the closest end of the diameter" is enough to reduce the problem to something simpler.

Find a diameter $$$a \rightarrow b$$$ (from now, $$$a \rightarrow b$$$ will always be a diameter, unless otherwise stated). Now, you may need to consider any path of the tree. There are two cases: the path intersects (blue) or doesn't intersect (green) the diameter.

Then, you may wonder how to make the path longer / "more optimal" / etc. according to the statement. For example, you may need to use $$$\text{dist}(7, 5) \geq \text{dist}(5, 19)$$$ to show that $$$8 \rightarrow 7$$$ is "more optimal" than $$$8 \rightarrow 19$$$.

1004E - Sonya and Ice Cream (rating: 2400)

Hint 1
Hint 2
Hint 3
Solution

Implementation by nor (C++): 151009669

633F - The Chocolate Spree (rating: 2600)

Hint 1
Hint 2
Hint 3
Solution

Implementation by nor (C++): 151018941

1434D - Roads and Ramen (rating: 2800)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Implementation by nor (C++): 151024814

Other problems

CSES — Tree Distances I (to check your implementation) (suggested by nor)
102694B - Dynamic Diameter
1404B - Tree Tag (flashmt)
734E - Anton and Tree (preet_25)
456E - Civilization (SleepingThread)
Code Jam 2022 — Interesting Outing (srishtik_16)
abc221_f
IOI 2013 — Dreaming (timreizin)
agc033_c (antontrygubO_o)
arc117_d (flashmt)
USACO 2018 — New Barns (Olympia)
1617E - Christmas Chocolates (feecIe6418)
arc108_f (feecIe6418)
IOI 2015 — Towns (defnotmee)
1214H - Tiles Placement (lrvideckis)
CEOI 2019 — Dynamic Diameter (hard) (nor)
RMI 2021 — Paths (hard) (valeriu)

Conclusions

We've seen that finding a diameter can also solve seemingly unrelated problems, and it's a good candidate idea if the problem involves a tree and maximum lengths/distances.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you have to use the diameter.

I hope you enjoyed the blog!

Full text and comments »

  • Vote: I like it
  • +259
  • Vote: I do not like it

By TheScrasse, history, 2 years ago, In English

I've just turned International Grandmaster. Now you can ask me anything in the comments.

Full text and comments »

Tags ask, ama
  • Vote: I like it
  • +49
  • Vote: I do not like it

By TheScrasse, 2 years ago, In English

1654A - Maximum Cake Tastiness

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

Official solution: 150288088

1654B - Prefix Removals

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288210

1654C - Alice and the Cake

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288232

1654D - Potion Brewing Class

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150288255

1654E - Arithmetic Operations

Author: emorgan
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288285

1654F - Minimal String Xoration

Author: dario2994, emorgan
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288326

1654G - Snowy Mountain

Author: emorgan
Preparation: dario2994, emorgan, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288345

1654H - Three Minimums

Author: dario2994, TheScrasse
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150306974

Full text and comments »

  • Vote: I like it
  • +133
  • Vote: I do not like it

By TheScrasse, history, 2 years ago, In English

Hello everyone,
in this tutorial we will see a trick that can be useful in combinatorics and/or DP tasks. In particular, you can use it when the statement says something similar to "the score of an array is the product of its elements, find the sum of the scores over all the possible arrays".

Prerequisites: basic combinatorics and DP

The trick

The trick is very simple.

"The score of an array $$$a$$$ is $$$\prod_{i=1}^n a_i$$$" can be rephrased as "if there are $$$n$$$ boxes, and the $$$i$$$-th box contains $$$a_i$$$ distinguishable balls, the score of $$$a$$$ is equal to the number of ways to color a ball for each box".

This is quite obvious, but it can be extremely powerful. Let's see some problems that are trivialized by this trick.

Dwango Programming Contest 6th, problem C (rating: 2618)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Implementation (C++)

abc231_g (rating: 2606)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus

Implementation (C++)

arc124_e (rating: 3031)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

arc147_d - Sets Scores (rating: 2145)
abc214_g - Three Permutations (rating: 2893) (suggested by __hermit__)
agc013_e - Placing Squares (rating: 3455) (zscoder)
1842G - Tenzing and Random Operations
IOI 2022/4 - Digital Circuit
abc225_h - Social Distance 2 (rating: 3061) (__hermit__)

Conclusions

We've seen that "product trick" is very useful to find a DP that solves the problem. There exist similar counting tricks: for example, "The score of an array $$$a$$$ is $$$\sum_{i=1}^n a_i^2$$$" can be rephrased as "if there are $$$n$$$ boxes, and the $$$i$$$-th box contains $$$a_i$$$ distinguishable balls, the score of $$$a$$$ is equal to the number of ordered pairs of balls belonging to the same box" (you can try to use it in 1278F - Cards).

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you can use this trick.

I hope you enjoyed the blog!

Full text and comments »

  • Vote: I like it
  • +217
  • Vote: I do not like it

By TheScrasse, history, 2 years ago, In English

UPD: I was wrong :(

UPD2: I was wrong, again.

Hello everyone,
I see that many people complain about copied problems. Their claim is that authors weren't able to come up with some problems, and decided to copy them from other sources instead.

Comments of last round

Although a contest shouldn't have already used problems, please convince yourself that no problemsetter would copy problems deliberately. The presence of some problems from the Internet is accidental. So, it's not correct to accuse the authors to "copy" the problems.

FAQ:

Q. The statement is completely the same, isn't it obvious that the problem was copied?
A. No. Proof: I invented 844C - Сортировка подпоследовательностями and 1088D - Ехаб и еще одна очередная задача на xor, with the same statement. Usually, if you want to write the statement formally, there is only one way that's much more convenient to use that the others.

Q. Maybe you remembered the statement because you had already read it without solving the problem?
A. No. Proof: I invented 1501C - Поеду домой and arc130_d before the contest.

Q. How is it possible that no author / tester was able to find the "copied" problem by googling?
A. Challenge: find arc115_e on Google, using only the statement of 1591F - Неравные соседи.

Full text and comments »

  • Vote: I like it
  • +255
  • Vote: I do not like it

By TheScrasse, history, 3 years ago, In English

Hello everyone,

this blog is similar to 90744, but it's specifically about implementation.

Although practicing for around 2 years, I'm still very slow in implementation. For example, during olympiads I usually spend ~ 70% of the time writing the code, so I don't have much time to think.
In fact,

  • during CEOI 2021 Mirror (Day 2) I spent a lot of time writing ~ 220 lines of code for problem C (the logic of that solution was wrong, but that's another story)
  • I've just solved CEOI 2016/1 (submission), but my solution is 239 lines long.
  • I don't perform well on DMOJ (my contests: 1, 2, 3)
  • I spent 1:30 hours implementing 101597A, although my final code is only 81 lines long.

How to improve? Should I learn new C++ features? Should I start implementing something significantly longer than competitive programming problems?

Full text and comments »

  • Vote: I like it
  • +173
  • Vote: I do not like it

By TheScrasse, history, 3 years ago, In English

Hello everyone,
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious. In this tutorial we will see some easy ideas and use them to solve some problems of increasing difficulty. I tried to put a lot of examples to make the understanding easier.
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.

Target: rating $$$[1400, 2100]$$$ on CF
Prerequisites: greedy, Fenwick tree (or segment tree)

Counting inversions

Let's start from a simple problem.

You are given a permutation $$$a$$$ of length $$$n$$$. In one move, you can swap two elements in adjacent positions. What's the minimum number of moves required to sort the array?

Claim

The result $$$k$$$ is equal to the number of inversions, i.e. the pairs $$$(i, j)$$$ ($$$1 \leq i < j \leq n$$$) such that $$$a_i > a_j$$$.

Proof 1

Let $$$f(x)$$$ be the number of inversions after $$$x$$$ moves.
In one move, if you swap the values on positions $$$i, i + 1$$$, $$$f(x)$$$ either increases by $$$1$$$ or decreases by $$$1$$$. This is because the only pair $$$(a_i, a_j)$$$ whose relative order changed is $$$(a_i, a_{i+1})$$$. Since the sorted array has $$$0$$$ inversions, you need at least $$$k$$$ moves to sort the array.
For example, if you have the permutation $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ ($$$16$$$ inversions) and you swap two adjacent elements such that $$$a_i > a_{i+1}$$$ (getting, for example, $$$[2, 3, 7, 6, 8, 9, 1, 4, 5]$$$), the resulting array has $$$15$$$ inversions, and if you swap two adjacent elements such that $$$a_i < a_{i+1}$$$ (getting, for example, $$$[3, 2, 7, 8, 6, 9, 1, 4, 5]$$$), the resulting array has $$$17$$$ inversions.

On the other hand, if the array is not sorted you can always find an $$$i$$$ such that $$$a_i > a_{i+1}$$$, so you can sort the array in $$$k$$$ moves.

Proof 2

For each $$$x$$$, let $$$f(x)$$$ be the number of inversions if you consider only the elements from $$$1$$$ to $$$x$$$ in the permutation.
First, let's put $$$x$$$ at the end of the permutation: this requires $$$x - \text{pos}(x)$$$ moves. That's optimal (the actual proof is similar to Proof 1; in an intuitive way, if you put the last element to the end of the array, it doesn't interfere anymore with the other swaps).
For example, if you have the permutation $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ and you move the $$$9$$$ to the end, you get $$$[2, 3, 7, 8, 6, 1, 4, 5, 9]$$$ and now you need to sort $$$[2, 3, 7, 8, 6, 1, 4, 5]$$$. Hence, $$$f(x) = f(x-1) + x - \text{pos}(x)$$$. For each $$$x$$$, $$$x - \text{pos}(x)$$$ is actually the number of pairs $$$(i, j)$$$ ($$$1 \leq i < j \leq x$$$) such that $$$x = a_i > a_j$$$. So $$$f(x)$$$ is equal to the number of inversions.

Counting inversions in $$$O(n \log n)$$$

You can use a Fenwick tree (or a segment tree). There are other solutions (for example, using divide & conquer + merge sort), but they are usually harder to generalize.
For each $$$j$$$, calculate the number of $$$i < j$$$ such that $$$a_i > a_j$$$.
The Fenwick tree should contain the frequency of each value in $$$[1, n]$$$ in the prefix $$$[1, j - 1]$$$ of the array.
So, for each $$$j$$$, the queries look like

  • $$$res := res + \text{range_sum}(a_j + 1, n)$$$
  • add $$$1$$$ in the position $$$a_j$$$ of the Fenwick tree

Observations / slight variations of the problem

By using a Fenwick tree, you are actually calculating the number of inversions for each prefix of the array.

You can calculate the number of swaps required to sort an array (not necessarily a permutation, but for now let's assume that its elements are distinct) by compressing the values of the array. For example, the array $$$[13, 18, 34, 38, 28, 41, 5, 29, 30]$$$ becomes $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$.

You can also calculate the number of swaps required to get an array $$$b$$$ (for now let's assume that its elements are distinct) starting from $$$a$$$, by renaming the values. For example,
$$$a = [2, 3, 7, 8, 6, 9, 1, 4, 5], b = [9, 8, 5, 2, 1, 4, 7, 3, 6]$$$
is equivalent to
$$$a = [4, 8, 7, 2, 9, 1, 5, 6, 3], b = [1, 2, 3, 4, 5, 6, 7, 8, 9]$$$

$$$a^{-1}$$$ (a permutation such that $$$(a^{-1})_{a_x} = x$$$, i.e. $$$(a^{-1})_x$$$ is equal to the position of $$$x$$$ in $$$a$$$) has the same number of inversions as $$$a$$$. For example, $$$[2, 3, 7, 8, 6, 9, 1, 4, 5]$$$ and $$$[7, 1, 2, 8, 9, 5, 3, 4, 6]$$$ have both $$$16$$$ inversions. Sketch of a proof: note that, when you swap two elements in adjacent positions in $$$a$$$, you are swapping two adjacent values in $$$a^{-1}$$$, and the number of inversions in $$$a^{-1}$$$ also increases by $$$1$$$ or decreases by $$$1$$$ (like in Proof 1).

1430E - Переворот строки (rating: 1900)

Hint 1
Hint 2
Hint 3
Solution

103148B - Luna Likes Love (EGOI 2021/2)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

arc088_e (rating: 2231)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

arc097_e (rating: 2247)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

IOI 2019/1
arc120_c (suggested by Ghassane)
Hackerearth — Swapping numbers (Inferno03)
Hackerearth — Make the strings equal (Inferno03)
1526D - Убить Антона (somil_jain_120)
JOI 2021/3 (Final Round) (you can submit here)

Conclusions

We've seen that a lot of problems where you have to swap adjacent elements can be tackled with greedy observations, such as looking at the optimal relative positions of the values in the final array; then, a lot of these problems can be reduced to "find the number of inversions" or similar.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you have to swap adjacent elements.

I hope you enjoyed the blog!

Full text and comments »

  • Vote: I like it
  • +223
  • Vote: I do not like it