### deltixlab's blog

By deltixlab, 13 months ago,

Prepared by AleXman111.

Prepared by AleXman111.

Prepared by netman.

Prepared by netman.

Prepared by netman.

Prepared by 300iq.

P.S. Editorial for problems E and G will appear a little later.

• +66

 » 13 months ago, # |   +45 can someone explain the O(n) approach for C .
•  » » 13 months ago, # ^ |   +5 You would need two stacks, one for the numbers and the second for the brackets before the brackets you are adding.Here is a case where you might get the idea8 1 1 2 1 1 1 1 2
•  » » » 13 months ago, # ^ |   0 https://codeforces.com/contest/1556/submission/128291088 can you please check my submission where is the wrong with my code?
•  » » 13 months ago, # ^ | ← Rev. 4 →   +6 A O(N) solution for Problem C in Typescript: https://paste.ubuntu.com/p/Y9JcZWkGFN/
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +3 can you put the code inside a spoiler?UPD : thanks :)
•  » » » » 13 months ago, # ^ |   +9 Sorry for that.
•  » » 13 months ago, # ^ |   +28 I considered the input two values at a time. If there are an odd number of integers in initial input we can ignore the last one, because that generates ('s which are not matched later.Consider a typical parens-matching problem, where you might consider the "depth" of the parens sequence. A open parens ( increases the depth by 1, and a close parens ) decreases the depth by 1. If the next two values in the input are $a$ ('s and $b$ )'s, then the closing parens will match $b$ times. We can simply add these values to our total.There is a case where having $b$ )'s will go below the lowest depth reached, and past that point we don't have any ('s to match on the other side. In that case, we can only match up to the lowest level.The last case to consider is that of valid sequences concatenated together, e.g. ()(()). One observation to make is that each of the valid subsequences (i.e. () and (())) all lie on the same level. Furthermore, we can if we convert this into an input as specified in the problem (1 1 2 2), we can see that these subsequences all end on closing-parens indices.So the idea is to keep a stack. For each pair of values in the input, take note of the level we end on ($cur+a-b$). Pop any levels off the stack that are higher than this — once we go down past a level, we can no longer concatenate to create another valid sequence. If the value on the stack is equal to the current level, this means we have a valid sequence to concatenate onto, and we can add it to our total.There are a few more little edge cases and extra details, but otherwise I hope this gives a good overview of the general idea.See my solution for reference: 127381648. It's actually quite short for such an annoying problem.
•  » » » 13 months ago, # ^ |   0 Yeah!I think this solution is actually quite short.I solved this problem with 100 lines of code.This solution has taught me a lot.
 » 13 months ago, # |   +9 The problems might be too difficult for me, but there's no doubt that the illustration in each problem is beautiful!
•  » » 13 months ago, # ^ |   0 Yes，you're right !For me,it is remarkably difficult to solve this problem.But I will work hard to understand it！
 » 13 months ago, # |   +108 I recognized the entire solution to H during the contest except that I don't have a template or know how to compute min cost matroid intersection. I know how to compute maximum cardinality matroid intersection only. Does anyone have a good resource about the weighted case?
•  » » 13 months ago, # ^ | ← Rev. 3 →   +78 Replace your bfs with bellman-ford, minimize the pair (total weight, number of edges). As in min-cost max flow, negate weights of elements currently in the answer.
•  » » » 13 months ago, # ^ |   +22 But I did that and got TLE on test 8... the implementation needs not only to be correct but optimized to pass this problem...
•  » » » 13 months ago, # ^ |   +22 I got this solution to pass 127485697. It's kind of funny because it makes two different mistakes that magically cancel out. It finds shortest path but ignores the part about number of edges. Also it builds the exchange graph incorrectly, where I throw away exchange edges if the added edge can just be added freely.I guess the wrong exchange graph eliminates many cases where shortcuts happen. But I don't see why it should resolve the issue fully. Anyone reading this, feel free to hack it.
 » 13 months ago, # |   +1 I did not know the relation used in D and was very happy to solve it without using the relation.Basically you can perform both operations for (n-1) pairs (0,1), (1,2) ... (n-1,n). if the jth bit is set in the 'and' value, then jth bit of both numbers is 1. if the 'or' value is 0, then jth bit is 0 for both the numbers.Now some bits will be left unknown but they will always be alternating. For any bit which has atleast one 1 or one 0. We can know all the other bits.If we have no knowledge on some bits. We can perform 'and' and 'or' on 1st and 3rd element because their parity will always be the same for all the unknown bits. After knowing these two numbers we can get all the others as well.
•  » » 13 months ago, # ^ |   0 In my solution, I recovered the value of the first array element by just using bruteforce (separately for each bit). Taking all 6 possible ways of doing AND/OR operations between the first 3 array elements as the input data: Spoiler/* 1-bit bruteforce version */ ll recover_a1(ll orab, ll andab, ll orbc, ll andbc, ll orac, ll andac) { ll ans = 0, cnt = 0; for (ll a = 0; a <= 1; a++) { for (ll b = 0; b <= 1; b++) { for (ll c = 0; c <= 1; c++) { if (andbc == (b & c) && orbc == (b | c) && andab == (a & b) && orab == (a | b) && andac == (a & c) && orac == (a | c)) { ans = a; cnt++; } } } } assert(cnt == 1); return ans; } /* * We know: A | B, A & B, B | C, B & C, A | C, A & C * Need to recover and return a 32-bit value A. */ ll recover_a32(ll orab, ll andab, ll orbc, ll andbc, ll orac, ll andac) { ll ans = 0; for (int shift = 0; shift < 32; shift++) ans |= recover_a1((orab >> shift) & 1, (andab >> shift) & 1, (orbc >> shift) & 1, (andbc >> shift) & 1, (orac >> shift) & 1, (andac >> shift) & 1) << shift; return ans; } 
•  » » » 13 months ago, # ^ |   0 Loved it
 » 13 months ago, # | ← Rev. 2 →   0 Can anyone help me figure my mistake for B I am unable to find and stuck for hour now :( https://codeforces.com/contest/1556/submission/127399981 upd: Got it AC'ed finally :)
