_FireGhost_'s blog

By _FireGhost_, 3 years ago, In English

Thank you for participating in the contest! We hope you enjoy the problems. You can also give feedback on each problem, it will help us much in future problem settings. By the way, feel free to share your solution!

1658A - Марин и фотосессия

Hint 1
Hint 2
Tutorial
Solution
Feedback

1658B - Марин и не взаимно простая перестановка

Hint 1
Hint 2
Tutorial
Solution
Feedback

1658C - Синдзю и потерянная перестановка

Hint 1
Hint 2
Hint 3
Tutorial
Solution
Feedback

1658D1 - 388535 (упрощенная версия)

Tutorial
Solution

1658D2 - 388535 (усложненная версия)

Hint 1
Hint 2
Tutorial
Solution
Feedback

1658E - Годзё и игра на матрице

Hint 1
Hint 2
Tutorial
Solution
Feedback

1658F - Дзюдзю и бинарная строка

Hint 1
Hint 2
Tutorial
Solution
Feedback
  • Vote: I like it
  • +87
  • Vote: I do not like it

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

Whoever named problem D is a legend!

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

    What does it mean?

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

      It's the sauce for our pasta. (Explaining it more than that would ruin it. You can google "sauce numbers" if you want to find out more)(NSFW)

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

    Dammn bro, you have unlocked "Advanced Observation Haki".

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

    I have solved problem D1 using binary search. I think there must be binary search tag in problem D1. :) Total time complexity is nlog^2(n)

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

      Explain plz

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

        I had seen some examples and noticed that the greater x, the greater the sorted array obtained by The XOR operations on the [ 0, r ] segment. I just used binary search to find such x ( and x is always in the given array as left boundary is always 0) afterward.

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

      Hey can you explain why you did this

      if(v==comp){ cout<<comp[m]<<"\n"; return; }else{ if(v<comp) l=m+1;else r=m-1; }

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

      it's really amazing approach::)

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I attempted to prove this, hopefully i make sense Proof: First of all this fact heavily relies on the fact that the elements of the array are from 0 to r. When counting from 0 we know that for a bit i first 2^i bits are 0 and the next 2^i bits are 1 and then the pattern repeats. Hence if n is a multiple of 2*2^i = 2^(i+1), then numbers in which ith bit is set equals numbers in which ith bit is unset, and for all bits < i this will be true. Now if we look at the binary representation of first 2^(i+1) numbers, we find that the only difference between these is ith bit consider the following example for i = 2

      000 001 010 011 100 101 110 111

      The point being if there is a number x, in this range, then a number y which is exactly same as x just that ith bit is different is also present. Now lets call first 2^(i+1) integers as a group. The next 2^(i+1) integers as another group and so on. That for i = 2, we say first 8 integers as a group (from 0 to 7), then the next group will contain the next 8 integers (8 to 15) and so on. Now lets say we do bitwise xor of these groups with a number x such that only ith bit is set in x. How will this affect our groups. In each group bottom 2^i numbers have ith bit set and and first 2^i have this bit unset, when we xor with x, bottom numbers will shift up and first numbers will move down and net difference in initial set and final set remains same. This means within a group there is no difference, also relative ordering of groups also doesn't change. Now have have a range from 0 to n, and i apply xor on this range with x, then if ith bit is set in x, then if n is a multiple of 2^(i+1) then this will bring no net change in the range. Now if n is not a multiple of 2^(i+1) then it means it has some complete groups and one incomplete group. In this incomplete group there will be more bits with ith bit unset than numbers with ith bit set. After doing xor with x, numbers of bits with this bit set will be more hence in this group net change will be increase in values of this group.

      Now consider xor of range from 0 to n with 2 numbers x and y such that x < y. This means that in binary of x and y when iterating from left to right we will have some prefix which is same and then when we find a different bit this bit will be set in y. Lets say this bit is ith bit. It is clear that any change that prefix (bits to left of i) will bring in the range will same for both x and y hence we ignore these bits. If n+1 (since number of integers from 0 to n are n+1) is a multiple of 2^(i+1) then we know XORing with y will bring no net change in the values. Also since n+1 is a multiple of 2^(i+1) it means this is also multiple of 2^i, 2^(i-1), . . .2^1 i.e all bits after this bit will have same number of set and unset bits and hence XORing will not bring any net change in the range. But what if n+1 is not a multiple of 2^(i+1) then it means that the latest group of ith bit will have more unset bit, and XORing with y will bring a change only in this group and cause a net increase in the values. Lets say this last group starts with some integer k and goes upto n i.e from k to n. Now when comparing the two arrays after XORing with x and y we know that values from 0 to k-1 (index wise) will be same and when we compare current group from k to n we find that group in case of y is larger (lexicographically). Any bit j after ith bit which tries to increase group size in favour of x will still not able to make it larger than y, this group size of group of jth bit will be smaller than size of group with i and hence we will find a greater value in array with y first.

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

PermutationForces

»
3 years ago, # |
  Vote: I like it +124 Vote: I do not like it
This is the sufficient condition. It can be shown that, if c[i+1]-c[i]<=1 for all 1<=i<=n, then there exists a permutation that satisfies.

