Author: NemanjaSo2005
Assume that cells $$$i-1$$$, $$$i$$$, and $$$i+1$$$ are covered in water. What happens if you remove water from cell $$$i$$$?
The water at position $$$i$$$ is replaced as both cells $$$i-1$$$ and $$$i+1$$$ have water in them.
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)$$$.
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
Check if only digits $$$1$$$ can remain. The situation is similar for checking if only digits $$$2$$$ or only digits $$$3$$$ can remain.
Try to find something that stays the same after each operation.
Look at the parity of the numbers.
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.
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)$$$.
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
Solve the problem if all of the characters on vertices are 'U'.
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.
Modify the DFS such that it takes into account that traversing some edges does not require an operation.
Add weights to the edges.
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)$$$.
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
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$$$).
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$$$.
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$$$.
Numbers up to $$$100\,000$$$ can have at most $$$128$$$ divisors.
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)$$$.
Solve the problem if $$$f(a,b,c) = \gcd (a,c)$$$.
Author:NemanjaSo2005
Try to simplify graph $$$H$$$.
Look at strongly connected components of $$$G$$$, and what happens with them.
Use dp to find the answer.
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)$$$.
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
Solve the problem for $$$q=1$$$.
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.
Solve the problem if each $$$l_i = 1$$$. So basically, solve the problem for each prefix.
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.
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.
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)$$$
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.
We 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 please please 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 answer
If 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 sir
How 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)
Great solution! Replacing the gcd with that summation was really smart. I could have never thought of that :O
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://codeforces.me/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://codeforces.me/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 whichd
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://codeforces.me/contest/1900/submission/234466578
C++ — https://codeforces.me/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.
(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.Hi, can you please tell why passing a string by value would make the soln O(N^2)? I know a copy of the string has to be made in the called function but shouldn't that make a minimal difference. Also in this soln the function is called only once.
I got TLE on 6th pretest with Python. If someone can see the problem, please tell me:
https://codeforces.me/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.
I 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://codeforces.me/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 updatingmagic[f]
wheref
is a factor ofarr[i]
.Thus the required sum is
Calculating
magic[x]
by factoring inO(n * MAX_FACTORS)
: SubmissionCalculating
magic[x]
without factoring inO(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://codeforces.me/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://codeforces.me/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 function so 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://codeforces.me/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 indexi
i'm considering that to be middle value of triplet that isb
. So as per question i need to find value ofa
andc
now. I initializedcurrentIndexAns = 0
for this loop. Sincea
index has to be less than index of middle that isi
for current loop. In an inner loop ofi
, i'm iteratingA
again. In this case if my inner loop index that isj
.(j<i)
, then i will check ifa[j]<=a[i]
, wherei
index is my assumed middle value, i will calculate itsgcd(a[j], a[i])
. And add it tocurrentIndexAns
answer. After this i will have sum of all possible gcd values which can havei
index as middle. Then i will multiply thiscurrentIndexAns
with count of indexes that is abovei
, so,j>i
anda[j]>=a[i]
. Let's call this count ascountMaxLeftMiddle
. Then i will multiply this, withcurrentIndexAns * countMaxLeftMiddle
. To get contributions of triplets which havei
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://codeforces.me/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.
Did anyone tried Problem F? I didnt understand the editorial here
Did anyone do Problem F? I do not understand the tutorials provided
can anyone explain me that how are we getting 2 in question A's 5th test case
haha infinite water glitch go brrr
Solution for the problem D Link
can someone help why i am getting TLE int this submission[submission:284642031]
In each test case you do memset(vis,-1,sizeof(vis)). Complexity of that is O(T * maxN), which is too much, as it's allowed to have 50000 tests with small N. If you only reset positions from 0 to N you should be fine.
Thanks man, it worked...
ohkk i might be making a very dumb mistake but in question A solutions says if the string contain substring '...' then answer is 2 otherwise no. of empty cell. ohkk but how will the distant 2 consecutive empty cell and 1 cell separated by blocks can be filled up
I don't understand your question.
"distant 2 consecutive empty cell" — How can they be both distant and consecutive?
Also, water does not travel trough blocked cells if that was your question.
my bad, i meant pairs that are distant
although, got it now, those three dots are just making an infinite water supply for all other remaining cells (minecraft type shit)