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 \gt 0$$$ and $$$c \gt 0$$$. If $$$b=c$$$, then we are done. Otherwise, without loss of generality assume $$$b \gt 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)$$$
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
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:
Thank you so much! It was helpful!!
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 \lt 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?
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://mirror.codeforces.com/problemset/problem/1843/D.
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
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.
(string should also be passed by reference) ...
Really!!? I didn't get AC for a singular "&" sign??
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]wherefis 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 \gt 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 \lt b \lt c$$$, $$$a=b \lt c$$$, $$$a \lt 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.
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));
} if(v[x].second!=0){ if(s[x-1]=='R') ans=min(ans,dfs(v[x].second,kount,s,v)); else ans=min(ans,dfs(v[x].second,kount+1,s,v)); } return ans;}
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 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.
Problems C and E are just... weird... Nothing really to solve, just implement standard algorithms.
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.
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.
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.
haha infinite water glitch go brrr
ahahahha
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.
For problem D, an alternative solution is to aggressively use prefix sums.
Let $$$\text{Max} = \max{ v }$$$, where $$$v$$$ is the given array.
First, we precompute the frequency array $$$\text{freq}$$$. Then we find its prefix sum array, say $$$\text{pref}$$$. Now, to calculate the initial value $$$X$$$ (before deleting the contribution of multiples — refer to hint 1 / solution to hint 1), for each integer $$$i$$$ ($$$1 \le i \le \text{Max}$$$), we have three sources in the summand: the number of triplets where the least two numbers are multiples of $$$i$$$, for every multiple $$$j$$$ of $$$i$$$ in increasing order.
(a) $$$j$$$ is taken 2 or 3 times. The contribution is:
(b) $$$j$$$ is taken exactly 1 time. The contribution is:
The first part is straightforward. For the second part, intermediate vectors of $$$\binom{\text{freq}[r]}{2}$$$ and $$$\text{freq}[r] \cdot (n - \text{pref}[r])$$$ can be computed in $$$\log(i)$$$ time (refer to hint 2), where $$$r$$$ runs across all multiples of $$$i$$$. Let these arrays be denoted by $$$\text{fC2}$$$ and $$$\text{f2Sp}$$$, respectively.
These arrays can be prefixed. Then, iterating over all multiples $$$j$$$ of $$$i$$$, we can compute the contribution from all multiples of $$$i$$$ greater than $$$j$$$ in $$$\mathcal{O}(1)$$$ time using:
where $$$ct = \left\lfloor \frac{j}{i} \right\rfloor$$$. Here, $$$\text{fC2.back()}$$$ refers to the total sum of the array $$$\text{fC2}$$$, effectively giving us a suffix sum. (It might have been simpler to describe this in terms of suffix sums directly, but that would introduce some index complications.)
The rest of the solution proceeds as in the editorial — we remove the contribution of the greater multiples accordingly.
Thus, the overall running time is $$$\mathcal{O}(m \log m)$$$, where $$$m = \max(v)$$$.
Here is my solution using this approach.