TeaTime's blog

By TeaTime, 2 years ago, In English

A — Burenka Plays with Fractions

Authors: glebustim

Solution
Code(C++)

B — Interesting Sum

Solution
Code(C++)

C — Corners

Authors: daubi

Solution
Code(C++)

D1 — Xor-Subsequence (easy version)

Authors: kirill.kligunov

Solution
Code(C++)

D2 — Xor-Subsequence (hard version)

Authors: kirill.kligunov

Solution
Code(C++)

E — Misha and Paintings

Authors: daubi, pakhomovee

Solution
Code(C++)
  • Vote: I like it
  • +154
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +210 Vote: I do not like it

We are sorry for statement of problem D being unclear :( We will do our best to write cleaner and easier to understand statements next time! We hope you enjoyed solving our problems though.

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

    But this problem is really good!

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

    Hey, thanks for the round. The problems were definitely enjoyable!

    Just to clarify, the statement was not unclear, it was wrong. On top of trying to write cleaner and easier statements, please update statements during the contest if it is pointed out as wrong.

    Thanks, hoping to see more rounds from you!

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

      Why was it wrong?

      I don't think it was wrong.

      Maybe the word subsequence can mislead someone, but there is no scientific mistakes in the statement.

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

        The use of "subsequence" was wrong.

        It is mentioned that array $$$b$$$ is a subsequence of array $$$a$$$. But this is not the case. $$$b$$$ is a subsequence of $$$[0, 1, 2,..., n-1]$$$.

        I'm not complaining about the problem being not understandable. If you read the statement and examples, you understand what $$$b$$$ actually is.

        I'm just saying that not fixing an obvious mistake after being pointed out is a bit insincere.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 3   Vote: I like it -27 Vote: I do not like it

          You thought the use of "subsequence" was wrong, just because you have believed that:

          if you use the word "subsequence" and say that an array $$$b$$$ is a subsequence of $$$a$$$, then the objects in $$$b$$$ must occur in $$$a$$$.

          and the definition is opposite your normal comprehension of the word "subsequence".

          But the statement gave us a different definition of "subsequence", then no wonder how the definition was odd, the following description with the word "subsequence" must obey the definition.

          In the statement, it said that an array $$$b$$$ is a subsequence of $$$a$$$ means that:

          $$$0 \le b_0 \le b_1 \le ... \le b_{m-1} < n$$$

          and the following statements did not conflict with this definition, so you can say the definition is trash and not understandable, but you can't say it is wrong.

          I'm just saying that the statement wasn't scientifically wrong even if it is not understandable.

          I know the word subsequence normally means picking some values in a. And I even didn't see any usage of subsequence that means picking some indexes.

          But I want to say, if the problem provider explicitly redefinite a word, then he has the right to use this word to express a different idea in his problem.

          Just like you can overload operators in your code, and use it in your meaning of the operators. This operator has normal meaning, but in this code, what it means depends on how you definite it.

          Why downvotes while I am explaining reasonably? I don't understand.

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

            How could you come up with "statement gave us a different definition of 'subsequence'"? If you choose numbers in $$$a$$$ which satisfy $$$a_i \leq n$$$, you can still get $$$0 \leq b_i < b_{i+1} \leq n$$$. Maybe by your standards, ambiguity doesn't affect correctness?

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it -9 Vote: I do not like it

              Yes, you can choose numbers in $$$a$$$ which satisfy $$$a_i \le n$$$. But how it matters?

              The statement is pretty clear that you can pick such $$$b$$$ only if $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$.

              Maybe you don't know even basic logic, the statement didn't say that you have to pick numbers within $$$a$$$, but if you want to pick numbers within $$$a$$$ which satisfy the condition, that's OK.

              It's just the difference between sufficient condition and necessary condition. It's not ambiguity.

              I hope you can understand.

              Just look at the statement, and tell me what two sentences conflicts, which means wrong. If there is no such sentences, don't say it is wrong.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                if you want to pick numbers within a which satisfy the condition, that's OK

                No, it's OBVIOUSLY not OK. You can only choose one of them: pick it from $$$a$$$, or pick it from indexes of $$$a$$$. If statements don't declare which one you should choose, it's totally ambiguous. Again, if you think ambiguity is not wrong, that's good for you.

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

                  Seems that you can't understand what a "definition" is.

                  Let me give you an example that probably helps you understand:

                  I can definite a diameter of a graph which means the length of the longest chain in the graph.(normal version)

                  I can also definite a diameter of a graph which means the length of an edge which is the longest of all shortest path between any two vertexes.(definition in 1712D - Empty Graph)

                  See? We can definite the same word in two different situations, and you didn't say that 1712D - Empty Graph was wrong, right?

                  Same for this problem.

                  In the normal sight, a subsequence of $$$a$$$ is a set which contains some of the numbers in $$$a$$$.

                  In this problem, a subsequence of $$$a$$$ is a set which doesn't matter with $$$a$$$.(You can understand it as $$$index$$$ of $$$a$$$, but actually it is just a set of numbers which satisfy the definition $$$0 \le b_0 \le...\le b_{m-1 }< n$$$.)

                  And you can use the set of numbers to do something: use $$$a_{b_p} \oplus b_{p+1}$$$ to compare with $$$a_{b_{p+1}}⊕b_p$$$.

                  But it is just a usage of this set of numbers, it doesn't means that $$$b$$$ was born to be a sequence of index of a. No one claims that, it is just your guess.

                  So understand? the definition of Subsequence in this problem is OBVIOUSLY not AMBIGUOUS. It is not AMBIGUITY. It just mislead you and other participants, but it's pretty clear that you are misleaded badly because you just can't understand what a definition is.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  it doesn't means that b was born to be a sequence of index of a. No one claims that, it is just your guess.

                  lmao. If it's my gusee, then where's the defination of the special meaning of subsequense in this statement?

                  By the way, shouldn't you google what "ambiguous" means first before you reply me?

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

                  where's the defination of the special meaning of subsequense in this statement

                  An array b=[b0,b1,…,bm−1], where 0≤b0<b1<…<bm−1<n, is a subsequence of length m of the array a.

                  Here. You can find it in the statement.

                  By the way, If you are too lazy to look again at the statement, then don't tell me to GOOGLE the definition of a word that I understand much better than you.

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

                  Also, your words of "choosing" one of the normal definitions in your mind and sight is absolutely ridiculous and absurd.

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

                The word subsequence implies that you are only allowed to pick values in a. When one looks at the examples it is clear that this isn't what it meant, but it is what it said. The condition on these values restricts which values you can pick (they have to be increasing and less than n).

                If one interprets the text of the problem literally, the only acceptable subsequence in example 1 would be [1] (which is trivially beautiful) so the answer to example 1 would be 1.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Seems that you still don't understand what I am saying.

                  I know the word subsequence normally means picking some values in $$$a$$$. And I even didn't see any usage of subsequence that means picking some indexes.

                  But I want to say, if the problem provider explicitly redefinite a word, then he has the right to use this word to express a different idea in his problem.

                  Just like you can overload operators in your code, and use it in your meaning of the operators. This operator has normal meaning, but in this code, what it means depends on how you definite it.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The issue is that there are two ways of reading the sentence:

                  An array b=[b0,b1,…,bm−1], where 0≤b0<b1<…<bm−1<n, is a subsequence of length m of the array a.

                  It can be read either as a definition of a subsequence, or as simply a definition of b.

                  If read as a definition of "b" it means:

                  An array b=[b0,b1,…,bm−1] is a subsequence of length m of a with the restriction that 0≤b0<b1<…<bm−1<n.

                  The word order implies that it is defining "b", not "subsequence". "X is a Y" is normally telling you about "X" not about "Y"; particularly if it is the first time X has been mentioned, and Y is already well known.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  No doubt it is a definition of a subsequence.

                  Let me simplify the sentence:

                  b which satisfy (condition) is a subsequence of length m of the array a.

                  Haven't you ever saw this kind of definitions?

                  An array b is a permutation of an array a if b consists of the elements of a in arbitrary order. For example, [4,2,3,4] is a permutation of [3,2,4,4] while [1,2,2] is not a permutation of [1,2,3].

                  It defines what a permutation is, not what b is.

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

                  The difference between "where" and "if" matters.

                  Consider:

                  A rek is a fafi **where** the top is red.

                  vs.

                  A rek is a fafi **if** the top is red.

                  The first is telling you that all reks are fafis, but that a fafi is a rek if and only if the top is red, the second is telling you all reks with red tops are fafis, and may be defining fafi. There may, however, be other reks with green tops that are not fafis.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The difference between "where" and "if" sure matters.

                  but you just ignored the word order.

                  look at the following two sentences:

                  an array a, where (condition), is a xxx of b.

                  vs.

                  an array a is a xxx of b where (condition).

                  The first is telling you that a is an array, and if the array fits (condition), it is a xxx.

                  The second is telling you that a is an array, and also it is a xxx, which also fits (condition).

                  Same as this sentence.

                  An array b=[b0,b1,…,bm−1], where 0≤b0<b1<…<bm−1<n, is a subsequence of length m of the array a.

                  • b is an array.
                  • if b fits (0≤b0<b1<…<bm−1<n), it is a subsequence of length m of the array a.
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No it doesn't. It says that this is a condition on the subsequence. Consider the sequence

            a = [1,5,2.3.7]

            a valid subsequence satisfying the condition would be: [1,2,3]

            [0,1,2,3,4] would not be a valid subsequence of a since 0 and 4 aren't in a, so it isn't a subsequence of a.

            [1,5,2] is a subsequence of a, but would not satisfy the condition.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The point is that b is not a subsequence of a, it is a subsequence of the indecies of a. It took me two readings of the problem to realise that the term subsequence was not being used with its normal meaning.

        The problem would have been clearer if it had simply said:

        b=[b0,b1,…,bm−1] is an array where 0≤b0<b1<…<bm−1<n
        
        Array b=[b0,b1,…,bm−1] of length m is called beautiful, if the following condition holds:
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Never mind, the whole contest is really enjoyable, and the problems are interesting (I like C and D1 best).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution to the misunderstood version of D1 has come out. The link is out there. :)

    Can anyone solve the misunderstood version of D2? I can't figure out. qaq

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey , Can u help me understand how can we prove that in D , we only need to check from i-256 to i-1 ?