•  » » 13 months ago, # ^ | ← Rev. 2 →   +4 Try this testcase:1 6 1 2 2 1 2 1Your output is 2, while the correct answer is 1.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 thanks man, a stupid doubt but how is it 1 I think 2 is the right answer ...
•  » » » » 13 months ago, # ^ |   0 swap the very first 1 and 2 and it become 2 1 2 1 2 1
•  » » » 12 months ago, # ^ | ← Rev. 8 →   0 https://codeforces.com/problemset/submission/1556/130640840 Its giving WA on test 2(58th numbers differ). Can't find the mistake after debugging for an hour. Please help me out if you have time! PS : main() is present from line 320. I'm referring to problem B!
•  » » 13 months ago, # ^ |   0 Stress-tested and got this:Input: 1 10 1 2 2 1 1 2 2 2 1 1Correct output: 3Your output: 4
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 thank you so much ,but I checked through an AC code it gave output 4 can u please test it again and help :)
•  » » » » 13 months ago, # ^ |   0 test case is 1 10 1 2 2 1 1 2 2 2 1 1 but not 1 12 1 10 1 2 2 1 1 2 2 2 1 1 
•  » » » » » 13 months ago, # ^ |   0 my bad lol smh
 » 13 months ago, # |   +5 In the solution for C, while describing balance I think it might have been intended to write c_{l+3} instead of c_{l+2} twice.
•  » » 13 months ago, # ^ |   0 I don't understand the meaning of minBalance. Can you explain it? Also, the formula for balance is -c[l+1] + c[l+3] — c[l+5] + c[l+7]... Is this correct?
 » 13 months ago, # | ← Rev. 2 →   +274 There is a ~$\frac{5n}{3}$ query solution to D. The main idea is to find the values of each group of $3$ elements in $5$ queries. First note that $(a ^ b) = (a & b) ^ (a | b)$, so you can find the xor of two indices using only the and and the or. Now if you want to find the values of the elements $(a, b, c)$, first query $(a & b)$ and $(a|b)$ to get $(a \oplus b)$, query $(a & c)$ and $(a|c)$ to get $(a \oplus c)$. Now $(b \oplus c) = (a \oplus b) \oplus (a \oplus c)$, so you get $(b \oplus c)$ for free. Another important fact is that $(a+b) = (a ^ b)+2*(a & b)$. You can get $(a+b)$ using $(a \oplus b)$ and $(a & b)$ (both of which were queried earlier). You can get $(a+c)$ the same way. You can query $(b & c)$ to find $(b+c)$. Now you have the values $a+b, a+c, b+c$, and you can just solve the system of equations on paper to get the values of $a$, $b$, and $c$. Thus, you can get the values of $3$ elements with $5$ queries, making the total number of queries $\frac{5n}{3}$. Note that if $n$ is not a multiple of $3$, you can use $2 \cdot (n \mod 3)$ queries to get the remaining two elements (by querying the xor of those elements with an element you already know).Sorry for the issues with latex, it doesn't like & for some reason (using \& doesn't work either).
•  » » 13 months ago, # ^ |   -11 Orz Int-Master heading for -> Grandmaster soon!.
•  » » 13 months ago, # ^ |   +1 That's perfect. It's a beautiful solution.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +3 I was also getting the value of the first 3 elements with 5 queries different from yours but I didn't notice until reading your comment. So here is my solution,$a = ((a | b)$&$(a | c)) ⊕ (((a$&$b)$&$(b$&$c)) ⊕ (b$&$c))$$b = ((a | b) ⊕ a) | (a & b)$$c = ((b | c) ⊕ b) | (b$&$c)$
•  » » » 13 months ago, # ^ |   0 So what's the principle of this solution? Could you please explain it to me?
•  » » » » 13 months ago, # ^ |   0 That part of finding $b$ and $c$ after we know $a$ is mentioned in editorial so I will just explain finding a.First, we define $a = ((a|b)$&$(a|c))$ but this definiton of $a$ includes some wrong bits which are not open on $a$ but open on both $b$ and $c$ and those bits are equal to $((a$&$b)$&$(b$&$c))⊕(b$&$c)$ so we delete them by $⊕$ operation from $a$'s old definition. Total query set is also 5 which is equal to $[(a|b)),(a|c),(a$&$b),(b$&$c),(b|c)]$
•  » » » » » 13 months ago, # ^ |   0 OK. Thank you.
•  » » 13 months ago, # ^ |   0 Learned a lot of things about BIT operations in a single comment.
•  » » 13 months ago, # ^ |   0 Same solution for me as well. I didn't realise the $a+b = (a\text{ a }b) + (a\text{ and }b)$ thing because I am dumb; then proceeded to solve by finding value of $a_1$ and instead of solving in $5n/3$ queries I take up almost all queries as predictable.
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 .
 » 13 months ago, # | ← Rev. 2 →   +3 Nice round.I did enjoy the struggle even though I lost rating :).
 » 13 months ago, # |   +8 Does anyone have a nice explanation for the inclusion exclusion formula in F? I'm struggling with the G(sub) factor in the subtraction
