Блог пользователя deltixlab

Автор deltixlab, 3 года назад, По-английски
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.

  • Проголосовать: нравится
  • +66
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 idea

    8 1 1 2 1 1 1 1 2

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится 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
»
3 года назад, # |
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 года назад, # |
  Проголосовать: нравится +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 года назад, # |
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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    .

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I'm confused about it too.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The key idea is that
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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 года назад, # ^ |
    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):

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

linear solution for C 127401730

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
    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 года назад, # ^ |
      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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me the solution to problem E please?

  • »
    »
    3 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you very much

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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 года назад, # ^ |
        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 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks for great problems , i have learnt a lot!

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +94 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
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 года назад, # |
  Проголосовать: нравится 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 года назад, # |
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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +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 года назад, # |
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
»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Nice problems!

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Когда будет доступен разбор задачи Е?

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Please, write the editorial of Problem E.

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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.com/contest/1556/submission/127455481

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

where E?

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
3 года назад, # |
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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 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 -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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # |
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:

test

Can someone give some help? Thanks.

  • »
    »
    3 года назад, # ^ |
    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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

When will the solution for E be published?

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    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 года назад, # |
  Проголосовать: нравится +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<<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....

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

pls upload tutorial for problem E