Author: NemanjaSo2005

**Hint 1**

Assume that cells $$$i-1$$$, $$$i$$$, and $$$i+1$$$ are covered in water. What happens if you remove water from cell $$$i$$$?

**Hint 2**

The water at position $$$i$$$ is replaced as both cells $$$i-1$$$ and $$$i+1$$$ have water in them.

**Solution**

Read the hints.

If there are 3 consecutive empty cells $$$i-1$$$, $$$i$$$, $$$i+1$$$, we can place water in cells $$$i-1$$$ and $$$i+1$$$ and then move water from cell $$$i$$$ to all other cells. If there are no such cells, we have to place water on every empty cell.

So if we find substring ''...'' in the array, the answer is $$$2$$$, otherwise the answer is the number of empty cells.

Time and memory complexities are $$$O(N)$$$.

**Bonus**

Solve the problem if it is required that each cell is filled with water, or next to at least $$$1$$$ cell that is filled with water.

Author: NemanjaSo2005

**Hint 1**

Check if only digits $$$1$$$ can remain. The situation is similar for checking if only digits $$$2$$$ or only digits $$$3$$$ can remain.

**Hint 2**

Try to find something that stays the same after each operation.

**Hint 3**

Look at the parity of the numbers.

**Hint 4**

The parity of each number changes after an operation. That means that if $$$2$$$ numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different.

**Solution**

Read the hints.

If the parity of $$$b$$$ and $$$c$$$ is not the same, then it is impossible for only digits $$$1$$$ to remain on the board, as it would require $$$b = c = 0$$$. Otherwise, the following construction will leave only digits $$$1$$$ on the board.

First remove digits $$$2$$$ and $$$3$$$ and write digit $$$1$$$ while $$$b>0$$$ and $$$c>0$$$. If $$$b=c$$$, then we are done. Otherwise, without loss of generality assume $$$b>c$$$. That means that after the operations $$$c=0$$$ and $$$b$$$ is even (Because $$$b$$$ and $$$c$$$ are the same parity). Now we perform the following $$$2$$$ operations $$$\frac{b}{2}$$$ times to get only digits $$$1$$$ left. Remove digits $$$1$$$ and $$$2$$$ and add digit $$$3$$$. After that remove digits $$$2$$$ and $$$3$$$ and add digit $$$1$$$. An effective change of these $$$2$$$ operations is the reduction of $$$b$$$ by $$$2$$$.

Time and memory complexities are $$$O(1)$$$.

**Bonus**

Come up with a problem that uses a similar idea and try to solve it. A lot of beginner problems use a similar idea.

Author: Riblji_Keksic

**Hint 1**

Solve the problem if all of the characters on vertices are 'U'.

**Hint 2**

We can run DFS from the root. Using it we can calculate the number of edges that we have to traverse to get to every edge. Just output the smallest value among all the leaves.

**Hint 3**

Modify the DFS such that it takes into account that traversing some edges does not require an operation.

**Hint 4**

Add weights to the edges.

**Solution**

Read the hints.

We will make edges from a vertex to its children. The weight of that edge will be $$$1$$$ unless one of the following holds:

The weight of an edge between a vertex and its left child will be $$$0$$$ if the letter written on that vertex is 'L'.

The weight of an edge between a vertex and its right child will be $$$0$$$ if the letter written on that vertex is 'R'.

Now we run a modified DFS to find the distance of each vertex from the root, but with weighted edges. We output the minimal value among all the leaves.

Time and memory complexities are $$$O(N)$$$.

**Bonus**

Solve the problem if after reaching a leaf, Keksic can teleport to any other leaf that he chooses and then needs to get back to the root, or report that it is impossible for him to complete such a travel.

Author:NemanjaSo2005

**Hint 1**

Let $$$m$$$ be the biggest value in the array. Calculate array $$$x$$$ such that $$$x_i$$$ ($$$1 \le i \le m$$$) is the number of triples which have $$$\gcd$$$ of $$$i$$$. Then the answer is the sum of $$$i \cdot x_i$$$ over all $$$i$$$ ($$$1 \le i \le m$$$).

**Hint 2**

Value of $$$\lfloor \frac{m}{1} \rfloor + \lfloor \frac{m}{2} \rfloor + \lfloor \frac{m}{3} \rfloor + \ldots + \lfloor \frac{m}{m} \rfloor$$$ is around $$$m log m$$$.

**Solution part 1**

We calculate $$$x_i$$$ from $$$x_m$$$ to $$$x_1$$$. For some $$$i$$$, we can first calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$, and then from it subtract $$$x_{2i}, x_{3i}, x_{4i} \ldots$$$. Because of the previous hint, the subtractions will be quite fast.

Now the question is how to calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$.

**Hint 3**

Numbers up to $$$100\,000$$$ can have at most $$$128$$$ divisors.

**The rest of the solution**

As the order in which numbers are given does not matter, we can sort the array. Now for each number $$$d$$$ ($$$1 \le d \le M$$$) store indices of all numbers that are divisible by $$$d$$$ in an array of vectors. Now we will for each number $$$d$$$ ($$$1 \le d \le m$$$) count the number of triples.

