Tutorial is loading...

**Prepared by** AleXman111.

Tutorial is loading...

**Prepared by** AleXman111.

Tutorial is loading...

**Prepared by** Vladik.

Tutorial is loading...

**Prepared by** Vladik.

Tutorial is loading...

**Prepared by** netman.

Tutorial is loading...

**Prepared by** netman.

Tutorial is loading...

**Prepared by** netman.

Tutorial is loading...

**Prepared by** 300iq.

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

can someone explain the O(n) approach for C .

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 idea

81 1 2 1 1 1 1 2A O(N) solution for Problem C in Typescript: https://paste.ubuntu.com/p/Y9JcZWkGFN/

can you put the code inside a spoiler?

UPD : thanks :)

Sorry for that.

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 validsubsequences (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.

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.

This is elegant!

The problems might be too difficult for me, but there's no doubt that the illustration in each problem is beautiful!

Yes，you're right !For me,it is remarkably difficult to solve this problem.But I will work hard to understand it！

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?

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.

But I did that and got TLE on test 8... the implementation needs not only to be correct but optimized to pass this problem...

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.

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.

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:

SpoilerLoved it

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 :)

Try this testcase:

1 6 1 2 2 1 2 1

Your output is 2, while the correct answer is 1.

thanks man, a stupid doubt but how is it 1 I think 2 is the right answer ...

swap the very first 1 and 2 and it become 2 1 2 1 2 1

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!

Stress-tested and got this:

Input: 1 10 1 2 2 1 1 2 2 2 1 1

Correct output: 3

Your output: 4

thank you so much ,but I checked through an AC code it gave output 4 can u please test it again and help :)

test case is

but not

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.

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).That's perfect. It's a beautiful solution.

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)$$$

So what's the principle of this solution? Could you please explain it to me?

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)]$$$

OK. Thank you.

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.

.

Nice round.I did enjoy the struggle even though I lost rating :).

Does anyone have a nice explanation for the inclusion exclusion formula in F? I'm struggling with the G(sub) factor in the subtraction

I'm confused about it too.

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.

Your formula matches with rfpermen in their excellent explanation below- I think you are both right

You are right! Sorry for mistake in editorial. Editorial will be updated soon,

The key idea is thatS 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

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)$$$.

Yes, you are right. I think the editorial missed this.

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)$$$.

Thank you so much, this is a great explanation. I will assume the editorial is wrong for now.

why we have to work with set of winners? I mean why we can't use the fact linearity of expectaion?

You struggling because of mistake in editorial :) Updated editorial with much simpler formula and explanation to it.

Thanks for the fix and the great contest! :)

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

thanks

you welcome!

linear solution for C 127401730

Could you explain the code bro,I feel confused about it.

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.thanks a lot！

I think D is an easy version of 1451E1 - Bitwise Queries (Easy Version)

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.

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.`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 :Can someone tell me the solution to problem E please?

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))$$$

Thank you very much

Your welcome :)

can you explain how segment tree is used to find max sum in l — r? I mean what is the merging operation here?

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 deltawe 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

Thankyou so much for this clear explanation!

Glad I could help you :)

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?

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,

I wonder how many solutions on E passed systests but fail this test case:

Apparently 92127388077 127367607 127372839 127374119 127366592 127374604 127390038 127386435 127362574 127375669 127363875 127390721 127375517 127389571 127364450 127387754 127385687 127394833 127372668 127389362 127364321 127356141 127361900 127386073 127383744 127378248 127378123 127380293 127367630 127380383 127390584 127383594 127355696 127372648 127375576 127375650 127388621 127384270 127387182 127361483 127391892 127387096 127363817 127380768 127394364 127387765 127376230 127382520 127381196 127365098 127374729 127382439 127352257 127382426 127365428 127387419 127385066 127365434 127373181 127368753 127373260 127372399 127376421 127374767 127357084 127389102 127394166 127381026 127363887 127379479 127387602 127390662 127359184 127383023 127380492 127393772 127390613 127378032 127386937 127371767 127358874 127389579 127386361 127382154 127391119 127362164 127386521 127361056 127380664 127394098 127385693 127385185

This list of submissions was found using a script written by skittles1412, have fun uphacking.

How do you write a script to find these people?

Thanks for great problems , i have learnt a lot!

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?

I don't know but why Deltix don't decide to update the testcase in E and rejugde all the submissions?

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.

Little did you know my submission for E failed the hack testcase also. :D

Can anyone please help with understanding the formula in Problem C editorial? Basically, the solution has the following skeleton.

codeNow, 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!

some_other_handle Did you figure out the solution?If yes then please explain.

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

Sorry,it's or，not xor.I read the question wrong.

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

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.

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.

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

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.

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)$$$.

G is kind of a harder version of POI XX spa, and the same idea works on that problem too.

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'codeInput:

1

10

1 2 2 2 2 1 1 1 1 2

Your output: 4

My output: 5

thanks a lot , i found my mistake.

Nice problems!

One of the finest rounds on codeforces. kudos to the problem-setters!

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

Please, write the editorial of Problem E.

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

The

shortestsolution of Problem H:Choose a valid spanning tree.

Use

simulated annealing algorithm, randomly delete and add an valid edge each time.Code:https://codeforces.com/contest/1556/submission/127455481

"$$$−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

where E?

Can someone tell me how to solve problem E ? :(

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

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?

Maximum sum of consecutive same sign numbers? You mean for:

vector $$$a$$$: 0 1 0 3

vector $$$b$$$: 2 0 2 0

dif $$$b-a$$$: 2 -1 2 -3

you would output $$$2$$$ as an answer, instead of $$$3$$$, the correct answer?

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 -2

calculate the sum of consecutive numbers that have the same sign, which is: 3 -1 0 1 -3

remove the sign: 3 1 0 1 3

so the answer is 3

but 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...

Oh, then take

vector $$$a$$$: 0 1 0 2 0 2

vector $$$b$$$: 2 0 2 0 1 0

dif $$$b-a$$$: 2 -1 2 -2 1 -2

Then your answer would be $$$2$$$ but it should be $$$3$$$.

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:

testCan someone give some help? Thanks.

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 :(

Now it's OK. I'll remember that later.

It is possible to solve $$$D$$$ with at most $$$2n-1$$$ queries.

yes, we know about it. I decided not to complicate the task.

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?

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.

When will the solution for E be published?

Can somebody explain to me the editorial solution of C, I am not able to understand it even after multiple reading...

For problem C, there are two rules on regular sequence. 1. The number of open and close brackets are same. i.e. the

balanceis 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 withbalance1 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 theminBalancein 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.

Thanks

Thank you so much

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<<j)] = mul(dp[S|(1<<j)],f[S][j]) ,f[S][j] means that the probability defeat j with at least one member in S.

How can we hack the thought.... I code it and fail on the test2... Can someone hack me,please,I almost be mad....

thanks for the editorial,

I didn't know this fact in problem D 1556D - Take a Guess

here 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

`x`

initially, 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 x

else

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 xif 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

pls upload tutorial for problem E