•  » » 13 months ago, # ^ |   +8 I'm confused about it too.
•  » » 13 months ago, # ^ |   +24 Same :/I think the formula should be $F(winners) = G(winners, ALL \setminus winners) - \sum_{sub \subset winners, sub \neq winners} F(sub) \cdot G(winners \setminus sub, ALL \setminus winners)$If I am wrong, please explain the correct formula.
•  » » » 13 months ago, # ^ |   0 Your formula matches with rfpermen in their excellent explanation below- I think you are both right
•  » » » 13 months ago, # ^ |   0 You are right! Sorry for mistake in editorial. Editorial will be updated soon,
•  » » 13 months ago, # ^ |   0 The key idea is that S is a winning set iff there exists no subset X of S, s.t. X is a winning set and everything in X beats everything in S-X
•  » » » 13 months ago, # ^ |   0 I get the complementary counting part but then shouldn't the summation part be$\sum \limits_{sub\in winners, sub \neq winners} {\frac{F(sub)}{G(sub, ALL \backslash winners)}}?$Otherwise it seems like they are accounting for the edges from $sub$ to $ALL\backslash winners$ twice. Once in $F(sub)$ and the other time in $G(winners, ALL \backslash winners)$.
•  » » » » 13 months ago, # ^ |   0 Yes, you are right. I think the editorial missed this.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +35 This is the formula that I got $F(winners)=G(winners,ALL∖winners)⋅(1-∑_{sub⊂winners,sub≠winners}F(sub)/G(sub,ALL∖winners))$Here is my explanation how I got the formula (please correct me if I wrong): You want to find $F(winners)$ by using $G(winners,ALL∖winners)$ but you can notice that $winners$ should make a cycle where everyone can beats everyone in set $winners$. Then you want to exclude case where $winners$ doesn't form a cycle, and that's when everyone in $sub$ beats everyone in $winners∖sub$. So you probably can guest probability of that is $G(sub,winners∖sub)$, but you also want to make sure that $sub$ form a cycle (because if you don't do this then there will be a lot of double counting) so you can take account probability of $F(sub)$ Notice that the formula that editorial give is $F(sub)⋅G(sub,winners∖sub)$. But wait, from $F(sub)$ we already calculate $G(sub,winners∖sub)$ from $G(sub,ALL∖sub)$, so we doesn't have to calculate $G(sub,winners∖sub)$. So the formula probably would be like this $F(winners)=G(winners,ALL∖winners)⋅(1-∑_{sub⊂winners,sub≠winners}F(sub))$. But, notice again that we also calculate $G(sub,ALL∖winners)$ two times, from $G(winners,ALL∖winners)$ and $F(sub)$, so then we want to exclude $G(sub,ALL∖winners)$ one time from our calculation, therefore $F(sub)/G(sub,ALL∖winners)$.
•  » » » 13 months ago, # ^ |   0 Thank you so much, this is a great explanation. I will assume the editorial is wrong for now.
•  » » » 13 months ago, # ^ |   0 why we have to work with set of winners? I mean why we can't use the fact linearity of expectaion?
•  » » 13 months ago, # ^ |   +5 You struggling because of mistake in editorial :) Updated editorial with much simpler formula and explanation to it.
•  » » » 13 months ago, # ^ |   0 Thanks for the fix and the great contest! :)
•  » » 13 months ago, # ^ |   +21 I come up with the following solution, that i think is easier to understand:Let $F(winners,X)$ be the probability that a subset $winners$ of $X$ win and the subset $X/winners$ lose, Using a similar idea to the editorial we can calculate $F(winners, X)$ as$F(winners, X)= G(winners, X / winners) \cdot (1-\sum_{sub \subset winners, sub \neq winners} F(sub, winners)$)Where $G(X,Y)$ is the probability that all members in $X$ beats all members in $Y$.Note that we omit the overcounting because first we insure that the set of $X/winners$ are losers, and then we can ignore them in the following calculations (we restrict the set $X$ to the subset $winners$ in $F(sub, winners)$), it seems as a $O(4^N)$ solution, but note that the term $(1-\sum_{sub \subset winners, sub \neq winners} F(sub, winners))$ doesn't depend of $X$, therefore it can be calculated in $O(3^N)$ if we save used information, the calculation of $G(X,Y)$ could be done as in the editorial.Here is the submission: https://codeforces.com/contest/1556/submission/127474511
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +8 thanks
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   +11 you welcome!
 » 13 months ago, # |   +14 linear solution for C 127401730