»
2 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Observation forces

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

thanks for fast editorial)

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A was a bit too tedious for a task in such a place, and I think many contestants today gave up completely because they cannot finish A.

All of the other problems are really nice, though.

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

    Didn't gave up. Tried till last minute. Yet couldn't manage to solve A :V

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

      I just quit A, and thankfully I solved C, which I usually dont do in a div 2

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

    Deciding to quit before submitting A is not giving up, it is strategy.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I agree with you, I did this strategy in this contest.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm confused. In D1 Wouldn't i-256 also work, since it toggles the 9'th bit (which cannot be toggled by any number in the array).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it does, but 500 works as well and might be easier to see why.

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

    i tought "xor 200 will add or subtract at most 200". So i went with 402 just to be sure. It feels like the most intuitive lower bound to me, but i didn't think about it too much

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The best bound I could think of is i-2*max+1 (and it does not need to be the maximum of the entire array, just of the elements before and including the current one, from 0 to i):

    If j < i-2*max+1, then j <= i-2*max and j^ai <= i-max <= i^aj. So, if j < i-2*max+1 we do not need to check this j.

    But maybe this is not the best possible bound: I just manually binary-searched the problem and i-255 is accepted, i-254 is not.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is correct. Technically, $$$i - 256$$$ and below are guaranteed to fail the condition (since the prefix before the last 8 bits cannot be XOR'd out), so you can start checking from $$$i - 255$$$ onwards.

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

      In fact, you can do something more interesting — simply tile n in sections of 256 and solve each section separately.

      168859265

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In the solution of D2, an 'equal' is wrong spelled.

and if it's equels 1).

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

C was a nice problem

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

d1 and d2 are two good problem!

»
2 years ago, # |
  Vote: I like it +52 Vote: I do not like it

I can't get the editorial of Problem E. Is it too simple or poorly explained? Can somebody please explain the solution ?

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

    There is a trivial case when the number of distinct values ($$$d$$$) is less than $$$k$$$. In that case we have to increase this value. So the best way to do is by doing $$$d - k$$$ operations of choosing $$$1 \times 1$$$ matrices and setting some values.

    Now, if $$$d \ge k$$$, it can be proven that the answer is at max $$$2$$$. Let's prove it. Choose a submatrix of size $$$L$$$ from the top left corner such that colouring the entire submatrix to some new colour makes the new value of $$$d$$$ at least $$$k$$$. We will choose the maximum possible such $$$L$$$. Since $$$L$$$ is the maximum possible, if we increase it by even one more, we will end up getting $$$d < k$$$. This means that the extra row and extra column that we are adding by shifting from $$$L$$$ to $$$L + 1$$$ contains a some distinct values that makes the value of $$$d$$$ cross over $$$k$$$ in a big jump. We only need to change some of these values. So we are looking from small jump instead of this big jump.

    So instead of changing these extra values from the top left, let's try to change them from the bottom right i.e. in our second operation we will choose a different submatrix such that it's bottom right corner lies at $$$(L, L)$$$ (the intersection of the row and column that makes all the difference). Notice, that we can tweak the size of this second operation submatrix to our own choice such that we can make a jump as close as possible to $$$k$$$. Increasing the length of this submatrix, can atmost create a difference of $$$2$$$ (one in row and one in column). So we can land our $$$d$$$ at $$$k$$$ or at $$$k - 1$$$. If we land at $$$k$$$, we're good to go but if we land at $$$k - 1$$$, we will still be good to go since, we can change the colour of this second operation to some new colour altogether which will increment our $$$d$$$ to $$$k$$$.

    So it has been proven that we can obtain the final state in atmost two operations.

    Let's first define a term I'll call complete coverage. A submatrix $$$S$$$ is said to completely cover a value $$$v$$$ if the complement of the submatrix (w.r.t. the original matrix) does not contain the value $$$v$$$ at all. Another term, I'll define is bounding box. The bounding box of a value is the smallest matrix that completely covers it.

    Now, we have to find out whether we can get the answer in one operation or not else the answer will be two. For the one operation that we want to do, we can iterate over the length $$$len$$$ of the submatrix of the operation and check whether there exists a submatrix such that treating it as our operation gives us the final state. For each possible length, we can iterate over all the possible values in the matrix and figure out which submatrices of size $$$len$$$ will completely cover this value. If we find a submatrix which completely covers exactly $$$d - k$$$ or $$$d - k + 1$$$ values, we can do 1 operation on this submatrix and get the new value of $$$d$$$ to be equal to $$$k$$$. We can do this in $$$O(n^2)$$$ time using 2D Lazy Addition using Prefix Sums (explained below). So this gives a total of $$$O(n^3)$$$ time complexity.

    For finding the number of complete coverages for each submatrix, what we can do is we can represent the submatrix firstly by just it's top-left cell. Now, for each value, we can calculate it's bounding box. We will use 2D Lazy Update on the extreme corners of this bounding box to add 1 (the submatrices of length $$$len$$$ that contain this bounding box have 1 more value completely covered). And then we can calculate 2D prefix sum to get the final number of complete coverages.

    Submission

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem-B it's mentioned that you cannot take subsegment of length = n (r — l — 1 < n) but it is taking subsegment of length=n as a correct solution, please let me know if I am wrong.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In which test case ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know in which test case, but i am getting it wrong considering max length=n-1, and i have seen some correct solutions considering max length=n

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        u didn't take n size and the logic is simple behind it u just have to maximized last answer so for that reason u need only 4 index of sorted array first second last second last

        then i will just select any of two index which doesn't have n size actually i can make it using r-l+1<=n-1 just think

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          1 6 2 1 3 6 10 9 In this case, to satisfy your condition we have to take subsegment with l=1 and r=6 which is not satisfying r-l+1<n. Please tell me where am i getting it wrong? Thanks

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh sorry, got it I misunderstood problem statement

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            also an answer in this case (n=8) is l=3,r=7, 7-3+1<8

»
2 years ago, # |
  Vote: I like it +78 Vote: I do not like it

The code for problem E in the Editorial is incorrect. Countertest:

3 5
1 2 3
4 5 6
7 8 9
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for noticing! I posted correct solution.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Here we go, Thanks for the lightning fast editorial:)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