To find the number of triples that have a gcd value that is an integer multiple of $$$d$$$, we can do the following. We go over the index of the number that will be value $$$b$$$ in the function. We can utilize the vectors we calculated in the previous step for that. Say that the current index is $$$i$$$. Then for value $$$c$$$ we can pick any number with an index larger than $$$i$$$ as the array is sorted. For value $$$a$$$, we can pick any of the numbers divisible by $$$d$$$ with an index less than $$$i$$$, the number of which we can get from the vector. By multiplying those $$$2$$$ numbers we get the number of triples that have $$$a_i$$$ as their middle value.

As numbers can have up to $$$128$$$ divisors, the step above is quite fast.

Total time complexity is $$$O(m log m + n log n + 128 \cdot n)$$$. Total memory complexity is $$$O(m + 128 \cdot n)$$$.

**Bonus**

Solve the problem if $$$f(a,b,c) = \gcd (a,c)$$$.

Author:NemanjaSo2005

**Hint 1**

Try to simplify graph $$$H$$$.

**Hint 2**

Look at strongly connected components of $$$G$$$, and what happens with them.

**Hint 3**

Use dp to find the answer.

**Solution**

The main observation is what $$$H$$$ looks like. All the strongly connected components (SCC) in $$$G$$$ will become fully connected subgraphs in $$$H$$$. Secondly, take any two vertices $$$a$$$ and $$$b$$$ such that $$$a$$$ and $$$b$$$ are not in the same SCC. We can let $$$S_a$$$ be a set of vertices that are in the same SCC as $$$a$$$ ($$$a$$$ included). Similarly, $$$S_b$$$ is a set of vertices that are in the same SCC as $$$b$$$. If there is an edge going from $$$a$$$ to $$$b$$$, then for any two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ belongs to $$$S_a$$$ and $$$y$$$ belongs to $$$S_b$$$, there is an edge going from $$$x$$$ to $$$y$$$. Both of the previously stated facts about the graph can be proven by induction.

Now, let's say that there is the longest path that goes through at least one vertex of an SCC. Then that path goes through all the vertices in the SCC, due to all vertices in SCC being connected to the same vertices outside the SCC and due to the fact that SCC is a complete subgraph.

Now we can construct the graph $$$H'$$$. Each of the SCCs from $$$H$$$ will be a vertex in $$$H'$$$. The number on the vertex will be equal to the sum of all numbers on the vertices of the SCC that it was constructed from. Edges between two new vertexes will be added if there is an edge between their original SCCs. The edge will have a weight equal to the size of the SCC that it is going into. An additional vertex will be added at index $$$0$$$ and an edge will be made between it and all other vertices with $$$0$$$ ingoing edges. Weight will be determined based on the size of the SCC of the vertex that the edge is going into.

Due to the previous observations, the answer for the $$$H'$$$ will be the same as the answer for the $$$H$$$. However, notice that $$$H'$$$ is a DAG. That means that the answer for it can be computed using DP after topological ordering.

Total time and memory complexity is $$$O(n)$$$.

**Bonus**

We will define the value of the path as the biggest value of a vertex on the path. Among the values of all the longest paths, find the median one. It is guaranteed that there are at most $$$10^{18}$$$ longest paths starting from each node. (So basically, you can ignore overflow in the number of paths) The rest of the constraints are the same.

Author: NemanjaSo2005

**Hint 1**

Solve the problem for $$$q=1$$$.

**Hint 2**

We can just simulate the process. Each operation removes at least half of the elements, meaning that we will perform at most $$$log n$$$ operations.

**Hint 3**

Solve the problem if each $$$l_i = 1$$$. So basically, solve the problem for each prefix.

**Hint 4**

Keep values that are in the array after $$$1$$$, $$$2$$$, $$$3$$$, $$$\cdots$$$, $$$log n$$$ operations. Let's call those array's layers. Layer $$$0$$$ is an array after $$$0$$$ operations, layer $$$1$$$ after $$$1$$$ operation, and so on. When we add a value to the end of the layer, only $$$1$$$ number that was previously local extreme (local minimum or maximum, depending on layer) might unbecome local extreme if the new value becomes local extreme. So we can just propagate this update to all layers.

**Hint 5**

Try to simulate the process of updating described in hint $$$4$$$. Also, notice that if the array is longer than $$$3$$$, we can handle prefix and suffix updates separately.

**Solution**

Read the hints.

Now we will precompute and store the array after each operation on the entire permutation. We will call those array layers.

We can now solve queries in $$$O(log n)$$$.

If a query involves a small number of elements, we can just brute force it. Otherwise, we do the following:

Now let's define our queries a bit differently. We are given some array $$$x$$$, which will be a subarray of some layer, and $$$2$$$ values, $$$a$$$ and $$$b$$$. We will get array $$$y$$$ by appending $$$a$$$ to the start of $$$x$$$ and appending $$$b$$$ to the end of $$$x$$$. We are interested in the value of $$$f$$$($$$y$$$). It is easy to see that all queries involving $$$3$$$ or more elements can be converted into the modified query.

If $$$|y|$$$ is small, we can just brute force it. Otherwise, we can transform it into a query on the next layer in constant time, or in $$$O(log n)$$$.

