damn, that was fast!

Thanks for the fast editorial!!

Order of Speed Cf editorial > light > bolt

somebody reads tags

someone mind explaining the 2nd question?

Fast editorial and good problems!

Very curious about the bonus in the tutorial. So hard!

I'm quite confused about D.

Can anyone hack me for the following method, as system test wouldn't be completed in quite a while?

I have observed that for each $$$r$$$, at most 1 $$$l$$$ should make $$$[l,r]$$$ a bad segment, so I used binary search too. If an $$$l$$$ can be find, I would check if there is already a point between $$$[l,r]$$$. If there isn't, mark a point on $$$r$$$ using BIT, as it would be optimized if I put a point on the right-most position; otherwise, there is no need to ans++, we can use former points. Each point would be changed into a big prime.

upd: it turned out that when I was using ST-chart to store range wise gcds I brainlessly put the loop for $$$2^j$$$ in the inner loop. And I (un)fortunately ACed it now,

Problem B:

Please check My Submission I don't know why this construction of permutation incorrect.

Thank you!

I failed to solve C

Giving hint is a good thing for beginner contestant like me and thanks for the fast editorial.

Love the contests more, when tutorial comes this fast.

Simpler (in my opinion) solution for D in O(n log^2 A). We'll replace all elements with huge and different prime numbers. Let's keep a stack for GCDs of suffixes on current prefix, but we'll keep it compressed — we'll compress all suffixes with the same GCD into 1 element. Let's notice that GCD can decrease at most log A times (each time at least divides by 2), so we will have maximum of log A elements in stack. After moving to current prefix we'll recalculate GCDs for all blocks of previous prefix, and we'll also add new suffix of 1 element. Then we'll compress new stack (you can also do it while recalculating GCDs). Now let's look through stack. If there's a block with GCD x, and suffix of length x is in this block, then we'll replace current element (you don't need to do it by actually replacing element, you can just add 1 to answer if you clear stack) and clear stack (all GCDs of suffixes which include current element will become 1, but their lengths are more than 1). If there's no such block, we won't replace element and clear stack. This solution ran in 124 ms on round testing.

Update: it seems like it's actually O(n log A) solution. We have n different begins for suffixes, and for each suffix there is at most log decreases, so total amount of decreases of gcd is O(n log A). But we still need to do compression, because otherwise we will do at most n operations per prefix (if gcd of suffix is not decreasing, we still do O(1) operations in gcd). So solution above has complexity of O(n log A).

Editorials with hints are a gem :D

I'll cope up my inability to solve C in contest with new eps of demon slayer and AOT T__T

Video Editorial if anyone is looking for video format

There was an unexpected fact that in problem C, instead of reading the problem as b = b + 1, I read it as a = a-1 . Then I solved this problem by DP algorithm and passed system tests ?_?. I was really shocked when I discussed it with my friends after the contest. Is this really the solution to this problem or is it just a luck? if so, can someone prove the correctness of this solution ?

This is my solution: 144542918

Sorry for my bad englisk

I solved Problem C slightly differently. I used binary search.

Firstly we can see $$$a|b >= max(a,b)$$$.

So if $$$b>a$$$ , then $$$a|b>b$$$. Now we can see that if perform the third type of operation than $$$a>=b$$$.

Once this has happened we can see that increasing a will not be optimal and so we will increase b by 1. These means that after the one operation of type 3 we will use use the operations of type 2 only($$$b=b+1$$$)

So this leaves us with two types of operations
Type 1-> (a++ a++ a++ a++ ... a|b b++ b++ .....)
Type 2-> (b++ b++ b++ b++ ... a|b b++ b++ ... )

Once we know about this we can simply binary search to find the minimum number of operations required to make $$$a=b$$$.

My code using this approach->144558213

In problem D,How to reach O(nlogn) by using a segment tree?(Cant understand the editorial) Could anyone give me a help?

More cheat today.

@ MikeMirzayanov

we need to ban the cheat accounts,this kind of account makes imfair to cp

What's more , I find that most of accounts which submitted their code in 01:59 of E1 were suspect of cheat.

I read $$$C$$$'s editorial as:

" It is optimal to have either a′=a or b′=b. Bonus: Prove it. "

Problem C: It could be easily solved using SOS DP, I couldn't come up with the idea during the contest, but I got it in up-solving phase.

