Hello codeforces!

BrayanD, dmga44 and I are glad to invite you to Codeforces Round 768 (Div. 1) and Codeforces Round 768 (Div. 2) which will be held on Jan/27/2022 17:35 (Moscow time).

Each division will have 6 problems, and you will have 2 hours to solve them. The round will be rated for both divisions.

We would like to thank:

• Aleks5d for his excellent round coordination.

• albertolg101 and jmrh_1 for helping in the early stages of the contest.

• ashmelev, nweeks, 16204, amanbol, Ali.Kh, vaaven, marcOS, low_, Riladavin, TeaTime, MDario, aniervs, Dragonado, Saborit, 4qqqq and saarang for testing and providing useful feedback.

• MikeMirzayanov for the great platforms Codeforces and Polygon.

Score Distribution:

Div. 2: $$$500 - 1000 - 1500 - 2250 - 2250 - 3000$$$.

Div. 1: $$$500 - 1250 - 1250 - 2000 - 2500 - 3000$$$.

Good luck to all participants! Hope you enjoy the contest.

UPD1: Editorial

UPD2: Congratulations to the winners.

Div. 1:

1. Um_nik

2. kiwihadron

3. heno239

4. ksun48

5. Radewoosh

6. maroonrk

7. 244mhq

8. Vercingetorix

Congratulations to all of them for solving all problems!

Div. 2:

1. YuulBA

2. wcdr

3. Dalia12

4. hrgd

5. Pure__Vessel

Inspired by Tutorial Non-trivial DP Tricks and Techniques, by zscoder, This is actually a well known DP trick, and has appeared in some problems, but I have not found a detailed tutorial to easily understand it from scratch, me and some friends had troubles to learn this trick, so I will try to explain in a simple and detailed way.

What is dp with connected components:

The main idea of this trick is building permutations inserting the elements in increasing order, and storing as a state of the dynamic programming the number of chunks or components that represents some prefix of elements (i.e elements $$$1, 2, ... i$$$), and the transitions are about how inserting the next element ($$$i + 1$$$), will affect this chunks or components. (note that these are the values of the elements, not their position in the permutation)

This trick can be useful to count the number of permutations with some characteristics or constraints and to find permutations that maximize or minimize some functions.

The simplest problem that can be solved with this:

Given a number $$$n$$$, count the number of permutations of length $$$n$$$.

Yes, you read it well, we are going to compute $$$n!$$$ with a complicated dynamic programming in $$$O(n^2)$$$, isn't that amazing? (Do not be afraid, with this trick you will solve problems that can not be solved with basic combinatorics)

Basic Insights:

We will try to build all the permutations.

We will insert the numbers from $$$1$$$ to $$$n$$$ in increasing order, when we insert the number $$$i+1$$$, we will have some chunks or connected components of the permutation that will contain all numbers from $$$1$$$ to $$$i$$$, let's focus on this $$$i$$$-th stage:

For example if we are going to insert $$$4$$$, and we are counting the permutations of size $$$7$$$, we can have two components, like $$$(2)$$$ and $$$(3, 1)$$$, that means that the final permutation will look like $$$(2??31??)$$$ or $$$(?2?31??)$$$, that is, there will be some numbers between each component (greater than $$$i$$$, because all others are already placed), that will be placed in some later operation, the components will appear in order, and the adjacent numbers in the components will be adjacent in the final permutation.

In the final permutation there will be some numbers from $$$i$$$ to $$$n$$$ (maybe $$$0$$$), then the first component, then other numbers greater than $$$i$$$ (at least one, since otherwise the first and the second component would be only one bigger component), the second component, and so on, finally after the last component there may be some numbers greater than $$$i$$$. Note that the components should appear in order.

States:

Now, let $$$DP_{i, j}$$$ be the number of ordered sets of components formed by the numbers from $$$1$$$ to $$$i$$$, with $$$j$$$ components, for example if we are counting the permutations of size $$$7$$$ and we have two components, $$$(2)$$$ and $$$(3, 1)$$$, their ordered set is $$$( (2) , (3, 1) )$$$ and will be counted in $$$DP_{3, 2}$$$.

Here in an ordered set, the order of elements matters, not just their values, set $$$(a, b)$$$ $$$\neq$$$ set $$$(b, a)$$$, and set $$$(a, b)$$$ $$$\neq$$$ set $$$(a, c)$$$.

