Theo830's blog

Codeforces Round #912 (Div. 2) Editorial
By Theo830, 11 months ago, In English

Problems A, B, C, D1 and E were authored by me and Adam_GS authored D2 and F.

1903A - Коробкии халлуми

Hint
Solution
Code (C++)
Rate this problem

1903B - ХранИЛИще

Hint
Solution
Code (C++)
Rate this problem

1903C - Кошмар Теофаниса

Hint
Solution
Code (C++)
Rate this problem

1903D1 - Максимум и запросы (простая версия)

Hint
Solution
Code (C++)
Rate this problem

1903D2 - Максимум и запросы (сложная версия)

Hint
Solution
Code (C++)
Rate this problem

1903E - Гео-игра

Hint
Solution
Code (C++)
Rate this problem

1903F - Няня

Hint
Solution
Code (C++)
jeroenodb's solution O(M log N)
Rate this problem
  • Vote: I like it
  • +123
  • Vote: I do not like it

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

Great contest! Solved A and C, i guess i should practice bit operations

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

    I'm too, I can accept some hard DP problems but, bit operations I can't, it is so much trick. :((

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it 

Interesting problem specially C and D


But C is similar to an old problem I solved before called

(Array Splitting) 1900

→ Reply
»
11 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Tutorial came too early :D

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Mij = ai | aj should be the statement in editorial of B

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

    Yes , a typo from their side. Other than this , the solution was brilliant.

    → Reply
»
11 months ago, # |
  Vote: I like it -30 Vote: I do not like it

BITFORCES

→ Reply
»
11 months ago, # |
  Vote: I like it +9 Vote: I do not like it

who can explain why C greedy works ?

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    If your suffix sum is positive, it's more optimal to make an extra group on your current position since making another group will double the values on the suffix.

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Consider scanning from front to back, deciding at each position whether to open a new subarray.

    If I start a new subarray from the current position, then according to the question, the multiplier of this subarray will be 1 more than the previous one, which also means that the multipliers of all subsequent numbers will also be "pulled high" at the same time. (It can be found that we do not need to know how the following numbers are divided)

    Obviously, it is not advisable to "increase" the multiplier if the suffix is negative, as that will make the answer smaller.

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

    Any subdivision can always be written as a sum of suffix sums, which should always include the very first suffix sum, i.e. 1*(subarray starting at 1) + 2*(subarray starting at i)+3*(subarray starting at j).. = suff[1] + suff[i] + suff[j]+. Once you are convinced, there is one to one correspondence between these 2 functions, you can just pick suff[1] and rest positive suffix sums.

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Greedy or DP is just a construct. What if I told you that the editorial's solution is just refactored DP solution?

    Here's a question for you: You might have heard of Kadane's algorithm. We define $$$dp[i]$$$ to be the maximum sum subarray ending at index $$$i$$$. When written in this form 

    dp[i] = max(a[i], a[i] + dp[i - 1])

    You can confidently say that it's DP.

    But, notice that $$$a[i] + dp[i - 1] > a[i]$$$ iff $$$dp[i - 1] > 0$$$. So if you do a space optimization, and keep a max_so_far and max_ending_here, you can see that max_ending_here would be a[i] + max_so_far if max_so_far is positive. And intuitively, that makes sense since you should keep the left extension if it gives you a net positive value. Would you still call this approach Greedy or DP since now the decisions make sense intuitively? I also talk more about Greedy vs DP for this problem here

    In case anyone's interested,I've added hints and thought process for problems:

    on CF Step

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

      Hey, Thanks for the dp approach, i was actually able to solve the problem but wasn't sure why it would work, Really appreciate the efforts you put in the explanation!!

      → Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it +77 Vote: I do not like it

I feel like these are indeed solutions, but sometimes there are no... proofs. Which is especially important for first problems so that beginners can understand the difference between a correct solution and an incorrect solution.

P.S. And the comment above perfectly illustrates my point.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Yeah, there is no intuition and approach. Just reading the code. What's the point in making editorials if they can't be understood by a learner.

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why it's not truth that |(mat[0][0..n-1]) = |(mat[1][0..n-1]) = ... = |(mat[n-1][0..n-1]) in problem B?

I checked it and it crashed my solution! lets look on example with 3x3 matrix:

a_i — ith element of our array then:

1st row: 0 | (a_1|a_2) | (a_1|a_3) = a_1 | a_2 | a_3

2nd row: (a_2|a_1) | 0 | (a_2|a_3) = a_1 | a_2 | a_3

3rd row: (a_3|a_1) | (a_3|a_2) | 0 = a_1 | a_2 | a_3

help me pls

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Here's how I solved E:

So, first we realise that checking if the sum of integers is even or odd should motivate reducing everything $$$\pmod{2}$$$. We note that $$$\text{distance}^2((x_1,y_1),(x_2,y_2)) \equiv (x_1-y_1) - (x_2-y_2) \pmod{2}$$$

(this follows from casework on the possible values of $$$x_i$$$ and $$$y_i$$$).

Nice, so we can reduce this 2D problem to a 1D problem. Create a new array $$$a$$$ satisfying $$$a_i = x_i - y_i \pmod{2}$$$

Then, the parity of the squared distance between points $$$i$$$ and $$$j$$$ is captured simply as $$$a_j - a_i \equiv a_i - a_j \pmod{2}$$$. (Doesn't matter the order, we'll see why this is nice).

Let's give the starting value its own special place in the array, Start $$$\to a_0$$$.

Now, let's make a couple moves. Suppose we choose to go to $$$(x_i,y_i)$$$ from Start. This is equivalent to going to $$$a_i$$$ from $$$a_0$$$. If the squared distance between $$$(x_i,y_i)$$$ and Start happens to be even, then it's necessarily true that $$$a_i - a_0 \equiv 0 \pmod{2}$$$. If the distance happens to be odd, then $$$a_i - a_0 \equiv 1 \pmod{2}$$$

After we make our move, our new Start is $$$a_i$$$. Let's choose another point $$$(x_j,y_j)$$$. What will the parity of the squared distance between points $$$j$$$ and $$$i$$$ be? Well, it'll just be $$$a_j - a_i \pmod{2}$$$. Note, that we care only about the sum of the parity of the squared distances, and what that's going to be. So if we keep a running tally of our score so far, we have:

$$$(a_i - a_0) + (a_j - a_i) + \dotsc \pmod{2}$$$. Isn't it weird that the $$$a_i$$$'s cancel?

Turns out that this pattern continues. It telescopes so that only the $$$0^{\text{th}}$$$ and the last index of the game, let's call that $$$k$$$, are the only ones remaining, i.e.

$$$a_k - a_0 \pmod{2}$$$

Now, we see that if we go first, we want to ENSURE that $$$a_k$$$ is the same value as $$$a_0$$$. This is a lot simpler to think about. Let's count the number of zeroes and ones in $$$a$$$ (disregarding $$$a_0$$$) and enumerate their indices into two sets, the zero set and the one set.

An optimal adversary will want to prevent us from ensuring the last element selected is the same value as $$$a_0$$$, so on each turn, they will try to use them up. That means, they will choose the points with those values. We can see that the only possible way for us to win if we go FIRST is if there are at least as many "$$$a_0$$$" values as non-"$$$a_0$$$" values. This is because we'll take the non-$$$a_0$$$ values and as long as there are at least as many $$$a_0$$$ values, the non-$$$a_0$$$ values will deplete first, guaranteeing a victory for us.

If there are strictly more non-$$$a_0$$$ values, we would want to go second, because then we'll just take the $$$a_0$$$ values and ensure the total sum parity is $$$1$$$, aka odd.

235128893 (Code is really bad, I went through each case individually because I was rushing to get it in before contest ended).

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

    It's pretty easy if just expand the formula, let the points chosen be 1,2,....,n+1, then the formula expands to s1^2+2*s2^2+.....+sn^2,-2*s1*s2.... You can eliminate all the terms with 2 coefficient for even sum , so the answer is just dependant on the first and last point and the starting point is fixed

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

      Hey, I used the same logic. I counted the even and odd parity coordinates and parity of the $$$s_x^2 + s_y^2 = v$$$. Then, I claim that if $$$v \oplus (\text{#odd} > \text{#even})$$$ equals 1, I will go second, or else I'll go first. If I go first, I will try to use all coordinates with parity $$$(1-v)$$$ (where v was the parity of the starting point).

      But unfortunately, my code is giving WA. Can you please help me out?

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

        There are 4 cases not 2 look at my submission

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

          Can you explain your approach in short? I am not getting which cases you are talking about?

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

            There are 2 cases if n is even and n is odd to determine who plays last further if the other player(who isnt playing last) can play all the points the last player needs to play on his last turn we go with the other player otherwise the last player

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

    beautiful explanation !

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why is this solution giving WA for test case 4 although I feel I have done what is mentioned in the editorial. Submission- 235137669

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

    could be integer overflow cum*count in your code (i have not looked very carefully)

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thanks for the reply but I dont think the reason can you please look into the following--> I discarded the cum variable cause its unnecessary 235118044

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain C in more detail? Didn’t understand the editorial(

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    If you open a new subarray at an index i, then it is like you are adding the suffix sum from index i to n to your answer. So, you would start first subarray at index 1, so you would add whole array sum to your answer, now if you start a second subarray at index i, then you only need to add the sum of second array one more time because you have already added it once when you added suffix sum of index 1. For the k-th subarray, you have already added it's sum (k-1) times, so you would add it just once.

    Now, it is beneficial to add the suffix sum only when it is positive, so we will do only that

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Completely understand after reading your solution. Thanks

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

      amazing explanation man, almost every soln or comment had dp which I am unfortunately not well versed with, this one cleared it though, thanks again :)

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

      Thanx bro, i couldn't understand anything from the editorial! But you made it so much more clearer.

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

      Man, your explanation is a million times better than the editorial solution. Thanks.

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

      This was the best explanation,thanks

      → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    this is how I did it.

    assume a b c d

    we have two choices at after a, divided it or don't divide. "cuts" is how many subarrays we already made.

    divide it=> (a*cuts) + ((b+c+d)*(cuts+1)) -->DI

    and

    don't divide=> (a+b+c+d)*cuts             -->DD

    now let's see why ((b+c+d)*(cuts+1)) will never decrease, after placing a cut after "a" we have this subproblem to solve the "b c d" similarly, we will repeat the process and only place a cut again if it is increasing the overall sum of our array hence it won't decrease.

    my solution 235124903

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for B, is there any way to confirm that solution doesn't exist without going through entire solution array?

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

I have another solution to the problem C (maybe more intuitive):

Let $$$dp_e$$$ denote the maximum division value for the array $$$[a_e, a_{e+1} ... a_n]$$$.

Then if we add some block $$$[s...e)$$$ in front the division value gets updated by $$$\sum_{s}^{e-1}{a_i} + \sum_e^{n}{a_i} = \sum_{s}^{n}{a_i}$$$ (that is because every element after $$$e$$$ adds $$$a_i$$$ to its corresponding block).

Thus we have $$$dp_i = max(dp_j) + \sum_{i}^{n} a_i$$$, where $$$j > i$$$.

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

    This is ridiculously slick. Nice solution!

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

    Such an elegant solution! Thank you for sharing!

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That is a brilliant solution! Hope someday even I can think of such solutions.

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

    If we try to do this from front instead of back, we would face the problem of computing dp i = max(dpj + summation of a's from j to i) for j < i. Thus this would take O(n^2) time to compute. Is this the reason we compute the dp from behind or I am wrong?

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

    Excellent analysis. Implementation of the above idea 236158727.

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think editorial in C should include that sum of suffix sums, results in what the problem is asking to maximize, i.e 1*(1st subarray sum) + 2*(2nd subarray sum)+..... This 'trick' is arguably the hardest part in the problem to figure out. The editorial just assumes that everyone knows this.

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

    True. I was trying to figure out what was going on until I saw your comment.

    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for the comment

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

    A great explaination! Although I solve it with greedy,but still have some trouble about correctness.Help me a lot.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody explain to me why the solution of problem C in the editorial works, like a solid proof ?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let $$$w_i$$$ be the id of subarray that contains $$$a_i$$$.

    It is not hard to see that $$$w$$$ is non decreasing sequence where each adjacent element can differ by at most 1. ($$$a_i + 1 = a_{i+1}$$$ or $$$a_i = a_{i+1}$$$ for $$$i \in [1..n-1]$$$

    Initially let $$$w_i$$$ be 1 for all i.

    For each element (excluding first element) $$$a_i$$$ we can either do nothing or increase $$$w_j$$$ by 1 for every $$$j >= i$$$, doing so will increase the cost by $$$suff_i$$$ so if $$$suff_i$$$ is nonnegative we can get not-worse answer by increasing $$$w_j$$$

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

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the binary operation of question B? It’s not suitable for understanding.

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

    Check my submission, you can get another approach, somewhat similar but easy to undersatnd

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sad. Int overflow in D

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

    Same, I wasted time trying to find mistake in my code. I used __int128 to deal with overflow.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problem Indeed!! Enjoyed very much..should have able to solve C and D. I even calculate the suffix array for C and still not able find suf[i]>0 contribute in the answer..Very frustrating!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How greedy works on problem C?Can someone explain me?

→ Reply
»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

F is absolutely brilliant. Amazing problem!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why we are doing AND operation in B problem what we get from common set bit

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    We use AND to unset bits.

    • If the $$$k$$$-th bit is set in $$$M_{ij}$$$, then that bit should be set in either $$$a_i$$$ or $$$a_j$$$ or both.
    • If the $$$k$$$-th bit is unset in $$$M_{ij}$$$, then that bit must be unset in both $$$a_i$$$ and $$$a_j$$$.
    → Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    0 7 7 5 5        000 111 111 101 101
7 0 3 2 6        111 000 011 010 110
7 3 0 3 7  --->  111 011 000 011 111
5 2 3 0 4        101 010 011 000 100
5 6 7 4 0        101 110 111 011 000

    solution array: 5 2 3 0 4 ---> 101 010 011 000 100

    Now, if you compare every elements of M that ai contributes. Their bits(bitwise) are gonna be either(ignoring i == j):

    all 1:               column 1 -> 11(1), 11(1), 10(1), 10(1)
or contains 0:       column 2 -> 11(1), 01(1), 01(0), 11(0)

    in latter case ai's corresponding bit has to be 0. Otherwise it could be 1. And AND gives us this operation.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the purpose of putting incorrect outputs in E's example testcases? I think it had confused people who didn't read problem statements carefully enough.

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

    They were correct, but then you'd have to pray for the interactions to go your way hahahahah

    → Reply
»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As Dr. Emix I can say that all of you helped in solving 1903C - Кошмар Теофаниса and now he can finally sleep peacefully!

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    As a solver, I want you to pay me for the help!

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain DP approach for problem-C?

→ Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain the solution of D2?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Although I solved D2, I found the editorial quite confusing as well, so my explanation might differ a bit from the post above.

    First, we are still using a similar greedy approach from D1 to iterate through all of the bits from most significant to least and turning it on when we can. However, because N * Q is no longer <= 10^5, we are motivated to come up with a way to check the cost of turning on a bit in the final answer faster than O(N).

    We can see that we want to increment each element by 1 until it has the bit we want on. If the bit is already on, the cost is 0. Otherwise, there are two cases we need to consider:

    First, if an earlier bit was already turned on. This means that the cost to turn on this bit will always be the bit itself. (proof: to turn on a more significant bit that was considered earlier, the number was incremented just enough so that that bit is on, meaning that any smaller bits are off). Since the value of the bit will be constant for all of the numbers, we can simply count how many numbers have already been turned on in a previous bit.

    Second, if this is the first bit that has to be turned on. This is a little harder to compute all at once, since the cost will be bit - (num % bit).

    We can also observe that if the bit that we want to turn on is greater than 2^20, all of the numbers will fall into the same category. So, we can compute the cost for bits greater than 2^20 quite quickly.

    If a bigger bit has been turned on: (sum of all the numbers mod bit is equal to zero) cost = bit * n

    If a bigger bit has not been turned on: (sum of all the numbers mod bit is equal to the sum of all the numbers) cost = bit — sum of numbers

    So we simply need to keep track of whether a bit greater than 2^20 has previously been turned on to deal with these cases. However, we still do not have a way to calculate the cost when we turn on bits smaller than 2^20. That's when SOS DP comes into play. Since we only need to keep track of which of the 20 bits has been turned on, we can turn this into a bitmasking DP problem, where we calculate the cost needed to turn on a bit when a set of bits has already been calculated already. Something like dp[20][1<<20]. However, to calculate this, we run into a problem, in that this will require us to iterate through all of the subsets of each number, which makes our runtime O(N * 2^20 * 20). This is obviously too big to compute, so we need to use a DP Optimization aforementioned called SOS DP. I will not explain this trick here since it is already better explained in other CF Blogs (ex. https://codeforces.me/blog/entry/45223). This allows us to calculate the cost to turn on bits when a set of bits has already been turned on in O(1) after O(2 ^ 20 * 20 * 20) precalculation.

    Hope this helps!

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in b we don't have to remove anything else ? Since there just one of ai or aj need to have it . so ai can have it and ai can don't obtain that bit too if aj have it. Why we do not have to remove anything else? If there a situation that ai doesn't have a bit then solution exists but we assume that ai need to have it then it seems not work properly. I understand that i may misunderstand or miss sth. Can anyone give me some explanations plz. Thx alot.

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I had the same question during the contest and took quite some time to figure out why we don't have to care about this thing.

    Suppose we had $$$x^{th}$$$ bit turned on in $$$a[i]$$$. Now, you are asking how about we just turn it in from a[i] and leave it turned on in the corresponding $$$a[j]$$$.That should be equivalent isn't it ?

    Well, we calculated a[i] as the cumulative bitwise AND of the entire row $$$M[i]$$$. This means $$$x^{th}$$$ bit of $$$a[i]$$$ got turned on because it was turned on in all cells of the row $$$M[i]$$$. That means, if you turn off $$$x^{th}$$$ bit from $$$a[i]$$$, then you will have to turn on the $$$x^{th}$$$ bit in all columns from $$$1$$$ to $$$n$$$ except the $$$i^{th}$$$ column. Why ? Because remember $$$x^{th}$$$ bit got turned on only because every cell of $$$M[i]$$$ required that to be turned on. (thats what taking the AND of the entire row means, right).

    Now, if all the elements $$$a[1],a[2]...,a[n]$$$ except a[i] have the $$$x^{th}$$$ bit turned on, then the entries in matrix $$$M[1][i], M[2][i], M[3][i],..., M[n][i]$$$ will have to get the $$$x^{th}$$$ bit turned on. But, isn't that exactly what would happen if we did not turn off $$$x^{th}$$$ bit of $$$a[i]$$$ ? Only the entry $$$M[i][i]$$$ will not have this constraint but it is anyways guaranteed to be zero in problem statement.

    Thus, conclusion, if you wish to turn off the $$$x^{th}$$$ bit from some $$$a[i]$$$, then you will have to turn this bit on in not just the corresponding $$$a[j]$$$, but in all of $$$a[1],a[2],...,a[n]$$$ (except $$$a[i]$$$). This will ultimately have such an effect which is exactly same as just leaving the $$$x^{th}$$$ bit on in a[i] in the first place.
    Hope you understood.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain D1

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B you wrote "We check if Mij = ai & aj holds for all element" Here it will be Mij = ai | aj. Isn't it?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F, how is it possible to only use one segment tree structure? Won't you need two (also for the negation nodes — whose edges go to the parents, instead of towards the children)?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting problem specially C and D

But C is similar to an old problem I solved before called (Array Splitting) 1900

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In the solution to problem C, I think it should be suff[i] >= 0 in the if condition.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D in detail I could get the core idea :\

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C Detailed Editorial : DETAILED EDITORIAL FOR PROBLEM C

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I think problem E has a simpler explanation.

After doing the math and finding out that going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) changes your overall parity by $$$x_0 \oplus y_0 \oplus x_1 \oplus y_1$$$. You can do some more math and find out that going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) to ($$$x_2$$$, $$$y_2$$$) changes your overall parity by $$$(x_0 \oplus y_0 \oplus x_1 \oplus y_1) \oplus (x_1 \oplus y_1 \oplus x_2 \oplus y_2) = x_0 \oplus y_0 \oplus x_2 \oplus y_2$$$.

Then we can easily see that this extends as follows: going from ($$$x_0$$$, $$$y_0$$$) to ($$$x_1$$$, $$$y_1$$$) to ($$$x_2$$$, $$$y_2$$$) to ... to ($$$x_n$$$, $$$y_n$$$) changes your overall parity by $$$x_0 \oplus y_0 \oplus x_n \oplus y_n$$$. This means that only the parity of the first and last points matter, all other points get cancelled out by the XOR. Additionally, the first point is fixed, so we only care about the last point.

Let's call points of the same parity as the starting point good, and the other points bad. If you are the first player, you want to make the last point be good, you can do this if the number good points are not less than the the number of bad points. You can do this by repeated choosing the bad points to deplete them until your last turn, then choosing (or forcing the other player to choose) a good point. Similarly, if you are the second player and the number of good points is greater than the number of bad points, you can just keep choosing the good points until the last turn, then choose (or force the other player to choose) a bad point.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[Doubt][Problem D] — Can someone explain how the formula 2^b — ai(mod)2^b comes in the editorial.

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

    Consider $$$bin(num) = 111001*0101$$$. I ask you to apply bit manipulation to clear all the bits to the left of * (eventually converting it to $$$000000*0101$$$).

    One way to do it is to iterate over higher order bits and manually turn them off one by one. But if you want a fancy way, you can just do $$$num \% 2^4$$$. This works because any number can be represented as $$$\sum 2^{set\_bit\_index}$$$, and all the set bits that we want to clear have index $$$\geq 4$$$. So their modulo is zero and they would be unset. The lower order bits won't be touched because $$$z \% 2^4 = z$$$ if $$$z < 2^4$$$.

    You already know a trick to unset the $$$i^{th}$$$ bit. Now you've learnt about a trick to unset all bits with indices $$$\geq i$$$.

    Why exactly do we want to unset the higher order bits is something specific to the problem. I'll leave it upto you to figure that out, feel free to respond to the comment if you are not able to.

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

      Thankyou so much adaptatron. I got the clear understanding.

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone with binary search solution for D1?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problemset! I liked E a lot, since we don't get game theory that often, and this one was an especially cool problem.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F can be solved using dfs on implicit graph. As mentioned in the editorial, the problem reduces to be able to visit all vertices in range $$$[l,r]$$$ from vertex $$$v$$$, but without creating actual edges. We can store unvisited vertices in the set. In the dfs we first visit all vertices in the main graph, and after that use lower_bound to find next vertex in range $$$[l,r]$$$ which is still not visited.

The code looks something like this

void dfs1(int v) {
	if (v % 2) {
		oddV.erase(v);
	}
	else {
		evenV.erase(v);
	}

	for (auto to : g[v]) {
		if (oddV.count(to) || evenV.count(to)) {
			dfs1(to);
		}
	}

	for (auto[l, r] : g1[v]) {
		while (true) {
			auto it = oddV.lower_bound(l);
			if (it == oddV.end() || *it > r) {
				break;
			}
			dfs1(*it);
		}
	}

	order.push_back(v);
}

I used odd and even vertices, because in 2-sat graph we only have edges from even vertices to odd vertices and vice versa

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

P

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not able to undersand any part of the editorial for problem F.

Can anyone help me understand the logic for problem F?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Editorial.learn useful trick.Thank you..

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I am trying D using binary search but getting TLE, I don't think the time complexity of my code is that bad. Here is my submission. https://codeforces.me/contest/1903/submission/235400941

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for Problem E: say the first point is $$$(x_0,y_0)$$$ and the remaining points (in the order in which they are chosen) be $$$(x_i,y_i)$$$ $$$(1 \le i \le n)$$$. The overall expression comes out to:

$$$( 2 \cdot \sum_{n=0}^n x_{i}^2$$$ + $$$2 \cdot \sum_{i=0}^n y_{i}^2$$$ - $$$2 \cdot \sum_{i = 0}^{n-1} (x_i \cdot x_{i+1} + y_i \cdot y_{i+1})$$$ ) - $$$(x_{n}^2 + y_{n}^2 + x_{0}^2 + y_{0}^2)$$$

Clearly the parity of the final sum is decided by the first (given) point and the last selected point. Since the parity of first point is fixed we can only try and select the ideal last point. If

$$$x_{i}^2 + y_{i}^2$$$

is odd, the first player will try to select

$$$(x_n , y_n)$$$

such that the parity changes i.e

$$$ x_{n}^2 + y_{n}^2$$$

is odd. Hence he will try to eliminate all even sum of squares if possible. Hence we can choose the winner for each case based on the parity of the sum of square of the first point and the number of points with odd or even sum of squares of their respective components. My Solution: https://codeforces.me/contest/1903/submission/235405790

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf the editorial is totally a piece of shit

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why this Binary search for Problem D1 fails on Test 5 236231559

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is $$$O(M \log(n))$$$ solution to F added?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial code for problem D, what does p+=ans^(p&ans) does??

why it has been used ?

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think in the editorial for D1, the two lines of p+=ans^(p&ans); are probably redundant? Because $$$ans$$$ would start with a series of '1's $$$p$$$ would start with the same series of '1', too.

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i did'nt expected that i would get stuck on this problem for 3hr . i was trying to actually reverse the array for the elements where there is decreasing order and repeat this step n times , but when i read hint i felt very dumb that we can sort any array of size k = 2 .

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for c problem (let's take all elements are positive ) how the summation is the suffix sum array elements is equal to summation of i*a[i]

example:

suppose elements are 1 2 5 6 8 suf sum =22 21 19 14 8 summetion of suf sum =84

also if we do 1*1 +2*2+ 3*5 +4*6 + 5*8 =84

how it is doing any proof please Theo830

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

    Start by having only one time each element (only one big group). Then as you add another suffix group you will have two groups. The first group/subarray with one time for each element and the second group/subarray with two times for each element.

    In the example that you are saying. We start with

    $$$[1,1,1,1,1]$$$ (This is how many times we take each element)

    Then it becomes $$$[1,2,2,2,2]$$$

    Then $$$[1,2,3,3,3]$$$ etc.

    In the end we will have $$$[1,2,3,4,5]$$$

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

How can I figure out patterns and problems faster in different types of questions. Is there a certain common way of approaching certain category of problems like for greedy we have to think in 1st way or for graphs in 2nd way???????

Like I couldn't think about Suffix in Problem C. I was thinking about something like Kadane.

→ Reply