Now, the first thing to notice is that all elements in $$$x$$$ that are neither first nor last will be deleted only if they were deleted when we performed operations on the whole permutation. That means that they will represent some interval on the next layer, let's call it $$$z$$$. (That interval can be found either with binary search or in $$$O(1)$$$ with precomputation) It holds that $$$ |z| $$$ is around half of $$$|x|$$$. Now, notice that among $$$a$$$ and the first element of $$$x$$$, there has to be at least one deletion. The same goes for the last element of $$$x$$$ and $$$b$$$.

So now we have transformed the query onto the next level in $$$O(1)$$$, or $$$O(log n)$$$. As we will do at most $$$O(log n)$$$ such transformations, the complexity of a single query is either $$$O(log n)$$$ or $$$O(log^2 n)$$$ depending on the way we find the next interval, both of which should be fast enough to pass.

Total time complexity: $$$O(n + q log n)$$$ or $$$O(n + q log^2 n)$$$. Total memory complexity: $$$O(n+q)$$$

**Bonus**

Imagine that you already decided for each layer which indices will be on it. Come up with a generator that will uniformly randomly pick one permutation that satisfies those conditions.

Problem B could be solved with XOR's as well. Here's a somewhat related problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=1232

can you please provide me the solution method you are discussing about!!

2xor3=1; 1xor3=2; 1xor2=3; easy simulation

I solved B using DP 234444052

Hats off to you to waste your time hhhh

I couldn't find the easier solution and I immediately noticed DP :skull:

Nice problems, I liked the contest. I had a different solution (which generalises to harder versions easily) for D though.

solutionWe will be using the following fact:

For any positive integer $$$n$$$ we have

First of all note that we can sort the array and work with the sorted version with the same summation. In this case, we need to compute the following expression:

Now the main idea is to use the previous summation on the gcd expression.

This means we need to evaluate the sum

Swapping the summation and seeing everything in terms of $d$, for a fixed $$$d$$$ and two $$$i< j$$$ such that $$$d \mid a_i, a_j$$$ we need to add a contribution of $$$\varphi(d) \cdot (n-j)$$$. Here the $$$n-j$$$ is irrelevant, and it could have been any function of $$$j$$$ or $$$a_j$$$ for that matter. (for example if it was $$$j+a_j$$$ the described solution still works)

Now we are going to use the crucial fact that numbers $$$\leq 10^5$$$ have at most $$$128$$$ divisors. This allows us to update the answer as we keep adding new $$$a_i$$$. For each number $$$1 \leq d \leq 10^5$$$ we store how many multiples of it we have seen so far. Then, when processing a new element $$$a_i$$$ we look through all its divisors $$$d$$$, add a value of

and increment the corresponding count for said divisor.

It's easy to keep track of all of this data, (we can also precompute $\varphi$ easily) and since $$$128$$$ is small enough to fit in the constraints, this gets the AC.

EDIT: Note that the bonus can be solved in essentially the same way as above. The multiplier expression with $$$\gcd(a_i, a_j)$$$ is denoted by some $$$j-i-c$$$ for some $$$c = 0, 1$$$ (too lazy to calculate which). If we split up the $$$i, j$$$ parts we can solve the problem on the original array and reverse array and simply combine the results to obtain the final answer.

Typo: you are writing a solution for problem D.

Great solution though :)

Nice solution (for D though)! Thank you!

Oh yes @boboge, @Megalovania sorry about that, I was only using 2 brain cells last night. lol

Wow hey your solution was the same as mine, I stored $$$\varPhi(d) * counts\ of\ multiples\ of\ d$$$ instead of counts only tho. Nice solution anyways!!!

Can you pleaseplease explain me what does phi (N) means ?It is Euler's totient function. $$$\varphi(N)$$$ returns the number of positive integers $$$n\le N$$$ such that $$$n$$$ and $$$N$$$ are coprime, ie, have $$$\gcd(n,\,N)=1$$$.

Can you please explain how does that helps here ?Well @NovusStellachan's explaination of the use of Euler's totient function is quite clear, can you explicitly state what you don't get about it?

I am not able to understand how phi is helping us to calculate the answerIf we sort the array then for each i, the answer get increased by an amount of:

Calculating gcd for every pair (i,j) would result in a complexity of $$$O(n^2)$$$ so we need to efficiently calculate them

Since

Therefore

Plug that into the fist expression and we got

What does this mean? It means that we can iterate through all divisors $d$ of $$$a_i$$$, count how many multiples of d which have appeared, then add $$$count * \varPhi(d)$$$ to the sum of gcd, afterwards add $$$(n - i) * gcdsum$$$ to the answer.

$$$\Phi$$$ can be precomputed and the simplest way of iterating through divisors of n have $$$O(\sqrt{n})$$$ complexity. We therefore achieve an overall complexity of $$$O(n\sqrt{MAX})$$$ in worst case scenarios which is enough to AC.

Thanks for the explaination sirHow do you type the math symbols so easily? Is it something built-in on CF or can I just do that everywhere with a specific keyboard settings? If so, how?

CF comments and posts have built-in Latex :D

This is great. With your generalization, i could understand D more. (You should write D's solution

laughs)thanks for the tutorial with hints problem E was one of the best problems i have seen live in a contest

Great editorial ! It is always appreciated to have hint based editorials.