•  » » 13 months ago, # ^ |   0 Could you explain the code bro,I feel confused about it.
•  » » » 13 months ago, # ^ |   +4 So from what it looks like he mantains a stack of the opening brackets that can be used to start a sequence. If you are processing and you have something like (((()) then after processing the closing brackets, only (( will be useful later. Also, they mantain another stack with the ammount of complete sequences that you can reach (for example after reaching something like ((()))()(()) there would be a 3 in the stack). I think with that thinking about the recurrencies wont be that hard.
•  » » » » 13 months ago, # ^ |   0 thanks a lot！
 » 13 months ago, # |   +6 I think D is an easy version of 1451E1 - Bitwise Queries (Easy Version)
 » 13 months ago, # |   +56 I'm not the first one to notice it, but the tests for E were quite weak. My contest submission used the fact that arrays a and b play a similar role (which of course they don't), and can easily be hacked with arrays of size 2.Nonetheless, it passed the 80 main tests and got Accepted.I understand that making tests is not a perfect science, but how did something this big slipped through ? Even with random tests, this seems unrealistic, as simply swapping the two arrays should cause it to fail.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Could you share such a test? In your submission a and b are used only through c = a - b, and I see no problem with their roles being "similar" here since indeed only c matters.EDIT: I guess the issue you mean is not with the subtraction but with max(abs, abs) below, nvm then.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 a - b is not the same as b - a, whereas my code treats them the same way. You can increase the first element of array a, but not the first element of array b for example. So the classic hack would be : 2 1 1 0 0 1 1 2 
 » 13 months ago, # | ← Rev. 2 →   0 Can someone tell me the solution to problem E please?
•  » » 13 months ago, # ^ | ← Rev. 3 →   +29 Let's create an array of deltas v, so $v[i] = b[i] - a[i]$. Now let's track sums of deltas on segments $[l; i], l <= i <= r$. The solution exists only if:1) there are no negative sums;2) the sum $[l; r]$ is zero.The answer for the query is the maximum of all found sums because if there are any of negative deltas between current positive delta and the delta where maximum is achieved (let's call it $maxIndex$), we decrease the absolute value of current positive delta and that negative delta without changing the maximum, otherwise when there are no negative values between current positive value and the $maxIndex$ (as an example, current positive value may actually be the $maxIndex$) we decrease value of the maximum value only by one per operation.For optimal complexity use prefix sums ($prefSums[i] = \sum\limits_{k = 0}^iv[k]$) to track sums of deltas and, for example, segment tree to get maximum and minimum values of that prefix sums on segment $[l; r]$ and decrease them by $prefSums[l - 1]$. Overall complexity is $O(qlog(n) + nlog(n))$
•  » » » 13 months ago, # ^ |   0 Thank you very much
•  » » » » 13 months ago, # ^ |   0 Your welcome :)
•  » » » 13 months ago, # ^ |   0 can you explain how segment tree is used to find max sum in l — r? I mean what is the merging operation here?
•  » » » » 13 months ago, # ^ |   -19 Tokyo dies in Money Heist s5
•  » » » » 13 months ago, # ^ | ← Rev. 4 →   +8 I'm very sorry I didn't answer earlier, I didn't see a notification. So let's build the segment tree on array of $prefSums$ mentioned in my previous comment. We will store maximum and minimum on ranges in nodes. To merge we will recalculate maximum and minimum from children of current node. To find the answer for query $[l; r]$ we will basically find maximum and minimum $prefSums$ for segments $[0; i]; l <= i <= r$ and then we will decrease found maximum and minimum by $prefSums[l - 1]$. This works because instead of decreasing all values on the segment before calculations by the same delta we decrease the result by that delta after searching for it which ends these two processes in the same answer.Sorry again for so much time taken to answer your question
•  » » » » » 13 months ago, # ^ |   0 Thankyou so much for this clear explanation!
•  » » » » » » 13 months ago, # ^ |   0 Glad I could help you :)
 » 13 months ago, # |   +28 I'm a fan of problem G but...Do you store all the edges? Do you sort them by the time they need to appear?From your complexity, it seems that you don't have a better bound for the number of edges than $O(mn^2)$. That's a lot. During the contest I think I have proven ($V$ is the number of vertices) $V \le 2m(n+1-k) + 2^{k}$ for any $k$, which roughly means $V \le 3.5 \cdot 10^6$. I think I have also proven ($E$ is the number of edges) $E \le V \cdot n / 2$, which will get us $E \le 9 \cdot 10^7$. That is an awful lot of edges. We can barely store them thanks to 1 GB ML, but to sort them by the time of appearance we should either use in-place sort, I know only of $O(E \log E)$ ones, and that sounds like TL, or use counting sort, which is $O(E)$ but not in-place. I did counting sort in the following fashion: generate edges, count them (for counting sort) but don't store them, then generate them again and now store in right places.I actually assume that it is really hard to construct tests of reasonable strength, but why set so high limitations then?
•  » » 13 months ago, # ^ |   +5 Using some asserts I deduced that on tests $V \le 1.5 \cdot 10^6$ and $E \le 6 \cdot 10^7$ (which means that my second proof is incorrect and I just got lucky).Also, I guess there are different ways to construct this graph, the numbers above are calculated for my particular construction, which is done in a different way compared to editorial, but should be the same in terms of vertices I think,
 » 13 months ago, # |   +55 I wonder how many solutions on E passed systests but fail this test case: 2 1 1 0 0 1 1 2 
•  » » 13 months ago, # ^ |   +100
•  » » » 13 months ago, # ^ |   +39 How do you write a script to find these people?
 » 13 months ago, # |   +1 Thanks for great problems , i have learnt a lot!
 » 13 months ago, # |   +8 My randomized greedy solution during contest got WA on test 133. I optimized it for a little and it passed all tests now. Can anyone hack me?
 » 13 months ago, # |   +94 I don't know but why Deltix don't decide to update the testcase in E and rejugde all the submissions?
