TheScrasse's blog

By TheScrasse, history, 2 weeks ago, In English

Today I've taken part in AtCoder Regular Contest 186, solved problem E and spent the remaining 90 minutes not solving anything.

Then I've taken part in Codeforces Global Round 27 and spent 90 minutes solving 2035D - Yet Another Real Number Problem.

How to stop being stupid?

Full text and comments »

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

By TheScrasse, history, 6 weeks ago, In English

I clearly cannot write editorials (see here, here, etc.)

Can anyone please actually explain me how to write editorials properly? What I do now is just providing my thinking process to reach the solution, but it seems that most people have a very different thinking process.

UPD: after reading the comments, I think I got what's wrong in my editorials (and I tried to fix that, especially in the editorial of 2018B - Speedbreaker). One of the main issues is that I tend to skip algebraic manipulations, inequalities, etc. (i.e., steps that require simple algebra and/or mathematical logic), and it turned out that they can be the bottleneck for most people here (and maybe this is also the reason why 2018B - Speedbreaker is harder than 2018C - Tree Pruning). Lesson learned: if some numbers / variables appears from nowhere, I should try to elaborate, even if it's a single mathematical step.

For earlier problems, maybe I should also focus on how to convert the ideas into code.

Anyway, I think this comment helped me a lot to write a "better" editorial. In an ideal world, I would ask testers to read the initial version of the editorial and write similar comments, to help me "fix" the editorial. But during problem preparation, the editorial is the most neglected part for obvious reasons (there are a lot of little things that can ruin a contest, but in theory a contest can be held without even publishing an editorial), and ideally I don't want to fix the editorial 2 days after the contest end, because most people would have already read it. A solution might be just to give write access to the editorial directly to the testers and let them fix it if they had trouble understanding something?

Full text and comments »

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

By TheScrasse, history, 6 weeks ago, In English

All the Polygon materials (including the official implementations of all the problems) are here.

2019A - Max Plus Size

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2019B - All Pairs Segments

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

2018A - Cards Partition

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

2018B - Speedbreaker

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2018C - Tree Pruning

Author: wksni
Preparation: TheScrasse

Hint 1
Hint 2
Solution

2018D - Max Plus Min Plus Size

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

2018E1 - Complex Segments (Easy Version), 2018E2 - Complex Segments (Hard Version)

Authors: lorenzoferrari, TheScrasse
Full solution: Flamire
Preparation: franv, lorenzoferrari

Hint 1
Hint 2
Hint 3
Hint 4
Solution

2018F1 - Speedbreaker Counting (Easy Version), 2018F2 - Speedbreaker Counting (Medium Version), 2018F3 - Speedbreaker Counting (Hard Version)

Author: TheScrasse
Full solution: Flamire
Preparation: TheScrasse

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

Full text and comments »

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

By TheScrasse, history, 7 weeks ago, In English

Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 975 (Div. 1) and Codeforces Round 975 (Div. 2), which will start on Sep/27/2024 16:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions. Some problems will be divided into subtasks.

UPD: the time has been changed to Sep/27/2024 16:35 (Moscow time), which is different from the time announced before. Please note the unusual starting time.

This round is based on Italian Olympiad in Informatics (OII) 2024.

The problems were authored by lorenzoferrari, wksni and me.

We would like to thank

Score distribution:

  • Div. 1: $$$500 - 750 - 750 - 1500 - (2250 + 750) - (1500 + 1500 + 1500)$$$
  • Div. 2: $$$500 - 1000 - 1750 - 2000 - 2000 - 3000$$$

We hope you'll like the problemset!

Update 1: the editorial is here.

Update 2: congratulations to the winners!

Winners and first solves

Full text and comments »

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

By TheScrasse, history, 2 months ago, In English

For the ninth 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.

This year, there will be three online contests in total, held in the following order:

  1. a mirror of the practice contest (featuring original problems);
  2. an official (rated) Codeforces round based on the main contest;
  3. a mirror of the main contest.

Official Codeforces round