Btw I might have been a bit rash in my feedback. Considering the amount of solves by div2 contestants, E made the job a div2 E should do (also, the bonus task looks super cool!!). Also, after thinking a bit more about it, I think it's not that bad to have a div2 C which isn't adhoc as it gives all contestants the opportunity to solve "algorithmic" problems and not "1-observation" problems. I'm interested in others advice

As a lower rated contestant, I definitely prefer more algorithmic problems. This problem reminds me of https://mirror.codeforces.com/problemset/problem/1843/D.

really enjoyed the round, THANKS. Looking forward to more from you!!

I'm facing a problem with solving problems with number theory tags and focused on GCD, can I have a resource to learn from so I can pass this kind of problems faster please?

Not really a resource but all you really need is prime decomposition of a number, the gcd trick used in D, the fact that numbers usually have up to O(m^1/3) divisors, the number of prime divisors is logarithmic, seeve, √N factoring. You can learn those by either looking it up, or solving number theory on codeforces/other platform.

bruh why is D so tough. Can someone simplify please..

We assumed that trick with subtracting higher multiples was quite well known. Also, predicted raiting for D is 1900, which is not that much for a D.

I never encountered it before but it was nice to find :)

I want to learn more about this. Is there a name for this trick or some resource you can share for it. Thanks for the help in advance

I think it will be 2000

This looks interesting. Where can I find information about this trick?

Check problem D over here — https://mirror.codeforces.com/blog/entry/121618

I had a slightly different solution for D. I iterated over i from 1 to maxi in order to compute x[i] (which is defined in the editorial). To compute each individual x[i], I had a list of indices of numbers in the sorted array divisible by i and I started from the third element in this list all the way to the last element. Something interesting is that if you pick some value for C with an index in the interval (x, y] in the sorted array where x and y are the indices of 2 multiples of i with no multiples of i between them with an index in that interval, then the number of possible choices for a and b such that both are divisible by i will always be the same. So you can iterate through the list of indices of multiples of i and get the #of ways to pick A and B and multiply this by the length of the current interval that tells us the #of ways to pick C. A nice implementation trick is to add the index n-1 to the end of every list of indices of multiples in order to catch all possible values of C for all x[i]. Once you've computed that, the rest of my solution is the same.

234519989

Can someone help me understand the solution to Problem D? I have been trying to understand the solution for a bit but I just can't understand it at all. Can someone give a simpler explanation because my brain just can't understand the solution for whatever reason?

Can provide a simple solution.

I am not a native English speaker and I use translation software. If you have any translation questions, please feel free to reply to me :)

The first step, as in the solution, is to find all divisors of all numbers in the range in $$$mlogm$$$ time, which can be preprocessed and stored through $$$10^5$$$ vectors. Note that this step precedes multiple rounds of testing. The second step is to sort the input array and enumerate $$$a_i$$$ from small to large as $$$b$$$, then $$$c$$$ can be selected arbitrarily after $$$b$$$, so the original problem can be converted into $$$\sum_{i=1 }^n\left((n-i)\sum_{j=1}^{i-1}\gcd(a_j,a_i)\right)$$$. That is, we now need to quickly find $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$ for each $$$i$$$.

The third step is to find that when $$$a_i$$$ is fixed, the result of $$$\gcd(a_j,a_i)$$$ must be a divisor of $$$a_i$$$. So enumerate all the factors $$$d$$$ of $$$a_i$$$ from large to small, try to check how many $$$a_j$$$ are multiples of $$$d$$$, and $$$d=\gcd(a_j,a_i)$$$, multiply this number by $$$ d$$$ , then add it to the answer.

More specifically, we have an array $$$cnt$$$ in the range. $$$cnt_d$$$ represents how many numbers in $$$a_1$$$ to $$$a_{i-1}$$$ are multiples of $$$d$$$. Since it has been sorted, this Arrays can be maintained simply by enumerating factors during previous traversals.

The following work will be better understood through an example. Consider the following sequence $$$2\ 3\ 6\ 7$$$. At this time, $$$i=3$$$, then $$$cnt_1=2$$$ (including $$$2$$$ and $$$3$$$), $$$cnt_2=1$$$ (including $$$2$$$) have been maintained. $$$cnt_3=1$$$ (including $$$3$$$). We enumerate the factors $$$d$$$ of $$$6$$$ from largest to smallest:

When $$$d=6$$$, $$$cnt_6=0$$$, we do nothing.

When $$$d=3$$$, $$$cnt_3=1$$$, which means that among the previous numbers, there is a number that is a multiple of $$$3$$$. Although we do not know who it is (in fact, it is $$$3$$$), because we Enumerate $$$d$$$ from large to small. At this time, $$$d=3$$$ must be the $$$\gcd$$$ of that number (in fact, it is $$$3$$$) and $$$a_i$$$ (although this is not actually completely correct, we will ensure the correctness of this soon) , we do $$$ans+=d*cnt_d$$$. And because the numbers in $$$cnt_d$$$ must also be in $$$cnt$$$ of all factors of $$$d$$$, and we only want these numbers to be counted in $$$d$$$, so we need to traverse all the factors of $$$d$$$ $$$d ^{'}$$$, do $$$cnt_{d^{'}}-=cnt_d$$$, thus ensuring correctness. In this example, we did $$$ans+=3\times1$$$, then traversed $$$1$$$ and $$$3$$$, and did $$$cnt_1-=cnt_3$$$ and $$$cnt_3-=cnt_3$$$, thus successfully converting the calculated $$$3 $$$ is removed from $$$cnt_1$$$ and $$$cnt_3$$$.

