You can also find video editorials for problems B-D on ak2006's Youtube channel!
1632A — ABC
Only a few strings have the answer "YES".
For $$$n \ge 3$$$, the answer is "NO".
Let $$$n \ge 3$$$ and the resulting string be $$$a$$$. For there to be no palindromes of length greater than $$$1$$$, at least all of these inequalities must be true: $$$a_1 \neq a_2$$$, $$$a_2 \neq a_3$$$, and $$$a_1 \neq a_3$$$. Since our string is binary, this is impossible, so the answer is "NO".
For $$$n \le 2$$$, there are 4 strings that have the answer "YES": $$$0$$$, $$$1$$$, $$$01$$$, and $$$10$$$; as well as 2 strings that have the answer "NO": $$$00$$$ and $$$11$$$.
Time complexity: $$$O(n)$$$
1632B — Roof Construction
The cost of construction is a power of two.
The cost of construction is $$$2 ^ k$$$, where $$$k$$$ is the highest set bit in $$$n - 1$$$.
Let $$$k$$$ be the highest set bit in $$$n - 1$$$. There will always be a pair of adjacent elements where one of them has the $$$k$$$-th bit set and the other one doesn't, so the cost is at least $$$2^k$$$. A simple construction that reaches it is $$$2^k - 1$$$, $$$2^k - 2$$$, $$$\ldots$$$, $$$0$$$, $$$2^k$$$, $$$2^k + 1$$$, $$$\ldots$$$, $$$n - 1$$$.
Time complexity: $$$O(n)$$$
Bonus: count the number of permutations with the minimum cost.
1632C — Strange Test
It is optimal to apply the third operation at most once.
It is optimal to apply the third operation at most once, because is does not decrease $$$a$$$ and always makes $$$b \le a$$$. This means that after we use it, we can only apply the second operation.
If we don't apply the third operation, the answer is $$$b - a$$$.
Suppose we do apply it. Before that, we used the first and second operations some number of times, let the resulting values of $$$a$$$ and $$$b$$$ be $$$a'$$$ and $$$b'$$$ respectively $$$(a \le a', b \le b')$$$. The answer in this case will be $$$(a' - a) + (b' - b) + ((a' \ | \ b') - b') + 1$$$ $$$=$$$ $$$a' + (a' \ | \ b') + (1 - a - b)$$$. This is equivalent to minimizing $$$a' + (a' \ | \ b')$$$, since $$$(1 - a - b)$$$ is constant.
To do that, we can iterate $$$a'$$$ from $$$a$$$ to $$$b$$$. For a fixed $$$a'$$$, we have to minimize $$$a' \ | \ b'$$$, the optimal $$$b'$$$ can be constructed like this:
Set $$$b'$$$ to zero and iterate over bits from highest to lowest. There are 4 cases:
- If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
- If current bit of $$$a'$$$ is $$$0$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$0$$$.
- If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$1$$$, set the current bit of $$$b'$$$ to $$$1$$$.
- If current bit of $$$a'$$$ is $$$1$$$ and $$$b$$$ is $$$0$$$, set the current bit of $$$b'$$$ to $$$1$$$ and stop.
This works in $$$O(\log b)$$$ and can also be sped up to $$$O(1)$$$ using bit manipulation.
Time complexity: $$$O(b)$$$ or $$$O(b \log b)$$$
Bonus 1: solve the problem in $$$O(\log b)$$$ or faster.
Bonus 2: prove that is optimal to have either $$$a' = a$$$ or $$$b' = b$$$.
- C++ code with complexity $$$O(b \log b)$$$.
- C++ code with complexity $$$O(b)$$$.
- Python code with complexity $$$O(b \log b)$$$.
1632D — New Year Concert
Let's call a segment $$$[l, r]$$$ bad if $$$\gcd(a_l \ldots a_r) = r - l + 1$$$. There at most $$$n$$$ bad segments.
For a fixed $$$l$$$, as $$$r$$$ increases, $$$\gcd(a_l \ldots a_r)$$$ does not increase.
Suppose you change $$$a_i$$$ into a big prime. How does this affect the bad segments?
Read the hints above.
Let's find all of the bad segments. For a fixed $$$l$$$, let's find the largest $$$r$$$ that has $$$\gcd(a_l \ldots a_r) \ge r - l + 1$$$. This can be done with binary search and a sparse table / segment tree. If $$$\gcd(a_l \ldots a_r) = r - l + 1$$$, then the segment $$$[l, r]$$$ is bad.
If we change $$$a_i$$$ into a big prime, no new bad segments will appear. And all bad segments that have $$$i$$$ inside of them will disappear. So we have to find the minimum number of points to cover all of them. This is a standard problem, which can be solved greedily: choose the segment with the smallest $$$r$$$, delete all segments that have $$$r$$$ in them, and repeat. In our case, this is easy to do because our segments are not nested.
Time complexity: $$$O(n \log n \log A)$$$ with a sparse table, where $$$A$$$ is the maximum value of $$$a_i$$$.
Notes:
There are many different modifications to the previous solution, some of them use two pointers (since segments are not nested) and some of them update the answer on the fly while searching for the bad segments. Using a segment tree and two pointers you can get the complexity $$$O(n (\log n + \log A))$$$.
You can also use the fact that for a prefix, there at most $$$O(\log A)$$$ different suffix $$$\gcd$$$ values. This leads to another way to find the bad segments.
- C++ code with segment tree and binary search with complexity $$$O(n \log n (\log n + \log A))$$$.
- C++ code with sparse table and two pointers with complexity $$$O(n \log n \log A)$$$.
- Python code with segment tree and two pointers with complexity $$$O(n (\log n + \log A))$$$.
1632E2 — Distance Tree (hard version)
It is optimal to add edges of type $$$(1, v)$$$.
Try to check if for a fixed $$$x$$$ the answer is at most $$$ans$$$.
For a fixed $$$x$$$ and answer $$$ans$$$, find the distance between nodes that have $$$depth_v > ans$$$.
For each node, find two children with the deepest subtrees.
Read the hints above.
Let $$$f_{ans}$$$ be the maximum distance between two nodes that have $$$depth_v > ans$$$. If for some $$$x$$$ the answer is at most $$$ans$$$, then either $$$ans \ge depth$$$ or $$$\lceil \frac{f_{ans}}{2} \rceil + x \le ans$$$, since we can add an edge $$$(1, u)$$$ where $$$u$$$ is in the middle of the path connecting the two farthest apart nodes with $$$depth_v > ans$$$. Since $$$f_{ans}$$$ decreases as $$$ans$$$ increases, we can use binary search. Also note that we can use two pointers and increase $$$ans$$$ as we increase $$$x$$$.
How to calculate $$$f_{ans}$$$? Let's find for each node its two children with the deepest subtrees. Let $$$a_v$$$ and $$$b_v$$$ be the depths of their subtrees ($$$a_v \ge b_v$$$). If there are not enough children, set this values to $$$depth_v$$$. If $$$b_v > 0$$$, do $$$f_{b_v-1} := \max(f_{b_v - 1}, a_v + b_v - 2 \cdot depth_v)$$$. After this, iterate $$$i$$$ from $$$n - 2$$$ to $$$0$$$ and do $$$f_i = \max(f_i, f_{i + 1})$$$.
Time complexity: $$$O(n)$$$ or $$$O(n \log n)$$$ with binary search.
Note: To solve E1, it is enough to calculate $$$f_{ans}$$$ in $$$O(n)$$$ or $$$O(n \log n)$$$ for each $$$ans$$$. One way to do that is to find the diameter of the resulting tree after repeatedly deleting any leaf that has $$$depth_v \le ans$$$ ($$$1$$$ is also considered a leaf).
- C++ code for E1 with complexity $$$O(n ^ 2)$$$.
- Python code for E1 with complexity $$$O(n ^ 2)$$$.
- C++ code for E2 with complexity $$$O(n)$$$.
- Python code for E2 with complexity $$$O(n)$$$.
P. S. Solution codes will be published a little later.
P. P. S. Do not forget to evaluate the problems in the announcement.
UPD: Solution codes have been posted.
damn, that was fast!
We tried our
bfast :)Problems were really good, but i am stupid.
Authors, please look at this solution for problem C. I have written a bruteforce solution (determined $$$b'$$$ with a loop).
Is there a possibility that the solution can get TLE for some cases? If not then why?
Notice that $$$b' \le 2b$$$, since $$$a < b$$$. This means that your first loop will run at most $$$b$$$ times, and your second loop will run at most $$$2b$$$ times, so at most $$$3b$$$ times in total. Since $$$\sum b \le 10^6$$$ over all test cases, your solution will run well within the time limit and won't TLE.
Thanks for the fast editorial!!
Order of Speed Cf editorial > light > bolt
somebody reads tags
someone mind explaining the 2nd question?
hi, so basically it says, for any permutation of numbers, the minimum of max xor's you will get is 2^k, i.e for range 0-9, for any permutation you cannot go below 8 = 2^3 for range 0-22 you cannot go below 16 = 2^4
so the nearest 2^k is the value you need
you can try doing it manually for smaller ranges eg 0-5 and then increase the range till 15 or 17, the largest bump you get is when you xor 2^k and (2^k)-1, eg 7^8 or 15^16, you need to avoid this , therefore you need to place the 0 appropriately
But if we want to avoid 2^k and (2^k)-1, why don't we divide them? and why the minimum of max I get is 2^k. I can't understand it I am new.
yes, if you need to avoid 2^k and (2^k)-1, you need to separate them, i.e put 0 between them for eg for 0,1,2,3,4 — you can rearrange as 1,2,3,0,4
although this is how I did it and not exactly the editorial suggested but i guess idea is the same
for knowing why 2^k is the min of the max, you can try that yourself manually with smaller ranges
or consider this example, range 0-18 here the highest power of 2 is 16(2^4) 16- 10000 (binary)
if you do xor with any number between (0-15), it will end up in a number >=16
16^2=10010=18 16^5=10101=21 16^0=10000=16
do some yourself
so here the concept of highest set bit comes into play here for 16 its the 5th bit from the right (10000) this is present in all numbers from 16-18 in the sequence
so if you do xor of any number in 16-18 with any numbers in 0-15, they will result in >=16 always as for these smaller numbers(0-15) the 5th bit is always 0
17- 10001 6 — 00110 xor-10111 — 23
you gotta minimize this...why? because for any permutation there will be at least one number among (16-18) which will be adjascent to a number in (0-15) whose xor will blow up the value (eg 1,2,3,4,**17**,5,6,...)
now interestingly if you xor 16^17 or 17^18 or 16^18 , the values are small cuz they have the 5th bit as 1
16- 10000 18- 10010 xor-00010 -2
so for a very simple solution, put them serially 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
the highest value you get is from 15^16, just put 0 between them 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,16,17,18 and it should work
try doing the xor's manually and you will recognize the pattern
I sincerely thank you for such a detailed explain.I totally understand it.I will study hard and make progress everyday. Thank you.
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!
try 9
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).
Sorry that I still don't understand your idea well. Can you share your submit? Many thanks!
144614536. Here is the implementation of glebustim approach.
But I think that sultan__'s implementation is also right
if implemented correctly, you can achieve O(n log A) time complexity. Let's store in basic array all blocks in increasing order of gcd and start of suffix. Then, for each new element, we will do two operations. First operation is to update all gcd by taking gcd with new element from last suffix to the first (in reverse order). Second operation is to remove duplicates from array by shifting (it works in O(length of the array) in worst case). Now, consider second operation: its total time complexity is O(n log A) because we know largest possible length of array will be log A, and the number of elements we will remove from array is not greater than number of elements we add into array. Now, consider first operation. We calculate log A times gcd. We need to use following fact: gcd(a[0], a[1], a[2], ..., a[n-1]) calculated in following manner g = 0, then for each i: g = gcd(g, a[i]) complexity is O(n + log(max(a)). This is because each time g is updated, it's at least twice lower, so we can't decrease g more than log(max(a)). Using this fact, first operation if we keep last result of gcd of last block we calculate, then it should be O(log A + log A) where first log is length of array, and second log is total running time of gcd. In the end, two operations is O(n log A + n log A) = O(n log A).
Yes, I think idea is right and this will work in O(n log A).
Update: I wrote this and submitted my old submission and this one at one time, but I got 124 ms on both. Maybe I wrote something wrong, but it feels that optimization shouldn't give huge performance boost, because for that you need sprecialized big tests and they don't usually appear in problems (only then authors want to kill one of the wrong solutions, which works on random testset).
Perhaps without this change it's still n log A we just don't know how to show it. Or, making test is really hard. Oh, I started to think of it right now, and here is what.
Consider 'life' of single element. It's pushed into array, interleaving hit by gcd with change and without change, and removed from array. Pushes and remove is clearly O(n log A). Now most interesting. To estimate without change — we just imagine all elements within array doesn't change every time. Thus, it's n log A times it doesn't change. BUT! When gcd(a, b) = b it does exactly one division and get remainder 0 straight ahead, so it's exactly O(n log A) in total. To estimate gcd hit with change, imagine during 'life' each element does maximum changes: maximum changes is log A, and number of elements is n. So again O(n log A). Perhaps I'm missing something.
Yes, I just understood that solution without optimization is still O(n log A). I will update solution.
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
lmao glad to see im not the only one who read b++ as a-- :p. i looped from 0 to b-a and checked if you could obtain b in i operations. tho similarly to u, i have no idea why it works xd
We have to make $$$a$$$ a submask of $$$b$$$, then apply the second operation once.
Makeing $$$a$$$ a submask of $$$b$$$ can be done by incrementing a some times, or incrementing b some times. The number of times we would increment b is also the number of times we would decrement a. This is why a-- works like b++ in this problem.
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
When you wrote
How did you reach the conclusion that we will only increase a or only increase b before operation of type 3?
It is clear that after type 3 operation we only need to increase b.
I don't have a proof for this but I can try to explain with the help of an example.
Suppose we are increasing the number a x times and increasing the number b 1 times. In this case (a+x)|(y+1)
As opposed to this if we simply increase the number a x times then the new a after the or operation is (a+x)|y
I don't have a proof for this but (a+x)|y <= (a+x)|(y+1)
(a+x)|y <= (a+x)|(y+1)
it seems to be wrong, check this case: a+x=2 and y=1I think this is the logic:
Our aim is to match the bit values in corresponding positions of
a
andb
.Proof for Type1:
Consider the highest bit which is set in
a
but not inb
. This can only set inb
by incrementingb
. But we can neglect setting that bit by making that bit0
by incrementinga
.Example: let binary representation of
a = 01110
andb = 10000
. Here, it is clear that using operationa|b
would be good only after incrementinga
upto10000
, else doinga|b = 11110
will costb++
operations more.Now, making b++ operations in between while incrementing a upto 10000 would be of no use
.Proof for Type2:
lets take example a = 01010 and b = 10101.
If we do a|b first,
a
would be11111
, after which we need to dob++
forb
to match11111
.But we can reduce the operations by incrementing b to 11000 (why-> we save the later b++ operations making the third highest bit
0
. Thena|b = 11010
. And then incrementing b upto11000
.Good observation about 2 types of operations. But I feel no need binary search, and just iterate operation times from 0 to (b — a) is good enough? Codes like:
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.
Congrats for becoming pink!
uha thank you . orz orz
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:
why upto 2 * b?
You don't want to check numbers greater than $$$2*b$$$ because it means that you have to do $$$b := b + b$$$ and since $$$a<b$$$, so is optimal to $$$a := a + (b-a)$$$
Note: $$$b-a < b$$$
Also, $$$a:=a+x$$$ should be submask of $$$b:=b+y$$$ and it is easy to prove.
Can you please explain your approach?
Well, if you iterate over a number (let it be $$$b'$$$), you want to find other number that is submask of $$$b'$$$ and it should be near as possible to $$$a$$$.
can anybody prove or disprove my solution for problem D ?
my solution :
we know that there exists 1 or 0 bad segment starting from each index and no bad segment lies completely in an other one
each time we select the first segment and erase the last element(put some good random number) and we continue from that one
for finding the first segment we can start from the first of the array and iterate until gcd of elements become less or equal to their number (j) if it's equal then that's the first segment otherwise we come backward and find the last place (i) where gcd[i,j] <= j-i+1 we erase [1,i) and continue computing starting from i
I used testers and could not find any counter cases for it
here is the submission : 144576517
I've solved it exactly this way during contest, however I was sure it was O(n^2).
Seems like the proof has a lot to do with the fact that when we go back gcd can decrease up to log times.
Maybe if I get some time, I'll try to prove it
-No bad segment lies completely in another one-
Lets suppose there is bad segment $$$[l_j,r_j]$$$ which lies completely in another one $$$[l_i,r_i]$$$
$$$r_j-l_j=gcd(a_{l_j},\ldots,a_{r_j})\ge gcd(a_{l_i},\ldots,a_{r_i})=r_i-l_i$$$
$$$r_j-l_j\ge r_i-l_i$$$ contradiction
-each time we select the first segment and erase the last element(put some prime number) and we continue from that one-
Consider optimal sequence of numbers $$$a_{i_1},a_{i_2},\ldots,a_{i_k}$$$ we change. Deonte $$$[a_{l},a_{r}]$$$ — leftmost segment by its left end point containing $$$a_{i_j}$$$. We have to prove that if we replace $$$a_{i_j}$$$ in optimal sequence by right end point of $$$[a_{l},a_{r}]~=~a_r$$$, our sequence stays optimal. We prove it by showing, that each bad segment containing $$$a_{i_j}$$$ contains $$$a_r$$$, because its left point $$$\le a_l$$$ because $$$ a_l$$$ was leftmost one, and its right end point $$$\ge a_r$$$ otherwise bad segment will be completely in another one — $$$[a_{l},a_{r}]$$$. It means that such segment contains $$$a_r$$$.
yes, but what about case where we don't find any bad segments in go back step? Then we cannot move our left pointer entirely to the right.
I dont quite get what you mean by -we don't find any bad segments in go back step-
I might be misunderstanding something but as far as I understand as long as gcd > l — r + 1 we increase our r.
The moment gcd becomes smaller than l — r + 1, we have to build new gcd and we do that by going back from r. Now if we manage to find a bad segment this way then everything is fine as we'll be able to move our l pointer to r + 1.
But what if we only find segment [new_l, r] such that l < new_l < r and
gcd(new_l,...,r) > r — new_l + 1
and
gcd(new_l — 1, ..., r) < r — new_l + 2
Then we have to continue analyzing from l = new_l and r = r + 1
is it possible to solve problem C, using dp and bitmask?
here https://codeforces.net/contest/1632/submission/144568997
For finding the first submask>=a and less than b
for every x>=b and x< (1<<(max_bit in b+1))
Finally I implemented my idea correctly!
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 :)
I also used the same approach, but I'm also not able to prove this.
If you get any proof in the future, then plz do share.
Why are there so less submissions for C?,it was the easiest question in this round
Can you explain why is it enough to increment only a or b, but not both of them simultaneously? I can't understand this.
You can see this comment which proves a'=a or b'=b. https://codeforces.net/blog/entry/99442?#comment-882489
C upsolved in "$$$O(\log b)$$$". Converted numbers to 1-0-strings and did string manipulations first. (144595427,Perl).
We find the rightmost
0/1
which is not preceded by1/0
somewhere. In this case it'sb
column, becaused
column is preceded byc
. Then we can discard all bits to the left fromb
, but we flag if we discarded any0/1
.Now we can either 1) increment B (without highest bit) upto A and apply
OR
, either 2) increment A upto B wihout lower bits (i.e. $$$2^{length(B)-1}$$$) and then applyOR
if we have flag=1 or B has any of lower bits (i.e. it is not power of 2). Instead of incrementing we subtract and find minimum of these two results.oh wow, Perl, that's nice
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?
We are not turning a' into b' using a'|b' , rather we are turning it into some value >= b', (a'|b'-b') tells us the number of moves we still have to do (using increment operation) to convert a'|b' into b'.
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):
Why it is correct?
i feel sorry for kids studying in school 179
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.
Hi, robinz62,
May I have a look at your code following the idea you mentioned here? Since I hold the same idea, however it returns TLE for 6th test, here is my code
The time complexity I used is O(n*nlogn), which should be very close to O(n^2) while n <= 3000. but the submission result proves that's not true (at least for problem E1 here ... )
I think the timing might be a bit tight, maybe also depending on the language. As I mentioned, my solution also TLEd if I used binary search instead of two pointers. Here is my submission: https://codeforces.net/contest/1632/submission/144598040
It's probably a bit hard to read:
Great explanation! Thanks a lot!
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."
I meant that it is easy to remove all segments that have $$$r$$$ in them since we can keep deleting the first one while the condition holds.
Why segments are not nested. Suppose they are, $$$[l_2, r_2]$$$ is inside $$$[l_1, r_1]$$$. We have $$$\gcd(a_{l_2} \ldots a_{r_2}) \ge \gcd(a_{l_1} \ldots a_{r_1})$$$ and $$$r_2 - l_2 + 1 \le r_1 - l_1 + 1$$$. Since the segments are bad, this is possible only when both of the inequalities have the right and the left side equal. This means that the segment lengths are equal => they can not be nested.
Got it, thanks a lot.
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.
I copied you code and submitted it again.only 46 ms i dont know why
GNU C11 vs GNU C++17 :)
Yes. I now realised that C is stupid slow compared to C++.
[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 - New Year Concert
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.
Oh, the complexity of ST with 2-pointers seems not accurate too. The preparation of ST does $$$O(n\log n)$$$ times of gcd and costs $$$O(n\log n\log A)$$$.
I have a doubt in the solution code of problem C
why have they chosen the inner lop to range from 21 to 0? Can somebody pls explain it to me
a and b are limited to 1e6, that means they have at most 20 bits.
Can anybody explain how to solve E1?
A general doubt. My codes output on codeforces differs from local output in 1632B — Roof Construction. https://codeforces.net/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).
This is error prone to rounding errors since floating numbers are used. Instead use a simple log2(int) function based on bit counting instead.
B Bonus solution is 2*(n-2)
Too small and seems to work only for $$$n = 3$$$.
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.
You still need to read the input.
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.
Failing test case
Thanks!
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:
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:
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:
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:
The previous differences imply:
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.
nice
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://codeforces.net/contest/1632/submission/144798711
So no matter what a number w/ the max bit is next to a number w/o max bit so the answer is at least 2^max bit. So you put all the max bits to the left and those don't matter, put the lowest max bit number (that one matters) next to the 0, which should be the answer, and then the rest which don't matter.
Alternative solution for 1632E2 - Distance Tree (hard version) (probably someone explained it here).
Suppose we know which edge to add. Obviously, there is no point to walk over the edge twice. Therefore we can split all vertices into two groups: one which is shorter to reach using the edge we add, and other group is one which is shorter to reach without passing the edge we add. Also we know the maximum distance. Now, key insight: we don't actually care shortest path, but instead we just want to reach it without exceeding maximum distance. So, let's make other groups instead: one group will be all those vertices which can be reached without exceeding maximum distance (the answer), and other group will be all other vertices, which require to use our new edge. Also, it's easy to see that all vertices from first group is just all vertices at distance not exceeding maximum distance (the answer) in the tree without edge we add.
Now, consider we still know which edge to add. Also, let's assume second group is not empty: there is at least single vertex which require to use edge to reach it without exceeding the limit. So, pick arbitrary vertex from second group and look at the path we take. If the edge is coming not from vertex 1 then we have additional distance from 1 to its one endpoint to jump to the other endpoint. And it's easy to see that if first endpoint would be vertex 1 we would save this distance we should take to reach it. It's true for arbitrary vertex from second group, thus one end point of edge should be vertex 1.
Since we have shown that we should add edge (1, v) we also know that shortest distance to vertices in second group will be in form of weight_of_new_edge + distance(v, vertex_from_group). This means, maximum distance for second group is maximum distance from vertex v among vertices within second group plus weight of new edge. Therefore we want to pick v such that maximum distance among vertices within second group is minimal. Even if in our answer that we have v is different, then we can use vertex with this property and it will also work (easy to prove by contradiction using definition of vertex we pick).
If for some vertex v the maximum distance from v to all other vertexes is minimal then this vertex is called "center" of graph. It's well known thing. Also, it's known that for trees there is one or two centers, and to find out them you can pick any arbitrary vertex. Then find out vertex u1 with largest distance from it. Then find out vertex u2 with largest distance from u1. Then, the path from u1 to u2 is called diameter because it's largest simple path within the tree. And then, center is in the middle of this diameter, and it's easy to see the maximum distance from center is distance from u1 to u2 divided by 2 round up. Using this knowledge we know maximum distance within second group, and we don't actually care where exactly vertex v is.
Now it's easy to solve 1632E2 - Distance Tree (hard version). We need to use following fact. Whatever edge weight is, there has to be the answer. We can try any possible answer. Just brute force the answer(limit): for each limit find out first group and all other vertices put into second group. Find u1 in O(n) using bfs, find u2 in O(n) using bfs, now we know maximum distance from center within second group. Solution: in O(n) iterate over all possible weights of edge (1, v), and update answers. We do O(n + n + n) for each limit, and number of limits in worst case is O(n) so its total time complexity is O(n^2). Here is part how I iterate over weights (here z is limit, and m is distance between u1 and u2):
Note, instead of iterating over limit, it's easier just add vertex in first group one by one in increasing distance (in order of bfs). Here is source code: 144641370
Hard version. First, notice if we do first bfs to find u1 from vertex 1 then we always traverse vertices in same order, and u1 is always last vertex within the order of same bfs which we add vertices into first group. This means, we can run bfs from vertex 1 once and store whole queue of vertices. u1 will be always last item of this queue. Then, we can add vertices in first group directly from this saved queue. With this optimization we have: bfs once, then in loop: bfs from u1 (which is constant) to get u2, and loop to update answers. O(n + n * (n + n)). Still O(n^2). But now let's use the fact that u1 is fixed. Let's also run bfs from u1 once and save queue. Now u2 is first vertex from the end of queue which is still in second group. Source code: 144641823. If we use two pointers technique new complexity would be O(n + n + n * n) where n * n comes only from loop to update all answers. (no source code example)
Time to optimize this loop which is mentioned above (part of the code). We can analyze when max(z, i + 1 + (m + 1) // 2) evaluates as z and when otherwise. With a little bit of algebra it's easy to see that it's equal to z in range [0, z — (m + 1) // 2), and other value in range [z — (m + 1) // 2), n). This leads to code:
First operation we can do using segment tree in O(log n). Second operation is tricky. Notice that each of them always has (i + 1) in it. So we just want to find out which (m + 1) // 2 was lowest applied for index i. So, we can make second segment tree which will store this info (minimum (m + 1) // 2). Now we have solution in O(n + n + n * (log n + log n)) which is O(n log n). Here is the code: 144643752
Now, let's get rid of segment trees. Notice how we use two pointers for u2 which means that distance between u1 and u2 is only decreasing. In the code above it's m, and z is always increasing. This means, that value of expression: z — (m + 1) // 2 always non-decreasing. Also the shape of function we update looks like this:
_/
if we plot. So each new relaxation is shifted up or right or up and right (or not shifted). Anyway, it can't be shifted left, or down. Using this knowledge you can show that shape in the end should be like this:Let's call 'midpoint' — vertex when horizontal line ends. And all those 'midpoints' can be stored in stack, and each time you add you need to compare only to last one. Then, suppose we left with 3 midpoints as in 'picture' above, then we can iterate once between midpoints of 1 and 2, then iterate once between midpoints of 2 and 3, and so on. O(n) in total. Also, iterate once up to midpoint 1, and iterate once after last midpoint. This solution time complexity is O(n). Source: 144647029
And, in the end, it can be shown, that those
/
parts can be ignored. Why? Well, for optimal solution we never exceed the limit in the second group. So, in last mentioned submission, lastfor
within solve function can be omitted. Source: 144832151Edit: sorry. I have mistake in part about
/
. Source mentioned without additionalfor
above remove only last/
and it passes the tests for some reason. But my claim was about all/
. If I ignore all/
I get WA2 144858000. But my claim is correct but only with big note: we need to keep all 'midpoints', because in my previous implementation I removed all midpoints which were aligned like this:But in new version I should keep them all. Source: 144858814 Now if you look closer you'll see that you don't need stack anymore. Source: 144860233
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.
How?
Check out my solution, it's based on the well known stack trick: 145373154
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:
(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