kirill.kligunov bring a new word for our: subsequence, mean for index of some array.

Learn a lot from statement of problem D.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah D statement is really confusing

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain why we dont have to go beyond 256 for checking for a particular i... i am not able to get this by editorial

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

    It's because when xoring a[i] with j, you will get j modified by maximum 8 bits (because a[i] <= 200), therefore you need to check only the last 256 to make it bigger than a[i] ^ j

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm sorry, but I didn't get you, could you explain a bit further?

      We have known that because $$$a[i],a[j]\leq 200$$$, so that utmost changes of j and i is 256. However, as j added 256 and i decreased 256, the gap between j and i was 512 in total.

      The editorial said the it was correct as well despite you started j from i-256, which is beyond my comprehension. Could you please explain why, if in your comfort?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You have to see it as binary representation to understand it better.

        You are now at position j, a[i] ^ j is gonna range between j and j — 256, because only the first 8 bits can change. Now you have to find this is i that satisfies the property that a[j] ^ i is bigger than a[i] ^ j. Because of what I said earlier, to achieve that the only posibilities of i are between j and j — 256.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for your reply.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Did it help you at least?

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Could you explain it a bit more ?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                What exactly?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  a[j]⊕i changes i not more than by 200. This part in the editorial

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  visualize in binary to understand better

                  when xoring, all that matters are the set bits (1)

                  because you have a[i] <= 200 => a[i] can have 8 set bits (from 0th to 7th)

                  so when you are xoring i with a[j], only the last 8 bits change in the binary represation of i, if you convert those possible outcomes in base 10, you get a maxmum of 256

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Of course. Thank you for your timely comment(and sorry for the time gap)!

              However, what I really want to know is the following. In your clarification, you have explained a[i] ^ j is in range(j-256, j), and you concluded that thus " that the only posibilities of i are between j and j — 256",but what about the i? a[j] ^ i makes it possible that i may increase 256 as well.(An obvious property is that $$$a-b \leq a \bigoplus b \leq a+b$$$), Then the maximum gap between a[i]^j and a[j]^i may be 512 instead of 256. The editorial said "it's not hard that we could prove j from i-256"(note that i and j have different meanings in your explanation and the editorial), which really confused me.

              Thank you again for making such timely explanation and I'm looking forward to your further comments! :)

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Because you are doing a[i] ^ j that is the boundary, because you habe to make a[i] ^ j < a[j] ^ i, because of that, the range of i is between j, j — 256 (the same observation applies here)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Get it. Thank you~

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  skytyf Can you explain it to me why it's not 512? how are we reaching 256?

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

                  I believed Sochu's clarification is one of the proof. To me, I understood it in this way:

                  (Please copy it into notepad to read more comfortably) If the gap between i and j is over 256, the last 9th digit of i and j in binary representation is bound to change by at least 1.(That is, the pattern of i and j in binary representation is like (1..M********)_2 and (1..(M-1)********)_2 [Of course we didn't consider the M=0 case because the reason is the same and '*' can be 0 or 1 arbitrarily] )

                  emphasis:We want to find a[j] ^ i < a[i] ^ j (when j<i) Suppose the case I raised above, why we didn't take the 512 into account?Let us consider why (i-512, i-257) definitely don't fit in the case. Due to the reason above, j in this range have the last 9th digit different from the i(or maybe 10th, 11th...), and a[i] <= 200, which is only have a (********)_2 format. And after a[j]^i a[i]^j,the last 9th digit didn't change, and then we reach that a[i] ^ j still less than a[j] ^ i(Because 9th digit is less), which didn't meet our condition.

                  So we just have to start j from i-256

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1720/submission/168870933 can anyone pls tell whats wrong in this submission?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it's due to the floating-point error.

    Try to compare a * c and b * d to compare a / b and c / d.

    Don't forget to use bigger data type such as long long!

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

    Never use doubles and floats if you can avoid it.

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

    Floating Point precision error. Try this test case:

    1 1000000000 0 1
    

    It should return 1, since you need to multiply the first numerator by 0, but your code seems to print 0, because it incorrectly calculated the first fraction as 0 due to precision errors.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B — Interesting Sum Proposed solution O(nlog(n)) fails with time limit on test 15 when it's implemented in Java (not sure about other languages).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suppose you can steal SecondThread's template and use his custom sort and input? It might be good enough.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't get the 'C' problem. Can anyone explain?

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

    Suppose you have two 0s that are next to each other, either horizontally, vertically, or diagonally. Then either the entire matrix is filled with 0s, or there exists a 1 that can be covered by an L-piece that also covers 2 zeros. The nice thing is that even after covering this 1, the property must continue to hold, so there is another 1 that can be covered by a single L-piece that also covers 2 zeros, and so on. As a result, if there are $$$k$$$ 1s in the matrix, then we can perform $$$k$$$ operations to zero them all, covering exactly one 1 with each operation. Try this out with Sample Input #2.

    But if you don't have two 0s aligned (horizontally, vertically or diagonally) at first, then you have to place the first piece in an area with two 1s (if a 0 exists), or in an area with three 1s (if there is no 0 at all initially). After that, however, the remaining 1s can be covered one at a time.

    Basically: if there exists two 0s aligned horizontally/vertically/diagonally, then the answer is the number of 1s initially. Otherwise, if there exists at least one 0, then the answer is (number of 1s) minus 1. Otherwise, if there is no 0, then the answer is (number of 1s) minus 2.

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

Weak pretest for A, there wasn't even a test case in pretest with b==d and a and c being coprime, (or variant of it) and many answers got failed in system test due to that. I guess it is easy to have all such simple combinations for pretest., Especially for current A question.

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

    I actually think this is a good thing for Problem A when the logic is actually simple, since it punishes those who try to speedsolve it without actually thinking properly about whether their answer is correct, while also rewarding the careful solvers with an opportunity to hack them.

    I can understand the annoyance if it was a really tricky edge case, but for this one, the system tests that are destroying A submissions are stuff that the solver really should have considered before submitting, instead of being so impatient.

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

      The point is pretest should represent minimum possible validation of correctness or trivial cases. And if the solution wrong, then penalty would do the job for wrong submission.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A and B harder than C ngl

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate to say this but I believe the statement for B isn't clear enough. When I read the equation to determine beauty of subsegment, I thought it's max(a) — min(a) + max(a[l:r]) — min(a[l:r]). So my intuition to that problem is we want the subsegment to be as long as possible since we can include more elements for the max of the subsegment to be bigger and min to be smaller. So what I thought was that the answer max of max(a) — min(a) + max(a[1:n-1]) — min(a[1:n-1]) and max(a) — min(a) + max(a[2:n]) — min(a[2:n]). (Here [l:r] both sides are inclusive) But it turned out to be different and I still can't turn my head around that. Only reason why I got to the answer was deducing from the sample explanation.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The reason it's different is that your formula is slightly wrong. Instead of the max and min of a, the first two terms should be the max and min of a excluding the subsegment [l, r]. Notice that in the equation for a subsegment's beauty, in the first two terms, the indices jump from l-1 to r+1.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I succeeded to solve D2 using bit tree on two values: 168855514. I struggle to evaluate the complexity of this solution. Can somebody explain it to me? I guess there is some countertest for getting TLE

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, same to you, except that I didn't implement this idea because of its confusing complexity. In normal Trie problem, we only need to choose one son (or we say direction) to go down. But here we might need to choose two out of four.

    So one possible countertest is that: we sue the first half to construct a trie exclusively for one certain pattern. And then we repeat this pattern in the latter half so that we need to go through all the leaves in Trie constructed by first half.

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

Cool... problem set was good.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Didn't get the logic of i-512 in question D. Can anyone explain it in detail.

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

    I think 400 is clearer. Because we need $$$a_{j}$$$ ^ $$$i$$$ < $$$a_{i}$$$ ^ $$$j$$$ with $$$i>j$$$ and $$$i,j$$$ is belong to the subseqenuce. We have $$$a_{} \le 200$$$,and operation xor can change the number +200 or -200 at most. So the extreme case is $$$i - 200 < j + 200$$$,then it is $$$j > i - 400$$$.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It means for each j we have to iterate till i-400?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's just a easier solution for me. Its complexity is right. I learned we can use i-256 in this blog.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain what mistake I made for A? 168826645

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I do not understand the solution to D2. Are we solving for each prefix in order ? Is i the index of the last element of the prefix ? Is j the index of the element before it ? Are the k bits the k most significant bits or least significant bits ? Are the "answers" the length of the subsequences for each prefix ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same questions. The editorial is quite unclear and has some grammatically wrong sentences that are hard to comprehend. Please, in case you finally understand how to solve D2, share an explanation

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically you are solving like the dp brute force. Because of the fact that a[i] ^ i has the same prefix of a[j] ^ j, you are trying to track it with a trie. Now if you traversed k bits, the k + 1'th bit should satisfy the property. Because of that you need to keep track in the trie the maximum answer which has the prefix of a[i] ^ i, between of all possible js, that has the k + 1 th bit of j and k + 1 th bit a[j]

    Check my submission: https://codeforces.net/contest/1720/submission/168889011

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for taking the time to explain !

      I still do not understand, why would a[i]^i and a[j]^j have the same prefix ? What are those bits that we are traversing ? Which property are you talking about ?

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

        There is a prefix which is equal in a[i] ^ j , and a[j] ^ i, now think of that prefix as a number: (imagine now that you have only the common prefix) a[i] ^ j = a[j] ^ i, xor it with j => a[i] = a[j] ^ j ^ i, xor it wity i => a[i] ^ i = a[j] ^ j

        We are traversing the bits of a[i] ^ i, the only thing that remains is to satisfy the property, by tracking what I explained last

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    See my comment below, I explained it in more detail (Also the guy above my comment explained it well)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone explain c . editorial is not at all clear

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but in the question they mentioned that take L shape such that one square at corner is left .

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I do not understand your remark.

        If there are two zeroes in a 2 by 2 submatrix and at least a one is still present in the grid, you are certain to be able to remove a single one in a single step, by including two zeroes in the L shape. Thus the answer will be the number of one in the grid.

        Otherwise, if there is at least one zero in the grid, you will be able to remove only two one in one step, by including a zero in the L shape. Then, you are left with the first case, so you just removed an extra one in the first step. The answer is the number of one in the grid, minus one.

        Finally, if there are no zeroes in the grid, your first step will remove two extra ones. The answer will be the number of one in the grid, minus two.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it
If the tut of Problem D1 is not clear. Have a look here : 
observe the inequality a[j] ^ i < a[i] ^ j.
notice that a[i] < 200 so, we can observe that : 
        1. by doing a[j] ^ i , we can reduce i by atmost 256
        2. by doing a[i] ^ j, we can increase j by atmost 256
Hence and after reducing i to i' and increasing j to j', we need to check if j' > i'.
So to find the max length ending at index i, we have to look only 512 indexes left to it.
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can a[j]^i really reduce i by 256. I mean according to me, it can reduce it by 200 atmost. If it can, can you please give any example.

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

Would someone mind explaining to me why if x=bc/ad then bc must be divisible by ad in problem A

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

    Because if bc/ad=x and x is an integer, then bc is divisible by ad by definition.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For $$$D2$$$, what I got from the editorial is that for each $$$i$$$ from $$$0$$$ to $$$n-1$$$ we will calculate $$$dp[i]$$$ which is the maximum size of a valid subset ending at $$$i$$$, then insert it into the trie by descending with value $$$a[i]\oplus i$$$.

My question is: While we are descending the trie to calculate $$$dp[i]$$$, if the $$$k^{th}$$$ bit is $$$0$$$ in $$$a[i]\oplus i$$$, we will descend in the left subtree but before that we want to know the best possible answer in the right subtree. So, we actually want the maximum value in the right subtree which corresponds to $$$j$$$ whose $$$k^{th}$$$ bit has a specific value (which will make $$$a[j]\oplus i < a[i]\oplus j$$$). How can we do this part?

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

    note that since the prefix of the bitstrings of $$$a_i \oplus i$$$ and every other string in this specific subtree of the trie must be identical. as such, the kth bit should be the first one to differ. We also know that this bit is identical in $$$i$$$ and $$$a_i$$$(because $$$i \oplus a_i = 0$$$). So, if it is on in both we want a $$$j$$$ such that the kth bit is on in $$$a_j$$$(since this is the other subtree of the trie where $$$a_j \oplus j = 1$$$, this means that the kth bit is off in $$$j$$$ by default). Otherwise, if it is off in both then we want the kth bit in $$$a_j$$$ to be off. Similar casework can be done for all other configurations of $$$i$$$ and $$$a_i$$$. As such, for each node in the trie, we can keep track of the max $$$dp$$$ value where the kth bit in $$$a_j$$$ is on, and the max $$$dp$$$ value where the bit is off separately.

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

      'We also know that this bit is identical in i and ai(because i⊕ai=0)' Can you explain how?

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

        It's because the original question proposed travelling to the left subtree as an example for that bit

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

    Suppose all the element idxs in the subtree you don't descend are {j1, ...}. If you are on the kth bit, you know for sure that the previous bits are equal, so the only important bit is the kth.

    So you only need to save the max dp for j's with kth bit equal to 0, and another for j's with kth bit equal to 1

    If kth bit of a[i] is 1, you'll need the answer for j with kth bit 0. If kth bit of a[i] is 0, you'll need the answer for j with kth bit 1.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks all for your insights, they are appreciated.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can someone explain D2 to me like I'm stupid? Because I couldn't quite understand the editorial after storing the answer in a bit trie and also because I pretty much am

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

    We can build the longest subsequence iteratively by sweeping from $$$0$$$ to $$$n$$$ and finding the longest subsequence so far that our current index(lets call it $$$i$$$) can add on to. Naively, this is $$$dp$$$ solution is $$$O(n^2)$$$.

    The main intuition behind the speedup to this problem is that, when comparing two numbers $$$a$$$ and $$$b$$$ in their binary representation, the only important digit $$$k$$$ is the first digit where they differ. Conveniently, there are only 30 possible values of $$$k$$$. This motivates us to use a binary trie that stores prefixes, and for each prefix we can keep track of the maximum $$$dp$$$ value where some bitstring with said prefix exists.

    However, how do we know if for some digit $$$k$$$, the required configuration of $$$j$$$ and $$$a_j$$$ such that we satisfy the inequality $$$a_j \oplus i < a_i \oplus j$$$? Let's do some casework and see if that simplifies anything.

    Case 1: $$$k$$$ is off in both $$$i$$$ and $$$a_i$$$.

    In this case, to satisfy the inequality, we want the kth bit to be set in $$$a_i \oplus j$$$ but not $$$a_j \oplus i$$$, so the kth bit should be set in $$$j$$$ but not in $$$a_j$$$. We can then update $$$dp_i$$$ accordingly. To figure out which subtree of the trie we should descend to, note that the prefixes of $$$a_j \oplus i$$$ and $$$a_i \oplus j$$$ should remain identical, so we want the status of $$$k$$$ in $$$a_j$$$ and $$$j$$$ to be the same. This raises a little bit of a problem, since this is two subtrees that we must visit. For now, lets look at the other cases.

    Case 2: $$$k$$$ is off in $$$i$$$ but on in $$$a_i$$$:

    In this case, to satisfy the inequality, $$$k$$$ should be off in both bits. The subtrees that we must descend to (so we can find answers where the differing digit between $$$a_j \oplus i$$$ and $$$a_i \oplus j$$$ is greater than k) are those where $$$k$$$ is on in one of $$$j$$$ or $$$a_j$$$ but off in the other.

    Case 3: $$$k$$$ is on in $$$i$$$ but off in $$$a_i$$$:

    Here, to satisfy the inequality, we want the kth bit to be on in both bits. The subtrees that we should descend to are those where the $$$k$$$ bits differ.

    Case 4: $$$k$$$ is on in both bits.

    And lastly, for this case, the kth bit should be on in $$$a_j$$$ but off in $$$j$$$. The subtrees that we should descend to are the ones where the kth bits are the same.

    We can notice one major observation so that we only visit one subtree, instead of $$$2$$$: only the value of $$$a_j \oplus j$$$ matters, since we wish to make the prefixes indentical.

    However, then there is the final question of, for the subtree that we don't visit, how do we know if the maximum $$$dp$$$ value is valid? For example, if we are on the kth bit where it is off in both $$$i$$$ and $$$a_i$$$, the maximal $$$dp$$$ value may have some configuration where the kth bit is on in $$$a_j$$$ and not $$$j$$$. This will obviously cause $$$a_j \oplus i$$$ to be greater than $$$a_i \oplus j$$$. Well, thankfully, there are only 2 possible configurations for such a subtree where $$$a_j$$$ and $$$j$$$ differ in their kth bit: either $$$a_j$$$ has the kth bit set and $$$j$$$ doesn't, or $$$j$$$ has the kth bit set and $$$a_j$$$ doesn't. Similarly, for the subtree where $$$j$$$ and $$$a_j$$$ have the same status for their kth bit, there are only two cases: either it is set in both or off in both. So we can keep track of such $$$dp$$$ values separately.

    So, our trie nodes only need to know: The child where the next bit is indentical in $$$a_j \oplus j$$$, the child where the kth bit differs, and the maximum dp values for the case where the kth bit is on in $$$j$$$, and the case where the kth bit is off.

    When we are finished processing $$$i$$$, all we have to do is insert it into the trie and update the max $$$dp$$$ values accordingly. Then we can move on to $$$i+1$$$. The answer should obviously be the max value of $$$dp_i$$$ for all $$$i$$$.

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

    Our goal will be to calculate $$$dp[i]$$$, which is the longest valid subsequence starting at index $$$i$$$. We will calculate $$$dp[i]$$$ in decreasing order of $$$i$$$. In addition, we will maintain a trie which somehow stores elements of the array / $$$dp$$$ values. The flow of our solution would be something like:

    a) For $$$0 \le i \le n - 1$$$: (decreasing)

    a1) Calculate $$$dp[i]$$$ based on previous $$$dp$$$ values, using our trie.

    a2) Insert the $$$i$$$'th element to the trie, somehow.

    The $$$O(n^2)$$$ $$$dp$$$ formula is something like: $$$dp[i] = max_{j > i, a[i] \oplus j < a[j] \oplus i}(dp[j] + 1)$$$. Therefore, we want to insert the elements into the trie in such a way that retrieving the maximal $$$dp[j]$$$ for all $$$j$$$ such that $$$a[i] \oplus j < a[j] \oplus i$$$ is easy.

    Recall that comparing two binary numbers can be done lexicographically. Assume that up to the $$$k$$$'th leftmost bit, the two expressions are equal. Then, LHS will be smaller than RHS for some $$$(j, a[j])$$$ if and only if one of two happens:

    1. $$$(a[i] \oplus j)_{k} = 0$$$ and $$$(a[j] \oplus i)_{k} = 1$$$.
    2. $$$(a[i] \oplus j)_{k} = (a[j] \oplus i)_{k}$$$, and in a later bit, 1 happens.

    The first condition is equivalent to $$$(a[i] \oplus i)_{k} \neq (a[j] \oplus j)_{k}$$$ and $$$a[j]_{k} \neq i_{k}$$$. The second condition is equivalent to $$$(a[i] \oplus i)_{k} = (a[j] \oplus j)_{k}$$$, and in a later bit, 1 happens.

    We can already start to see that it might be worth it to save $$$a[j] \oplus j$$$ values. These are exactly the values we will insert into the trie at step a2). It is only left to figure out how to perform step a1). We will traverse the trie bit-by-bit. For the $$$k$$$'th bit, we will

    1. (Condition 1) Check the maximal $$$dp$$$ value among all $$$j$$$ s such that $$$(a[i] \oplus i)_{k} \neq (a[j] \oplus j)_{k}$$$ (easy — this is how we store the trie), and $$$a[j]_{k} \neq i_{k}$$$ (also easy — for each trie node we will also store the maximal $$$dp$$$ value for $$$a[j]_{k} = 0$$$ and for $$$a[j]_{k} = 1$$$).
    2. (Condition 2) Traverse to the subtree of $$$(a[i] \oplus i)_{k} = (a[j] \oplus j)_{k}$$$, and recursively continue.

    If we maintain these values, we will get $$$O(n \cdot log(C))$$$ total complexity, and total trie nodes.

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

      Why is it sufficient to check only for the first $$$k_{th}$$$ different bit in our trie and no not see further down the trie for the condition $$$(j > i), (a[i] \oplus j) < (a[j] \oplus i)$$$ to be true, as the value of successive bit increases as we go down the trie example : $$$2^{k+2} > 2^{k}$$$, for some bit k+2 and k. $$$\newline$$$ Or like can you help me in understanding how does $$$a[i] \oplus i$$$ helps in finding $$$j$$$ for our original inequality $$$(a[i] \oplus j) < (a[j] \oplus i)$$$ to satisfy. $$$\newline$$$

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

        We're going from MSB to LSB (Values are inserted MSB first). So we know which expression is bigger on the first such bit which is different.

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

      1.) Can u explain kth bit in a[j] ≠ kth bit in i? It seems if kth bit in a[i] = 0 and i = 0, it will fail. 2.) Also, can u explain in detail how to calculate this using dp?

      I think either it should be kth bit in a[j] = i or kth bit in a[i] ≠ j

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. This is because if $$$a[j]_{k} \neq i_{k}$$$, it necessarily means that $$$a[j]_{k} \oplus i_{k} = 1$$$, which is what we want (this also implies that $$$a[i]_{k} = j_{k}$$$, or equivalently $$$a[i]_{k} \oplus j_{k} = 0$$$

        2. For each trie node we save two values: $$$max_0, max_1$$$. $$$max_i$$$ is the maximal $$$dp$$$ value in the subtree of that node, amongst all $$$j$$$ s such that $$$a[j]_{k} = i$$$. Best way to go with it is an example: Initialize $$$bestSoFar = 0$$$. Suppose we're at the $$$k$$$th bit, and $$$a[i]_{k} = 1, i_{k} = 0$$$. For condition (1) to hold, we need $$$j_{k} = 1, a[j]_{k} = 1$$$ which is equivalent to $$$a[j]_{k} \oplus j_{k} = 0$$$ and $$$a[j]_{k} = 1$$$. From the current trie node, check its child that has $$$a[j]_{k} \oplus j_{k} = 0$$$, and update $$$bestSoFar$$$ accordingly ($$$bestSoFar = max(bestSoFar, max_1)$$$). Then, go to the other child (with $$$a[j]_{k} \oplus j_{k} = 1$$$) and continue recursively.

        Also
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah understood. In my case I assumed j < i Thnx for the explanation

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Going back to problem statement. It says For **any** p (0≤p<m−1) holds $condition. Does it not mean we need to find single closest pair of (i, j) matching that condition and we are done?

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Codeforces Round #815 (Div. 2) video Editorial for Chinese :

Bilibili

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

It seems that $$$cur$$$ is not used in the solution of Div2 D1.

for (int i = 0; i < n; i++) {
		ll cur = 0; // not use
		dp.push_back(1);
		for (int j = i - 1; j >= max(0ll, i - CHECK); j--) {
			if ((vec[i] ^ j) > (vec[j] ^ i)) {
				dp.back() = max(dp.back(), dp[j + 1] + 1);
			}
		}
		
		bst = max(bst, dp.back());
	}
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The pretest for A is too weak, I had just wrote a weird code and got a FST status :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Somebody explain how to use "offline prefix sums" in problem E ?

thx.

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

    If a square with top left corner in $$$(x,y)$$$ completely covers number $$$c$$$ , let its side be equal to $$$L$$$, then for all $$$a_{i,j}=c$$$, $$$i-L+1\le x\le i,j-L+1\le y\le j$$$.Thus, we just care about the maximum and minimum values of $$$i,j$$$.After getting these values,we will add $$$1$$$ to each top left corners of squares which following above conditions,which can be done by offline prefix sums.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

d1 and d2 are two good problem!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

need to clarify if there is not such subsequence satisfying the condition, should we output 1 or 0 ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There will always be a subsequence satisfying the condition. Just pick any element, it is a subsequence of length 1.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but it does not make sense for the inequality to hold if there is only one element

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

Hi, can someone explain why my submission for D2 168922715 has an MLE for test case 2? As far as I'm concerned, the memory complexity is $$$O(n\log10^9)$$$, which should be good, but it doesn't pass the memory. I've tried to make the code as clean as possible, so I'd appreciate it if someone could take a look.

My solution basically uses a trie, and to consider the value of the bitstring of $$$a_i \oplus i$$$ as we traverse down the trie. Most of the memory complexity thus comes from the set of indices that I store in each trie node, indicating that these indices $$$i$$$ at this node have the same prefix in the bitstring $$$a_i\oplus i$$$. Thanks!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Editorial of Problem D1

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Task D is nice, except the misleading statement

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the TL on D2 too tight? My submission TLEs on test 3, even though it is $$$O(n \log (a_i))$$$. 168961089

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most correct solutions pass in less than 500ms, something might be wrong in your code. Maybe try to run it with 300,000 elements to see how far you are from the 2s limit?

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

      It takes around 3500ms. Any fixes to improve that?

      Edit: It takes <500 ms on some n=300000 cases, custom hash for unordered_map didnt help either

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(all appeareances of this numbers are in thsi square)

——(In the tutorial of E)

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have a problem with task B. The condition says we can take any subarray. But then why for the input data "1 2 3 100 200" the answer is 297? We can take the subarray 2 3 100 200 and the answer will be 100 more than in the example. Or I don't understand something. Please explain.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we take the subarray 2 3 100 200, then the beauty of this subsegment is $$$200-2+1-1=198$$$. Why is the answer more than the example 100?

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

      omg. I understood... we exclude this sub-segment. aah, thanks!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldnt problem B be done with complexity O(n) ? I believe my solution does it in O(n).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, you can find the minimum and maximum in $$$O(n)$$$. But doing it twice is unnecessarily painful compared to sorting.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for second problem NlogN ( sorting the array )solution give timeout for Java , however for other languages c++ and python same solution works , Please work on test cases and time set for diff languages

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can also find 2 maximums and 2 minimums of the array in linear time. Such implementation passes if you code it in Java too

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The answer of problem B doesn't only exceed max1+max2-min1-min2, but also is equal to max1+max2-min1-min2. So the best complexity is O(n).

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For D1, please let me know why my solution 169032390 WA on test 3 while for j′<i−512, definitely aj′⊕j>aj⊕j′.

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

    my mx is used to caculate the maximum dp[j] (j from 0 to i — 512)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I love constructive div 2 E's where the key observation is answer turns out to be at most [small number] like 2. Other recent examples like 794 E and 798 E though these are different kinds of problems. But I wonder how you come up with these constructions or guesses that you can the construction can be done in a small number of moves because it seems like the problem is easily hit or miss if you don't see the idea or think this is possible.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone please explain the editorial code for D2? I don't understand this implementation of trie.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

fix D statement please !!! it's wrong

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't quite understand, why can't the proper subsegment contain the maximum or minimum values of the whole array or both? It's not stated in the problem that it can't.. the only constraint over the subsegment that it can cover at most n-1 elements, stated as (r — l + 1 < n).

for example in the second test case where n = 5 and the values are 1 2 3 100 200 we can choose l = 2 and r = 5 so the subsegment is (2 3 100 200) and the answer should be (200 — 1) + (200 — 2) = 397

so can anyone explain what I'm missing?