We hope you enjoyed the problems! Thank you for your participation! We are really sorry that A and D turned out to be harder than usual.
Problem A: idea by prvocislo and satyam343, prepared by prvocislo
If someone would claim that the number of draws that happened between the three players are $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$, can you check in $$$O(1)$$$ whether this can be true?
The constraints are very small. The number of draws between any two players is at most $$$30$$$.
Hint 3: Try all the possibilities for $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$ and find the one with the biggest sum out of all possibilities that could've been the result of game that ended with scores $$$p_1$$$, $$$p_2$$$ and $$$p_3$$$.
After each round, sum of players' scores increases by 2, so if the sum $$$p_1 + p_2 + p_3$$$ is odd, answer is $$$-1$$$.
Now, as the hints suggest, you can try all possible combinations of $$$d_{1, 2}$$$, $$$d_{1, 3}$$$ and $$$d_{2, 3}$$$ with three for-loops and check for each combination whether it could result in scores $$$p_1$$$, $$$p_2$$$ and $$$p_3$$$. Specifically, it must hold that $$$p_1 - d_{1, 2} - d_{1, 3} \equiv 0 \mod 2$$$, $$$d_{1, 2} + d_{1, 3} \leq p_1$$$ and the same two conditions for $$$p_2$$$ and $$$p_3$$$ analogously. Now you can find the biggest value of $$$d_{1, 2}$$$ + $$$d_{1, 3}$$$ + $$$d_{2, 3}$$$ over all valid choices and print it as the answer.
The time complexity is $$$O(t \cdot \max(p) ^3)$$$.
Implementation in Python: 261998440
There exists an $$$O(1)$$$ solution with simpler implementation. Claim: The answer is min($$$(p_1+p_2+p_3)/2$$$,$$$p_1+p_2$$$). Let's prove this: if $$$p_1+p_2 \leq p_3$$$, then it's possible that players $$$1$$$ and $$$2$$$ played $$$p_1$$$ and $$$p_2$$$ draws with player $$$3$$$, after which there can't happen any additional draws in the game. if $$$p_1+p_2 > p_3$$$, that means $$$p_1 > p_3-p_2$$$, so player $$$1$$$ can first play $$$p_3-p_2$$$ draws with player $$$3$$$. Note, that if sum $$$p_1+p_2+p_3$$$ is even, then $$$p_1-(p_3-p_2)$$$ will also be even, so player $$$1$$$ can play $$$(p_1-(p_3-p_2))/2$$$ draws with each of players $$$2$$$ and $$$3$$$, thus adding up his score to exactly $$$p_1$$$. Finally, players $$$2$$$ and $$$3$$$ can play $$$p_2 - (p_1-(p_2-p_3))/2$$$ draws anong them, after which their scores become $$$p_2$$$ and $$$p_3$$$ respectively. Thus, it is possible that all rounds played ended with draws, making answer equal to $$$(p_1+p_2+p_3)/2$$$.
Implementation in C++: 261998652
Problem B: idea by prvocislo, prepared by prvocislo
We will say that the array is $$$k$$$-lonely if $$$a_i|a_{i+1}| \ldots |a_{i+k−1}=a_j|a_{j+1}| \ldots |a_{j+k−1}$$$ is true for any two positive integers $$$1 \leq i,j \leq n−k+1$$$. Let $$$A$$$ be the maximum value an element in array $$$a$$$ can have.
how to check if the array is $$$k$$$-lonely in $$$O(n \log A)$$$?
if the array is $$$k$$$-lonely, the array is also $$$k+1$$$-lonely
binary search the answer :)
If the array is $$$k$$$-lonely, then since $$$a_i | \ldots | a_{i+k} = (a_i | \ldots | a_{i+k-1}) | (a_{i+1} | \ldots | a_{i+k}) = (a_j | \ldots | a_{j+k-1}) | (a_{j+1} | \ldots | a_{j+k}) = a_j | \ldots | a_{j+k}$$$, the array is also $$$k+1$$$-lonely.
You can check whether an array is $$$k$$$-lonely in $$$O(n \log A)$$$ by calculating the OR of every segment of length $$$k$$$. You can do this by iterating $$$i$$$ from $$$1$$$ to $$$n-k+1$$$ and mantaining an array $$$t$$$ of size $$$\log n$$$ where $$$t[j]$$$ will be equal to the number of elements from $$$a_i, ..., a_{i+k-1}$$$ that have the bit $$$2^j$$$ set. For $$$i = 1$$$ we can calculate this array in $$$O (k \log A)$$$ and then when moving $$$i$$$ to the right, we can update the array in $$$O (\log A)$$$ complexity and we can also calculate the OR of all elements in the segment, using the array $$$t$$$, in $$$O (\log A)$$$.
Once you have a checking function that runs in $$$O (n \log A)$$$, you can binary search the answer in $$$O(n \log A \log n)$$$ time, which is fast enough to pass.
Implementation in C++: 261999140
There also exists a nice $$$O(n \log A)$$$ solution, you can try to find it and get AC with it too :)
Try calculating the lower bound on the total loneliness for each bit separately. Then the maximum of these is the answer.
Originally the problem had the same constraints, but you could also insert up to one arbitrary number in the array and find the minimum loneliness you can achieve in this way. It was proposed as the problem C. However, since the original B turned out to be too hard, this problem was made easier and shifted to this position.
Problem C: idea by prvocislo, prepared by prvocislo
$$$n$$$ is even. What is the obvious upper bound on the number of the local maximums?
Right, it is $$${n \over 2} - 1$$$. We can actually achieve this value for any permutation.
Consider $$$p_1 = n$$$. Can you find $$$q$$$ such that all other odd positions will be local maximums?
We can easily prove that the sequence can have at most $$${n \over 2} - 1$$$ local maximums, because the corner elements can't be the local maximums and no two consecutive elements can be local maximums. Let's see how we can achieve this upper bound.
Let's consider the case when $$$n$$$ is at odd position in the original array first. We will construct a permutation $$$q$$$ such that the resulting array $$$a$$$ will have local maximums at all the odd positions except the first one. We can do this by placing the numbers $$${n \over 2} + 1, {n \over 2} + 2, \ldots n$$$ at the odd indexes in $$$q$$$, giving the bigger numbers to the indexes with smaller $$$p_i$$$, and placing the numbers $$$1, 2, \ldots, {n \over 2}$$$ at the even indexes in $$$p$$$, giving the smaller numbers to the indexes with bigger $$$p_i$$$. Then since $$$n$$$ belongs to an odd index, the $$$a_i$$$ for each odd $$$i$$$ will be at least $$$n + 1$$$ while the $$$a_i$$$ for each even $$$i$$$ will be at most $$$n$$$. So every element of $$$a$$$ at odd position, except for the corner, will be a local maximum. This means we will have $$${n \over 2} - 1$$$ local maximums, which is optimal, as we noitced above.
We can get the solution for the case when $$$n$$$ is at even position analogously. For example, by reversing the permutation $$$p$$$, calculating the right permutation $$$q$$$, reversing them again and printing this $$$q$$$ as the answer.
Time complexity: $$$O(n \log n)$$$ because of sorting. Actually, since you are sorting a permutation, you can do it in just $$$O(n)$$$ but it's not necessary.
Implementation in C++: 261999352
Problem D: idea by prvocislo and TimDee, prepared by prvocislo and TimDee
Let $$$m$$$ be value we want to find. What values can $$$m$$$ take?
Look at the maximum value in array $$$a$$$.
Can you find the maximum value in array?
Think about the segment containing the maximum value.
Can you finish the problem in $$$n$$$ queries?
Let's denote maximum value in array $$$a$$$ as $$$mx$$$. Since the element with maximum value will belong to some segment, then if $$$m$$$ exists, $$$m$$$ will be divisible by $$$mx$$$. Obviously, $$$m$$$ can't be greater than $$$n \cdot mx$$$, so now the candidates for value of $$$m$$$ are $$$mx, 2 \cdot mx, 3 \cdot mx, \dots, n \cdot mx$$$.
To find the value of $$$mx$$$ we can query $$$?$$$ $$$1$$$ $$$n \cdot i$$$ for each $$$1\leq i \leq n$$$ and $$$mx$$$ will be equal to such $$$i$$$, querying which will give $$$n$$$ as the answer.
We can check each of $$$n$$$ possible values in $$$k$$$ queries, but that wouldn't fit in query limit.
Actually, since the length of each segment in partition will be greater than or equal to $$$\frac{m}{mx}$$$, and there are exactly $$$k$$$ segments, we can get a simple inequality $$$k \cdot \frac{m}{mx} \leq n$$$ (since sum of lengths of segments is exactly $$$n$$$), which means $$$m$$$ can not be greater than $$$mx \cdot \lfloor{n/k}\rfloor$$$, so it is enough to check first $$$\lfloor{n/k}\rfloor$$$ candidates for $$$m$$$ in $$$k$$$ queries each. Total number of queries used would be $$$n + k \cdot \lfloor{n/k}\rfloor$$$ which doesn't exceed $$$2n$$$.
Implementation in C++: 261999488
Problem E: idea by prvocislo, prepared by prvocislo
Forget about graphs and data structures, there exists a simple $$$O(n)$$$ solution.
Find the number of pairs with $$$l = r$$$ for which you can sort the permutation.
Okay now that you have the special case handled, let's proceed to the general case. Find the minimum and maximum number that need to be swapped. Write down the inequalities that $$$l$$$ and $$$r$$$ have to satisfy so that we can swap these two elements with some other elements. This is the obvious necessary condition, right?
Right, so if $$$l \neq r$$$ and additionally, $$$l$$$ and $$$r$$$ satisfy the inequalities mentioned above, is it enough?
Yes, it is enough. But you can try to find the proof too :)
Let's consider the pairs $$$l, r$$$ that have $$$l = r$$$ first. Then you can swap each $$$x$$$ with at most one other element, $$$l - x$$$. So if $$$i \neq p_i$$$ for some $$$i$$$, then we need to be able to swap the element $$$i$$$ with the element $$$p_i$$$, so it must hold that $$$l = i + p_i$$$. This is obviously also a sufficient condition, so it's enough to just find all $$$i + p_i$$$ for $$$i \neq p_i$$$, if there exist more then one different value, there's no good pair with $$$l = r$$$, if there's exactly one different value, there's exactly one good pair with $$$l = r$$$ and otherwise there are $$$2 n$$$ such pairs.
Now let's count the pairs with $$$l \neq r$$$. If the array is sorted already, all pairs of $$$l, r$$$ are good. From now, consider only the case when the array isn't sorted yet.
Let $$$L$$$ be the smallest value such that $$$p_L \neq L$$$ and $$$R$$$ the largest such value respectively. We obviously need to be able to swap $$$L$$$ and $$$R$$$ with some other values.
Note that $$$L \neq n$$$ and $$$R \neq 1$$$, otherwise the array would be sorted already. Now we can get the inequalities $$$l \leq L + n$$$ and $$$R + 1 \leq r$$$, those are the necessary conditions for being able to swap the numbers $$$L, R$$$ with at least one other element.
We can actually prove that these are the sufficient conditions too. If $$$l, r$$$ satisfy these conditions, then for any number $$$X$$$ in the range $$$[L, R-1]$$$, we can find an $$$x$$$ in the range $$$[l, r]$$$ such that $$$1 \leq x - X \leq n$$$ and then we can swap the numbers $$$X$$$ and $$$X + 1$$$, while not affecting any other element, by swapping $$$X$$$ and $$$x - X$$$ first and then swapping $$$X + 1$$$ and $$$x - X$$$. Thanks to this, we can sort the whole range of values between $$$L$$$ and $$$R$$$ — while the array isn't sorted, we will always find the smallest index $$$i$$$ that doesn't have the right value and keep swapping the value $$$p_i$$$ with the value $$$p_i - 1$$$, so eventually we will get $$$p_i = i$$$ and we can continue sorting on the right.
So it's enough to just count the number of pairs $$$l, r$$$ such that $$$l \neq r$$$, $$$l \leq L + n$$$ and $$$R + 1 \leq r$$$, add it to the answer and print it.
All of this can be done in time and memory complexity $$$O(n)$$$.
Implementation in C++: 261999566 (I used set and therefore the time complexity is $$$O(n \log n)$$$ because it was more comfortable)
Problem F: idea by prvocislo, prepared by prvocislo
What are the possible pairs of $$$\gcd$$$'s of the two arrays we can have after some swaps?
For every pair $$$(X, Y)$$$ such that $$$X$$$ divides $$$a_1$$$ and $$$Y$$$ divides $$$b_1$$$, let's calculate the total number of indices $$$i$$$ such that we can have $$$X | a_i$$$ and $$$Y | b_i$$$ (either with or without the swap), and the minimum cost of swaps to achieve this. This is all we need to solve the problem, right?
Write for each $$$i$$$ the conditions that the pair $$$(X, Y)$$$ has to satisfy in order to add $$$i$$$ to the result/make swap on the position $$$i$$$. Use something like SOS-DP to add up all the values efficiently.
Let $$$k$$$ be the maximum value of $$$a_i$$$, $$$b_i$$$ on input ($$$10^8$$$). Let $$$D(k)$$$ be the maximum number of divisors a number in range $$$[1, \ldots, k]$$$ can have and $$$P(k)$$$ the maximum number of prime divisors such number can have.
Let's think about how to solve one query (with $$$M$$$ coins) for now. Assume that in the optimal solution, we never swap $$$a_1$$$ and $$$b_1$$$. In the end, we will just run the same solution on input where $$$a_1$$$ and $$$b_1$$$ is swapped and $$$M$$$ is decreased by $$$c_1$$$, and then we will take the maximum of the two values these two runs will find.
So now, in the optimal solution, the gcd of $$$a$$$ is always a divisor of $$$a_1$$$, and the $$$\gcd$$$ of $$$b$$$ is a divisor of $$$b_1$$$. Let's start by factorizing the two numbers in $$$O(\sqrt k)$$$.
Now we will precalculate something in order to be efficiently able to determine for every $$$X$$$, a divisor of $$$a$$$, and $$$Y$$$, a divisor of $$$b_1$$$, whether we can have $$$\gcd(a_1, \ldots, a_n) = X$$$ and $$$gcd(b_1, ..., b_n) = Y$$$ simultaneously (and also the minimum cost of making it so). Then we can obviously answer the query by finding the best pair with sum at most $$$M$$$.
Let's create new two dimensional arrays $$$P$$$ and $$$S$$$ of size $$$D(a_1) \times D(b_1)$$$. We will use $$$P$$$ to be able to tell the number of indexes $$$i$$$ such that we have either $$$X | a_i$$$ and $$$Y | b_i$$$ or $$$X | b_i$$$ and $$$Y | a_i$$$. If this count won't be $$$n$$$, then obviously we can't have $$$X$$$ and $$$Y$$$ as $$$\gcd$$$'s of $$$a$$$ and $$$b$$$. Also, we will use $$$S$$$ to tell us the sum of costs of all swaps we need to perform to have $$$X | \gcd(a_1, \ldots, a_n)$$$ and $$$Y | \gcd(b_1, ..., b_n)$$$.
Now how to make two such arrays efficiently? It is obvious that if the pair of $$$\gcd$$$ s $$$(X, Y)$$$ is consistent with some indexes in the original array, then for every pair $$$(x, y)$$$ such that $$$x|X$$$ and $$$y|Y$$$, this pair of $$$\gcd$$$s is also consistent with those indexes (and maybe even more, also maybe some swaps just became unnecessary, but the point is, it doesn't get worse). So if we want to add some value to a pair, we also want to get it added to all its divisors. That's why, in order to calculate the arrays efficiently, we will first add some values on some positions and then do something like $$$2D$$$ prefix sums — for every cell $$$(x, y)$$$ we will sum the values for all pairs $$$(X, Y)$$$ such that $$$x | X$$$ and $$$y | Y$$$ and update its current value with it. Assuming this is going to happen in the end, let's look at every $$$i$$$ and consider what pairs are "good" for this index — with or without the swap:
a) If $$$X$$$ divides $$$a_i$$$ and $$$Y$$$ divides $$$b_i$$$: For this type of pairs, we don't need to make any swaps on this index. Let's add $$$1$$$ to $$$P[\gcd(a_1, a_i)][\gcd(b_1, b_i)]$$$ to indicate that for all $$$(X, Y)$$$ such that $$$X|a_i$$$ and $$$Y|b_i$$$, we don't have to perform any swaps at the position $$$i$$$, the index is good as it is.
b) $$$X$$$ divides $$$b_i$$$ and $$$Y$$$ divides $$$a_i$$$: In this case we will add $$$1$$$ to $$$P[\gcd(a_1, b_i)][\gcd(b_1, a_i])]$$$ and $$$c_i$$$ to $$$S[\gcd(a_1, b_i)][\gcd(b_1, a_i)]$$$ to indicate that if we pick $$$X$$$, $$$Y$$$ such that $$$X|b_i$$$ and $$$Y|a_i$$$, we can make index $$$i$$$ good if we swap $$$a_i$$$ and $$$b_i$$$.
c) $$$X$$$ and $$$Y$$$ both divide both $$$a_i$$$ and $$$b_i$$$: To avoid counting both of the previous cases and therefore overcounting, we will add $$$-1$$$ to $$$P[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$$$ and $$$-c_i$$$ to $$$S[\gcd(a_1, a_i, b_i)][\gcd(b_1, a_i, b_i)]$$$ (we have to undo paying for the swap since in this case we actually don't have to pay for it, but it falls under the case b) too).
This step can be done in $$$O(n \log k)$$$.
Now let's fix the arrays $$$P$$$ and $$$S$$$ so they store the actual values, not just the values we need to add.
We will go through all primes $$$p$$$ dividing $$$a_1$$$ and update $$$P[X][Y]$$$ with $$$P[p \cdot X][Y]$$$ and $$$S[X][Y]$$$ with $$$S[p \cdot X][Y]$$$, similarly for all primes dividing $$$b_1$$$. If we make those updates in the right order, we achieve that $$$P[x][y]$$$ is the sum of all original values $$$P[X][Y]$$$ for all the pairs $$$(X, Y)$$$ such that $$$x|X$$$ and $$$y|Y$$$ like we wanted (and we can do the same for $$$S$$$).
By careful precalculation of divisors and their order while factorizing, we can do this step in $$$O(D(k)^2 P(k))$$$. Some efficient implementations with extra log might pass also, but you will have to be more careful.
For multiple queries, after precalculating the possible sums of $$$\gcd$$$ s and their costs, you can sort them and use binary search to answer the queries.
Time complexity: $$$O(n \log k + \sqrt k + D(k)^2 P(k) + D(k)^2 \log D(k) + q \log D(k))$$$ Memory complexity: $$$O(n + D(k)^2 + P(k))$$$
Implementation in C++: 261999743
Fun fact: While making the original proposal, I invented a version of this problem with lower constraints and thought it could be nice Div2C. Few days later, while I was on a walk, I realized this solution exists, so we decided to try to propose it as the hardest problem.
Auto comment: topic has been updated by prvocislo (previous revision, new revision, compare).
first. please don't downdoot me
also I think B was a very nice problem
you have a great growth within 10 months on your profile how do you manage to do so?
I appreciate it broski but I have also done a lot of leetcode so, between the two platforms, it is normal growth. I think that leetcode is better than codeforces when you are beginning 100%.
will surely try leetcode because i have barely any growth on cf. any tips?
don't waste time or energy learning advanced stuff, just focus on simple 9th grade math, logic and thinking. after u got better at that(rating around 1000), learn prefix sums, sets, lower/upper bound
yup i kind of couldn't even get 1st problem here in this contest
In my opinion, leetcode is the best way to start competitive programming because it introduces the most common competitive programming concepts (greedy, binary search, dp, graphs/trees, etc etc) through more or less straightforward problems. The good thing about this is that you aren't gonna have to do some weird math things while solving leetcode dp problems, for example. You can just focus on learning dp. Another benefit of leetcode is that it has a much bigger community than cf. If you get stuck on a problem, you will have much more than just a single editorial to read. There are videos, writeups, and there is even a solutions tab that you can use to understand the problem.
If I were you, I'd go to https://neetcode.io/roadmap and just start working through that list. NeetCode, the guy who made that website, has great explanations for each problem. Once you finish that list, start doing random mediums, and when you feel comfortable with those, start trying some hards. When I was grinding out mediums, I'd try to limit myself to 45 minutes and then I'd look at the solution.
Make sure you're doing the weekly and biweekly contests while you're practicing. Once you reach a 2000+ rating, I'd say that you should start practicing on some more serious competitive programming websites. 2000 rating should get you to specialist on codeforces at least.
will surely try so
Thanks a lot man, very helpful :)
Yes I agree, I did Leetcode for a few months and now codeforces seems much more approachable to me. I still have a lot to learn, but at least I can now understand what topics, and how to learn them
:)
Growth starts from the point you feel like quitting. Do leetcode but don't leave cf. Leetcode contests are very good, try that also.
true that my growth has just been downwards wanted to quit but did that once and ended up in not so good institution so won't do that again
I am not able to solve problem A. Can you help me with the logic. I couldnot understand the editorial. only got -1 part. and how do you come up with such logic.
So you understand that if the sum is odd, the answer must be -1. Let's show that if the sum is even, the answer is never -1. In order for p1 + p2 + p3 to be even, all 3 must be even or 2 / 3 of them must be odd. We can achieve all possible (p1, p2, p3) when p1, p2, p3 are even through just wins (aka by adding 2 to each one independently). Now for the case where 2 / 3 of them are odd, we can just throw in a draw between the two which we want to be odd (add 1 to each), and we can then keep adding 2 to each one of them and we can see that, by doing this, we can achieve all (p1, p2, p3) where 2/3 of them are odd. So whenever p1 + p2 + p3 is even, the answer is never -1.
Now that we know that, how can we find the max number of draws? Well let's try to take draws from the two greatest elements in (p1, p2, p3). You can think of this intuitively like this: if you take a draw (that is subtract 1) from the two greatest elements in (p1, p2, p3), you bring the elements in (p1, p2, p3) closer together. If the elements are closer together, there is more "drawing potential" since if the elements are all equal to each other, we can guarantee that all the games can be draws (we can draw p1, p2 then draw p2, p3 then p1, p3 and then our elements become (p1 — 2, p2 — 2, p3 — 2) and we can do this down to 0). Hopefully the intuition here makes sense.
So the algorithm is just sort (p1, p2, p3) and while the second greatest element is > 0, take a draw between the first and the second greatest elements and resort the list.
Don't focus too much on the proof of div. 2 A in contests though. This comment doesn't even prove the greedy algorithm but rather shows what the intuition to get there might be. Do your best to solve A by educated guesses.
Is the math written in the solution correct:
I'll just put the scores in here:
This is what the math in the bonus states the answer should be. I get that there can be another draw between p2 and p3. Just wanting to know whether I'm doing the math wrong or the math written in the bonus question is incorrect.
looks right to me
But I did the above calculation for the case where the final scores are 3 4 5. Yet the final result on following the calculations is coming out to be 3 3 4. Seems like there's a typo in the bonus hint then.
Where are you confused? You wrote out 5 draws to get to 3 3 4 and you can add another draw to get to 6 draws at 3 4 5. The answer is min( (3 + 4 + 5) / 2, 3 + 4), which is 6
Deleted
If you want the explanation for the $$$O(1)$$$ solution, it goes like this:
As, we are always increasing $$$p_1+p_2+p_3$$$ by $$$2$$$ ($$$1,1$$$ in case of draw and $$$2,0$$$ in case of win), the invariant is pretty clear, i.e.., $$$(p_1+p_2+p_3)\%2 = 0$$$ for a valid game.
Now, we have $$$p_1 \le p_2 \le p_3$$$, so we can always have atleast $$$p_1$$$ draws. Thus, from $$$p_2$$$ and $$$p_3$$$, we have to remove $$$p_1$$$ points, leaving us with $$$p_2+p_3-p_1$$$ points. Obviously, in the most optimal case, we could have $$$(p_2+p_3-p_1)/2$$$ more draws (if we had equal points left for both), but this is not necessarily the case as it is possible that $$$p_2 < (p_2+p_3-p_1)/2$$$, in such a case, we can add $$$p_2$$$ to the score. So my final $$$O(1)$$$ solution looks like:
1) If $$$(p_1+p_2+p_3)\%2 \ne 0 \implies$$$ No solution possible.
2) Otherwise, the answer can be found out using the expression $$$p_1 + min(p_2,(p_2+p_3-p_1)/2)$$$.
Hope this helps!
Thank you
could you explain this claim in detail ? if the array is k-lonely, the array is also k+1-lonely .
Sure. If we look at this problem bit by bit, there are two cases:
The ith bit is not set anywhere in the array. If this is the case, we can think of the array as [0, 0, 0, 0 ...] where array[j] represents whether or not the jth element in the original array has the ith bit set. The or of all subarrays in this array is 0 so every k works.
The ith bit is set in some places in the array. We can think of our set bit array as [0, 1, 1, 0, 0, 1, 0, 1] or something. In order for some k to work, it must be the case that every subarray of length k contains at least 1 set bit. This is true because there is at least 1 subarray of length j (1 <= j <= n) that has at least 1 set bit, so therefore all subarrays of length k must contain at least 1 set bit for this k to work. If every subarray of length k contains at least 1 set bit, then surely every subarray of length k + 1 contains at least 1 set bit. So if k works, k + 1 works too.
thanks got it !
idk why in B i' didn't think of binary search
can someone please the logic of this solution for B: 261346413, I'm not getting it
EDIT: got it
imagine there exists a bit j, such that $$$x-1$$$ consecutive elements don't have that, I claim that the answer is at minimum x.
why? imagine the answer is x-1(or anything less), then by the pigeon-hole principle there exists at least 1 segment where that bit hasn't occurred, thus its OR is different with one segment that has it. now for each bit from 0 to 20, find the longest subarray where no elements have that bit, and take the maximum of all of them in the answer.
Look at the problem bit by bit: in order for all of the subarrays of length k to have the same or, for each bit, there has to be at least 1 of them in each subarray or there has to be 0 of them in all subarrays (aka 0 of them in total).
For example, if we have the array [1,0,0,1,0,1], and we try to have k = 2, well there is a subarray of length 2 that doesn't have an on bit and the rest of the subarrays have at least 1 on bit. So k = 2 can't work. Looking at a few more examples, you will see that k has to be the maximum distance between consecutive 1s so that once a subarray loses a 1, it will surely gain another 1.
The answer will be the max of these maximum distances for each bit that is present in the array. If a bit is not present in an array, we can disregard it.
thx for the explanations, I just understood how it works and it took a while to write the edit, sorry for the waste of time, maybe someone doesn't understand my explanation and yours is more understandable, sorry for the inconvenience
haha no problem broski, the more explanations the better
SO, for example 2 0 4 0 2, why is the answer not 3, but 4??
for 2 bit, the array is [1, 0, 0, 0, 1]
Ahh, my bad !!!. Was thinking from another angle . Got it, thanks. Will try more next contest :)
Interesting, I thought of binary seraching for B but couldn't come up with the NlogA traversing algorithm, so instead I stumbled on the NlogA solution.
C is really good
Wow rating changes and editorial were kinda fast... speedforces
I used segment tree for B. I am sooorry ;).
that's what happens when u learn something too soon, it could be solved using just prefix sums for query, or sparse table at worst, a segment tree...
Haha my solution used sparse table. The core idea is that range
or
has a similar property to rangeminimum
, that is a range can be split into two overlapping subranges and merge the result.me too. what's the complexity?
Can you please look into my code and tell why its giving me MLE i m not sure what is going wrong 261444005
I couldn't understand the logic, nor the reason of mle
It is binary search on all values of K,it led to TLE during contest. So i tried to optimise it using hashing for previous values of K for any index or the maximum subarray of size K' form the same index. So here is the first iteration: from B.S--> K=3 i.Since its first iteration than map will be empty. ii. For all subarray of size K=3,we also can hash the OR for all subarrays from an index i, of size t such that t<=K (i.e 3,2,1) which is why i used the
map[(index,K_size)]=OR_value
. iii. Theprev
is just for checking if there are different OR.iv.Next time when BS gives K=5,then i found the max(t) such that (t<=K) from the map using
findK
function.If it finds it then we will use it for all index that it has already computed and for indexes it hasn't we will compute it normally.This led to MLE
Finally understood the code, I believe there is a way to set up the inputs such that the map will take n² pairs of numbers leading to tle
Not really too soon, I think learning it is good but overusing it is really problematic
Me too!! Used binary search with segment tree!!
B without binary search: 261388922
prvocislo orz <3
berr orz <3
I think for Problem C hint 2 should be n/2-1.
prvocislo
Thank you, I will fix it
C was nice from the proof and math work side
in C 2nd hint
n/2 -1 not +1
B with segment tree and binary search 261367730
Can someone explain the intuition, rather than proof, behind problem C?
"... Then since $$$n$$$ belongs to an odd index, the $$$a_i$$$ for each odd $$$i$$$ will be at least $$$n+1$$$ while the $$$a_i$$$ for each even $$$i$$$ will be at most $$$n$$$."
While I can indeed verify this statement after the contest, I found it rather counter-intuitive that a simple greedy method would work, so I quickly dismissed the thought of trying it out. Any thoughts?
The fact that n is even should signal that maybe you can somehow split numbers into two groups.
Secondly, it'd fairly common to sort permutations in opposite directions (ascending/descending) and match them greedily.
Also worth noting, it's very easy to get sums of all elements of final array to be equal to (1+n), by matching $$$p_i$$$ with (1+n-$$$p_i$$$).
This was my thought process during the contest, it's really just 3 standards ideas combined together. If you write all these out at some point you'll notice that you can ensure (n+2) is reachable in n/2 points so ot suffices to make the others no greater than n+1, which like we said has an easy construction.
Makes sense, thanks for this
I ended up coming up with the editorial solution and another in the contest, so I'll describe them both:
Editorial Intuition We suppose $$$n$$$ has odd index and then try to make all odd elements into peaks. Is it possible? The worst case might be when $$$1, 2, 3 ... n/2-1, n$$$ are the elements in the odd positions and $$$n/2, n/2+1, ... n-1$$$ are the elements in the even positions. We can even go further and assume $$$n-1$$$ is next to $$$1$$$ and $$$2$$$, and $$$n-2$$$ next to $$$2$$$ and $$$3$$$ and so on.
Obviously let's assign smaller labels to the ones in the even position and larger labels to the ones in the odd positions. Well $$$n-1$$$ gets the label $$$1$$$, so $$$1$$$ and $$$2$$$ need the labels $$$n$$$ and $$$n-1$$$ respectively, and then continuing in this way we can make the observation that you call counter-intuitive.
My Intuition We can construct $$$q$$$ so that all the $$$a_i$$$ are equal (make $$$q_i + p_i = n+1$$$).
Now we want to reorder some elements of $$$q$$$ such that all the odd/even elements become peaks. Since all elements of $$$a_i$$$ are equal at this point, we just need to reorder the elements of $$$q$$$ so that the ones in odd indices increase, and the ones in even indices decrease (or vice versa).
There's a lot of ways to do this, the first one that came to my mind is just suppose that $$$n$$$ appears at an even index $$$2k$$$ and sort the odd indices in increasing order of value.
Then do $$$q_{o_1} \rightarrow q_{o_2} \rightarrow q_{o_3} \dots \rightarrow q_{2k} \rightarrow q_{o_1}$$$.
i.e. the smallest odd index gets value of the next larger odd index, etc. and the largest odd index gets the value of n.
Nice alternative approach :)
So after making the sum equal at all indices, we have to solve the problem: increase values at even indices and decrease values at odd indices. This (for me at least during the contest) was not helping to explain why there will always be a solution that gives n/2 — 1 peaks (though i agree it is easy to get the solution for n/2 — 1 peaks this way). We still need the editorial approach to build the worst case and show that n/2 — 1 peaks will always exist (for best q). Can you elaborate if you could show n/2 — 1 peaks always exist with your intuition?
With my approach, first we get a permutation $$$q$$$ that makes all values of $$$a$$$ equal. Then we increase the value of $$$q_i$$$ at all odd indices, without increasing any value at an even index. (In fact, we decrease the value at one of the even indices.)
Therefore $$$a_i$$$ increases for odd $$$i$$$, and doesn't change change (or decreases) for even $$$i$$$. Therefore all odd indices will become peaks and we will have $$$n/2 - 1$$$ peaks.
This is pretty much independent of the editorial approach.
in problem C hint 2, it should have been n / 2 — 1 : )
B is a very nice problem.
My idea for C is slightly different and imo cleaner. Its also much easier to prove why my idea actually works.
Here's my code: 261430375
Alright so we know that the answer is at most $$$\frac{n}{2} - 1$$$ (the proof is given in the editorial)
We will of course construct a solution that has exactly these many local maximums, and that has to be optimal.
So here's the idea. Before thinking about making some indices local maximums and some minimums, can we make everything equal by mapping the given permutation $$$p$$$ to a permutation $$$q$$$?
Yes we can! We just map $$$p[i]$$$ to $$$q[i] = n + 1 - p[i]$$$, and the sum is going to be $$$n + 1$$$
Now, without loss of generality let us assume that $$$p[j] = 1$$$ and $$$j$$$ is odd. Then we want to make all the elements in the even positions the local maximums. Incase $$$j$$$ was even, we'd make the positions at odd indices local maximums. How do we achieve this?
We iterate over the elements at even indices in increasing order of their value. Let us say that the value of the current element is $$$x$$$. Then we perform the following operation -
(Here $$$pos[x]$$$ is the index of the value $$$x$$$ in $$$p$$$, ie. $$$p[pos[x]] = x$$$)
And we are done! The resulting array $$$q$$$ is our answer!
Note that $$$q[pos[i]]$$$ > $$$q[pos[j]]$$$ for $$$i < j$$$
And since $$$q[pos[1]]$$$ > $$$q[pos[x]]$$$, after the swap $$$pos[x]$$$ becomes a local maximum (as all the elements were same initially and after the swap the value at $$$pos[x]$$$ increased)
And as we are swapping with increasing value's of x, the values at even indices become more than the values at their neighbours.
Hence the even indices are all local maximums.
Incase I explained something poorly, please let me know! And I'll try to help if I can. :D
great explanation sir : )
Excellent solution! I didn't get the part "We iterate over the elements at even indices in increasing order of their value." -> could you explain this part?
Overall, how did you come up with this thinking, if you could share your thought process!
Yeah, so lets take an example, lets say the array is this -
Here $$$p[2] = 1$$$, so we try to make values at odd indices local maximums.
The values at odd indices are $$${5, 6, 4}$$$.
Since we are going to iterate over increasing values, we go in the order $$$4 \rightarrow 5 \rightarrow 6$$$.
So we first
swap(q[pos[1]], q[pos[4]])
to get -Then we perform
swap(q[pos[1]], q[pos[5]])
to get -Then we finally perform
swap(q[pos[1]], q[pos[6]])
to get -And we are done!
Thanks!
Damn ! that's a nice observation
in problem A, what's the intuition behind if p1 + p2 > p3 , then the answer is (p1+p2+p3)/2 ? , I wasn't able to prove it, all I did was guess it based on the test cases
After giving it a thought, I was able to come up with this explanation, correct me if I'm wrong please.
Since each 2 points contribute to a game, (p1+p2+p3)/2 is the total number of games, and since we want to maximize the number of draws, we would consider all the games to be a draw.
ah yes and for the case p3>p1+p2 it is not possible to have all the matches draw
You can check out https://codeforces.net/blog/entry/129556?#comment-1149923 for an intuitive explanation :)
Thank you prvocislo for all the hard work <3
I have another solution for F, which run in 796ms, but I don't know the time complexity for it
https://codeforces.net/contest/1973/submission/261433060
Idea: - Calculate least common multiple (lcm) for each pair a,b
- Calculate lcmv = gcd of all lcms
- Reduce a,b of each pair to gcd(lcmv, a), gcd(lcmv, b)
- Add cost of all elements with the same new a,b (From the observation that for any i,j, if ai == aj and bi==bj then we must either swap i,j or not swap any)
- Sort all triple (a,b,c) by a ascending, b ascending
- For each item, maintain a map of (a,b) => minc; with a,b is the current gcd of sequence a,b; c is minimum possible cost
- After that, we create the array of [(sum gcd value), (min cost)] ascending for both elements, and do binary search for each query
Can anyone explain problem A intuition? why are we drawing between two maximums?
Our task is to maximize the number of draws . So the first thought should be to assume if all games played are draw . We know each game played contributes 2 points to the total . So
total_games=(p1+p2+p3)/2
Our assumption fails if all games are not possible to be a draw . Only time this fails is if (p1+p2)<p3 . In this case p1 games are played between p1 and p3 and p2 games are played between p2 and p3 which result in draw . Further games which leads to a draw is not possible. So out final answer ismin(total_games,p1+p2)
can someone please tell why am i getting TLE on test2 in this submission
You only need to query K times for one iteration but in your case it can get >K times, Take K=1 case and all elements are same then in this case you are iterating n * ( n+n/2 + n/3 +n/4....) or n^2 logn which is clearly greater than n query .
Thanks
It seems that there's a typo in problem C, Hint 1.
"the number of the prefix maximums" -> "the number of the local maximums"?
prvocislo
What a talented prvocislo, writer of one of the best Div2 round. A great round and great problems.
I don't understand the Editorial for problem E. Isn't L + n > R + 1? it's very confusing
think i kinda understood it by algebra, but it doesn't look intuitive. can somebody explain the intutition?
By definition, the value $$$L$$$ is misplaced and wants to participate in some swaps to reach index $$$L$$$. If we set $$$l > L + n$$$, then there are no swaps that value $$$L$$$ can participate in. This is bad, so $$$l \leq L + n$$$. You can argue similarly for the $$$r$$$ constraint.
I solved the B problem using two pointers only. During the contest, I was missing an edge case that's why my code didn't get AC. But when I up solved and found the loophole. I managed to get AC using two-pointers.
Here is my submission: https://codeforces.net/contest/1973/submission/261450556
most 2 pointer problem can be solved using binary search, bs on the length of the subarray
C is amazing! Brilliant round!
Hey! Check out my video solutions for the contest. I've covered Problem A-D here: https://youtu.be/owawrSp2ywU
Thanks for the tutorial, it was really helpful.
Loved The B Problem.
My Binary Search Solution
in case anybody wanted it:
B with binary search: 261420803, without the use of any fancy data structure
B without binary search: 261423079, logic
The number of draws between p2 and p3 should be p2-(p1-(p3-p2))/2.
D is a very good problem.Interesting.
Can you explain why M will always be a multiple of N(size of the array)?
M is a multiple of MX(max element of the array)
Round is awesome. But error in Russian statement was fixed only after 5 minutes, and I spend that time solving wrong problem with wrong statement
can anyone explain me problem A. I could not understand the editorial. I got the -1 part but how do you guys come with such logic in the contest.
You could check my comment in this thread for a detailed explanation of the $$$O(1)$$$ solution, and ask me if you have any questions or if you feel like I've made any mistakes. I could get this solution only an hour after the contest ended though :(
In problem B why can we say if an array is k-lonely then it is k+1-lonely too??
Update: nvm I got it
fxxk problem B, I use "bin" function many times caused the TLE, fxxk!! After trying for 10+ times, I preprocess the bin of each num, and then accepted! WTF!
In Problem B, my solution is giving tle verdict while another solution get accepted using my same idea. Can someone help me finding out mistake in my code.Thanks in advance.
My Submission
Accepted Submission
Maybe in solve1 you should pass reference to avoid copying
yes,it works.thanks
can someone tell me why https://codeforces.net/contest/1973/submission/261471081 tle? I think the complexity of it is o(20*n*logn) is there anything wrong with it?
you should only initialize the part of the array you use. (memset part) and you should learn std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr) and stop using std::endl.
thx bro, its ac now
I am not able to understand the solution for problem C.
It is saying that
We can do this by placing the numbers
$$$\frac{n}{2}+1,\frac{n}{2}+2,…n$$$at the odd indexes in q, giving the bigger numbers to the indexes with smaller pi, and placing the numbers
$$$1,2,…,\frac{n}{2}$$$at the even indexes in p, giving the smaller numbers to the indexes with bigger pi. Then since n belongs to an odd index, then ai for each odd i will be at least n+1 while the ai for each even i will be at most n.
Let us suppose $$$p_3 = 1$$$ and we choose $$$q_3 = \frac{n}{2}+2$$$, then $$$a_3 = \frac{n}{2}+3$$$, which is less than $$$n+1$$$ and similarly, we can show it for even index.
Is there anything that I am missing out here? If someone can help me, I would highly appreciate it.
Thanks
why ai|...|ai+k=(ai|…|ai+k−1)|(ai+1|…|ai+k) is correct ? when I expanded these term, it didn't match.
Because of a property of bitwise-or ($$$a_i | a_i = a_i$$$, also note that it is associative):
Thanks, I mistake bitwise-or for XOR.
| is the symbol for the bitwise OR
⊕ is the symbol for the bitwise XOR
& is the symbol for bitwise AND
it's always the case
The Rating Change and Editorial came in like 10 mins... Great Work Authors
In problem F the step to calculate "prefix sum" of $$$P$$$ and $$$S$$$ can also be some in $$$D(k) \sum D(d_i)$$$ somehow. Does anybody have some upperbound of this sum? It feels like it's some really small $$$D^3(k)$$$ or something.
I have some trouble understanding the given proof for the $$$O(1)$$$ solution for Problem A. I'll explain how I got that solution. Let us take an optimal solution (i.e., a solution with the max possible number of draws that corresponds to the given values of $$$p_1$$$, $$$p_2$$$, and $$$p_3$$$). The total number of games played is $$$\frac{p_1 + p_2 + p_3}{2}$$$. Let $$$a$$$, $$$b$$$, and $$$c$$$ denote the number of draws in the $$$A_1$$$ vs. $$$A_2$$$, $$$A_2$$$ vs. $$$A_3$$$, and $$$A_1$$$ vs. $$$A_3$$$ matches respectively, where the names of the players are $$$A_1$$$, $$$A_2$$$, and $$$A_3$$$. Since this is an optimal solution, the correct answer to the problem is $$$a+b+c$$$. Now, if it so happens that more than one of these players had wins (say, $$$A_1$$$ and $$$A_2$$$ both had nonzero wins — say, $$$k_1$$$ and $$$k_2$$$) — then, we could have repurposed them as $$$\min(k_1,k_2)$$$ more draws in $$$A_1$$$ vs. $$$A_2$$$ games, and one of them having $$$\mid k_2 - k_1 \mid$$$ wins instead, contradicting the optimality of our solution. Therefore, we may assume that only one of these players had wins (if any), say $$$w$$$ of them, in our optimal solution.
Suppose $$$A_3$$$ is the player who had all $$$w$$$ wins ($$$w \geq 0$$$) in our optimal solution. Then, $$$p_1 = a + c$$$, $$$p_2 = a + b$$$, and $$$p_3 = b + c + 2w$$$. Solving for $$$a$$$, $$$b$$$, and $$$c$$$, we get $$$a = \frac{p_1 + p_2 - p_3 + 2w}{2}$$$, $$$b = \frac{p_2 + p_3 - p_1 - 2w}{2}$$$, and $$$c = \frac{p_1 + p_3 - p_2 - 2w}{2}$$$. Verify that these values for $$$a$$$, $$$b$$$, and $$$c$$$ will be the same even if you assume $$$A_1$$$ or $$$A_2$$$ won all $$$w$$$ games! Note that we get integral solutions for $$$a$$$, $$$b$$$, and $$$c$$$, iff the number of odd numbers in $$${p_1, p_2, p_3}$$$ is even. If this is not the case, we output $$$-1$$$, and finish.
Now, thanks to $$$p_1 \leq p_2 \leq p_3$$$, $$$w = 0$$$ (i.e., all games are draws) leads to a valid (i.e., nonnegative integer) solution for $$$b$$$ and $$$c$$$, and a valid solution for $$$a$$$ only if $$$p_1 + p_2 \geq p_3$$$. That is, if $$$p_1 + p_2 \geq p_3$$$, the answer we must output is $$$\frac{p_1 + p_2 + p_3}{2}$$$. The case left to deal with is when $$$p_1 + p_2 < p_3$$$. To make the value of $$$a$$$ nonnegative, the minimal value of $$$w$$$ to be set (we want a minimal value for $$$w$$$ as we want maximum draws) is $$$\frac{p_3 - p_1 - p_2}{2}$$$. With this setting of $$$w$$$, we get a valid solution $$$a = 0$$$, $$$b = p_2$$$, and $$$c = p_1$$$, so that the answer is $$$a + b + c = p_1 + p_2$$$. I wrote this solution (sadly, after the contest) and it was accepted.
Very nice explanation,loved it.
For Problem, C, can someone prove how the upper bound n/2-1 is always achievable, i.e., there always exists a permutation q such that the array constructed by summing individual elements of p and q will contain n/2 -1 local maxima?
Endpoints can't be local maxima, so the possible positions of local maxima is 2..n-1
(n — 2 positions)
2 local maxima can't be next to each other
=> Maximum n/2 -1 local maxima
So what? Question is not "why n/2 — 1 is at most value", but "why we can always can obtain n/2 — 1"
You see in this case, you can construct a sequence such that:
for $$$i \bmod 2 = p$$$ you'll have $$$a_i >= n + 1$$$
Otherwise you'll have $$$a_i <= n$$$
Where p is $$$0$$$ or $$$1$$$.
So then you'll find expect these numbers which is at position $$$1$$$ or $$$n$$$,you will have $$$i \bmod 2 = p$$$ is greater than both on the sides.
In solution editorial for problem B, the size of array t is log A (not log n). I'm confused so much reading that editorial.
for the question B, what am i getting wrong here: any corner cases or something?? or my logic is wrong?
https://codeforces.net/contest/1973/submission/261565983 i tried to debug but im unable to
here is the testcase where your code failed
it's giving 2 unstead of 3
Here's my O(20n) approach for B https://codeforces.net/contest/1973/submission/261367948
For problem F I wonder if it's necessary to swap a[1] & b[1] and solve twice, I think we can record the minimum and maximum cost to achieve a solution case and add the less of minimum cost and total cost minus maximum cost.
With this method I can solve some cases but got wa on test 10, and I cannot figure out what is wrong. For detailed implementation here is my submission: 261587221
Correctness Proof for Problem C Algorithm
Observation
There can be at most $$$\frac{N}{2} - 1$$$ local maxima (because boundaries cannot achieve this).
Constructing $$$\frac{N}{2} - 1$$$ Local Maxima
Even Positions (excluding $$$N$$$
Odd Positions (excluding (1))
Since there is only one $$$a_i = N$$$, the above discussion ensures that one of the above approaches must be correct.
259945476
Anyone why MLE??
I think the query function is making a lot of recursive calls (O(n * lg (n) * lg(n)) which is a lot. Maybe write it iteratively?
Problem C (Cat, fox And double maximum) Video Editorial (Audio : Hindi) YOUTUBE CHANNEL LINk :: --Click Here
the spoilers make the solutions hard to read
261627325 Anyone why does it fail??
For problem E, why the necessary condition is "l<=R+1" and "L+n<=r". I can't understand... What do you mean by "being able to swap L,R with anything"? Under such condition, we can just swap L with [1,n] and swap R with [1,n-R+L]. Can anyone further explain it? Thank you very much.
Sorry, I meant "to be able to swap $$$L$$$ and $$$R$$$ with at least one other element". The paragraph explaining this was a bit hard to understand, so I rewrote it a bit, hopefully it's clearer now.
Sorry, I'm still confused. $$$l\le L+1, r\ge R+1$$$ should be enough to swap $$$L,R$$$ with one other element like $$$1$$$, right?
$$$l \leq L + 1$$$ is stronger than $$$l \leq R + 1$$$, so some pairs $$$(l, r)$$$ for which you can sort the permutation may not satisfy your first condition. For example, in the last sample from the statement, the pair $$$(4, 5)$$$ doesn't satisfy your first inequality, yet you can still sort the permutation by choosing it. That's why you should look for another set of inequalities to describe the necessary condition.
Note that we don't care about $$$1$$$ or any other element in particular, we just want to be able to swap $$$L$$$ and $$$R$$$ with anything else, possibly two different elements.
Thanks for your reply!
I just realize it is $$$l\le L + n$$$ or $$$r\ge R+1$$$.
It's actually $$$l \leq L+n$$$ and $$$R+1 \leq r$$$. You need to be able to swap both $$$L$$$ and $$$R$$$ with at least one other element.
how is it guarantee we can swap L and R with at least one other element? Tutorial does not clarify this and I can't
Separated these conditions are useless, why if we combine them it's enough to swap them with at least one another?
https://codeforces.net/contest/1973/submission/261664728
Can someone check what's the issue with this?? I know I am bad in implementations.
Problem A
The last test case
1 1 10
.How this is possible ? Question says , first and second friend made two points by two draw with the third friend( One by each) . So the third friend should have made 2 points . How he managed extra 8 points ?
He wins 4 times again first friend
I think Problem B is high-quality.
Problem C was easier than B
C was more maths and problem solving based , B relied on knowledge more,i mean anyones who know segment tree or sparse would kill the problem .
For Problem C.
How did the no.of local maximas are atmost n/2-1?
For n=5
We've 2 maximas then how it is n/2-1
Got it
n will be always even
highly recommend this round cuz every problems have step-by-step hints so that we can solve the problem without relying too much on editorials. Wish to see in other rounds.
In problem B why can we say if an array is k-lonely then it is k+1-lonely? I don't understand why (ai|...|ai+k-1)|(ai+1|...|ai+k) = (aj|...|aj+k-1)|(aj+1|...|aj+k) in the editorial.
You know that $$$(a_i| \ldots |a_{i+k-1}) = (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) = (a_{j+1}| \ldots |a_{j+k})$$$ if the array is $$$k$$$-lonely (it follows from the definition), so then you also have $$$(a_i| \ldots |a_{i+k-1}) | (a_{i+1}| \ldots |a_{i+k}) = (a_j| \ldots |a_{j+k-1}) |(a_{j+1}| \ldots |a_{j+k})$$$ , thanks to the properties of bitwise OR.
I got it know. Thank you very much.
Can someone tell me how to solve the bonus2 in B? I'm just interested in it. Thanks.
I'll leave some hints on how to get to the solution.
binary search the answer, you can prove we can do it just like in the original solution.
what should be the number you are going to insert equal to?
that's right, it should be the OR of all numbers in the array $$$a$$$, since that's what every OR of subsegment of length $$$k$$$ should be equal to.
when binary searching and checking if the array can be $$$m$$$-lonely, just greedily insert the new number on the first position such that if you didn't insert it here, the array wouldn't be $$$m$$$-lonely anymore (you can find it by going from left to right and keeping an array of size $$$O(\log A)$$$ telling us what was the last time we saw this bit in some number in the array), then just check if the array is $$$m$$$-lonely.
Total time complexity will be $$$O(n \log n \log A)$$$.
Thanks! It helps a lot!
i am not able to figure out the checking if array is m-lonely part , how to check that in less than o(n*m) , i am so confused
B was a very good problem. Has a very reusable idea
Yeah I think it's great too,especially the two Bonus. Also D is pretty good, just interesting.
I have a weird WA in problem D when I add a line of code in the beginning:
if (n == k && k == 1) {cout << "! 1" << endl;continue;}
which will output the answer directly when n and k are both 1 and continue to the next testcase
following are two submitsions which only differ from the description above
https://codeforces.net/contest/1973/submission/263160320
https://codeforces.net/contest/1973/submission/263160243
Can someone teach me why, I'm new with interactive problems, thanks
problem B is also can be solved using segment tree and binary search
for problem E, i am not able to count the number of pairs $$$l, r$$$ such that $$$l \neq r, l \le L + n, r \ge R + 1$$$. Specifically, i don't know how to count when $$$L + n > R$$$. It seems that some pairs would be count more than once. 261999566 I can't understand the impementation.
what does $$$l, r$$$ denote? and why add those number to answer?
For problem E, the editorial only mentioned that such an $$$x \in [l, r]$$$ exists.
we can actually let $$$x = \max(l, X + 1)$$$ which is valid.
Assume that $$$x = \max(l, X + 1)$$$.
It's obvious that $$$x \ge l$$$. consider $$$x = l$$$ and $$$x = X + 1$$$ respectively.
in the case of $$$x = l$$$, $$$x < r$$$ beacause $$$l < r$$$.
otherwise $$$x = X + 1$$$, because $$$X \in [L, R - 1]$$$, $$$x = X + 1 \in [L + 1, R]$$$ and $$$r > R$$$ therefore $$$x < r$$$.
check whether $$$x - X \in [1, n]$$$. $$$x - X = \max(l, X + 1) - X$$$.
in the case of $$$X + 1 \ge l$$$, it equals $$$X + 1 - X = 1$$$.
otherwise $$$l > X + 1$$$, it equals $$$l - X$$$ which is greater than $$$X + 1 - X = 1$$$. Besides, $$$l \in [1, L + n]$$$ and $$$X \in [L, R - 1]$$$ so $$$l - X \le L + n - L = n$$$.