The final answer of the problem will be $$$DP_{n, 1}$$$, since that will store the number of single components of size $$$n$$$, that is, the number of permutations of size $$$n$$$.

Transitions:

Now, for the transitions think how inserting the $$$i+1$$$-th number will affect the set of components formed by numbers from $$$1$$$ to $$$i$$$:

• We can create a new component that will contain only number $$$i+1$$$, we can place this new components in any place between two already existing components, before the first one, or after the last one. This transition will be $$$DP_{i+1, j+1} += DP_{i, j} \cdot (j + 1)$$$ since we will end up with one new component, and we will have $$$j+1$$$ available places.

• We can add the number $$$(i+1)$$$ at the beginning or the end of any existing component, let's say, we have this set of components $$$( (1, 2), (4), (3, 5) )$$$, we can place the $$$6$$$ at the beginning or the end of any component, if we put at the beginning of the first one, we will end up with $$$( (6, 1, 2), (4), (3, 5) )$$$. This transition will be $$$DP_{i+1, j} += DP_{i, j} \cdot (2 \cdot j)$$$, since we will end up with the same number of components, and we will have $$$(2 \cdot j)$$$ available places for $$$i+1$$$.

• We can merge two components into a bigger one placing $$$i+1$$$ at the end of a component and at the beginning of the next one at the same time, let's say, we have this set of components $$$( (1, 2), (4), (3, 5) )$$$, we can merge the first and the second components with $$$6$$$, which will lead to $$$( (1, 2, 6, 4), (3, 5) )$$$. This transition will be $$$DP_{i+1, j-1} += DP_{i, j} \cdot (j - 1)$$$, since we will end up with one less component (we merged two into one), and we can merge any two consecutive components, so there are $$$(j - 1)$$$ choices.

Complexity

There are $$$O(n^2)$$$ states, and $$$O(1)$$$ transitions per state, each one can be done in $$$O(1)$$$ time complexity, also we can get rid of storing all states in memory only storing the current and the previous one, so the total time complexity is $$$O(n^2)$$$ and the memory usage is $$$O(n)$$$ or $$$O(n^2)$$$ depending on the implementation.

Proof of correctness:

First, we will prove that any permutation can be counted with this dp, and after that, that each one will be counted exactly once.

First, let's show by induction that the subset of the $$$i$$$ elements of smallest value (i.e. the elements $$$1, 2, 3, ..., i$$$ by value, not by position) of any permutation $$$p$$$ is always an ordered set of components, it will be obviously true at $$$i = 0$$$, since it's just the empty set. Now, for each $$$i$$$, we claim that we have the ordered set of the first $$$i-1$$$ elements, let's denote $$$j$$$ as the position of $$$i$$$ in the permutation:

• If $$$p_j < p_{j-1}$$$ and $$$p_j < p_{j+1}$$$ (remember that $$$p_j = i$$$), then we can add a new component with the element $$$(i)$$$ between the rightmost existing component before $$$j$$$, and the leftmost existing component after $$$j$$$.

• If $$$p_j > p_{j-1}$$$ and $$$p_j < p_{j+1}$$$, then we can add $$$i$$$ at the end of the component that ends at $$$j-1$$$.

• If $$$p_j < p_{j-1}$$$ and $$$p_j > p_{j+1}$$$, then we can add $$$i$$$ at the beginning of the component that starts at $$$j+1$$$.

• If $$$p_j > p_{j-1}$$$ and $$$p_j > p_{j+1}$$$, then we can merge the component that ends at $$$j-1$$$ with the one that starts at $$$j+1$$$ by placing $$$i$$$ between them.

So for any case we can obtain a new ordered set from the previous one by adding $$$i$$$.

This way we have proven that each subset that contains the smallest $$$i$$$ numbers of a permutation of size $$$n$$$ corresponds to a ordered set of components, and, since for a fixed permutation, in each stage we will only have exactly one option that can end up in that permutation after all stages are done, each permutation will be counted exactly once.

Code

Problems that can be solved with this trick:

Building the permutations in this way can be used to count the number of permutations with some properties, Now I will share some problems that can be solved with this trick, in relative increasing order of dificulty:

• Count the number of permutations of length $$$n$$$, that don't have three consecutive elements increasing or decreasing, that is, there is no $$$i$$$ $$$(1 \leq i \leq n-2)$$$ such that $$$p_i > p_{i+1}$$$ and $$$p_{i+1} > p_{i+2}$$$, or $$$p_i < p_{i+1}$$$ and $$$p_{i+1} < p_{i+2}$$$, starts with a number $$$s$$$ and ends with a number $$$e$$$. This problem is actually CEOI 2016 Kangaroo. You can see the solution explained here.