When $$$d=2$$$, $$$cnt_2=1$$$, we do $$$ans+=1\times2$$$, $$$cnt_1-=cnt_2$$$ and $$$cnt_2-=cnt_2$$$.

When $$$d=1$$$, we will find that $$$cnt_1$$$ has been reduced from $$$2$$$ at the beginning to $$$0$$$, so we do nothing

Finally, we undo all modifications made during this process, i.e. restore $$$cnt$$$ to $$$cnt_1=2$$$, $$$cnt_2=1$$$, $$$cnt_3=1$$$. This can be achieved by creating a $$$\log$$$ sized backup of $$$cnt$$$ before calculating

Note that the number of divisors of a number in the int range does not exceed $$$1600$$$ at most, and the amortized number should be $$$\log$$$ level, so the complexity is not a problem

Why does cnt[1] also need statistics? From back to front, why do we need to subtract the factor of d? What will be the impact if we don’t subtract it? Do you have any examples?

For your first question, $$$cnt_1$$$ certainly needs to be counted. Because there is a case $$$\gcd(a_j,a_i)=1$$$, they need to be added to the answer. I'm confused by this question and I'm not sure I fully understand your first question.

For your second question, I can provide further explanation.

Still based on the premise that $$$a$$$ has been sorted.

For example, the current situation is $$$i=9$$$, $$$a_9=18$$$, and its factors are $$${18,9,6,3,2,1}$$$.

Suppose we had $$$a_7=12$$$ before, and its factors are $$${12,6,4,3,2,1}$$$.

Obviously, $$$\gcd(a_7,a_9)=6$$$, this $$$6$$$ should be part of $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$ when $$$i=9$$$.

So now we want $$$\gcd(a_7,a_9)$$$ to be evaluated, and only once, when enumerating up to a factor $$$6$$$ of $$$a_9$$$.

By the way, we need to make it clear that $$$a_i$$$ is added to $$$cnt$$$ after calculating $$$\sum_{j=1}^{i-1}\gcd(a_j,a_i)$$$. This is very important.

According to the definition of $$$cnt_d$$$, $$$cnt_6$$$ definitely includes $$$a_7$$$, but does not include $$$a_9$$$. When I traverse the factors of $$$a_9$$$ from large to small, $$$a_7$$$ will enumerate to $$$cnt_6$$$ is considered and calculated correctly, but if we do nothing, $$$a_7$$$ will be calculated again at $$$cnt_3$$$, $$$cnt_2$$$ and $$$cnt_1$$$. That is, if we do nothing, $$$a_j$$$ and $$$a_i$$$ will be evaluated at all divisors of $$$\gcd(a_j,a_i)$$$, which is obviously wrong.

Sorry for still using translation software. Translating from Chinese to English is too easy to cause ambiguity. If you have any questions, please continue to ask :)

The purpose of enumerating the divisors from large to small is to traverse to the "largest" common divisor.

