### deltixlab's blog

By deltixlab, 3 years 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

| Write comment?
 » 3 years ago, # |   +45 can someone explain the O(n) approach for C .
•  » » 3 years 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
•  » » 3 years ago, # ^ | ← Rev. 4 →   +6 A O(N) solution for Problem C in Typescript: https://paste.ubuntu.com/p/Y9JcZWkGFN/
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 can you put the code inside a spoiler?UPD : thanks :)
•  » » » » 3 years ago, # ^ |   +9 Sorry for that.
•  » » 3 years 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.
•  » » » 3 years 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.
•  » » » 8 months ago, # ^ |   0 This is elegant!
 » 3 years ago, # |   +9 The problems might be too difficult for me, but there's no doubt that the illustration in each problem is beautiful!
•  » » 3 years ago, # ^ |   0 Yes，you're right !For me,it is remarkably difficult to solve this problem.But I will work hard to understand it！
 » 3 years 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?
•  » » 3 years 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.
•  » » » 3 years 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...
•  » » » 3 years 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.
 » 3 years 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.
•  » » 3 years 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; } 
•  » » » 3 years ago, # ^ |   0 Loved it
 » 3 years 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 :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 Try this testcase:1 6 1 2 2 1 2 1Your output is 2, while the correct answer is 1.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 thanks man, a stupid doubt but how is it 1 I think 2 is the right answer ...
•  » » » » 3 years ago, # ^ |   0 swap the very first 1 and 2 and it become 2 1 2 1 2 1
•  » » » 3 years 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!
•  » » 3 years ago, # ^ |   0 Stress-tested and got this:Input: 1 10 1 2 2 1 1 2 2 2 1 1Correct output: 3Your output: 4
•  » » » 3 years 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 :)
•  » » » » 3 years 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 
 » 3 years 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.
 » 3 years 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).
•  » » 3 years ago, # ^ |   +1 That's perfect. It's a beautiful solution.
•  » » 3 years 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)$
•  » » » 3 years ago, # ^ |   0 So what's the principle of this solution? Could you please explain it to me?
•  » » » » 3 years 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)]$
•  » » » » » 3 years ago, # ^ |   0 OK. Thank you.
•  » » 3 years 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 .
 » 3 years ago, # | ← Rev. 2 →   +3 Nice round.I did enjoy the struggle even though I lost rating :).
 » 3 years 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
•  » » 3 years ago, # ^ |   +8 I'm confused about it too.
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   0 Your formula matches with rfpermen in their excellent explanation below- I think you are both right
•  » » » 3 years ago, # ^ |   0 You are right! Sorry for mistake in editorial. Editorial will be updated soon,
•  » » 3 years 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
•  » » » 3 years 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)$.
•  » » » » 3 years ago, # ^ |   0 Yes, you are right. I think the editorial missed this.
•  » » 3 years 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)$.
•  » » » 3 years ago, # ^ |   0 Thank you so much, this is a great explanation. I will assume the editorial is wrong for now.
•  » » » 3 years ago, # ^ |   0 why we have to work with set of winners? I mean why we can't use the fact linearity of expectaion?
•  » » 3 years ago, # ^ |   +5 You struggling because of mistake in editorial :) Updated editorial with much simpler formula and explanation to it.
•  » » » 3 years ago, # ^ |   0 Thanks for the fix and the great contest! :)
•  » » 3 years 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
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +8 thanks
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +11 you welcome!
 » 3 years ago, # |   +14 linear solution for C 127401730
•  » » 3 years ago, # ^ |   0 Could you explain the code bro,I feel confused about it.
•  » » » 3 years 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.
•  » » » » 3 years ago, # ^ |   0 thanks a lot！
 » 3 years ago, # |   +6 I think D is an easy version of 1451E1 - Bitwise Queries (Easy Version)
 » 3 years 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.
•  » » 3 years 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.
•  » » » 3 years 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 
 » 3 years ago, # | ← Rev. 2 →   0 Can someone tell me the solution to problem E please?
•  » » 3 years 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))$
•  » » » 3 years ago, # ^ |   0 Thank you very much
•  » » » » 3 years ago, # ^ |   0 Your welcome :)
•  » » » 3 years 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?
•  » » » » 3 years 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
•  » » » » » 3 years ago, # ^ |   0 Thankyou so much for this clear explanation!
•  » » » » » » 3 years ago, # ^ |   0 Glad I could help you :)
 » 3 years 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?
•  » » 3 years 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,
 » 3 years ago, # |   +55 I wonder how many solutions on E passed systests but fail this test case: 2 1 1 0 0 1 1 2 
•  » » 3 years ago, # ^ |   +100
•  » » » 3 years ago, # ^ |   +39 How do you write a script to find these people?
 » 3 years ago, # |   +1 Thanks for great problems , i have learnt a lot!
 » 3 years 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?
 » 3 years ago, # |   +94 I don't know but why Deltix don't decide to update the testcase in E and rejugde all the submissions?
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +83 Little did you know my submission for E failed the hack testcase also. :D
 » 3 years 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!
•  » » 3 years ago, # ^ |   0 some_other_handle Did you figure out the solution?If yes then please explain.
 » 3 years 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
•  » » 3 years ago, # ^ |   0 Sorry,it's or，not xor.I read the question wrong.
•  » » 3 years 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
 » 3 years 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.
 » 3 years 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.
 » 3 years 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
•  » » 3 years 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.
 » 3 years 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)$.
•  » » 3 years ago, # ^ |   +28 G is kind of a harder version of POI XX spa, and the same idea works on that problem too.
 » 3 years 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
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Input:1101 2 2 2 2 1 1 1 1 2Your output: 4My output: 5
•  » » » 3 years ago, # ^ |   0 thanks a lot , i found my mistake.
 » 3 years ago, # |   +20 Nice problems!
•  » » 3 years ago, # ^ |   +29 One of the finest rounds on codeforces. kudos to the problem-setters!
 » 3 years 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
 » 3 years ago, # |   +17 Please, write the editorial of Problem E.
 » 3 years 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
 » 3 years 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.
 » 3 years 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
 » 3 years ago, # |   +19 where E?
 » 3 years ago, # |   +16 Can someone tell me how to solve problem E ? :(
 » 3 years 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
•  » » 3 years 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?
•  » » » 3 years 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?
•  » » » » 3 years 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...
•  » » » » » 3 years 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$.
 » 3 years 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.
•  » » 3 years 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 :(
•  » » » 3 years ago, # ^ |   +11 Now it's OK. I'll remember that later.
 » 3 years ago, # |   +11 It is possible to solve $D$ with at most $2n-1$ queries.
•  » » 3 years ago, # ^ |   +27 yes, we know about it. I decided not to complicate the task.
 » 3 years 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?
•  » » 3 years 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.
 » 3 years ago, # | ← Rev. 2 →   +8 When will the solution for E be published?
 » 3 years ago, # |   +9 Can somebody explain to me the editorial solution of C, I am not able to understand it even after multiple reading...
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   0 Thanks
•  » » » 3 years ago, # ^ |   0 Thank you so much
 » 3 years 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<
 » 3 years 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
 » 3 years ago, # |   0 pls upload tutorial for problem E