deltixlab's blog

By deltixlab, 4 weeks ago, In English
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.

 
 
 
 
  • Vote: I like it
  • +66
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    8 1 1 2 1 1 1 1 2

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +108 Vote: I do not like 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?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +78 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like 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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me figure my mistake for B I am unable to find and stuck for hour now :( https://codeforces.cc/contest/1556/submission/127399981 upd: Got it AC'ed finally :)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Try this testcase:

    1 6 1 2 2 1 2 1

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Stress-tested and got this:

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

    Correct output: 3

    Your output: 4

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
        
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
4 weeks ago, # |
Rev. 2   Vote: I like it +274 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Orz Int-Master heading for -> Grandmaster soon!.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    That's perfect. It's a beautiful solution.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Learned a lot of things about BIT operations in a single comment.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    .

»
4 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I'm confused about it too.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The key idea is that
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

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

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

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

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

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.cc/contest/1556/submission/127474511

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

linear solution for C 127401730

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like 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.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone tell me the solution to problem E please?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        Tokyo dies in Money Heist s5

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 4   Vote: I like it +8 Vote: I do not like it

        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 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thankyou so much for this clear explanation!

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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,

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for great problems , i have learnt a lot!

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you briefly explain what you are doing regard to Problem F, 罗思远 ?

»
4 weeks ago, # |
  Vote: I like it +94 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -96 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +83 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it -56 Vote: I do not like it

        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.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

code

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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Can someone please explain it in more detail? I am having difficulty understanding editorial for this problem too :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.cc/contest/1556/submission/128076123

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now we are going to have another problem for interactive in the future.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same doubt lol..i thought im the only one not getting it :(

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C problem was almost done but got wrong answer on pretest 13

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it +136 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain me how we will solve question B by two pointer method???

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.cc/contest/1556/submission/127420215

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

AleXman111 Can you plz. provide me the code that follow the approach that you explain in the editorial of problem B?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the solution for C

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Your code here...
    #include <bits/stdc++.h>
    
    using namespace std;
    using ll = long long;
    
    int main() {
    	cin.tie(0)->sync_with_stdio(0);
    
    	int n;
    	cin>>n;
    	vector<ll> c(n);
    	for (auto &i:c) cin>>i;
    
    	ll ans=0;
    	for (int i=0; i<n; i+=2) {
    		ll s=0, mx=c[i]-1;
    		for (int j=i+1; j<n; j+=2) {
    			s+=c[j-1]-c[j];
    			ll u=min(mx, s+c[j]), d=max(0ll, s);
    			ans+=max(u-d+1, 0ll);
    			mx=min(mx, s);
    			if (mx<0) break;
    		}
    	}
    
    	cout<<ans<<'\n';
    
    	return 0;
    } 
    

    why he take mx=ct[i]-1 ?

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone help me with my code at problem B :<. I got WA at pretest 2.

here is my submission 127369911

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the solution of b problem

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the solution of second question i am stuck on it please

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain for me problem B test case 1 1 1 2 2 2 ? when I use two pointer

  1. 1st swap result will be 1 2 1 1 2 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.cc/contest/1556/submission/127426964

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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
»
4 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Nice problems!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Not able to understand the editorial for

Compressed Bracket Sequence

Can someone please explain that formula dry run with an example?

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good editorial thank u :"

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Please, write the editorial of Problem E.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.cc/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.cc/contest/1556/submission/127400247 this one is failing at case 13

»
4 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

The shortest solution of Problem H:

  1. Choose a valid spanning tree.

  2. Use simulated annealing algorithm, randomly delete and add an valid edge each time.

Code:https://codeforces.cc/contest/1556/submission/127455481

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

where E?

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 3   Vote: I like it +36 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

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:

test

Can someone give some help? Thanks.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

When will the solution for E be published?

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there a typo in the definition of $$$balance$$$, which it writes $$$-c_{l + 1} + c_{l + 2} - c_{l + 2} + \dots$$$. Shouldn't it be $$$-c_{l + 1} + c_{l + 2} - c_{l + 3} + \dots$$$

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Can you please briefly explain the solution? I'm unable to understand the editorial.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I do not know how to explain the solution in editorial length. But I believe you can check out the link: https://youtu.be/7AHvvTWSsqY This tutorial has better explanation than the editorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Yes its a typo

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it -8 Vote: I do not like it

    For Compressed Bracket Sequence : The minimum bracket balance is the minimum number of opening brackets that we must put before the sequence of brackets in order for it to be regular, provided that we can put any number of closing brackets at the end.

    can You explain how to calculate minBalance taking [1, 3, 2, 1, 2, 4, 4, 2] eg for l = 1, r = n(8). Please!!

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 questions

knowing 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 set

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

pls upload tutorial for problem E

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the problem C I m not getting the tutorial pls...