The format of the Codeforces round (2.) will be the usual Codeforces format, so you don't need any extra steps to register / participate. Another blog will be published a few days before the round.

Other rounds

About the other rounds (1. and 3.):

  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 2024 September 13th, 22:01 UTC and will end on 2024 September 25th, 21:59 UTC.
  5. Then, a rated Codeforces round based on the main contest will be held on September 27th (time to be decided).
  6. The time window for the main contest will start after the official Codeforces round, i.e., on September 27th (time to be decided).

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: practice contest, main contest.
  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
  • +140
  • Vote: I do not like it

By TheScrasse, history, 10 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, 11 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, 11 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, 11 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, 11 months ago, In English

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

Problem

but it has exactly the same solution as 1913D - Array Collapse.

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, 13 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, 15 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 :)

Update after Pinely Round 3

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 - Michael and Hotel) may have more interesting stories.

Fun facts:

  • I struggled a lot to find a suitable div2A for Codeforces Round 778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round). I proposed a lot of problems that turned out to be unsuitable (for example, because they were too hard), then I used them somewhere else.
  • While I was writing this blog, I realized that 1849E - Max to the Right of Min is identical to my problem preoii_allenamento - Allenamento su ChinaForces, and I could just copypaste the code. Unfortunately I realized this $$$20$$$ minutes after the start of the contest, and I couldn't get the first AC :D
  • Sometimes, if you just remove parts of the statement, the problem becomes better (and sometimes harder)! For example, initially 1854D - Michael and Hotel and preoii_statue - Galleria d'arte were relatively easy problems with a slightly longer statement (e.g., in 1854D - Michael and Hotel it was guaranteed that the input had a special structure), but making the statement simpler also made these problems more interesting.
  • Coming up with a good problem starting from the solution is really hard (at least for me). After failing to generate any difficult problem from the solution, I would say I fully agree with Um_nik's last pro tip.

Authored (roughly sorted by difficulty)

preoii_vm - Aggiornamento della macchina virtuale

Story

cc PATHPAR - Path Parity

Story

cc XORPERM - Xor Permutation

1909A - Distinct Buttons

Story

1485A - Add and Divide

Story

cc SUMPRODSEG - Sum Product Segments

Story

cc MXMODSUM - Maximum Pairwise Modular Sum

Story

1855B - Longest Divisors Interval

Story

terry 2023/3 - Dipingere i muri

Story

1485B - Replace and Keep Sorted

Story

1928B - Equalize

Story

cc SEGFAULT - Segmentation Fault

Story

cc SUBARRAYLEN - Subarrays with length

Story

terry 2023/4 - Viaggio intrigante

Story

1909B - Make Almost Equal With Mod

Story

1909C - Heavy Intervals

Story

cc ANTIKNAPSACK - Anti-knapsack

Story

cc THROWTAKE - Throw and Take

Story

ois_fibonacci - Fibonacci Sequences

Story

1854A2 - Dual (Hard Version)

Story

1909D - Split Plus K

Story

1485D - Multiples and Power Differences

Story

1854B - Earn or Unlock

Story

preoii_armadio - Evasione dall'armadio

Story

UOI 2023/7 - Add Again

Story

1485E - Move and Swap

Story

1485F - Copy or Prefix Sum

Story

1909E - Multiple Lamps

Story

cc NDANDANDOR - Non-decreasing AND and OR

Story

1854C - Expected Destruction

Story

preoii_allenamento - Allenamento su ChinaForces

Story

ois_aliga - A Day in Olbia

Story

cc PERMSEGMENTS - Permutation Segments

Story

1909F2 - Small Permutation Problem (Hard Version)

Story

1854D - Michael and Hotel

Story

1909G - Pumping Lemma

Story

1909I - Short Permutation Problem

Story

1909H - Parallel Swaps Sort

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

oii_corridoi - Arte nei corridoi

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, 16 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, 16 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, 16 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, 17 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, 19 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, 20 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, 22 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, 22 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, 2 years 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, 2 years 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, 3 years 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, 3 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, 3 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