Solutions Codeforces Round #830 (Div. 2) Editorial
- Get link
- X
- Other Apps
Codeforces Round #830 (Div. 2) Editorial
Thanks for the participation!
1732A - Bestie
Let's make an important observation:
Let
- If
g=1 , then the operation can be omitted and the answer is0 , - Otherwise, let's try the cheapest operation
i=n . Ifgcd(g,n)=1 , then the answer is1 . - Otherwise, let's try the next cheapest operation, ie
i=n−1 . Ifgcd(g,n−1)=1 , then the answer is2 . - Otherwise, the answer is
3 , sincegcd(g,n−1,n)=1 .
1732B - Ugu
Let's mentally imagine the following array of length
- For
i≤j , note that thej th and(j+1) th elements invert their value, soaj does not change. - For
j<i−1 , note that thej -th and(j+1) -th elements do not change their value, soaj does not change. - For
j=i−1 , note that thej th element does not change its value, but the(j+1) th element does, soaj will change its value.
If we look at the array
Let
Let's prove that if the string starts with
- Choose
i=3 , thens=0000001101 , - Choose
i=7 , thens=0000000010 , - Choose
i=9 , thens=0000000001 .
1732C1 - Sheikh (Easy version)
Note that
Then it was possible to use two pointers or binary search to solve the problem. If you solve the problem in the second way, then you iterate over the right boundary of the answer and look for the optimal left boundary for it by binary search. You will need
1732C2 - Sheikh (Hard Version)
Note that
Next, let's see in which case
Let's put all these facts together: we can remove at most
1732D1 - Balance (Easy version)
Let's look at a stupid solution and try to improve it.
In a stupid solution, we can simply add to the set, and when answering a query, iterate over the numbers
We will improve the solution. If a request comes to us for the first time for a given
Let's count for each value
1732D2 - Balance (Hard version)
Let's look at a stupid solution and try to improve it.
In a stupid solution, we can simply add and remove elements from the set, and when answering a query, iterate over the numbers
We will improve the solution, first consider the solution of the problem without the removal operation. If a request comes to us for the first time for a given
Now consider a variant of the problem with the delete operation. Let's set for a fixed
It remains to figure out how we can recalculate these set in the case of an add/remove operation. Let's actually just remember for each value in which set it participates and we will update all of them.
Let's calculate the running time. Let's understand how many sets a given value
1732E - Location
Tasks of this kind, as a rule, are solved using data structures, and this one is no exception. Since the constraints in the problem are not large enough, it is logical to think in the direction of root optimizations.
Let's divide the array into blocks of length
Let's see what happens with the first type of operation. If the block partially intersects with the segment of the request, then it is possible to go through this block for
To do this, let's precalculate the following value for each block:
Already now we can calculate the answer for
Let's note that
Let's calculate the running time and find the optimal
- Get link
- X
- Other Apps
Comments
Post a Comment