•  » » 13 months ago, # ^ |   -96 u funny hahahahahahahaha u taking internet points personal lololololol.if ur solution was failing u not be talking like this. how this different to weak tests were solutions that should tle ac or use pragma to squiz slow solution? i c no reson to do the new tests.some contests same complexity python or java code fail and c++ ac why not increase limit.ppl lik u always crying bcz ur bad performance there hundred examples lik this and nobody ever suggest lik this.let ppl be happy with whut was solved in contest.u just salty bcz u was slow and could rank high.if tests weak u hack. it part of contest. stop cry.
•  » » » 13 months ago, # ^ |   +83 Little did you know my submission for E failed the hack testcase also. :D
•  » » » » 13 months ago, # ^ |   -56 still.had pretest use counter test many ppl would find mistake in code.it willn't be ok if it happen.whats role of pretest & test if(we add more test after contest to fail solution).its author fault make poor test.correct solution not fail why fix problem if it dont exist.these solution fit this contest. the contest with poor test.
 » 13 months ago, # |   +8 Can anyone please help with understanding the formula in Problem C editorial? Basically, the solution has the following skeleton. code for (int l = 0; l < n; l += 2) { long long balance = 0; long long minbalance = 0; for (int r = l + 1; r < n; r++) { if (r & 1) { // MAGIC HERE balance -= c[r]; } else { balance += c[r]; } minbalance = min(minbalance, balance); } } Now, if $minbalance < 0$, then we take $-minbalance$ opening brackets out of $c[l]$ to fix the issue, ending up with $c[l] + minbalance$ opening brackets. If that value is negative, there is no way we can create a correct bracket sequence as we are lacking the opening brackets. On the other hand, if $c[l] + minbalance > 0$, then we can take $c[r] - balance$ closing brackets, and so the answer in this case must be $min(max(c[l] + minbalance, 0), max(c[r] - balance, 0))$.If $minbalance > 0$, then we can take $c[l]$ opening brackets and $c[r] - balance$ closing brackets, having $min(c[l], max(c[r] - balance, 0))$ as the answer for this case.Clearly, my reasoning here is utterly wrong. Can you please advice how to think here in the right way? Thank you!
•  » » 13 months ago, # ^ |   -10 Can someone please explain it in more detail? I am having difficulty understanding editorial for this problem too :(
•  » » 13 months ago, # ^ |   0 twistedE6 Did you figure out the solution?If yes then please explain.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 In the fifth line,i think it is min(c[l]+minbalance,c[r]-(balance-minbalance))+1. "minbalance" is added to "balance", but "minbalance "is supposed to be subtracted from c[l]. So we may need to remove "minbalance" from "balance".it seems to me that you need to make a case when c[r]-(balance-minbalance) <0." In the case of "() ((((()", there are too many "(" before r=3 (c[r]-(balance-minbalance)=-4), so you can not create a regular bracket that starts at l=0 and ends at r=3.Also, I think you need to add 1 at the end. when "(()(()))" l=0 r=3, min(c[l]+minbalance,c[r]-(balance-minbalance))=1. but there are two answers. (()(())) and ()(()).Sorry if I'm wrong.https://codeforces.com/contest/1556/submission/128076123
 » 13 months ago, # |   0 In D,why a+b=(a or b)+(a and b)， not a+b=(a or b)+(a and b)<<1 ?127410355 AC a+b=(a or b)+(a and b)127409931 WA a+b=(a or b)+(a and b)<<1
•  » » 13 months ago, # ^ |   0 Sorry,it's or，not xor.I read the question wrong.
•  » » 13 months ago, # ^ |   +2 Because (a or b)+(a and b) will just do standard summation. Fixate a bit for example, there will be 3 cases.1) It is active in both a and b: it will be active in both "and" and "or"2) It is active in either a or b: it will be active in "or" but not in "and"3) It is not active in neither a or b: it will not be active neither in "and" or "or".If it's still not clear, try doing some cases, you will see that doing (a or b)+(a and b) will give you an equivalent situation to summing a and b
 » 13 months ago, # | ← Rev. 2 →   0 Another approach for D: If a bit appears in x | y and not in x | z, y will have the bit.We can use this fact to calculate the whole array.
 » 13 months ago, # |   0 I think there is something wrong with the second formula in the solution for F.I tried to simulate it.And when n is equal to 3,$F((11)_2) \neq 0$,but it is obviously wrong.
 » 13 months ago, # | ← Rev. 2 →   0 I have a doubt in first part itself: In example say I want 5,3. I add 1 to both a,b. Now the value of k = 4. and with second operation, I add it to a and subtract it from b. which makes a=5 and b = -3. Can someone explain me how are operations justified ? .... Thanks for explaining. 300iq
•  » » 13 months ago, # ^ |   0 Same doubt lol..i thought im the only one not getting it :(
•  » » 13 months ago, # ^ |   +1 say you have 5, 3 and a,b = 0,0 initially. adding 4,4 to a,b using first operation will get you 4,4. Then you can add 1 to a and sub 1 from b using second operation and hence you got 5, 3. You can easily achieve this by checking the difference between the given numbers c and d. If the difference is even and either of the numbers are >0, the solution is always 2 (Try it). When the difference is odd, you can never find a solution using the given three operations. (why?) Lastly, if you have c=0 and d=0, obviously you need 0 operations.
 » 13 months ago, # |   0 C problem was almost done but got wrong answer on pretest 13