• B. Ant Man

• E. Phoenix and Computers , editorial doesn't mention that can be solved with this, but you can see a code with comments here.

• JOI 2016 Open Contest — Skyscrapers, Given $$$a_1, a_2, ..., a_n$$$ find the number of permutations of these numbers such that $$$|a_1 - a_2| + |a_2 - a_3| + ... + |a_{n - 1} - a_n| ≤ L$$$ where $$$L$$$ is a given integer. Constraints : $$$n ≤ 100, L ≤ 1000, a_i ≤ 1000$$$. You can see the solution explained here in "Connected Component" DP section.

• UTS Open '21 P7 — April Fools, editorial notes can be found here

I would be grateful if you discuss about the topic in comments, let me know if there is any mistake in the blog, or share other problems that can be solved with this trick.

UPD: Here I will list the problems shared by community members, Thanks to everyone who contributed, note that these problems are not sorted by any particular order:

• SWERC 2020 F

• CSES problem Abridged Statement: Count the number of permutations of length $$$n$$$, $$$(n \leq 30)$$$, such that the diference between each pair of adjacent elements is strictly greater than $$$1$$$.

• ARC 117 E: Zero-Sum Ranges 2

• Malaysian Computing Olympiad 2017 P5, Magical Teleporter

• Malaysian Computing Olympiad 2020 P4, Reading Novels

• TOKI Regular Open Contest #11 H

In this blog I will be talking about a problem that I consider instructive and interesting, because it has several solutions from which some tricks can be learned.

Prerrequisites:

• Tree basic theory
• Binary Search
• Euler Tour
• Lowest common ancestor
• Persistent Segment Tree.

Note that you don't need all of them for each approach.

Tricks or techniques that you can learn with the discussion of this problem:

• Some square root application in descomposition of search space of queries

• How to know in $$$O(1)$$$ if a node is an ancestor of some other node in a tree

• Parallel Binary Search

• The persistent segment tree can be builded over a tree

Story:

I created a version of this problem a while ago (which will be left as bonus challenge at the end of this blog), and I thought to put it in a contest that I am planning (Maybe not in the near future). But then dmga44 (thanks to him for discussing this problem with me, and provide feedback) noticed that it has a data structure painful and not very interesting(for a contest) solution that is the easier to come up with if you are good in data structures, but it has some quite interesting approaches, so I wanted to share it with the community.

The base problem:

You have a tree, and each edge has a weight, the weights of edges are all distinct, and form a permutation of size $$$n - 1$$$. You also have $$$Q$$$ queries of the form $$$(u, v, k)$$$, in the path from node $$$u$$$ to node $$$v$$$, if we add the edges of this path to a vector and sort it in increasing order, which one will be in the k-th position in the sorted vector. $$$1 \leq N, Q \leq 2*10^5$$$.

Maybe you want to think the problem a bit before keep reading.

First insights:

Let the spoilers begin:

We can do exactly what the statement says and get a $$$O(n^2\log{n})$$$ solution, but this solution can't be improved too much, so we need to try a different approach.

We can binary search over the possible results, and for asking if the answer is smaller or equal to some $$$x$$$ we can check if the number of edges in the path that are smaller than $$$x$$$ is greater or equal than $$$k$$$. We can consider all edges smaller or equal than $$$x$$$ as $$$1$$$, and greater as $$$0$$$, then we just need to check if the sum of the path is at most $$$k$$$. This can be done with dfs storing the sum from each node to the root and lowest common ancestor, this solution is also $$$O(n^2\log{n})$$$ but it can be improved to some faster solutions.

Square root approach:

Think about having the sums precomputed for some $$$p$$$, after this when we ask a query, we can easily check if the answer is greater or smaller than $$$p$$$, so we can select some integer $$$r$$$ and precompute the sums from each node to the root if all edges smaller or equal than $$$r$$$ have value $$$1$$$, and the greater ones have value $$$0$$$. Then we will do it for $$$2\cdot r$$$, $$$3\cdot r$$$, ... , $$$\frac{n}{r} \cdot r$$$ and keep the sums. After this when we answer a query we can reduce the space of search of the solution to $$$\frac{n}{r}$$$, finding the largest multiple of $$$r$$$ such that our answer is grater or equal than it.