Code:

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T;
	cin>>T;
	while(T--){
		int a, b;
		cin>>a>>b;
		int ans = 1e9;
		vector<int> dp(2*b + 10, 1e9);
		for(int i=a; i<b; i++){
			dp[i] = i;
		}
		for(int i=0; i<=21; i++){
			for(int j = 0; j<=2*b+2; j++){
				if(j & (1<<i) ){
					dp[j] = min(dp[j],dp[j^(1<<i)]);
				}
			}
		}
		for(int i=b; i<=2*b; i++){
			ans = min(i-b + 1 + dp[i] - a,ans);
		}
		cout<<min(ans, b-a)<<'\n';
	}
	return 0;
}

can anybody prove or disprove my solution for problem D ?

my solution :

I used testers and could not find any counter cases for it

here is the submission : 144576517

is it possible to solve problem C, using dp and bitmask?

I don't know why this solution works for C: Either answer is:
1. b-a or
2. increase a until a is a subset of b (i.e. a|b = b) and then do OR operation or
3. increase b until b is a superset of a (i.e. a&b = a) and then do OR operation

I just found it intuitively correct during the contest and checked on various test cases before submitting it, I have no clue of the proof.

Bonus Task 3: Prove it :)

Why are there so less submissions for C?,it was the easiest question in this round

C upsolved in "$$$O(\log b)$$$". Converted numbers to 1-0-strings and did string manipulations first. (144595427,Perl).

A_2: 0100|0|0[0]1011(0)101 <- lowest bit
B_2: 0100|1|0[1]1001(1)100
----------a---b---c--d----

A_2: ...[0]1011(0)101 <- lowest bit
B_2: ...[1]1001(1)100
---------b---c--d---- flag=1 ('a' was discarded)

can someone help me to understand c more? in this equation : (a′−a)+(b′−b)+((a′ | b′)−b′)+1