So show it

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

    believe me bro

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

    One way to build a satisfying permutation: After rotating the array c[], write the numbers 1 to n one-by-one from the position(s) with highest c[i] to lowest c[i]. If there exists multiple positions with the same value, go from the largest index to the smallest.

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

      not vice versa from largest index to the smallest? take a look at c = [1, 2, 2] according to your algorithm we get [3, 1, 2] instead of [3, 2, 1]

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

      How will this help?

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

      According to your algorithm, from this sequence c

      1 2 3 4 2 3
      

      we construct the following premutation

      6 5 3 1 4 2
      

      But I don't think this is correct. The corresponding numbers of this permutation should be 1 2 3 3 2 2 or 1 2 2 3 3 2 depending on whether you do left-shift or right-shift.

      Please correct me if I'm wrong.

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

        Note that no matter we do left-shift or right-shift of the permutation, we always construct the prefix maximums array from left to right (clockwise).

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

    Probably not the easiest way to do it, but one of them. Assume we are adding elements from 1 to N — 1 in front of element N. Now, let's make the permutation. From now on, f[i] equals number of different prefix maximums after we add i elements (so, if N is in position k, then f[1] = c[k + 1] etc.). Claim: if we put element N — 1 into position num, then: A) f[num] = 2 — it will be bigger than all elements at the front, and smaller than N. B) if pos1 > num, then f[pos1] > f[num] (otherwise, this element is bigger than N + 1) So, we put N — 1 into position [k + num]. Then, we have divided our sequence into two parts. If the length of the first one is l1, and the second one l2 (l1 + l2 = N — 2), then let the values of the first sequence be one of a permutation[1:l1], and the second [l1 + 1; l2]. Solve for them recursively. So, we have constructed a permutation which satisfies our condition.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    I also wrote this below and I don't wanna flood
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      It's easy to see that it's the necessary condition but not sure how to prove that it's sufficient.

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

    Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.

    let a = no. of 2s in array c, b = no. of 3s in array c and so on.

    s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.

    Now traverse the array c from 2nd position.

    if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].

    We're done.

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

      Adding an example:

      let c = 1 2 3 3 3 3 2 2 3 4 5 5 6 4

      s[2]={13,12,11} s[3]={10,9,8,7,6} s[4]={5,4} s[5]={3,2} s[6]={1}

      step 1: 14 _ _ _ _ _ _ _ _ _ _ _ _ _

      step 2: 14 _ _ _ _ _ _ _ _ _ _ _ _ 11

      step 3: 14 _ _ _ _ _ _ _ _ _ _ _ 6 11

      step 4: 14 _ _ _ _ _ _ _ _ _ _ 7 6 11

      step 5: 14 _ _ _ _ _ _ _ _ _ 8 7 6 11

      step 6: 14 _ _ _ _ _ _ _ _ 9 8 7 6 11

      step 7: 14 _ _ _ _ _ _ _ 12 9 8 7 6 11

      step 8: 14 _ _ _ _ _ _ 13 12 9 8 7 6 11

      step 9: 14 _ _ _ _ _ 10 13 12 9 8 7 6 11

      step 10: 14 _ _ _ _ 4 10 13 12 9 8 7 6 11

      step 11: 14 _ _ _ 2 4 10 13 12 9 8 7 6 11

      step 12: 14 _ _ 3 2 4 10 13 12 9 8 7 6 11

      step 13: 14 _ 1 3 2 4 10 13 12 9 8 7 6 11

      step 14: 14 5 1 3 2 4 10 13 12 9 8 7 6 11

      This works because if i>j then x<y for all x belongs to s[i] and y belongs to s[j].

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

        Great construction! I guess you can also set s[1] = 14 here to put the entire process in a unified way. Also the condition "c[i + 1] — c[i] <= 1" plays an important role here, because then we can guarantee that at each step of the construction, we have already put enough larger numbers in the array to guarantee the corresponding value of c[i].

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

      insane bruh

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

    This is an example of how the construction would go: Suppose n = 8, c array = 1 2 3 4 5 3 4 2

    We always start with the largest element:

    • [8, _, _, _, _, _, _, _] 1

    • [7, 8, _, _, _, _, _, _] 2

    • [6, 7, 8, _, _, _, _, _] 3

    • [5, 6, 7, 8, _, _, _, _] 4

    • [4, 5, 6, 7, 8, _, _, _] 5

    • [6, 3, 4, 5, 7, 8, _, _] 3 (rightmost r where c_r = 3, leftmost l where c_l = 5. Decrement l to r by 1. (l,r) = (0, 2). Add original a_r to first position.)

    • [6, 5, 2, 3, 4, 7, 8, _] 3 ((l, r) = (0, 0))

    • [7, 5, 4, 1, 2, 3, 6, 8] 2 ((l, r) = (0, 6))

    We can check this is correct:

    • [8, 7, 5, 4, 1, 2, 3, 6] 1

    • [6, 8, 7, 5, 4, 1, 2, 3] 2

    • [3, 6, 8, 7, 5, 4, 1, 2] 3

    • [2, 3, 6, 8, 7, 5, 4, 1] 4

    • [1, 2, 3, 6, 8, 7, 5, 4] 5

    • [4, 1, 2, 3, 6, 8, 7, 5] 3

    • [5, 4, 1, 2, 3, 6, 8, 7] 3

    • [7, 5, 4, 1, 2, 3, 6, 8] 2

    Sketch of Formal Proof: To be added.

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

problem D2 : "count the number of $$$a_i$$$ that $$$l\leq a_i \oplus x \leq r$$$ " this can be done with checking if $$$\min_{i=0}^{i=n} (a_i \oplus x) = l$$$ and $$$\max_{i=0}^{i=n} (a_i \oplus x) = r$$$ ($$$a$$$ only contains pairwise distinct elements , thus bijection)