When the space of search is $$$\frac{n}{r}$$$ we can loop over the edges that have values inside our space of search in increasing order of their values (there are just $$$\frac{n}{r}$$$ of this edges because the weights of the edges form a permutation), then add $$$1$$$ for each edge inside the path, and when we reach $$$k$$$ we are done, to ask in $$$O(1)$$$ if a node $$$a$$$ is ancestor of a node $$$b$$$, we can precompute the euler tour of the tree, doing a dfs and storing the first time that we see each node $$$a$$$ ($$$l_{a}$$$), and the last time that we see each node $$$a$$$ ($$$r_{a}$$$). Then we can say that a node $$$a$$$ is ancestor of $$$b$$$ if and only if $$$l_{a} < l_{b}$$$ and $$$r_{a} > r_{b}$$$. For asking if a node $$$x$$$ is on a path from $$$u$$$ to $$$v$$$ we can say that $$$x$$$ is on the path from $$$u$$$ to $$$v$$$ if $$$x$$$ is an ancestor of $$$u$$$ or $$$v$$$ and is not an ancestor of $$$lca(u, v)$$$, or $$$x$$$ is equal to $$$u$$$ or $$$v$$$.

With $$$q = O(n)$$$ and choosing $$$r = \sqrt{n}$$$ we can have a $$$O(n\sqrt{n})$$$ online solution which is not too hard to code.

Parallel binary search (with divide and conquer) approach:

Doing an individual binary search for each query is too slow, so we need to come up with some other idea, in this case we can think about answering some queries at once for reusing some data, we already know that to ask if a path has at least $$$k$$$ elements smaller or equal than $$$p$$$ we can assign a value of $$$1$$$ to each edge with weight smaller or equal to $$$p$$$ and 0 otherwise.

Initially, the space of search of each query is the segment $$$[1, n]$$$, after the first query it can become $$$[1,n/2]$$$ or $$$[n/2+1,n]$$$, and this will be for all querys, so we can have a function $$$solve(l, r, Q)$$$ where $$$l$$$ is the lower limit of the space of search, $$$r$$$ is the upper limit and $$$Q$$$ is a vector that contains all queries that currently have this range of search. We can select $$$mid = \frac{l + r}{2}$$$ and ask for each query in $$$Q$$$ if its result is greater or smaller than $$$mid$$$ fast, we will see how to do this later, if its result is smaller or equal, we will add it to other vector $$$Q_l$$$, otherwise we will add it to $$$Q_r$$$. After processing all this queries, we will call $$$solve(l, mid, Q_l)$$$ and $$$solve(mid + 1, r , Q_r)$$$ because now we know that all queries in $$$Q_l$$$ has a space of search of $$$[l, mid]$$$ and all queries in $$$Q_r$$$ have a space of search of $$$[mid+1, r]$$$. Thus we have reduced it's space of search by a factor of $$$2$$$.

Calling this function $$$solve(1, n, Q)$$$ where $$$Q$$$ contains all queries will solve our problem offline, since we need to know all the queries before calling our function, the basis case of this function is when $$$l = r$$$, in this case obviously the answer of all queries will be $$$l$$$. Otherwise we can reduce the space of search as wee see in the previous paragraph.

A tutorial about parallel binary seach(the trick we discussed above) can be found here