There seems to be something wrong with the translation of this sentence, if you are confused about it just ignore it :(

As for the first question I raised, I misread it, and I would like to apologize to you. For the second question: For example, test sample 1 5 2 3 6 12 17

When gcd is a multiple of 1: there are 10 situations When gcd is a multiple of 2: there are 4 situations When gcd is a multiple of 3: there are 4 situations When gcd is a multiple of 6: there is 1 situation

Here I use the array f[m] to represent the number of cases when gcd is a multiple of m

When we count from back to front: First calculate gcd which is a multiple of 6, ans+=i*f[i], ans+=6*1 ans=6 Next, it is calculated that gcd is a multiple of 3, but at this time multiples of 3 include 6, so ans += i*f[i] cannot be used directly. Need f[3]-=f[6] in front and then calculate ans+= i*f[i] again.

Is my understanding correct?

The effect of the translation software is not good. I can't guarantee that I understand what you said, but based on your final description, I think your basic counting idea is correct. Do you have instant software contact information? For example discord? If you still have questions, you can add me on discord "cap1tal_lol". Faster communication may reduce misunderstandings caused by translation software. If adding social software friends in this way is offensive to you, or is not allowed by codeforces, please forgive me and ignore what I said. If you have any questions about passing, you can continue to contact me :)

i got the way you intended to do this problem , really amazing to be honest. for any further query i would like to communicate using discord but problem is we do not have discord servers in common so can you share one server link where i can join so that we can communicate from there ? -Cap1taL-

https://discord.gg/HB9SdETT

Thanks, -Cap1taL-! You helped me finally solve this problem.

Here is a clarification on the part that I was missing.

To calculate $$$∑^{i−1}_{j=1}gcd(a_j,a_i)$$$ for a specific $$$i$$$, we should do the following:

Most definitions in this code are preserved from the original explanation by -Cap1taL-.

`dd`

is the same as $$$d'$$$.`already_accounted[d]`

indicates the number of values in $$$a$$$ for which`d`

is a divisor but not the greatest divisor (not GCD).Additionally, let's analyze the time complexity. Let's find out how many operations this cycle will do in the worst case:

The result is $$$2835$$$ operations if $$$a[i]=90720$$$. So, in the worst case, our program will perform $$$(8 \cdot 10^4) \cdot 2835 = 2 \cdot 10^8$$$ operations, which is feasible as long as you don't allocate memory in the loops.

I understand the rest of the solution from the tutorial, but I do not understand how to do this "The first step, as in the solution, is to find all divisors of all numbers in the range in mlogm time". I am just a beginner. What I can think of is that we use seive to find all prime factors for each number, but I do not understand how to go from here to finding all factors.

that cost $$$n\ln n$$$

Problem B, I try to test 1 1 11 in everybody AC code and all code print 1 1 1, that a wrong answer.

for 1:

1 1 11

0 2 10 // turn 1 and 3 into 2

2 0 8 // use 2 twos and 2 threes to make 2 ones

0 2 6 // use 2 ones and 2 threes to make 2 twos

2 0 4 // etc.

0 2 2

2 0 0 // two ones

1 is possible

for 2:

1 1 11

2 0 10

0 2 8

2 0 6

0 2 4

2 0 2

1 1 1

0 2 0 // 2 twos

2 is possible

for 3:

1 1 11

2 0 10

0 2 8

2 0 6

0 2 4

2 0 2

1 1 1

0 0 2 // two threes

3 is possible

therefore 1 1 1 is a correct answer

Yes sirr

In problem C, I was able to identify the need for DFS. I wrote my code in both Python and C++. Tried both. But got TLE on pretest 2 in Python and TLE on pretest 5 in C++.

Python — https://mirror.codeforces.com/contest/1900/submission/234466578

C++ — https://mirror.codeforces.com/contest/1900/submission/234467214

Any kind of help is greatly appreciated.

You used reference for the vector but you should also use it for the string. Your solution is quite nice! I think you are unlucky accepted submission

Thanks for mentioning,i was not able to understand why i got tle on pretest 5.

Spoiler(string should also be passed by reference) ...

Really!!? I didn't get AC for a singular "&" sign??

Yes, because the string was been copied every time the function was called. It leads to an

`O(n^2)`

time complexity.I got TLE on 6th pretest with Python. If someone can see the problem, please tell me:

https://mirror.codeforces.com/contest/1900/submission/234478784

Same with me, though when I tried solving it after the contest using C++, with similar logic and passing everything by reference/ making everything global. It passed.

Hey I just checked your submissions and looks like you solved it using Python! Can you explain it to me what was the issue that you were facing before. I wrote a recursive dfs (without any memoization) and got TLE in pretest 6, maybe writing it some other way might have helped.

SpoilerI have examined other's solutions and wrote bfs based on their solutions. I didn't figure out the reason of failure of my own dfs solution :(

Hey, I got the solution to this. There is a workaround to deep recursion functions in Python. It's a method generated by pajenegod. You can find a discussion about bootstrap here https://mirror.codeforces.com/blog/entry/91490 . It is a really useful script.

Thank you for letting me know. I saved it for the future. Now we know why

Problem C.Anji's Binary Tree Solution Link : HERE

Anyone solved D using Mobius inversion?

Yes Submission

Can you please explain your approach too?

Sorting the array gives the same value of the required sum

The required sum $$$S$$$ is therefore

Applying the procedure described in this blog:

Applying mobius inversion:

Let

Which can be calculated "on the fly", by factorizing each

`arr[i]`

and updating`magic[f]`

where`f`

is a factor of`arr[i]`

.Thus the required sum is

Calculating

`magic[x]`

by factoring in`O(n * MAX_FACTORS)`

: SubmissionCalculating

`magic[x]`

without factoring in`O(M log M)`

: Submissioninfinite water source ftw

Ikr? Minecraft players had an advantage in the problem!

D could solved in O(MlogM) without factorizing. Just do the normal trick of counting gcd pairs and count in the contribution of c.

could you please explain?

I will first explain the normal method to count gcd pairs. Typical problem is, given an array $$$a$$$ of length $$$N$$$ with value range $$$[1,M]$$$. Count the sum of $$$gcd$$$ of each pair of elements, formally $$$\sum_{i=1}^N\sum_{j=i+1}^Ngcd(a_i,a_j)$$$.

Instead of iterating each pair of elements, we calculate the contribution from $$$1$$$ to $$$M$$$ as $$$gcd$$$ of a pair of elements. Define two functions:

$$$g(i) = $$$ the count of pairs that $$$gcd$$$ is $$$i$$$.

$$$h(i) = $$$ the count of pairs that $$$gcd$$$ could be divided by $$$i$$$.

Suppose number of elements that could be divided by $$$i$$$ is $$$cnt_i$$$, then $$$h(i)=cnt_i*(cnt_i-1)/2$$$. By inclusion-exclusion principle, $$$g(i)=h(i)-\sum_{j>i\ and\ i|j}g(j)$$$.

Iterate from $$$M$$$ to $$$1$$$, calculate $$$cnt$$$ and $$$h(i)$$$ with the harmonic trick.

Now come back to the original problem.

We need to calculate the contribution of each $$$i$$$ where $$$f(a,b,c)=i$$$. WLOG, suppose $$$a\le b\le c$$$. Suppose we are iterating all multiples of $$$i$$$ and reach $$$j$$$. We fix $$$j$$$ as $$$b$$$. All numbers smaller than or equal to $$$j$$$ and is a multiple of $$$i$$$ could be a choice of $$$a$$$. All numbers greater than or equal to $$$j$$$ is a choice of $$$c$$$. Notice here $$$c$$$ is not required to be a multiple of $$$i$$$. Then we have four cases: $$$a<b<c$$$, $$$a=b<c$$$, $$$a<b=c$$$, $$$a=b=c$$$.

By calculating the count of $$$a$$$, and precalculating the count of numbers greater than each $$$b$$$, each case could be calcualted in $$$O(1)$$$. Then by a similar inclusive-exclusive calculation, the whole problem could be solved in $$$O(MlogM)$$$.

Here is my code. https://mirror.codeforces.com/contest/1900/submission/234450747

Thank you very much. This was really awesome and helpful.

Great explanation! Seems like gcd convolution is just a generalization of this, but even knowing how to do gcd convolution, I was not able to solve the initial problem, so your commentary has really helped a lot :)

ABC was too easy this contest.

and my rating dropped for not solving more than one question in the contest

Problem B. If all numbers are odd or all are even. Then [1,1,1] since you can make any of them after some operations. Else pick the index of the number which has the unique parity. [1,2,1] pick two, [2,1,2] pick one. [1,2,3] pick two.

Operatio on [1,2,3]

[1,2,2,3,3,3] -> [&1&,2,2,&3&,3,3] -> [2,2,3,3,2] -> [2,2,&3&,&3&,2] -> [2,2,2,2].

Magic as described by the author.

234542604

Hi , can smb tell me whats wrong with dfs that returns the answer in task C , because I have TLE in pretest 5.

## include <bits/stdc++.h>

using namespace std;

## define endl '\n'

int dfs(int x, int kount,string s, vector<pair<int,int>> v){ if(v[x].first==0 && v[x].second==0) return kount; int ans=1000000000; if(v[x].first!=0){ if(s[x-1]=='L') ans=min(ans,dfs(v[x].first,kount,s,v)); else ans=min(ans,dfs(v[x].first,kount+1,s,v));

}

void solve(){ int n; cin>>n; string s; cin>>s; vector<pair<int,int>> v(n+1); for(int i=1; i<=n; i++) cin>>v[i].first>>v[i].second; cout<<dfs(1,0,s,v)<<endl;; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--){ solve(); } return 0; }

P.S it works O(n) and n from the text is <=3*10^5 , I can't understand why it's TL

it might be because the vector and string are not passed by reference, causing the program to make a copy of both of them, causing the time complexity to be O(n^2) instead of O(n).

can some one please tell why it is giving TLE on test case 5 and please correct it.

https://mirror.codeforces.com/contest/1900/submission/234547330

Problem D can be solved by

mobius inversion formula.Which can be solved in $$$O(n\log n + n \sqrt{m} + m\log m)$$$. Code: 234463754

Note that we need to solve

Use the equation

We have

Pretreatment

Euler functionso that we can solve the equation in time complexity $$$\mathcal{O}(n\sqrt{n})$$$234478574

Why do you need sqrt in complexity?

Assume that $$$n$$$ equals to the range of $$$a_i$$$, we need to find out all the factors of $$$a_i$$$, check my code in the following link and you will get it ;)