example

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

    can you explain more

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

      i'm sorry if my explanation wasn't clear . as it's said in editorial we will iterate over all posibilities of $$$x$$$ and for each $$$x$$$ we will check if it can have correct mapping or not . for $$$x$$$ we will consider only $$$r-l+1$$$ values because $$$a_0$$$ should be mapped at least to one of them .

      now how to check if $$$x$$$ can give us correct mapping or not ? i'm saying that if maximum value that $$$x \oplus a_i$$$ can get for every $$$i$$$ is $$$r$$$ and minimum value that $$$x \oplus a_i$$$ can get is $$$l$$$ then there is correct mapping . how can we check minimum and maximum value that $$$x \oplus a_i$$$ can have ? by trie ,which is quite well known technique .

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

    Why take the min of all x and not stop when you find the first one?

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

      i don't understand question

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

        I changed your code to stop at the first value of x and it got ACC 152482164. So I was wondering why ans=min(ans,x); instead of just stopping there.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same thing: 233974285
    But I am assuming that $$$a_i = l \oplus x$$$ and checking if $$$x = a_i \oplus l$$$ for each $$$i$$$ like in the editorial.
    You seem to be checking if $$$x = a_0 \oplus i$$$ for each $$$i$$$. Why does that work?

    Okay while writing this I understood you are just trying to find the $$$i$$$ for which $$$x \oplus i = a_0$$$.
    Amazing solution!

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's correct, I am assuming that in the permutation first element was $$$i$$$, then $$$x = a_0 \oplus i$$$.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you please explain why d1 approach not working for d2. i know how to solve d2 but i can not understand why d1 approach not valid for all l.

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

    @variety-jones In this ticket the expected and the actual output seem to be the same but still it says they're different. What am I missing?

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

      It's because the exit code of your submission was not 0. (It did print 7, but it also had runtime errors), hence I consider it as a failing testcase. (On some platforms, it might have different exit codes, depending upon how uninitialized value access works).

      An even smaller test case might be

      1
      0 0
      0
      

      Hint: Look at your array size.

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

        Ya just saw it. From user experience perspective, would "runtime error" or something similar be better? (Not trying to turn the blame on you, just a suggestion :P)

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

          Sure, thanks for the feedback. Will try to incorporate it the next time I make major changes to the website.

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

Could someone give a proper explanation how to use trie in D1/D2?

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

    In this problem, we use trie(or similar structures) to calculate the number of $$$a_i$$$ such that $$$a_i \oplus x\in [l,r]$$$. So it is sufficient to calculate the number of $$$a_i$$$ satisfying $$$a_i \oplus x < r$$$.

    In such queries, we can enumerate the longest common prefix of $$$a_i \oplus x$$$ and $$$r$$$ (in binary, of course, starting from the highest bit). Say this common prefix ends at the $$$k$$$-th bit.

    Then we know exactly what the highest $$$17-k$$$ bits for $$$a_i$$$ should be, since $$$a_i \oplus x$$$ share the same bits with $$$r$$$. And the $$$k-1$$$-th bit in $$$r$$$ must be equal to $$$1$$$ (for the $$$0$$$ bits, just skip them), while the same bit in $$$a_i \oplus x$$$ should be $$$0$$$. The last several bits (from $$$k-2$$$ to $$$0$$$) no longer matters.

    Thus, for each $$$k$$$, all we need to do is to precaculate the number of $$$a_i$$$ with some specific highest $$$18-k$$$ bits. This can be done using trie or simple arrays.

    Trie : the number we wanted is equal to the number of leaves in a specific subtree, which can be precalculated during the trie building part. To find the subtree, just go down the trie while decreasing $$$k$$$. See my code for details.

    Arrays : you can precalculate the number using arrays of size $$$2^{17-k}$$$ for each $$$k$$$ (or simply cnt[17][1<<17]). It's like a counting machine. Each $$$a_i$$$ will only contribute to one position in this array for each $$$k$$$. The time and space complexity should be the same as trie.

    (Sorry for my poor English. The details in my explanation may not be very clear. Hope you understand the method.)

    You can also use trie or arrays to solve "the max and min of $$$a_i \oplus x$$$" problem, which is mentioned in other comments.

    BTW, I've been wondering whether $$$x$$$ is fixed when $$$r-l+1$$$ is odd, since $$$\oplus a_i=\oplus_{l\le i\le r} (i\oplus x)$$$. Hope I'm not alone.

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

      Yes, when $$$r - l + 1$$$ is odd, then $$$x$$$ can be uniquely defined. I actually used this in my solution for D1. Surprised that it wasn't mentioned much. But maybe it's not a complete solution as you'd need still to solve for the even cases.

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