•  » » 13 months ago, # ^ |   0 Damn my 10th pretest got tle :( Looking at the tutorial I can say I was using a very naive approach (O(N)) lol. But then again, I didn't know any other way to solve the problem
 » 13 months ago, # |   +136 My solution on G used $O(nm)$ DSU operations.You don't need to split each interval into $n$. Notice for any nonnegative integer $x$, $[0,x]$ is connected. Thus it's enough to split an interval into two (from the LCP of both endpoints).To find the edges, iterate digits, using two-pointers method to find pairs of intervals that contains a pair of numbers whose difference is $2^k$. There are $O(m)$ of them on each digit, so the total number of edges is $O(nm)$.
•  » » 13 months ago, # ^ |   +28 G is kind of a harder version of POI XX spa, and the same idea works on that problem too.
 » 13 months ago, # |   0 can someone explain me how we will solve question B by two pointer method???
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 My soln is not the best one but I hope it helps. the idea is the editorial idea plus one condition that if count of odd if greater than count of even then our solution cannot start even no (the case when even is greater case is similar).count of odd>=even now in case of count of odd greater than equal to count of even we want odd,even,odd,even,odd we can have variable o point to the starting no with odd parity and e to the even parity one. now we can run a loop and when the parity is not equal to the required one then ,lets say we required an odd no at position p, we will increment o till we reach an odd no then we swap the two values and add the difference in o-p to ans.(similarly increment e when we require even no)if count of even >=odd we can do similar to above. and ans will be smaller of both of them. link to my soln-https://codeforces.com/contest/1556/submission/127420215
 » 13 months ago, # |   0 AleXman111 Can you plz. provide me the code that follow the approach that you explain in the editorial of problem B?
 » 13 months ago, # |   0 can someone explain the solution for C
•  » » 13 months ago, # ^ |   0 Your code here... #include using namespace std; using ll = long long; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin>>n; vector c(n); for (auto &i:c) cin>>i; ll ans=0; for (int i=0; i
•  » » » 13 months ago, # ^ |   0 approach please
•  » » » » 13 months ago, # ^ |   0 lol i am also asking dout
 » 13 months ago, # | ← Rev. 2 →   0 can anyone help me with my code at problem B :<. I got WA at pretest 2.here is my submission 127369911
 » 13 months ago, # |   0 Can anyone explain me the solution of b problem
 » 13 months ago, # |   0 Can someone explain me the solution of second question i am stuck on it please
 » 13 months ago, # |   0 can someone explain for me problem B test case 1 1 1 2 2 2 ? when I use two pointer 1st swap result will be 1 2 1 1 2 2 2nd swap result will be 1 2 1 2 1 2 then my answer is 2 but expected 3. Please help https://codeforces.com/contest/1556/submission/127426964
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 You are only allowed to swap two adjacent elements.
•  » » » 13 months ago, # ^ |   0 Thanks you !!! I missed this desciption
 » 13 months ago, # | ← Rev. 2 →   0 can anyone please give any testcase for Div2B that fails my code i have implemented with same logic that editorial says. my code verdict WA on test case 2 ,wrong answer 17th numbers differ — expected: '3', found: '1' code/* CREATED BY STREAM_CIPHER aug-2021 */ #include using namespace std; void __print(long long x) {cerr << x;}void __print(unsigned long long x) {cerr << x;}void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';}void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long int #define double long double #define fix_precision(n) cout<5*8M byte ->40MB size for long long int (64 bit) // long long can cause TLE int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif int t; cin>>t; while(t--){ int n; cin>>n; vectora(n+1); // arr.clear(); int one=0,zero=0; for(int i=1;i<=n;i++){ cin>>a[i]; one+=(a[i]%2==1); zero+=(a[i]%2==0); } if(abs(one-zero)>1){ cout<<-1<see; int ans=inf; for(int i=1;i<=n;i++){ if((a[i]%2)!=(i%2)){ see.push_back(i); } } int temp=0; for(int i=1;i
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Input:1101 2 2 2 2 1 1 1 1 2Your output: 4My output: 5
•  » » » 13 months ago, # ^ |   0 thanks a lot , i found my mistake.
 » 13 months ago, # |   +20 Nice problems!
