TheScrasse's blog

By TheScrasse, history, 3 weeks 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).

Read more »

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

By TheScrasse, history, 6 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!

Read more »

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

By TheScrasse, history, 6 months 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_1) \leq \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.

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 (Ajam)
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 (definitelynotmee)
1214H - Tiles Placement (lrvideckis)
CEOI 2019 — Dynamic Diameter (hard) (nor)
RMI 2021 — Paths (hard) (cadmiumky)

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!

Read more »

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

By TheScrasse, 7 months ago, In English

1654A - Maximum Cake Tastiness

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Solution

Official solution: 150288088

1654B - Prefix Removals

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288210

1654C - Alice and the Cake

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 150288232

1654D - Potion Brewing Class

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Official solution: 150288255

1654E - Arithmetic Operations

Author: emorgan5289
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288285

1654F - Minimal String Xoration

Author: dario2994, emorgan5289
Preparation: dario2994, TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 150288326

1654G - Snowy Mountain

Author: emorgan5289
Preparation: dario2994, emorgan5289, 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

Read more »

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

By TheScrasse, history, 9 months 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)
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 - Карты).

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!

Read more »

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

By TheScrasse, history, 10 months 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 - Неравные соседи.

Read more »

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

By TheScrasse, history, 13 months 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?

Read more »

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

By TheScrasse, history, 15 months 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 - String Reversal (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 - Kill Anton (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!

Read more »

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

By TheScrasse, history, 16 months ago, In English

Hello everyone,
here is a very simple idea that can be useful for (cp) number theory problems, especially those concerning multiples, divisors, $$$\text{GCD}$$$ and $$$\text{LCM}$$$.

Prerequisites: basic knowledge of number theory (divisibility, $$$\text{GCD}$$$ and $$$\text{LCM}$$$ properties, prime sieve).

Idea

Let's start from a simple problem.

You are given $$$n$$$ pairs of positive integers $$$(a_i, b_i)$$$. Let $$$m$$$ be the maximum $$$a_i$$$. For each $$$k$$$, let $$$f(k)$$$ be the sum of the $$$b_i$$$ such that $$$k | a_i$$$. Output all pairs $$$(k, f(k))$$$ such that $$$f(k) > 0$$$.

An obvious preprocessing is to calculate, for each $$$k$$$, the sum of the $$$b_i$$$ such that $$$a_i = k$$$ (let's denote it as $$$g(k)$$$). Then, there are at least $$$3$$$ solutions to the problem.

Solution 1: $$$O(m\log m)$$$

For each $$$k$$$, $$$f(k) = \sum_{i=1}^{\lfloor m/k \rfloor} g(ik)$$$. The complexity is $$$O\left(m\left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m}\right)\right) = O(m\log m)$$$.

Solution 2: $$$O(n\sqrt m)$$$

There are at most $$$n$$$ nonzero values of $$$g(k)$$$. For each one of them, find the divisors of $$$k$$$ in $$$O(\sqrt k)$$$ and, for each divisor $$$i$$$, let $$$f(i) := f(i) + g(k)$$$.
If $$$m$$$ is large, you may need to use a map to store the values of $$$f(k)$$$ but, as there are $$$O(n\sqrt[3] m)$$$ nonzero values of $$$f(k)$$$, the updates have a complexity of $$$O(n\sqrt[3] m \log(nm)) < O(n\sqrt m)$$$.

Solution 3: $$$O(m + n\sqrt[3] m)$$$

Build a linear prime sieve in $$$[1, m]$$$. For each nonzero value of $$$g(k)$$$, find the prime factors of $$$k$$$ using the sieve, then generate the divisors using a recursive function that finds the Cartesian product of the prime factors. Then, calculate the values of $$$f(k)$$$ like in solution 2.

Depending on the values of $$$n$$$ and $$$m$$$, one of these solutions can be more efficient than the others.

Even if the provided problem seems very specific, the ideas required to solve that task can be generalized to solve a lot of other problems.

1154G - Минимально возможный LCM

Hint 1
Hint 2
Hint 3
Solution

agc038_c - LCMs

Hint 1
Hint 2
Hint 3
Solution

Implementation (C++)

abc191_f - GCD or MIN

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

Other problems

1493D - НОД массива (suggested by nor)
1436F - Сумма по подмножествам (nor)
Codechef — Chefsums (nor)

Conclusions

We've seen that this technique is very flexible. You can choose the complexity on the basis of the constraints, and $$$f(k)$$$ can be anything that can be updated fast.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems that can be solved with this technique.

I hope you enjoyed the blog!

Read more »

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

By TheScrasse, history, 20 months ago, In English

1485A - Add and Divide

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232596

1485B - Replace and Keep Sorted

Author: TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Official solution: 107232462

1485C - Floor and Mod

Authors: isaf27, TheScrasse
Preparation: Keewrem

Hint 1
Hint 2
Solution

Official solution: 107232416

1485D - Multiples and Power Differences

Author: TheScrasse
Preparation: MyK_00L

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232359

1485E - Move and Swap

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232216

1485F - Copy or Prefix Sum

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Solution

Official solution: 107232144

Read more »

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

By TheScrasse, history, 21 month(s) ago, In English

It's quite weird that $$$11$$$ submissions are still running from at least $$$20$$$ minutes, while hundreds of submissions (even with long execution times) are usually evaluated in a few seconds. It seems that the last tests run much more slowly than the other tests. Does anyone know why it happens?

Image

Read more »

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

By TheScrasse, history, 23 months ago, In English

As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).

1438A - Specific Tastes of Andre

Hint 1

1438B - Valerii Against Everyone

Hint 1

1438C - Engineer Artem

Hint 1

1438D - Powerful Ksenia

Hint 1

I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.

Also, please send a feedback if the hints are unclear or if they spoil the solution too much.

Read more »

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

By TheScrasse, history, 2 years ago, In English

Hi everyone,

many people are a bit disappointed because, for example, while the most difficult problems of Div. 3 contests are still interesting for Div. 2, Div. 3 contests are unrated for higher divisions. The same argument is valid for Div. 2 and Div. 4 contests.

An idea could be make contests rated for everyone, but that's not the best solution because, to reach a $$$\geq 1900$$$ rating, solving Div. 3 and Div. 4 problems very fast would be enough.

An improvement could be make contests partially rated for higher divisions, that is, the rating variation is multiplied by a $$$k$$$ factor ($$$0 \leq k \leq 1$$$) that depends on the target division of the contest and on the initial rating of the contestant (i. e. the relevance of that contest for that contestant). An example: there's a Div. 2 contest, then $$$k$$$ could be $$$1$$$ for a $$$1900$$$ rated contestant, $$$0.8$$$ for a $$$2100$$$ rated contestant, $$$0.5$$$ for a $$$2200$$$ rated contestant, etc.

Read more »

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

By TheScrasse, history, 3 years ago, In English

Hi everyone, I have just tried to solve the problem 161D.
If I use a matrix dp[50010][510], I get a tle verdict, even if the time complexity of the solution is $$$O(nk)$$$, $$$nk < 10^8$$$ and the constant factors are quite small. But if I use a matrix dp[510][50010] and I swap the indices, I get ac with a time of 498 ms (much less than the time limit).
Why does it happen?
Thanks

Submission with tle verdict: 73781168
Submission with ac verdict: 73781989

Read more »

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