Привет, Codeforces!
Я и ooaa рады пригласить вас принять участие в Codeforces Round 922 (Div. 2), который состоится во Jan/30/2024 17:35 (Moscow time).
Этот раунд будет рейтинговым для участников, чей рейтинг ниже 2100. Участники с более высоким рейтингом могут принять участие вне конкурса.
Вам будет предложено 7-8 задач и 2 часа на их решение. Мы советуем вам прочитать все задачи. В раунде может встретиться 1 или более интерактивных задач. Рекомендуем прочитать этот пост.
Мы хотим поблагодарить:
- Akulyat за прекрасную координацию раунда.
- wuhudsm за то, что нашел, что предыдущая задача С уже встречалась на одном из раундов.
- A_G, bashkort, orz, Andreasyan, green_gold_dog, zwezdinv, EJIC_B_KEDAX, hopele555, makrav, sam571128, Undying, htetgm, wuhudsm, const, JustNik77, Chaska, Murinho, leoper, Ileonov за тестирование раунда и ценный фидбек.
- MikeMirzayanov и geranazavr555 за прекрасные платформы Codeforces и Polygon.
- Вас, за участие в этом раунде.
Всем удачи на раунде и высокого рейтинга!
UPD. Разбалловка: $$$500 - 1000 - 1250 - 2000 - 2500 - 3000 - 3250$$$.
UPD2. Поздравляем победителей!
Div. 2
Div. 1+2
Поздравляем участников, заславших первые решения по каждой задаче:
- А. EyadBT
- B. __jk__
- C. Golovanov399
- D. thisisnotaclone
- E. WLZ
- F. tute7627
- G. NetSpeed1
UPD3. Разбор.
As a tester, it's the first time I tested an actual Codeforces round!
orz
As a tester,the problemset is incredible!Hope you enjoy it :)
As a tester, it’s my first round that I tested, good luck to everyone!
As a tester, it is very good round! Good luck!
Lets goooo , its time i become pupil
I loved testing the round, problems are of high quality. Good luck!
5-6 or 7-8 tasks
You should read the blog which said
You will be given 7-8 problemsSj Body?
Sj Batya
-1 tasks anyway.
Score Distribution??
Score Distribution?? Edit : Very Balanced Score Distribution according to toughness..
Hoping to stay cyan
Why not aim higher and reach blue? :)
I don’t think a plus 150 is possible at 1456 for me, a -56 is very pills
As a tester, I hope you enjoy the round as much as I did.
As not tester, idk
As a tester, the problems are very good. I encourage you do participate in the round!
2 hours and 7 tasks :O
How to reach Expert?
How to reach expert ?
How to reach purple?
53 points to Master. Hope to be a master tonight!
53 points to master. Hope to be a master tonight!
As a tester, good luck to everyone! It's the first time i tested a round.
Score distribution?
Hopefully I move to green this time! Excited for this round! Btw which rating should I be to become a problem setter / tester?
You need to achieve twice your rating to be a problem setter.
So basically 2000? Wow alright. What about a tester?
No, you need to achieve master to purpose a contest/problems . Master's rating is 2100 or up, which is just twice your rating.
tibinyte2006 orz
You can be a tester at any rating, as long some contest setters know you and tell you test.
What will be the score distribution?
waiting for that tree based div 2 D since forever
Knowing Anton, I will be very surprised to see a segment tree in any of his problems
Lost 50 pt in previous div2. Hope to recover
are the round writers siblings?
Yes, we are. ooaa is my sister.
orz
Alice and Bob.
All the best guys! Hoping to reach 1300 today.
me too, Hoping to reach 1300 today! xD
ace5 will the score distribution be announced?
hope to become CM in this contest. Now only 72 rating.
As a participant, I hope I can get non negative delta again.
Hope not to drop down to pupil, spec is fine
GLHF
they write to read about interactive problems but dont give any, hope to see one today (ofc i wont be able to solve it)
good luck!
Is D that easy? 1000+ solves and I am not able to figure out from where to begin? :(
I have no idea how to start thinking about D!
Binary search? NO
Two Pointers? NO
DP? NO
Gready? NO
Graphs? NO
Range queries? NO
Math? NO
What is going through your head??? Why are you discussing problems before the end of the contest???
Not ended yet?
Sorry, that's quite weird, the round was extended for 10 minutes.
No worries ^^
The funniest thing is that D is actually binary search with dp (not sure about the intended solution, but I've solved it this way)
I also solved it that way.
Binary search on answer?
If so how to check if If the cost can be less than or equal to x? I was stuck at this point
DP, DP[i] is the minimum sum of blocked elements such that you covered all elements from 1 to i, i used segment tree to query minimums.
You can also just use a set instead of a segment tree. Since you only want the min value of dp in some range $$$[j, i]$$$ where $$$j$$$ is non-decreasing as $$$i$$$ increases, just keep the values in the relevant sliding window in the set and check for the minimum value.
I saw your code and I am not getting why you wrote that additional Prefix_sum[n+1]=Prefix_sum[n]
can you explain why that steps is crucial
Binary search the max sum of the segments. The best answer happens when the max of all segments is close to the sum of blocked elements.
Let's suppose we want to check, is it possible to make $$$cost \le x$$$.
We must erase some elements such that all remaining subarrays have $$$sum \lt = x$$$, and the sum of erased elements must be $$$\le x$$$.
So, we calculate $$$dp[i]$$$ = minimal sum of erased elements such that there is no range with $$$sum \gt x$$$ in $$$a[0..i]$$$. Then, $$$cost \le x \leftrightarrow dp[n - 1] \le x$$$.
can you also explain how you are finding the value of dp[i]?
My solution is a bit complicated (i believe there is a simpler one), but here it is:
First, if $$$x \lt max(a)$$$, there is no solution.
Let's define $$$dp[i][0]$$$ same as $$$dp[i]$$$ above, but with additional constraint: $$$a[i]$$$ is erased. $$$dp[i][1]$$$ is essentialy the opposite: $$$a[i]$$$ is not erased.
Base cases are: $$$dp[0][0] = a[0], dp[0][1] = 0$$$.
We calculate $$$dp[i][0]$$$ just as $$$min(dp[i - 1][0], dp[i - 1][1]) + a[i]$$$, since when we erase $$$a[i]$$$, we don't care about the range which ends before, we just know that it's sum $$$\le x$$$.
Finding $$$dp[i][1]$$$ is another task. We have the following relation:
$$$ dp[i][1] = min_{j} dp[j][0]$$$, where $$$j \lt i$$$ and $$$\sum_{k=j+1}^{i} a_i \le x$$$, since if we don't erase $$$a[i]$$$, it must be the end of a certain range (e.g. the entire range $$$[j + 1..i]$$$, because it's sum is less or equal than $$$x$$$).
The least suitable $$$j$$$ can be maintained during dp calculation with two pointers, and the desired value is just segment minimum of $$$dp[j][0]$$$, which can be found with segment tree (or minimum queue). The complexity of calculating such dp is clearly $$$O(n)$$$ or $$$O(n \log n)$$$, depending on data structure you use.
Code: 244130581
Got it. THanks for the explanation.
why in transition state of dp[i][1] no contribution of dp[j][1]?
and i did not understand why a[i] must be end of certain range , plz explain this also
as if a[i] is end element of some segment , then a[i+1] must be blocked element , how we assume this
are_you_tilted
When we calculate $$$dp[i]$$$, we consider only the prefix of $$$a$$$, which ends in $$$a[i]$$$. That's why in $$$dp[i][1]$$$ there's always a range which ends in $$$a[i]$$$ (because it's the last element so far, and it is not erased).
Why don't we use $$$dp[j][1]$$$? Consider any $$$j$$$ such that $$$\sum_{k=j+1}^{i} a[i]$$$ <= $$$x$$$. If we make transition from $$$dp[j][1]$$$, we continue a range which ends in $$$j$$$ now. But we actually don't know where this range starts, and we don't know, will it's sum be still less or equal than $$$x$$$ after continuing in up to the $$$i$$$.
For better understanding, consider the array $$$d$$$ built on a certain sequence of operations, where $$$d[i] = 0$$$ if we erased $$$i$$$th element, and $$$1$$$ otherwise.
For example, $$$d = [0, 1, 1, 0, 0, 1, 1]$$$. In terms of $$$d$$$, when we calculate $$$dp[i][1]$$$, we want to choose the start index of a consequtive segment of ones, end of which will be in $$$i$$$. That is, our current transition looks like "choose a zero $$$j$$$, then fill $$$d[j + 1..i]$$$ with ones — once we've created a range of ones, we don't extend it to the right. Maybe now it is more clear, why it suffices.
The first three are actually YES. (And maybe 6th too, depending on your implementation)
Thanks a lot for this round! Problems are really interesting, especially E with it's idea of solution(just asking questions as in quicksort?).
Can you explain your solution?
Let's understand comparing an element $$$a[i]$$$ to all others for ~$$$3n$$$ questions. first we will ask about this element $$$a[i]$$$ until $$$X$$$ is equal to a[i]. (this will happen since $$$X$$$ goes sideways each time to the number it is being compared to). Now we have $$$X = a[i]$$$. Now to compare $$$a[i]$$$ and $$$a[j]$$$ we just need to ask the question about $$$a[j]$$$ first. This is how we know the answer.($$$a[i] \gt a[j]$$$ or vice versa). And now ask about $$$a[i]$$$ again (to make $$$X$$$ equal to $$$a[i]$$$ again). We have learned how to compare this element with all the others. But this is the same as quick sorting!!! We are comparing an element and sorting all the smaller ones and all the bigger ones. the number of queries $$$~O(n log n)$$$ which hopefully will pass.
I had thought of a solution, where LIS + LDS of a permutation has certain minimum lower bound. I had tried to implement with that logic, but timed-out.
Is D really this easy? or am I just dumb? 1k+ already solved. It's a recursion problem I know that but somehow not able to form the code ughhhhhhhh :D
D is just binary search + dp, maybe there is an easier solution.
thought of binary search and dp but could not implement dp can u share your approach and code
I wasn't able to even think of it. :)
I wouldn't say it's easy, I'm probably biased towards F, but I personally think that D > E > F.
Ternary search in D?
Binary search + DP
What is the value you search? I thought about the max sum of interval with "free" elements.
https://mirror.codeforces.com/blog/entry/125215?#comment-1111743
Guys why my this code is wrong for codeforces question 3 xor distance one
Do we use divide and conquer on E?
I used divide and conquer in E that reminds of quick sort algorithm.
Yep. I did something like quick sort.
Yes, use a recursive function to solve for a set of indices $$$S$$$ and at each stage you pick a random indice $$$i$$$ from $$$S$$$ and make $$$x$$$ equal to the value $$$p_i$$$.
Then remove $$$i$$$ from $$$S$$$ and split $$$S$$$ two sets : indices with values $$$ \lt p_i$$$ and values $$$ \gt p_i$$$, solve for both these sets recursively.
This takes $$$O(n \log{n})$$$ queries.
So we just splitting the set of indecies on two partitions on each step, with "pivot" index value remaining their parent. Then we just restore the answer from a tree. Overall, it shoudn't take more than $$$2nlog(n)$$$ requests. Is this your approach?
Yes, but it takes something like $$$3 n\log{n}$$$ queries
how C?
Oh god, I'm so lucky. I freakin stared at monitor looking for overflow errors in D, but couldn't find anything, since locally everything works ok. Decided to go ooga-booga mode and wrote
#define int long long, and it freakin passed. After it passed I realized the error. No-Wconversionmoment, shame on meI write every contest with
#define int long long.Never got MLE/TLE because of that.
This is a cool contest with a cool problemset ☝☝☝☝
How C?
is C brute force?
from topbit(r) to 0, if we can flip current bit then copy it and compute abs(a^r — b^r) to determine bit should be flipped or not.
had 10 WA pretest2 still no clue
If you also tried this approach starting from topbit(r) — 1 you would get AC
Can someone please explain, how to solve D?
how to manage the states, within the constraints
Man, I was struggling with C :( TLE or MLE was troubling me? Can anyone give the solution?
basic steps to solve C problem
1 -> find maximum(mx) and minimum(mn) among a and b.
2 -> ignore common bits because they didn't affect the answer.
3 -> ignore the first missmatch bit of mx(1) and mn(0)
4 -> traverse from MSB -> LSB whenever this condition reached that bit of mx is set and bit of mn is unset try to transfer this bit form mx to mn(if possible).
lets take an example
7 4 3
7 -> 1 1 1
4 -> 1 0 0
ind-> 2 1 0
mx = 7,mn = 4
2nd bit -> ignore because both are same
1st bit -> first time occur 1 in mx 0 in mn
0th bit -> try to transfer this bit from mx to mn.
how to transfer ?
if (curr bit is set in mx and unset in mn) and we set this bit in x, then after xor with x, curr bit of mx will be unset and curr bit of mn will be set.
so check whenever this(curr bit is set in mx and unset in mn) condition reach and after setting this bit in x if x <= r then set this bit otherwise ignore this and move on next bit.
Bro can you please help me out with this. I've done the exact same thing as you described but I'm getting WA. Submission
your code is giving WA on testcase 7 4 3. I think you are not applying the third step
what was your intuition behind step 3
Think about the above example:-
7 4 3
7 -> 1 1 1
4 -> 1 0 0
if we don't ignore the second the bit then we have enoung r to shift second and third bit from mx to mn and after shifting both bit diff will remain 3 which is wrong.
simply we want like this:-
mx -> 10000000
mn -> 01111111
which minmizes the gap between them.
Spent 1h+ on C because wrote
1<<iinstead of1ll<<i=(The problems are really interesting!
same
Same
live and learn. this will also overflow
Wow!!
B is similar to ARC149B, and I think they probably have somthing in common.
Today i solved 3 problems, and enjoy this contest, Thankyou
Can someone please explain, how to solve D?
how to manage the states, within the constraints
use binary search to find the answer. For an answer $$$x$$$, the maximum sum of the segments should below or equal $$$x$$$, and the minimum sum of the blocked elements, too. you can find the sum by an $$$O(n^2)$$$ dp, then optimize it with monotonic queue to $$$O(n)$$$, then you solve this problem in $$$O(n\log V)$$$.
sry, my english is not very good. if ur chinese, you can look look this solution.
Wow, I used the same idea but with segment tree instead of monotonic queue, this is a good observation, thank you!
Oh bad I spent 1:10 and almost 100 lines of code C Why are solutions from my room so short...
Was the intended solution for F sth like: sort the sons for each node by greatest depth of node in its subtree, then do dfs in that order and maybe get the profit of jumping from each node on the trampoline when you traverse the tree in dfs order, and take the best profits? I did that without having an actual proof or something and got WA on test 27, but maybe I was missing something.
You can solve it with Aliens trick+DP
Please stop create monkey-problems like B
Can someone please tell me what's wrong in this submission for C? Spent over an hour but I couldn't find anything :( Submission
Thanks to preparing the contest! I enjoeyed A,B,C, and G That's how I solved G
if n==3 or n==5: impossible.
otherwise, possible. if n==2: just print any array
if n-2 can possible, then let this array as [A1, A2, ... A_(n-3), A_(n-2)] append as A_(n-1) = -A_(n-2), A_n = (A_(n-3)-A_(n-2))
Then now you can get an array which holds property and length n
for even number: starts with 1,2,-2,-1
for odd number: starts with -1,-1,2,-2,-3,4,1
and here's my code.(Python)
I'm just curious. To solve G, I have worked out the cases when n is even. But when n is odd, I have completely no idea.
I wonder if we randomly choose numbers from {-3,-2,-1,1,2,3}, is is possible to "random" out a possible permutation?
For even, yes.
For odd, I've proved that it is possible as {-4, -3, -2, -1, 1, 2, 3, 4}, but I'm not sure if it is possible as {-3, -2, -1, 1, 2, 3}.
If you don't mind, please refer to my solution. https://mirror.codeforces.com/blog/entry/125215? ad#comment-1111742 and I think this main idea can lead you to solve or dissolve the problem.
My solution 244154502 doesn't choose numbers randomly, but they do end up being in the set $$$\{-3,-2,-1,1,2,3\}$$$ for $$$n$$$ not divisible by 4 (in particular, for odd $$$n$$$). You probably can get all numbers in the said set with a slightly different base case.
did 1<<i instead of 1ll<<i :(
did 1<<i instead of 1ll << i :(
i hate bitmask problems a little bit
My solution for problem D
We will binary search on the answer. Let's call the currrent value we are deal with is X Let's call dp[i] : Consider position 1 to i, if we take element i, what will be the sum of blocked elements So : - dp[i] = dp[j] + a[i] - sum from j + 1 to i — 1 must be <= X. We can find the range of j by binary search and get the minimum value by segment tree simutanously. - The function check on binary search return true if there is exist an indice i such that : sum(i + 1, n) <= X && dp[i] <= x Hope it make sense
My solution for problem D
We will binary search on the answer. Let's call the currrent value we are dealing with is X Let's call dp[i] : Consider position 1 to i, if we take element i, what will be the sum of blocked elements. So :
dp[i] = min(dp[j] + a[i]) and sum from j + 1 to i — 1 must be <= X. We can find the range of j by binary search and get the minimum value by segment tree simutanously. The function check on binary search return true if there is exist an indice i such that : sum(i + 1, n) <= X && dp[i] <= x Hope it make sense
Great explanation. Thank you so much!
C is stolen from codechef just expanded the constraints https://www.codechef.com/problems/XORDIF
I am sorry for what I said,this is two different problems.
Don't use terms like "stolen" if you don't have proof.
My guess is that the author found the motivation behind problem C from this problem and used similar problem name to somehow convey it.
I also think I have solved this problem before
These are two different problems
the difference is that existence of r
Yes, I'm glad you understood.
Did someone prove that in B we are getting the best number of inversions by just sorting one of the permutations? That is not that intuitive for me...
Consider index $$$i, j$$$ If $$$a_i \lt a_j$$$ and $$$b_i \lt b_j$$$ or $$$a_i \gt a_j$$$ and $$$b_i \gt b_j$$$ , then eliminating inversion in $$$a$$$ eliminates inversion in $$$b$$$.
If $$$a_i \lt a_j$$$ and $$$b_i \gt b_j$$$ then in any configuration you must have 1 inversion due to this pair, thus sorting will eliminate all the inversions pairs of type 1 and 1 inversion is anyway there in type 2 for any configuration
Consider two indices, $$$i$$$ and $$$j$$$ and $$$i \lt j$$$.
If the order is different in the arrays:
this means if it becomes $$$i \gt j$$$ in the answer array, the sum of inversions will not change, because if the inversion disappears in a, it reappears in b and vice versa.
However, if both of the arrays contain inversion with indices $$$i$$$ and $$$j$$$, meaning
Then if the indices $$$i$$$ and $$$j$$$ become somehow $$$i \gt j$$$ in the final array, sum of inversions will decrease by 2.
If:
then their order should be preserved, in other words $$$i \lt j$$$ should hold after reordering.
so we want to swap preserve all $$$ai \lt aj$$$ and remove as much $$$ai \gt aj$$$ as we can. because the array $$$b$$$ doesn't contribute anything (look at the cases). so the operation that accomplishes this is sorting.
you can use bubble sort to understand. Consider what happens when you swap 2 consecutive numbers
Consider optimal answer by score (number ov inversions in $$$a$$$ + number of inversions in $$$b$$$). If there are more than one optimal answers consider one with lexicographically smallest array $$$a$$$.
$$$Claim:$$$ array $$$a$$$ will be sorted in such an answer.
$$$Proof$$$ $$$by$$$ $$$contradiction:$$$ assume it's not. Then there is an index $$$i$$$ such that $$$a_i \gt a_{i+1}$$$. Let's make operation with $$$i$$$ and $$$i+1$$$, i.e $$$swap(a_i, a_{i+1})$$$ and $$$swap(b_i, b_{i+1})$$$. Number of inversions in array $$$a$$$ decreased by one after a swap, and number of inversions in array $$$b$$$ increased by no more than one, since $$$b_i, b_{i+1}$$$ is the only pair of elements whose relative order was changed in $$$b$$$. Therefore number of inversions in $$$a$$$ + $$$b$$$ $$$\bf{not}$$$ $$$\bf{increased}$$$ after a swap, but array $$$a$$$ became lexicographically smaller. But we chose array $$$a$$$ as lexicographically smallest $$$\to$$$ contradiction, array $$$a$$$ is sorted in optimal answer.
Can someone explain the statement of problem B, please?
Is there a non-random solution for E?
Yes — you can do parallel binary search to find all values in worst case $$$O(n \log n)$$$ queries. My code (244112756) is very messy and might FST; I have a proven, more efficient version that I haven't yet submitted and I'll clean up the code. I'll probably post a comment on the editorial about my solution with a proof of the number of queries.
Firstly you can request X=1 (I think by 2n queries)
Secondly supporse you have $$$k$$$ indices of consecutive numbers $$$L \ldots R$$$ ($$$R-L+1=k$$$). Find position of $$$m=(L+R)/2$$$ (likely it can be done by $$$O(R-L)$$$ queries). Then split indices to two groups and solve recursively.
Start call from $$$L=1$$$, $$$R=n$$$, indices = $$$1 \ldots n$$$.
Where is the Editorial?
Is Carrot extension not working?
How to solve E?
QuickSort
upd
maybe not, it didn't pass the system tests :(
I used quick sort and passed by randomising the order of positions to call for queries + randomising pivots. https://mirror.codeforces.com/contest/1918/submission/244143789
as i understad:
During contest someone hacked this 244128703 randomized E submition which use rand() without seed.
Then my randomized E submission 244133027, which happened to be identical to mentioned one, failed on auto generated after hack sys test 26.
I am not sure what to think about it :)
always use something like srand(timestamp) i guess
My B solution uses just bubble sort, but I get TLE anyways. Could someone give me some hint?
Bubble sort is O(n^2) which is too slow for the bounds which are 10^5. You need a faster sorting algorithm. If you can use the built-in sort for your language that should be fine.
Just make a pair array where first element is a[i] and second is b[i] and sort this according to first element. the proof of correctness you can do by yourself.
I spent a lot of time on B. I think it's too difficult for people without prior knowledge like me. I don’t know how to prove the correctness of my ideas. ;(
same but I just submitted it even though I wasn't sure if greedy worked.
My E solution got TLE for java. Had to use chat gpt to convert to c++. Time constraints too tight?
Is there a proof for randomised solution for E?
I think E is too tight. I got TLE. However, someone got AC using same idea (maybe just a different select point). too sad~.
Looking at the output for the failed test, it seems that it was actually a WA due to exceeding the query limit, but since the program failed to handle the WA input and exit, it was judged a TLE.
Next contest coming in 3 weeks? Why is it taking so long? or am I missing something.
when can i submit after the contest
Can someone explain me why this is TLE ?Code
std::vector::eraseis $$$O(n)$$$Thank You
Top5 are always smurfs :)
Is there no hacking phase?
There is no hacking phase in regular div2 rounds.
rating updates ?
"Submissions have been scheduled for rejudge on the next testset." This notification came after the system tests were over. What does this mean?
Can anyone explain the intuition behind why, for problem C, you need to avoid swapping the bits between a and b until the first time the bits differ?
Because you don't accomplish anything by adding that bit in x. Example: a = 1, b = 1, a⊕0 — b⊕0 = a⊕1 — b⊕1.
@blaze Right, but I'm trying to figure out why this is the case. For the case of 9 and 6, for example, you can notice setting X to 1001 rather than 0001 (or just 1) ends up making it so that, if a > b before this, a < b afterward. I think this is the key insight, but I'm trying to figure out why this is only the case until the first bit differs.
Don't look at the numbers a and b as "numbers", separate them bit by bit and look at them that way. You can assume that a > b because $$$|a \oplus x - b \oplus x| = |b \oplus x - a \oplus x|$$$. You don't want to toggle unnecessary bits in x so that it can be <= r. During subtraction of $$$a \oplus x - b \oplus x$$$ notice that the bits that are the same don't affect the result, xoring them with something won't make those bits different.
Thanks for the reply but I don't think we are talking about the same thing. I understand the bits that are the same between a and b should not have anything xor'd with them. But in correct solution, you skip not only the positions where a and b have the same bit, but also the first position where a and b's bits differ, even if that position has a 1 bit for a and a 0 bit for b. That is the part I am confused on.
we skip first bit because if we swap the MSB, we would have to add that bit to our cost, i.e., r, instead we let it be as it is. best explained with an example:
suppose these are two numbers in binary:
110011 001010
now, in this case we would avoid swapping the first bit because it alone costs 2^5, which would be higher than any cost we would incur to swap subsequent bits however we like. suppose r = 100000 (in binary) in this case.
then, if had we swapped the first bit, we could not swap any further bit and new numbers would be 010011 and 101010
notice the third bit from the left would have been better in first number but we don't have any r left but, if we did not swap the first bit, we could do anything later on in this case because r is sufficient.
if any doubt ask me.
Thanks for your help! I understand if you swap the MSB it comprises the whole cost, but I'm having trouble understanding why this means we shouldn't use it. After all, it makes the biggest change in the numbers, and thus brings them closer together, right?
However, here the correct X to use is 010001. If instead we used 100000, which is what you get if you don't skip the MSB, you end up subtracting too much from the bigger number and adding too much to the smaller number, which results in not getting an optimal solution.
What I am trying to understand is, why is this only a problem for the MSB? Why do we always avoid swapping only for the MSB, but we can always do the swaps for any other bit?
Because Suppose n has msb, now the later bits, we are trying to push to m to make n-m as smaller as possible. As m increases and n-m decreases.
we are greedily avoiding first msb in case a solution existed in which we could switch the first msb then later on we would get the best answer, suppose like this 2 numbers 1111, 0000 and r is 1000 in this case we can switch msb to get best answer but its clearly possible avoid msb and switch rest bits in lesser cost.
Did i answer your question? If not, i dont think i understand your doubt
approach is like this ->> (without loss of generality, assume n>m) avoid swapping first bit, and later on try to get significant bits to m. since, n>m, first bit will be in n and getting bits to m would make n-m smaller and smaller.
This contest be like:
can anyone give test for C ? https://mirror.codeforces.com/contest/1918/submission/244131222
try this
1
1 6 4
https://mirror.codeforces.com/contest/1918/submission/244195848
can you help me why my code is failing it is showing WA on tc-2 at number 4268
My Solution for problem D https://mirror.codeforces.com/contest/1918/submission/244169954
Thank you for fast Editorial
where?Editorial?thanks!
great problemset, definitely one of the best div2's of last months!
D problem (Blocking Elements) Video Editorial : https://youtu.be/ZfqWLxBG-Ow?si=WxQOHwg_hdelqH4C
Why the downvotes? Did I write something wrong?
You didn't write anything wrong, but you shouldn't to editorials to problems you didn't solve during the contest.
everything went as planned, I will farm next div 4
i had solved 1 problem and it is accepted but why my rating get minused?
Based on your current rating, you are expected to have a better rank now to get a positive delta. i.e. Solve B to climb up in the rank-list.
I like this round, especially the strong input/output examples. Good round.
Hey! This was indeed a very educational type of round, thanks to the contest problem-setters. I just managed to curate some well-elaborated problem discussion sessions covering problems A to D https://youtube.com/playlist?list=PLxHsiA8Ewxn24IVOuNjADlvah8d_eIXuW&si=IbM9faXnzHYP7uSH They should be helpful for beginners and many Div2 participants, especially problem D. Excited to see the community grow together!
PS: Didn't get time till now to work on the problems E to G, but would be glad to have discussions on them on any forum!