Could someone give a rough proof of why the condition is sufficient in C (how would the permutation be constructed)?

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

    Think in a permutation of lenght 5 like {5 4 3 2 1}, whose power is 1, now is there a way so in just one shift the power becomes 3? there isn't since whichever number you choose to put in fisrt place {x 5 ...} the five will make the array b = { x 5 5 5 5}. in other words, you can sum 1 to the power by sifhting the last number x where x < P[0], because this number will be counted in the power but for summing two you need to put at least two numbers in the beginning so that the b of the permutation becomes b = {x, y, 5, 5, 5} where x < y < 5 which is impossible with one shift (you only sifht one number).

    This isn`t to mathematical and I only did this with a permutation of lenght 5, but i think it could be intuitive.

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

    Sharing again!

    Let 'c' be an array satisfying the necessary conditions. Rotate 'c' such that its first position is 1 without loss of generality. We will explicitly construct a permutation p obeying c. The first element of p is N.

    let a = no. of 2s in array c, b = no. of 3s in array c and so on.

    s[2] = {N-1,N-2,N-3...N-a} s[3] = {N-a-1, N-a-2, N-a-b} and so on.

    Now traverse the array c from 2nd position.

    if the element of c is k, place the lowest element of s[k] at the last available position of p and remove that element from s[k].

    We're done.

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

      what does s[2] denote here?

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

        s[k] is a set of elements to be placed in your permutation whenever you encounter k while traversing c.

        All elements of s[2] will be bigger than any element of s[i] where i>2.

        In general all elements of s[i] will be bigger than any element of s[j] for j>i

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

Auto comment: topic has been updated by _FireGhost_ (previous revision, new revision, compare).

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

wow what an editorial for C, just awesome

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

Can someone explain what does mean "x is inside a" in D1 tutorial?

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

Anime fans before contest: Step on me MARIN

Anime fans after contest: Oh yeah baby, oh yeah (delta < 0)

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

Editorial for problem F is really confusing. Read twice, didn't understand a thing. Can you please elaborate?

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

    Ok, let me try to rewrite and add some pictures and examples too. Sorry for the inconvenience right now.

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

    Agreed, I haven't seen an editorial so cryptic in a long time, it took me a while to realize what they're getting at. Here's an attempt at explaining the idea.

    Note: all variable names will either be the same ones used in the problem statement or explicitly defined.

    Part 1: How many zeros and ones are in the answer?

    Let the number of ones in $$$s$$$ be $$$ones$$$. The cuteness of the entire string by definition is $$$\frac{ones}{n}$$$. The concatenated string of length $$$m$$$ that we're looking for has the same cuteness, so the number of ones in it is $$$\frac{ones}{n} \cdot m$$$. Therefore, there is no answer if that value is not an integer (i.e. $$$ones \cdot m \not \equiv 0 \bmod n$$$).

    Part 2: How do we find the answer with the minimum number of parts?

    Let $$$x = \frac{ones}{n} \cdot m$$$.

    Let's also assume the string is circular for now. Consider any length $$$m$$$ subarray in this circular string, including subarrays that wrap around. If we can find a subarray with exactly $$$x$$$ ones, then the minimum number of parts we need is either $$$1$$$ or $$$2$$$, depending on whether or not it wraps around. And both can be checked with sliding window/prefix sums.

    It turns out such a subarray always exists. Let $$$c_i$$$ be the number of ones in $$$s[i \dots i + m - 1]$$$ if $$$i \leq n - m + 1$$$, or $$$s[1 \dots m - (n - i + 1)] + s[i \dots n]$$$ otherwise (basically, subarrays that wrap around versus subarrays that don't). Note that $$$|c_{i+1} - c_i| \leq 1$$$ for all $$$1 \leq i < n$$$ and $$$|c_1 - c_n| \leq 1$$$. This is because if we slide the subarray we're considering from $$$i$$$ to $$$i + 1$$$, we exclude $$$s_i$$$ and include $$$s_{((i+m-1) \bmod n) + 1}$$$. So the number of ones in our subarray can only increase or decrease by at most $$$1$$$. The implication of this is that there exists some $$$c_i = y$$$ for all $$$\min c_i \leq y \leq \max c_i$$$ because there's no way to go from a small to large $$$c_i$$$ while "skipping" over the values in the middle.

    It holds that $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$, implying some $$$c_i = x$$$. Assume that $$$\max c_i < x$$$. This means $$$\sum_{i=1}^n c_i < n \cdot x$$$. Furthermore, each index is included in exactly $$$m$$$ different subarrays. So $$$\sum_{i=1}^n c_i = m \cdot ones$$$. Thus, $$$m \cdot ones < n \cdot x$$$, or $$$x > m \cdot \frac{ones}{n}$$$ which is a contradiction by definition of $$$x$$$. Similarly, assume $$$\min c_i > x$$$. $$$\sum_{i=1}^n c_i = m \cdot ones > n \cdot x$$$, or $$$x < m \cdot \frac{ones}{n}$$$ which is a contradiction. Therefore, $$$\max c_i \geq x$$$ and $$$\min c_i \leq x$$$.

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

      Thank you very much for your wonderful proof. I have completely understood it.

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

      Thank you for writing this! Now everything is clear :)

      As for the proof — I don't see anything wrong with it. There are a lot of proofs by contradiction)

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

        Thanks! Also I figured out why my previous proof attempts are wrong as well as why they don't undermine the current proof.

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

      Yes, it is was my fault that make it so cryptic, it is a huge basic mistake when I am too familiar with this problem (when trying to solve it in different ways, make strong tests, ...) I skipped most of the not-so-obvious ad-hoc observations.

      For direct proof, I think we can do something like this:

      Spoiler

      There is also a geometric way, you can use Borsuk–Ulam Theorem for problem F generalization of $$$x$$$ colors. In this theorem, AFAIK it claims that when $$$n = 2 * x$$$ and if it is not an impossible case then we don't need more than $$$x$$$ subarrays.

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

I can't see what property of solution for D1 uses the fact that $$$l = 0$$$ any ideas for this?

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

    It doesn't work on a test $$$l=1$$$, $$$r=2$$$, $$$a = [0, 3]$$$.

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

      Thanks! But still I can't see where the editorial used the fact :) Can you show me the point?

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

        If number of ones equals number of zeroes at some position $$$i$$$ and $$$l=0$$$, then you know for a fact that $$$n = k \cdot 2^{i+1}$$$ for some $$$k$$$ and the proof from the last paragraph of the editorial works. Otherwise it doesn't.

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

          Oh I see It is for the last line of the editorial. Thanks a lot :)

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Hello, in the A problem if n==1 and s="0" should be the answer 1, not 0, and because of that i had wrong answer, the judge is wrong, how can i reclaim?

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

    You cannot form any substring of length >= 2 in a string of length 1 as the statement says

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

In C tutorial should also be a condition, that there must be only one '1' in array c. Because '1' means, that the largest number is first, so if there are at least two '1', p can't be a permutation.

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Is this round unrated as rating changes are still not visible?

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

Can someone prove or refute and hack my solution of task B? I have no idea why this works, just noticed the pattern from example. Submission UPD: I guess I've figured that out, it's like a dynamic calculation of (n!)**2

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

Why does solution for D1 (bit count) not work for D2?

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

    Think about this case

    1 4

    0 2 3 5

    The answer is 1 and with bit count the answer should be 0.

    1 4

    2 1 0 7

    Another case, answer = 3 and with bit count should be 0.

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

      What did you give as test case the original array a or xored with x (a xor x)

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

    According to me, if we solve D2 using bit count (method to solve D1) , there will not be any issue if bit count at any position for actual array and xored-array will be different. But if at any position, bit count will be same, we can't directly take (any of) 0 or 1 as the value of bit at that position for x ( as we did in D1 ).

    LET'S CONSIDER THIS TEST CASE:

    l=1 r=4

    2 3 0 5 ( xored-array )

    If we solve it using method used in D1, we will get output 0, but it's answer should be 1.

    Please verify if I am correct.

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

      Ok, I think I understand why the D1 algo does not work for D2.

      If we got equal bitcount for 0 and 1 at some position, then in D2 only one of the both options is correct, but we cannot decide which one.

      But in D1 both options work.

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

        "But in D1 both options work." — could you please explain why ?

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

          Thats difficult ;)

          Well, I think it as: If we allways choose 0 if we can choose, then we will get the lowest possible value for l. That fits D1, since l==0.

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

            But we can't say that ( a xor (x-1) < a xor x ). Maybe if we apply the operation (all elemets in a) xor x+1 that will be less than (all elemets in a) xor x. For example, array (2,3) xor 1 = (3,2) but array(2,3) xor 2 = (0,1) We took greater x (2>1) but got an less array (0,1)<(3,2). Maybe we can take a greater x to got a less initial array ? Why exactly when an initial array is (0 to r) array xor (lesser x) = lesser array ?

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

        My solution is split the whole array into two parts so that we can apply the D1 algo for each part. If for any of the two parts, the number of 1 of some position is not correct, the answer is 1 on this position.

        I split the array by the highest position which has both 0 and 1.

        For example: l=6, r=10, answer=3 a: 4(0100) 5(0101) 9(1001) 10(1010) 11(1011)

        So the highest position which has both 0 and 1 is the 4th one. Then array a is split into [4 5] and [9 10 11].

        My Code

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

C would be worth a picture. Problem here is to wrap head arround rotation, permutation, position...things.

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

    I just realized that the "next cyclic shift" is not created by moving the first element to last position, but instead by moving the last element to first position.

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

The solution for D2 is missing a "few" details, so I wrote one to make sure I fully knew how to solve the problem.

You can read my solution in the comments here: 151187878. Code is in python but hopefully it's readable since it's python.

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

    Thank you so much for your explanation.The tutorial for D2 didn't tell why initialize ans to l or r(Line 23-25 in C++ code), so I was confused. You explain this in your solution(Line 11-12). Now I understant that because the number we can't pair(i.e.a[i]^1 is not in the set) must used to be either l or r(when l%2!=0&&r%2!=1). So that we can initialize ans so.

    Another thing, there may a typo in your solution: in Line 12-"similarly, if r = 2*i+1", "2*i+1" should be revice to "2*i"?

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

      Glad you found it helpful! Yes, it should be r = 2*i since 2*i^1 = r+1 which is not in the range.

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

    thanks, you save my day!

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

can someone please explain why the solution for d1 doesnt work for d2??

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

This tutorial can be improved... On the surface it seems like you have put so much effort but for some one who was not able to solve a question , then to read these editorials and then understand and solve it is not possible. Most of the important points and proofs the authors have skipped. The problems were good but the editorial could have been improved.

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

Proof for D1: Left as an exercise for the reader

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

I upsolved/practiced 1658D2 - 388535 (Hard Version) this way:

  • enclose the wanted range $$$[l; r]$$$ in smaller and smaller (aligned) blocks of size $$$2^b$$$, if not all $$$a_i$$$ are inside the block, set corresponding bit in $$$x$$$
  • when $$$[l;r]$$$ doesn't fit in a smaller block: instead enclose $$$l$$$ and $$$r$$$ each in their own $$$2^b$$$-block (again: smaller and smaller), count the number of $$$a_i \oplus x$$$ in those blocks, if count is unexpected set bit in $$$x$$$.
more details

Submission: 151190666

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

In problem.E, Why do you maintain the set S of all pairs $$$(i',j')$$$ such that $$$dp[i'][j']=1$$$ instead of $$$dp[i'][j']=0$$$ ?

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

In problem E where did $$$|i-i'|+|j-j'| \leq k \Leftrightarrow \max(|(i+j)-(i'+j')|,|(i-j)-(i'-j')|) \leq k$$$ come from? What's the intuition behind this? Is it something well known?

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

    I think maybe it's a normal method to deal with the absolute value.

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

    We can transform from 2d Manhattan distance metric to Chebyshev distance by transforming all the points $$$(x, y)$$$ to $$$(x+y, x-y)$$$. I think its relatively well known

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

    Consider all points at distance at most $$$k$$$. Actually, this points form a diamond shape. It's hard to work with diamond, so we can rotate the plane by 45 degrees ($$$(x,y)$$$ -> $$$(x+y,x-y)$$$), and now all points at distance at most $$$k$$$ form a square shape. So after this we have a different function for distance: $$$|x_1-x_2| + |y_1-y_2|$$$ -> $$$max(|x_1'-x_2'|, |y_1'-y_2'|$$$, where $$$x' = x+y$$$ and $$$y' = x-y$$$.

    How it can be used in this problem? After the transformation we need to know is there any winning points outside the rectangle (it's the same as: are all winning points inside the rectangle). This problem can be easily solved with 2D BIT, for example (but there are simpler solutions, as mentioned in the editorial).

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

      Thank you. I saw this ($$$(x, y) \rightarrow (x+y, x-y)$$$) transformation once before, but I don't understand why it works. It's not just a simple "rotation by $$$45$$$ degrees", is it?

      For example, if you take $$$2$$$ points $$$(3, 4)$$$ and $$$(3, 5)$$$ (distance $$$1$$$) and do the transformation, it will be $$$(7, -1)$$$ and $$$(8, -2)$$$ (distance $$$\sqrt{2}$$$). Am I missing something?

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

        The Manhattan distance between $$$(3,4)$$$ and $$$(3,5)$$$ is $$$|3-3|+|4-5|=1$$$, which is equal to the Chebyshev distance between $$$(7,-1)$$$ and $$$(8,-2)$$$($$$\max(|7-8|,|(-1)-(-2)|)$$$).

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

          Yes, I understand how it works. Can you please explain why it works?

          As far as I know, rotation keeps distance between points unchanged. This is not happening in this case.

          Futhermore, I can't even say it's a rotation, it's something more strange.

          Here $$$A$$$, $$$B$$$, $$$C$$$ are points before the transformation and $$$A'$$$, $$$B'$$$, $$$C'$$$ are points after the transformation.

          Formula for distance works here, definitely. But can you please elaborate why? What's exactly happening here? Why it's called "rotation by $$$45$$$ degrees"?

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

            Let's define the Manhattan distance between $$$a(x_1,y_1)$$$ and $$$b(x_2,y_2)$$$ to be $$$d(a,b)$$$.Then we can find that:

            $$$ \begin{aligned} d(a,b)&=|x_1-x_2|+|y_1-y_2|\\ &=\max\{x_1-x_2+y_1-y_2,x_1-x_2+y_2-y_1,x_2-x_1+y_1-y_2,x_2-x_1+y_2-y_1\}\\ &=\max\{|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|\} \end{aligned} $$$

            that is, the Manhattan distance between $$$a(x_1,y_1)$$$ and $$$b(x_2,y_2)$$$ is equal to the Chebyshev distance between $$$(x_1+y_1,x_1-y_1)$$$ and $$$(x_2+y_2,x_2-y_2)$$$.

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

              Thank you. Now I almost got it.

              The only thing I don't understand is, why it's called a "rotation by $$$45$$$ degrees"? Isn't it just elegant coordinate transformation?

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

                To be precise, transform from 2d Manhattan distance metric to Chebyshev distance involves rotating and zooming, These are two operations.

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

What does the first solution for D2 mean? I have no idea about it. How does it work?

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

In c why do we have to rotate it?

»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

n

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

Why does solution in D1 does not work for D2? Plz explain

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

You used same variable name k in F. This is not easy for readers to understand .

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

    The contest is great , but the editorial is not so good .

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

When I choose "Good problem",I add it to liked.When I choose "Bad problem",I add it to liked too?

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

Sorry for my rudeness , I think ConclusionForces is boring, Problem ABCEF is all Conclusion problems.

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

    Sorry but what is conclusion problems?

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

      A problem that you can solve it only by guessing a simple conclusion.

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

        Is it another name for observation problems?

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

        Eh, I don't think my problem F only needs a simple guess conclusion tho.

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

          why? I guessed one so I get accepted during the contest.

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

            Wow, how did you guess it?

            When I am setting the problem, I expected at least 3 ad-hoc observations to solve the problem tho :<

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

"However, if the number of ones is equal to the number of zeros, we can actually assign the i-th bit anything we like." — how can we proof this part ? Can somenone please explain me ?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you known the answer now, I have the same question.

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

I have solved problem D1 using binary search. I think there must be binary search tag in problem D1. :) Total time complexity is nlog^2(n)

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

Problem setters please note that avoid writing note once in a separate statement.

In D1, you said find the value of x. I read it and left everything else and started solving. You wrote in the next paragraph that multiple x can exist.

Its better to write in the original statement itself. I wasted hours trying to form and solve equations

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

Weak tests for Problem E. A trivial edge case (where one of the 'winning' cells is present at a corner of the matrix) was enough to uphack my AC submission.

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

For D2, I think the final answer is l or r xor the isolated element in array a after the first step. I can't understand why we should check by this sentence "f &= ((cur ^ j) >= l && (cur ^ j) <= r)". Could anybody tell me this? Thanks

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

In D2 you can not count the number of numbers in the segment, but just check min(a[i] ^ x) == l and max(a[i] ^ x) == r. Because if all the numbers were different, then they will remain different if they are xoring with x => all number belongs segment

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

For D2 I have another simple solution :

First sort the array given to you, then divide it into several consecutive intervals.It can be proved that the number of these intervals will not exceed log(r-l+1).

Then for each interval [L,R], check whether x={l^L,l^R,r^L,r^R} satisfies the condition。

It means that the XOR of these continuous intervals will also be a continuous interval after our answer x, and l, r must appear in one [L,R].

more details:151127931

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

[Deleted]

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

In Problem.F I have a wrong guess: if $$$m\leq \frac{n}{2}$$$, then $$$k=1$$$. And it gave the wrong answer on case 24 in test 156. But I can't prove it wrong officially. Who can help me?

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

    Let me check for this

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

    In test 156 I generated only testcases that give $$$k = 2$$$ as answer

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

    You can try this testcase I just manually make

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

    Actually, when $$$m = \frac{n}{2}$$$ and $$$b, w$$$ are even then your guess is correct and provable.

    Let $$$D[x] = $$$ (number of '1' in $$$s[x \dots x + m - 1]$$$)

    If $$$D[x] = m$$$ then we are done

    Otherwise WLOG $$$D[x] < m < D[x + m]$$$

    Since $$$|D[x + 1] - D[x]| \leq 1$$$ then applying IVT you can prove there is $$$y$$$ in $$$[x + 1, x + m - 1]$$$ that $$$D[y] = m$$$

    There is another solution without using IVT and an overkill solution for an even more generalized F problem, if you are interested then I will make a blog about it.

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

    after taking an hour of reading the codes, seeming there are 3 guys make that same wrong guess, but I dont know how to prove for $$$m < \frac{n}{2}$$$ can make $$$k = 2$$$ test using math. I will try to brute-forces for some small cases then..

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

      I'm unable to find errors under random data. maybe we can try constructing some special data.

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

        dunno, I failed to prove it wrong using math too

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

        cunzai_zsy0531 SPyofgame

        You can consider this counter example.

        Input
        Expected Output
        Reasoning
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          You can also systematically construct the counter example to disprove the fact. We need to create a string of length 50, containing 30 ones, we create it as

          str = Base + Base + Remain
          str = 11111111111000000000 + 11111111111000000000 + 1111111100
          

          where Base = 11111111111000000000 (11 times one, followed by 9 zeroes). (This restricts a substring of length 20 from being an answer).

          and Remain = 1111111100 (8 times one, followed by 2 zeroes). (Since we need to ensure that the string contains exactly $$$(11 + 11 + 8 = 30)$$$ ones.

          Now, it's easy to see that no window of length 20 contains 12 ones. Hence, we will need to split it into 2 segments.

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

            Interesting, but can you generalize it?

            As you can see from my generator that only generates k = 2 tests, I make it completely random without any specific forms.

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

              I think the method to generate it is that you put more zeros than you need between the one's subsegments.

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

            that's fantastic. Thank you very much.

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

Perhaps in magical Codeforces,I lost my ability of datastructrue...I wonder why I cannot think of solutionof 01 Trie in D2 qwq

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

Could someone help me understand why this code is getting TLE? 151271702

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

I tried the problem F during the contest,but I had failed.

It's really an amazing problem,and I love it.

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

    Thank you. Also, if you find this problem interested you enough, do you wanna try its generalized problem for $$$k$$$ colors and $$$n = 2 \cdot k$$$ ?

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

Such blasphemy. Marin simps will never forgive you for D.

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

can someone please explain me how to find all the squares within k manhatten distance in problem e.I have understood the whole approach of editorial just struggling in implementing last part of the editorial.

Thanks in advance.

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

I found a pretty elegant proof for E: let's call a cell $$$x$$$ winning if the first player wins starting from $$$x$$$, otherwise let's call it losing. Let's induct backwards from $$$n^2$$$ to $$$1$$$, assuming correctness of previously marked cells. Suppose that we're currently deciding whether cell $$$i$$$ is winning or losing.

There is an important observation: for all previously marked losing cells $$$a$$$, there exists a winning cell $$$b$$$ such that $$$b > a$$$ and $$$dist(a, b) > k$$$. Furthermore, for all previously marked winning cells $$$a$$$, all cells $$$b$$$ such that $$$dist(a, b) > k$$$ are either less than $$$a$$$ or marked losing.

If there exists a marked winning cell $$$j$$$ such that $$$dist(i, j) > k$$$, the second player has a winning strategy: pick the cell $$$j$$$, suppose the first player then picks $$$w$$$. From our observation, either $$$w < j$$$, or $$$w$$$ is a losing cell. In the first case, the second player can respond with $$$j$$$ again. In the second case, from our observation, they can respond with a strictly larger winning cell. We can see that by repeatedly following this strategy, the second player will accrue an advantage of at least $$$10^{100}$$$, since on their turn, they will always respond with a cell strictly larger than that of the first player.

If there doesn't exist such a cell $$$j$$$, then the first player has a similar winning strategy. This time, it can be proven that they can accrue an advantage of at least $$$10^{100} - n^2$$$ (we can imagine that their first move is a "sacrifice", and then they can repeatedly choose a larger cell than what the second player got in the preceding turn).

So I believe that if the number of moves of each player was reduced to $$$n^2 + 1$$$, then the solution would remain the same.

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

I didn't participate in the contest, but I solved problem C just now with a similar approach.

I first realized that there has to be exactly one 1 in the input array c. Find this index, and reset the array starting from that index. Then I realized that if you go from c[i] to c[i + 1], the following two inequalities hold true if a valid permutation exists: 2 <= c[i + 1] <= c[i] + 1 and c[i + 1] <= n. So a simple O(n) solution is to find the index of the element with a 1, reset the array to start with that element, and check consecutive pairs to make sure the inequalities are satisfied.

I used proof by ac. 152800406

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

Hi all! I need a help to understand problem D2. Test2 has case: 0 0 1 with answer '0'. As i understand the input values, l=0, r=0, so, initial value of 'a' is '0'. Result of 'xor' operation with 'x' is '1'. We have to find 'x'. Why it is '0'? Pls help to understand.

The question is cleared.

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

161418396

For D2, we can fix the starting bits. If our first few bits in our array doesn't match with the necessary number of bits (according to l...r), then invert the bits. Otherwise, keep as is. Recurse.

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

In problem D2's tutorial, Otherwise, we will pair a_i with a_i⊕1, and we will left with at most 2 candidates for x to check. I do not quite buy it. Why do we pair $$$a_i$$$ and $$$a_i⊕1$$$? And what do you do to check the 'x'?

Uhmm... Sorry, I have just understood it, so I am no longer need for explainations.

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

Regarding C : Blog

Question link : https://codeforces.me/problemset/problem/1658/C

Pre-requisite : Relationship between $$$p$$$ and $$$c$$$

In the question, we are given that:

$$$c_i$$$ is the power of the (i — 1)th cyclic-shift of the permutation $$$p$$$

This means that $$$c_1$$$ is the 0th shift : Which means that is, for that case, the permutation remains as is => $$$p_1, p_2, p_3,...,p_n$$$

$$$c_2$$$ is the 1st shift : $$$p_n, p_1, p_2, ..., p_{n-1}$$$ $$$c_3$$$ is the 2nd shift : $$$p_{n-1}, p_n, p1, p2, ..., p_{n-2}$$$

So as you see items in $$$c$$$ from 1st index to nth index, you start with the first item being at the start, then you suddenly go $$$p_n$$$ and come back until $$$p_2$$$

So: $$$c_1 \rightarrow p_1$$$ $$$c_2 \rightarrow p_n$$$ $$$c_3 \rightarrow p_{n-1}$$$ ... $$$c_n \rightarrow p_2$$$

Where does $$$c_i + 1 \geq c_{i+1}$$$ come from?

Case 1 : $$$p_1 > p_n$$$

Note that $$$p_1$$$ corresponds to $$$c_1$$$ and $$$p_n$$$ corresponds to $$$c_2$$$

In this case, the next item that is coming at the start ($$$p_n$$$) is smaller than the current item. When $$$p_n$$$ was at the last point, it didn't contribute to $$$c_1$$$ as $$$p_n < p_1$$$, therefore it's removal from the last point doesn't affect the $$$c$$$ value of $$$p_1$$$. But now that it has come to the start of the permutation, we can see that the c-value increases by 1. Therefore in this case $$$c_i + 1 =c_{i+1}$$$

Case 2 : $$$p_1 < p_n$$$

Note that $$$p_1$$$ corresponds to $$$c_1$$$ and $$$p_n$$$ corresponds to $$$c_2$$$

Now at the start we are bringing a bigger element.

When $$$p_n$$$ was at the end of the array, it was more than $$$p_1$$$ so it might be contributing to the c-value in that case (this will happen when $$$p_n$$$ is the largest number in $$$p$$$). So removing it from the last position might decrease the c-value.

Also, when $$$p_n$$$ comes at the start of the array, then it will shadow $$$p_1$$$ and other items smaller than $$$p_n$$$. This means, that the c-value could further decrease.

So we can see that in this case $$$c_i \geq c_{i+1}$$$ (There are cases where the c-value remains the same. Example : 1, 3, 2 has c-value of 2, and 2, 1, 3 also has a c-value of 2)

So by combining $$$c_i \geq c_{i+1}$$$ and $$$c_i + 1 = c_{i+1}$$$ we can say that $$$c_i + 1 \geq c_{i+1}$$$

How is this condition enough to check whether a valid permutation can be formed?

Let's first think about what a permutation would look like, when following the condition $$$c_i + 1 \geq c_{i+1}$$$

This, simply, means that we can have drastic reductions, but increments can only be done in 1s.

Case 1 : Maximum value in $$$c$$$ is $$$n$$$

In this case, we will have a simple incremental array from 1 to n in $$$c$$$. That is, it will look like : $$$1, 2, ..., n$$$ because we NEED to have a single one, to represent the biggest element in $$$p_n$$$, and we need to reach $$$n$$$ from this value, and we can only increase by 1.

This would generate the simple permutation : $$$n, 1, 2, ..., n-1$$$

Case 2 : Maximum value in $$$c$$$ is less than $$$n$$$

In this case, we would have repetitions of numbers in $$$c$$$. Note that we can not have more than one 1 in $$$c$$$. Other numbers can repeat.

So we need to reach this max number (let's say $$$m$$$) from 1, and we can increase by one only.

So this can look like : $$$1, 2, 3, 4, ..., m, m - 2, m - 1, ...$$$ Basically an increasing phase, followed by random drops and increases. The increasing phase can also have repetitions, and drops.

In order to construct the array, this construction method : https://codeforces.me/blog/entry/101302?#comment-899615

When the c value increases, then we can simply put a smaller number at the curr position. That will ensure that a correct permutation is being generated.

When the c-value decreases, note that this value would be a repetition — We already would have seen this value atleast once. Why? Because we started from 1, and in order to decrease, we must have reached the current value by increments of 1. That means we have seen all numbers between 1 and the current number. Therefore, all drops / decrements would generate a number, which already has been seen.

Another point to note : Between the previous instance of this number, and the current instance of this number, we either: - Decreased and increased - This would be handled by the "c-value increase" case. - Increased and decreased - This would mean that c-value increased, and decreased to come back at the same point. An "increase" in c-value means a decrease in absolute value in $$$p$$$. Therefore, all numbers between the same instances would be smaller. This simply means that we can indeed have a correct permutation in this case too.

I think these inferences are enough to see that the condition is enough to check whether a valid permutation can be created from the given c-values.

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

Btw if the n is odd we can easily solve it just take the xor of numbers from 0 to l-r say it comes out to be x1 and then take xor of the array say x2 and now traverse the array and check if x1^v[i]==x2 that is our answer

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

can anyone explain why approach of d1 not working for d2

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

my master give me this D1 problem couldn't able to do was thinking for hours but cant think D1 optimal solution feeling bad , :( idk whether i am improving or not not able to solve as going to higher ratings . feels very demotivated.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solve D2 using tires i think it is much easier then. please look at this code 265873403