Yeah, I just meant you can precalculate divisors for each i (note that it's O(n log n) both time and memory complexity), then you can go through all divisors of a number (which are up to 128 for a numbers <= 10^5).

ur right :D

Thanks for the fast editorial !

Are the "Bonus problems" somewhere for us to submit them??

No, you can only mind solve them.

.

Hey! guys, I'm new to competitive programming. I tried to implement anji's tree solution but I got a TLE, but when I passed the string by reference to the dfs function it worked Could someone explain to me how passing an argument by reference influence the run time. This is my code: https://mirror.codeforces.com/contest/1900/submission/234732141

Problems C and E are just... weird... Nothing really to solve, just implement standard algorithms.

Can anyone explain why this approach doesnt work for Problem D?

So i was iterating over

`A`

, and at index`i`

i'm considering that to be middle value of triplet that is`b`

. So as per question i need to find value of`a`

and`c`

now. I initialized`currentIndexAns = 0`

for this loop. Since`a`

index has to be less than index of middle that is`i`

for current loop. In an inner loop of`i`

, i'm iterating`A`

again. In this case if my inner loop index that is`j`

.`(j<i)`

, then i will check if`a[j]<=a[i]`

, where`i`

index is my assumed middle value, i will calculate its`gcd(a[j], a[i])`

. And add it to`currentIndexAns`

answer. After this i will have sum of all possible gcd values which can have`i`

index as middle. Then i will multiply this`currentIndexAns`

with count of indexes that is above`i`

, so,`j>i`

and`a[j]>=a[i]`

. Let's call this count as`countMaxLeftMiddle`

. Then i will multiply this, with`currentIndexAns * countMaxLeftMiddle`

. To get contributions of triplets which have`i`

as middle index.Here is my code:

when you dont try E, because of stucking in d :(((

Seems easy for me the E one. (I solved it in one go)

I cannot understand this part in tutorial for E : The edge will have a weight equal to the size of the SCC that it is going into.

Why is that ? Shouldnt all the weights of edges be 0 ? and find the longest path by vertex numbers ?

You can also keep the number of vertices in SCC in DAG vertex. Doesn't matter.

Puf did that. somehow I cannot get pass test 4. Is there any corner case or something ?

just a stupid mistake nevermind

In D how to create that divisor array in NlogN. i am doing it in NrootN.

You precalculate all divisors for each number using something similar to sieeve.

Hi, I have a question related to the time limit in problem C (Anji's Binary Tree).

I got many TLE in submissions like 235439131, 235440112, 235441383. The idea was fine, but after reading some of the comments, I realized that removing some things like memset, global variables, and setting reference variables will get me to the AC (235443694).

I would like to know what kind of aspects I have to think when I want to use memset or other kinds of stuff. Why do the last submissions differ in seconds to each other? What are the technical aspects related to the stuff that I have used in the first submissions? Thanks!

Memset is O(array_size) complexity. So using it for each testcase on array of size 300 000 for 50 000 testcases is just too slow. Always reset arrays by iteratting from begin to N as you know elements after it are unaffected. Rarely you might even need to keep elements you changed in a queue.

Edit: Also, note that locally declared variables are not guaranteed to have all values set to 0, so they are even worse than forgetting to reset global ones.

Got it, thanks for fast reply!

Can someone Please explain why I am getting a TLE in this solution for problem C 234510811

even after lot of modifications and changes, I am getting memory limit exceeded on test case 3 where n = 200000, m = 200000.I think it is due to DFS3() call but couldn't think for it's substitute. This function calculates the maximum length simple path and then for that length path minimum value. this is my submission link.

There might be some other reason for TLE but I have gone through other submissions and they have also allocated same complexity of memory.( vectors and arrays for graphs )

Problem D can be solved without the constant of 128.

Firstly notice swapping the indexes doesn't influence the sum. Then swap the indexes to a sorted state.

Then, for each $$$g$$$, we want to know, $$$dp[g] = $$$ how many indexes tuples that $$$i < j < k$$$, that $$$\gcd(a[i], a[j]) = g$$$. Similar to the question, we first calculate $$$cnt[g] = $$$ number of tuples $$$i < j < k$$$ that $$$a[i] = a[j] = 0 \pmod{g}$$$, then minus $$$dp[2g] + dp[3g] + ... dp[\text{max multiplier} \times g]$$$ to $$$cnt[g]$$$

Because we are in a sorted state, we can work on those $$$pg$$$ for each $$$p = 1 .. \text{max multiplier}$$$.

Notice that, there are two cases. The first case is $$$a[i] < p g$$$. In this case, $$$pg$$$'s contribution to $$$cnt[g]$$$ is #$$$(i) * S(pg)$$$. $$$S(pg)$$$ is the number of tuples $$$(j, k)$$$ that $$$j < k$$$ and $$$a[j] = pg$$$. #$$$(i)$$$ is the number of index $$$i$$$s that $$$a[i] < a[j], a[i] = 1g .. (p-1)g$$$ (notice $$$i < j$$$ is obvious because we sorted it).

The second case is $$$a[i] = a[j] = pg$$$. In this case, the sum is $$$T(pg) = \Sigma_{l \in \text{first } pg \text{ index} .. \text{last } pg \text{ index} } (l - \text{first } pg \text{ index}) (N - l) $$$.

Both $$$S(pg)$$$ and $$$T(pg)$$$ are able to be precomputed by walking through the sorted array. So we can result a time complexity in $$$O(N \log N)$$$

In question 1 , in 5th test case

10

## ...#..#.

someone pls explain how the output is 2 ?

Read the editorial...

In Problem C, Test case 3: I can just change the string to LRLR by modifying R -> L and U-> R and reach Vertex 2, that takes 2 modification but Why the answer is 3? Can anyone explain that bit to me?

2nd letter is letter on vertex with index 2. Not on 2nd vertex you reach.

initial RULR(1 2 3 4) path and replace 1-L 3-R 4-L final LRLR modification done in (1 3 4) in your case, you are modifying node 2 which won't affect and increase in one operation You should draw tree clearly

Why the BFS soln is not working?? Isn't it O(n)

Can Anyone explain solution with code of F local deletions ??

## include<bits/stdc++.h>

## define ll long long int

## define llq __int128 using namespace std;

## define level 18

## define mod 1000000007

## define lim 100008

## define lldb double

## define ln "\n"

const int U = (1 << 30) — 1; // bit operator

int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); ll t; cin>>t; while(t--) { ll n,m; cin>>n; string s; cin>>s; vectorans(n+1,0); ll sol=INT_MAX; vectorleaf; for(ll i=1;i<=n;i++) { ll x,y; cin>>x>>y; if(s[i-1]=='R') { ans[x]+=ans[i]+1; ans[y]=ans[i];

}

}

Why this is wrong answer ,I am just updating distance from root according to given condition?? can any give me test case ?? @C Question

In Problem C, I used memorization to calculate the answer. Although being of time complexity of O(n), It is giving Time limit exceeded for n=10^5. Can someone suggest me the problem?

https://mirror.codeforces.com/contest/1900/submission/239971869

You are passing string s in each recursion call and therefore it is actually $$$O(n^2)$$$. I recommend using global variables for stuff such as graphs or labels and preferably all arrays/vectors.