•  » » 13 months ago, # ^ |   +29 One of the finest rounds on codeforces. kudos to the problem-setters!
 » 13 months ago, # |   0 Not able to understand the editorial forCompressed Bracket SequenceCan someone please explain that formula dry run with an example?
 » 13 months ago, # | ← Rev. 4 →   0 I can't figure out problem C. How did you come up with the equation min(cl,cr-balance)-max(1,minBalance)+1? balance is -c[l+1]+c[l+2]-c[l+3]+c[l+4]-.... +c[r-1]?In the explanation, the second and third terms are c[l+2]-c[l+2], which cancel each other out to zero. -c[l+1]+c[l+2]-c[l+2]=-c[l+1].Also, am I correct in understanding that these range from l+1 to r-1? thank you.
 » 13 months ago, # |   +5 My explanation for F :- its clear that we want to calculate for some subset the probability that it is strongly connected, to do that observe that if some mask is not strongly connected then consider all its strongly connected components their would exist some node (in SCC) with zero in degree. Now their would exactly one such node as each pair of nodes have some edge b/w them (crux of the problem), we iterate on this submask and calculate its contribution. my submission
 » 13 months ago, # |   0 Good editorial thank u :"
 » 13 months ago, # |   +17 Please, write the editorial of Problem E.
 » 13 months ago, # |   +3 https://codeforces.com/contest/1556/submission/127394438 Can anyone review my code, it is failing at test case 17, can you please suggest som good test case. https://codeforces.com/contest/1556/submission/127400247 this one is failing at case 13
 » 13 months ago, # |   +35 The shortest solution of Problem H: Choose a valid spanning tree. Use simulated annealing algorithm, randomly delete and add an valid edge each time.
 » 13 months ago, # |   +3 "$−c_{l+1}+c_{l+2}−c_{l+2}+… as balance$"Is there a problem with this sentence? Nothing is done like this one plus one minus
 » 13 months ago, # |   +19 where E?
 » 13 months ago, # |   +16 Can someone tell me how to solve problem E ? :(
 » 13 months ago, # | ← Rev. 3 →   +36 I try to present my thoughts and my solution for Problem E. I had 45 minutes left, when i tried solving this task, so what I did was looking at small examples. The examples gave me an idea what the solution could be and lo and behold it got accepted. Let's get to it. My first example tried to find out, how many steps do we need to equalize the values of the query, if it is solvable? Let's look at this: We can see, that we obviously need 21 operations. Each operation can always take only 2 Elements at once. I calculated the differences $b-a$ and built the prefixarray on those differences. My assumption was: If it is solvable, then we have to take the maximum value of this prefixarray. That is the amount of operations we need. We can verify it with some more examples. if we double the arrays $a$ and $b$ (so $a$ will be 000777000777)? Yes, we still get 21! We need to adjust twice the values, but we can pick 4 elements at once for each operation!Now I want to find out, when is it impossible to equalize the arrays? Of course it is impossible, if the sum of $a$ is not equal to $b$. But there are cases, where the sums are equal, but it is still impossible: In the left example, we cannot increase $b_1$. So this case is not possible. In the second case, we could increase $b_2$, but that would lead to us needing to increase $b_1$ to $4$. So this case is impossible too. My assumption was: If we have a negative value in the prefix sum, then it is impossible. Turns out, those are the ideas needed to get AC. Rest was creating the right datastructures. Prefixsum is easy to generate. Now we need a data structure, to obtain the maximum and the minimum values from the prefixsum $[prefix_l, prefix_{l+1}, ... prefix_r]$. This can be done with a segmenttree (I guess there are simpler data structures for this, we do not need updates). We obtain $prefix_{min}$ and $prefix_{max}$. We still need to subtract $prefix_{l-1}$ from our values, to obtain the right numbers (to obtain, like in the examples, $prefix_0=0$).So the solution is: If $prefix_{min}-prefix_{l-1}$ is smaller than $0$ or if $prefix_r-prefix_{l-1} \neq 0$ (the sums of the subarrays are different), then there is no solution. We can output $-1$. Else there is an solution in $prefix_{max}-prefix_{l-1}$ queries. Complexity is $O(N log N)$ for preparing the prefix sums and segment tree, and then $O(Q log N)$ for answering the queries, in sum $O((N + Q) log N)$. Here is my submission: 127385969
•  » » 13 months ago, # ^ |   0 Hi~ I have a similar thought, except after I got b-a array, I took the maximum sum of consecutive same-sign numbers in [L,R], and got wrong at test 17. Turns out it's close too the solution but... how to proof it?
•  » » » 13 months ago, # ^ |   0 Maximum sum of consecutive same sign numbers? You mean for:vector $a$: 0 1 0 3vector $b$: 2 0 2 0 dif $b-a$: 2 -1 2 -3you would output $2$ as an answer, instead of $3$, the correct answer?
•  » » » » 13 months ago, # ^ |   0 Yeah, nearly, only for negative numbers I will take the absolute value, let me exemplify this.if I got a b-a: 2 1 -1 0 1 -1 -2calculate the sum of consecutive numbers that have the same sign, which is: 3 -1 0 1 -3remove the sign: 3 1 0 1 3so the answer is 3but this method turns out to be wrong. But it still passed many of the tests, so I considered it's the right way and just had some little bugs easy to fix but...
•  » » » » » 13 months ago, # ^ |   0 Oh, then takevector $a$: 0 1 0 2 0 2vector $b$: 2 0 2 0 1 0dif $b-a$: 2 -1 2 -2 1 -2Then your answer would be $2$ but it should be $3$.
 » 13 months ago, # | ← Rev. 2 →   +31 I tested my solution to problem H locally using this solution and randomly generated graphs. On a case the solution reported answer is 1e9.I submitted the test to Hacks, but Unexpected verdict is given. Such a verdict is previously discussed here.The test is attached below: test10 1 3 2 1 3 3 4 9 3 1 5 5 3 6 2 3 4 2 5 10 5 5 6 8 9 6 7 5 5 7 3 10 5 6 6 6 3 5 10 10 3 2 2 3 2 7 4 Can someone give some help? Thanks.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +35 I removed the solution that WA was giving. This was the solution of one of the participants. Can you please try again?Please, if such problems arise, then I can solve them much more efficiently and faster if you contact me in private messages.I don't always have enough time to read new comments :(