i understand that we use the first term to find number of steps required to turn a into a' and the second term to find number of steps required to turn b into b' and the "1" is the step when we turn a' into b' using (a' | b') but what about the third term ((a' | b') — b') can someone explain it more?

Problem C. Can someone proof, that optimal solution can be achieved if and only if we perform one of two procedures (i. e. one of two procedures always represents optimal solution):

Procedure 1: (a++) ... (a++) (a|b)
Procedure 2: (b++) ... (b++) (a|b)

Why it is correct?

i feel sorry for kids studying in school 179

E2 Так как с возрастанием ans, fans убывает a в индексе, а не ans

My solution to E1 which is somewhat different from the editorial (although shares some ideas):

Think about computing the answer for a particular $$$x$$$. Similar to the editorial, we will see if we can achieve an answer of $$$ans$$$. This can be done with binary search or the two pointers method (although actually the former TLE'd for me). :(

We consider the nodes with depth greater than $$$ans$$$. Unlike the editorial which deduces where we should add the edge $$$(1, u)$$$, my solution tries all nodes (i.e. $$$1 \leq u \leq n$$$). The new distance to some node $$$v$$$ with depth greater than $$$ans$$$ is now $$$x + dist(u, v)$$$. We can achieve $$$ans$$$ if the maximum value over all $$$v$$$ of this expression is $$$\leq ans$$$. In other words, if the max $$$dist(u, v)$$$ is $$$\leq ans - x$$$.

How do we quickly query this max value? In precomputation, calculate the distance from each node to every other node. If we're adding the edge $$$(1, u)$$$, we only want to think about the distance from $$$u$$$ to nodes $$$v$$$ with $$$depth[v] > ans$$$. So sort the distance array (with source node $$$u$$$) by the nodes' depth. Now, we can create a suffix maximum array out of this array, which, along with knowing which index each depth starts at in this array, will allow us to answer the queries above.

really good contest, my respect to the authors

In the editorial of D, what does this line mean? "In our case, this is easy to do because our segments are not nested."

Here's another (Harder) solution for E:

Instead of calculating the answer for $$$X$$$, Calculate the maximum $$$X$$$ for each answer, then do a suffix max.

Finding the maximum $$$X$$$ is just getting the node that has minimum distance to all nodes with $$$f(v) \ge ans$$$, this is easy with an $$$O(N^2)$$$ brute force by iterating $$$ans$$$ from $$$N$$$ to $$$1$$$ and having addition events for nodes.

Solving it in $$$O(N)$$$ just needs an extra observation that all optimal nodes form a chain up to the root so you just need to start at the node with the largest $$$f(v)$$$ and whenever it's better to consider the parent just do that you can maintain the distances of nodes inside and outside the subtrees by using sets.

Problem C
Proof of Bonus 2: a'=a or b'=b

We know that once we apply the third operation, we have to increase $$$b$$$. Let's see how many of these operations are required after the third operation.
Let's say a' = (a|b). So we would have to add $$$2^i$$$, for all bits $$$i$$$, where $$$a'$$$ is 1 and $$$b$$$ is 0. This also means that the $$$i_{th}$$$ bit in $$$a$$$ is 1 and $$$b$$$ is 0.
So, we have to look for the bits where $$$a$$$ is set and $$$b$$$ is not. Let's start greedily. We will look for the highest such bit. Let's say that bit is the $$$x_{th}$$$ bit. Now we have two ways to handle it. We can either increase $$$a$$$ till its $$$x_{th}$$$ bit becomes 0 or we can increase $$$b$$$ till its $$$x_{th}$$$ bit becomes 1. Let's go with the first way. (Second could be explained in a similar way).
Now to make the $$$x_{th}$$$ bit in $$$a$$$ as 0, we would have to keep increasing it till all bits from $$$0$$$ $$$to$$$ $$$x$$$ become 1, and then we increase once more to make all these bits 0 and some bit $$$j$$$ becomes 1,for $$$j>x$$$.

Now if the $$$j_{th}$$$ bit is already set in $$$b$$$, we have found our solution without using the second operation. Else, if the $$$j_{th}$$$ bit was not set in $$$b$$$, we again have a similar problem, now with $$$x=j$$$.
WLOG, this time let's choose to increase $$$b$$$. So we have to increase $$$b$$$ till its $$$j_{th}$$$ bit becomes 1. In doing so, first we will most definitely reach a state in which the bits from $$$0$$$ $$$to$$$ $$$j-1$$$ in $$$b$$$ become a superset of these bits in the original $$$a$$$ (the $$$a$$$ we were given). (One such example is when all these bits become 1).
So we see that could originally just have increased $$$b$$$ to make $$$b$$$ a superset of $$$a$$$, which would have taken less operations, instead of first increasing $$$a$$$.

Following this logic, we can see that it's best to either just increase $$$a$$$ or just increase $$$b$$$ before doing the third operation.

The idea of problem D is similar to 475D.

the time limit for B is too tight. Even with O(N), I got over 700 ms. When the time limit is 1 second.

[1632D — New Year Concert] You can also use the fact that for a prefix, there at most O(logA) different suffix gcd values. This leads to another way to find the bad segments.

Does anybody have the code with this method? thanks.

1632D - Новогодний концерт

How to solve with segment tree and two pointers with complexity $$$O(n (\log n + \log A))$$$?

For a query on the segment tree, there are $$$O(\log n)$$$ times of $$$\gcd$$$. So it will cost $$$O(\log n\log A)$$$ for each query, the total complexity should be $$$O(n\log n\log A)$$$?

Similarly, the code of segment tree and binary search in the tutorial may be with complexity $$$O(O(n\log^2 n\log A))$$$, although we can do binary search on the segment tree itself to decrease it to $$$O(n\log n\log A)$$$ as well.

The complexity of the method with ST is ok.

I have a doubt in the solution code of problem C

for(int a1 = a; a1 < b; a1++) {
            int b1 = 0;
            for(int i = 21; i >= 0; i--) {
                if((b >> i) & 1) {
                    b1 ^= (1 << i);
                } else {
                    if((a1 >> i) & 1) {
                        b1 ^= (1 << i);
                        break;
                    }
                }
            }
            ans = min(ans, a1 - a - b + (a1 | b1) + 1);
        }

why have they chosen the inner lop to range from 21 to 0? Can somebody pls explain it to me

Can anybody explain how to solve E1?

A general doubt. My codes output on codeforces differs from local output in 1632B — Roof Construction. https://mirror.codeforces.com/contest/1632/submission/144622647

On Codeforces for n = 9

1 2 3 0 4 5 6 7 8

Locally I get (Which is correct) n = 9

1 2 3 4 5 6 7 0 8

I couldn't find any early termination and I don't employ global variables. There are also no uninitiallized variables looking at the code. I'm guessing It to be compiler specific? (Tried for both C++14, C++17).

а почему решение за O(n^2) работает быстрее O(n) в E2?

B Bonus solution is 2*(n-2)

For problem A shouldn't complexity be O(1) (instead of O(n))? We compute answer purely by looking and the length of the string (the n parameter) and that must give us YES or NO in constant time.

why is my C Solution is working?

What's the use of giving contests, when all you see is Maths and Bits? Great Problems?

Is there a way to download the CF test cases? This submission on D is wrong, but I can't debug it. The idea is that I store the (prime, power) pairs and count in how many last entries they appear. Then I create a map with GCDs and I propagate it downward. If I find the pair where the number of last occurrences == GCD, it is bad. If the smallest number of occurrences is >= the value of GCD it is also bad.

I tried generating some small random test cases, but couldn't repro the issue.

can anybody help me with the proof for C. that a'=a or b'=b i am not able to get it.

My approach to C: make $$$a$$$, submask of $$$b$$$, that is $$$(a | b) = b$$$.

1) we can do $$$a = a+1$$$, keep doing that until $$$(a | b) = b$$$. 2) we can do $$$b = b+1$$$, which is the same as $$$a = a-1$$$, keep doing it until $$$(a | b) = b$$$.