Now to answer the queries we need to implement some data structure that allows to change an edge's value from 0 to 1, and viceversa, and ask for the sum of edges' values on a path, the path can decomposed be in 3 paths from some nodes to the root(sum the path from $$$u$$$ to the root, sum the path from $$$v$$$ to the root, substract the path from $$$lca(u,v)$$$ to the root twice, and then adding the value of $$$lca(u, v)$$$), this can be done using the tree's euler tour, changing an edge's value can be seen as adding or substracting 1 to a contiguous subarray of the euler tour, and ask for the value of a node, is a query to some element, this can be done with a fenwick tree or a segment tree, achieving a total complexity of $$$O(n\log^2{n})$$$, since each query can be asked at most $$$O(\log{n})$$$ times(because we reduce it's space of search by a factor of $$$2$$$ each time), and we need $$$O(\log{n})$$$ to answer it each time.

PST approach

We are going to make a Persistent segment tree over the alphabet, that is, the i-th leaf of the segment tree will store the number of times that the number i is on the range, or path that this version of the segment tree consider, a node that represents the range $$$[l, r]$$$ will store the number of ocurrences of the numbers from $$$l$$$ to $$$r$$$, doing this, we can do an implicit binary search and answer the queries in $$$O(\log{n})$$$.

An explanation about solving the k-th element in a range of an array with PST can be found here at the section Finding the k -th smallest number in a range.

The first version of the segment tree will consider only the root, then each version will be created adding the the node to the father's version, this way a version will consider the path from the root to the node, then to answer the queries we can do an implicit binary search, adding the values from the versions of $$$u$$$ and $$$v$$$ and substracting the values from the version of $$$lca(u, v)$$$. This way we can solve the problem in $$$O(n\log{n})$$$.

Bonus problem:

You are given a tree, such that each edge can be traversed using two weights, $$$a_i$$$ and $$$b_i$$$, the weight of a path is the maximum weight of an edge on it, and $$$Q$$$ queries in the form $$$(u, v, p)$$$ you'll need to find the minimum possible weight of a path from $$$u$$$ to $$$v$$$ if you can traverse exactly $$$p$$$ edges with it's weight $$$a$$$ and the other edges of the path with it's weight $$$b$$$, it's guaranteed that $$$p$$$ is smaller or equal to the size of the path.

Can you solve it in $$$O(n\log^2{n})$$$?, and in $$$O(n\log{n})$$$?

This is a well known technique, but I couldn't find almost any detailed tutorial, so I'll try to help with this one.

Motivational Problem:

You have an array $$$A$$$ and $$$Q$$$ queries, which are, say if the subarray from $$$l$$$ to $$$r$$$, ($$$A[l]$$$, $$$A[l+1]$$$, $$$...$$$, $$$A[r]$$$) forms a permutation.

Some basic observations:

Only the set of elements matters, the order is irrelevant.

You want to know if each element is exactly once.

Solution:

Assign a random number $$$randval[i]$$$ to each number $$$i$$$, now we can say that if the XOR of the subarray ( $$$randval[A[l]]$$$ xor $$$randval[A[l+1]]$$$ xor $$$...$$$ xor $$$randval[A[r]]$$$ ) is equal to the xor of any permutation of size $$$r - l + 1$$$ (for example $$$1$$$, $$$2$$$, $$$3$$$, ... ,$$$r-l+1$$$, which hash is $$$randval[1]$$$ xor $$$randval[2]$$$ xor $$$...$$$ xor $$$randval[r-l+1]$$$ ) the subarray is a permutation.

Some Insights:

With the XOR we have some issues, we are counting if the number of occurrences of each element is even or odd, not the real number of occurrences, however in this problem if we had repeated elements the XOR-hash will never be the same than the XOR-hash of $$$1$$$, $$$2$$$, $$$3$$$, ... ,$$$r-l+1$$$, because if we have some numbers more than once, since there are only $$$r - l + 1$$$ numbers in the subarray, and also $$$r - l + 1$$$ numbers are needed to form the permutation, some of them cannot appear.

As an alternative to this technique we can use polynomial hash over a binary string that represents the occurrences of each element modulo $$$2$$$ ($$$x$$$-character of this string represents the number of occurrences of $$$x$$$ modulo $$$2$$$), but with XOR hash we can do it faster, with less code and case handling, and with less care about collisions and hacks.

With bitwise-OR we count the number of occurrences of each element of the set modulo $$$2$$$, if we use $$$k$$$-nary xor we will count the number of occurrences modulo $$$k$$$.

Collisions:

Now it's time to talk about collisions, as the numbers are random, the probability of collision in each query if we had only $$$1$$$ bit will be about $$$1/2$$$. And since XOR is independent on each bit, if we use k bits, the probability of collision in each query is $$$2^{-k}$$$. We can use 32-bit random integers or 64-bit random integers depending on the number of queries required. Since the numbers are generated randomly, I think this hashing can't be hacked, but I am not sure, if someone knows more about this, please send some feedback.

More problems using this technique (in no particular order of difficulty):

F. The Number of Subpermutations from Educational Codeforces Round 66 Here editorial doesn't use it, but I have one solution with this technique.

E. The Untended Antiquity from Codeforces Round #439 Div 2

G. Three Occurrences from Educational Codeforces Round 95

C. Square Subsets from Codeforces Round #448 Div 2 but if we had just 40 numbers up to 10^6.

Feel free to send any feedback.

Hello I been recently solved this problem and I found a greedy solution and I don't know why is ok. I hope that any of you could explain me why it works or show me that it should not Here is my code http://codeforces.net/contest/1132/submission/51950554