•  » » » 13 months ago, # ^ |   +11 Now it's OK. I'll remember that later.
 » 13 months ago, # |   +11 It is possible to solve $D$ with at most $2n-1$ queries.
•  » » 13 months ago, # ^ |   +27 yes, we know about it. I decided not to complicate the task.
 » 13 months ago, # |   +8 In problem F why do we it why do we insist that every x in the set winners has an edge with every y in the set of ALL\winners? Since the set of winners contains a cycle isn't it sufficient that for every y in the set of ALL\winners the exist some x in winners such that there is an edge from x to y?
•  » » 13 months ago, # ^ |   +8 oh, sorry for the stupid question. since we can't have an edge from the set of "losers" to the set of "winners" then obviously the reverse has to be the case.
 » 13 months ago, # | ← Rev. 2 →   +8 When will the solution for E be published?
 » 13 months ago, # |   +9 Can somebody explain to me the editorial solution of C, I am not able to understand it even after multiple reading...
•  » » 13 months ago, # ^ | ← Rev. 3 →   +1 For problem C, there are two rules on regular sequence. 1. The number of open and close brackets are same. i.e. the balance is 0 if +1 for open and -1 for close brackets. 2. The first and last brackets are open and close brackets repetitively. )))((( is not regular even the balance is 0.The difficult part of this problem is counting the subsequence that having two or more neighbor sets of valid bracket sequences(let's call this as grouping sequence). Let's take the string of bracket sequence as input instead of the size of the compressed sequence. For example, take a look on ()()() with 0 based index, the normal bracket sequences are (0,1),(2,3),(4,5) and grouping sequence are (0,3),(0,5),(2,5). Please noticed that the grouping sequence can only have 1 at most for the same set of sequences. Like ((())(())), the grouping sequence is (1,8) only but not (0,9). (0,9) is treated as the normal bracket sequence.Then how do we find the grouping sequence? It needs to refer to the deepest depth in between the left most and right most open and close brackets(i.e. the segment from l+1 to r−1). Take (())((())) as example, the middle segment ))((( is with balance 1 and deepest depth -2 from the balance from left to the right [-1,-2,-1,0,1] which means it requires 2 opening brackets before the sequence to make the sequence regular. It is the minBalance in editorial exactly. We can use balance plus the minBalance for the left open bracket to deduce the minBalance for the close bracket on the right minRightBalance = minLeftBalance+balance. If the left and right sequences can fullfill the minBalance, there is a grouping sequence. Any brackets pairs beyond these minBalance that can maintain balance 0(rule 1) can be considered as normal regular sequence. Let's talk about the formula in editorial. The idea to how to count the number regular sequence between [l,r] is finding the minBalance for open and close brackets of the middle segment [l-1,r-l] to make the sequence completed. If r = l+1 which means no middle segment, the count is min(c[l],c[r]). Otherwise, there is middle segment. The count is min(c[l]-minBalance, c[r]-(minBalance+balance)) + 1 if c[l] >= minBalance and c[r] >= minBalance+balance. +1 is the grouping sequence and the min() are the extra normal sequence mentioned above(#128132046). You can combine both cases, min(c[l]-minBalance, c[r]-(minBalance+balance)) + 1 > min(c[l], c[r]-balance) -minBalance + 1 > min(c[l], c[r]-balance) - max(1, minBalance) + 1 since the minBalance and balance are always 0 for case r=l+1(#128135566).Hope this can help you understand the editorial.
•  » » » 13 months ago, # ^ |   0 Thanks
•  » » » 11 months ago, # ^ |   0 Thank you so much
 » 13 months ago, # |   +11 For F:Can we just calculate every one's contribution independently,let's denote we make I be the winner and I have defeated the S(include I) and we want to defeat j , the transition is dp[S|(1<
 » 13 months ago, # | ← Rev. 2 →   0 thanks for the editorial, I didn't know this fact in problem D 1556D - Take a Guesshere is my solution which performs 2*n - 1 questionsknowing the first number in the array we can get the rest of the array let the array be [x, y, z] y = (x&y) | (~x & (x|y))z = (x&z) | (~x & (x|z))it's not hard to prove why this is correct you just need the value of x and all values of x&(other n-1 elements)all values of x|(other n-1 elements)assume the array is [x, y, z]to Compute the value of the first number let it be xinitially, the value of x is x&y | x&z and now for each bit i in x if it is not sethow to know it must be set in x? first, to know it must be unset, we just see the values of x|y, x|z if the $i_{th}$ bit is unset in at least one value of those then it must be unset in xelse there are only two cases:1- $i_{th}$ bit is set in x only.2- $i_{th}$ bit is set in all other numbers except x.we can check the second case by asking about & between any two numbers except x if the $i_{th}$ bit is set in the result then the second case is true else the first case is true and adds 2^i to x.here is my solution for better understanding, hope it helps :D 128722532
 » 13 months ago, # |   0 pls upload tutorial for problem E
 » 13 months ago, # |   0 can anyone explain the problem C I m not getting the tutorial pls...
 » 12 months ago, # |   0 Can Someone tell me what is wrong with this code https://codeforces.com/problemset/submission/1556/130615105 It is for the B problem
 » 4 weeks ago, # |   0 Can someone please explain the intuition behind this solution 128899193 for 1556B - Take Your Places!.Thanks in Advance.