Explanation:

If $$$ith$$$ bit of $$$a$$$ is on, but in $$$b$$$ it is off, then $$$a$$$ is not a submask of $$$b$$$. Either you turn off $$$ith$$$ bit of $$$a$$$ (by doing $$$a = a+1$$$ enough times), or you turn on $$$ith$$$ bit of $$$b$$$ (by doing it $$$b = b+1$$$ enough times). Yes, you might turn on other bits in the process, but you can always turn them of by doing these operations enough times. now if $$$x =$$$ turn on $$$ith$$$ bit of $$$b$$$ by doing $$$b$$$++, $$$y =$$$ turn off the $$$ith$$$ bit of a by doing $$$a$$$--, you can actually observe $$$x = y$$$.

Code

A proof for bonus $$$2$$$ in $$$C$$$ (it also proves why it is always optimal to only increase $$$a$$$ until it is submask of $$$b$$$ or only increase $$$b$$$ until it is supermask of $$$a$$$):

Some observations:

1. $$$x+y$$$ is equivalent to finding two masks $$$m_1$$$ (its set bits are not set in $$$x$$$) and $$$m_2$$$ (its set bits are set in $$$x$$$) where $$$x+y=x+m_1-m_2$$$.
2. Any application of $$$b:=b+1$$$ after $$$a:=a|b$$$ is replaceable by $$$b:=b+((a|b)-b)$$$ first then $$$a:=a|b$$$ and the cost will be the same. So, we can always find an equivalent solution with $$$a:=a|b$$$ being the last applied operation.

Suppose the set of bits set only in $$$a$$$ is $$$set_a$$$, bits set only in $$$b$$$ are $$$set_b$$$, and bits set in both $$$a$$$ and $$$b$$$ are $$$set_{ab}$$$. Our final goal is to make $$$set_a$$$ empty.

Scenario $$$1$$$: If we apply $$$a:=a+1$$$ only, this means we want to unset all the bits belonging to $$$set_a$$$ in $$$a$$$. If the $$$MSB$$$ of such bits is the $$$i^{th}$$$ bit, it can be seen that is enough to find a $$$k^{th}$$$ bit ($$$k>i$$$) which is in $$$set_b$$$, then do the following:

1. For all the bits with index $$$<k$$$, unset them in $$$a$$$.
2. Set the $$$k^{th}$$$ bit in $$$a$$$.

Scenario $$$2$$$: If we apply $$$b:=b+1$$$ only. For all the bits in $$$set_a$$$, set them in $$$b$$$. If the $$$MSB$$$ of such bits is the $$$i^{th}$$$ bit, for all the bits in $$$set_b$$$ with index $$$<i$$$, unset them in $$$b$$$.

Scenario $$$3$$$: If we apply both $$$a:=a+1$$$ and $$$b:=b+1$$$, this is equivalent to doing the following:

1. Choose some index $$$j$$$ that is not set in $$$a$$$, where we have bits $$$<j$$$ and bits $$$>j$$$ in $$$set_a$$$.
2. If the $$$j^{th}$$$ bit is not set in $$$b$$$, set it.
3. Apply Scenario $$$1$$$ on the bits whose $$$MSB$$$ is $$$j$$$.
4. If the $$$MSB$$$ of bits in $$$set_a$$$ is the $$$i^{th}$$$ bit, apply scenario $$$2$$$ on the bits from $$$i$$$ to $$$j+1$$$, and for all the bits with index $$$<j$$$, unset them in $$$b$$$.

Claim: Scenario $$$2$$$ is always better than Scenario $$$3$$$.

Proof: Let's see which bits are set and which are unset in Scenario $$$3$$$ compared with Scenario $$$2$$$. In both scenarios the cost is the same for the bits from the $$$i^{th}$$$ bit to the $$$(j+1)^{th}$$$ bit.

Starting from $$$j^{th}$$$ bit (iteration order is from $$$MSB$$$ to $$$LSB$$$), we can notice the following differences:

1. If the $$$j^{th}$$$ bit is set in $$$b$$$, Scenario $$$2$$$ unsets it in $$$b$$$ while Scenario $$$3$$$ sets it in $$$a$$$. If the $$$j^{th}$$$ bit is not set in $$$b$$$, Scenario $$$2$$$ keeps it unset while Scenario $$$3$$$ sets it in both $$$a$$$ and $$$b$$$.
2. Staring from the $$$(j-1)^{th}$$$ bit:

• For all the bits in $$$set_b$$$, Both Scenario $$$2$$$ and Scenario $$$3$$$ unset them in $$$b$$$.
• For all the bits in $$$set_a$$$, Scenario $$$2$$$ sets them in $$$b$$$ while Scenario $$$3$$$ unsets them in $$$a$$$.
• For all the bits in $$$set_{ab}$$$, Scenario $$$2$$$ keeps them set in both $$$a$$$ and $$$b$$$ while Scenario $$$3$$$ unsets them in both $$$a$$$ and $$$b$$$.

The previous differences imply:

1. The contribution of the $$$j^{th}$$$ bit to the cost is $$$2$$$ times higher in Scenario $$$3$$$ whether the $$$j^{th}$$$ bit is set in $$$b$$$ or not.
2. Starting from the $$$(j-1)^{th}$$$ bit, the contribution of the bits in $$$set_a$$$ and $$$set_{ab}$$$ is $$$2$$$ times higher in Scenario $$$2$$$, and the contribution of the bits in $$$set_b$$$ is similar in both scenarios.

Conclusion: Since $$$set_a$$$ and $$$set_{ab}$$$ are disjoint sets representing bits set in $$$a$$$, the contribution of the $$$j^{th}$$$ bit will be always higher.

I don't understand why my div2B solution works of using the highest power bit and looping down. Can someone give me a proof?

https://mirror.codeforces.com/contest/1632/submission/144798711

Alternative solution for 1632E2 - Дистанционное дерево (сложная версия) (probably someone explained it here).

for i in range(n):
    ans[i] = min(ans[i], max(z, i + 1 + (m + 1) // 2))

for i in range(z - (m + 1) // 2):
    ans[i] = min(ans[i], z)
for i in range(max(0, z - (m + 1) // 2), n):
    ans[i] = min(ans[i], i + 1 + (m + 1) // 2)

     _/
  __/
_/

  _/
 _/
_/

Why in C taking | at last only is optimal like if we take general case we will apply x1,y1 operation of 1st and 2nd kind and then taking | and again x2,y2 no of operation and so on...

Would BFS work for problem C?

For problem C, I don't understand how to construct the optimal version of b prime

Interestingly problem D can be implemented using $$$O(\log A)$$$ memory, no need to even store the array.

Hi, All. Would you provide me a rationale behind problem C's editorial that getting optimal b' using a' and b?

E can be reduced to the following problem:

Given a tree, perform following queries:

1. Add a new child v to node u
2. Query diameter of tree.

(We can solve this by creating another version of tree which we build in a "bottom up" manner) Implementation: Link

I solved problem C

with time complexity O(log(b)^2) 239809162

I'm just curious that 1632D — New Year Concert can be solved in O(n)? By combining building spare table for gcd in O(n) and using two pointers O(n).