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

Автор Dalgerok, история, 6 лет назад, перевод, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Round 553 (Div. 2)
  • Проголосовать: нравится
  • +176
  • Проголосовать: не нравится

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

thanks for tutorial and your effort

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

Thank you for fast editorial!

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

  • Fast System Testing

  • Quick Editorial

  • Overall Great contest :)

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

Here's how i did problem D. 52982122

Just sort the array according to the below comparator.

bool comp( pair< int ,int > a, pair< int, int > b){
    if(a.first + b.second > a.second + b.first) return true;
    else return false;
}

Proof: Let there be two pairs a and b. The dissatisfaction is i*(a1 + a2 — b1 — b2 ) + n*(b1 + b2) — a1 — a2 . We have to just consider the i term as rest are constant terms. Sort it according to a1 — b1 > a2 — b2

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

    Thx! Easy to understand !!

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

    the formula given is Ai(i -1) + Bi(N-i). So if you take two pairs A and B. then Ai and Bi for A and B are A1,A2 and B1,B2 respectively. Then total dissatisfaction due to both would be A1(i-1) + A2(N-i) + B1(i-1) + B2(N-i). So this should reduce to (A1 — A2 + B1 — B2)i + constants. Now Please tell how did you get A1+A2-B1-B2 for 'i' term.

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

I used divide and conquer in E. Let $$$f(l,r)$$$ equals answer for segment $$$[l;r]$$$ and $$$half = (l+r)/2$$$ then $$$f(l,r) = f(l,half) + f(half+1,r) - min(arr[half], arr[half+1]) * (n - max(arr[half], arr[half+1]) + 1)$$$.

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

    Oh! Egor Letov is alive!

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

    Hi, I went through your submission but couldn't understand the intuition behing Divide and Conquer.

    Could you please explain your intuition behind it ....

    Thanks in advance !

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

      I used the same approach as him so I will try to explain it.

      Let say we want to find the answer for an array A. Now imagine that for some of the ranges (l, r) the two halves of A always belong to different components.

      For example the array A is: 2 4 6 2 7 3 and the range is (2, 3) or (6, 10). For these type of ranges we can just calculate the answer of each half seperately and sum them up.

      However this is not always the case since the exist some ranges for which the right point of the first half is connected to the left point of the second half. Say the range (2, 6) or (1, 10) in the example.

      How to handle these cases? Well we will sum them up similar to what we do with the first case. Now the answer will contain some invalid components — for each range similar to (2, 6) or (1, 10) we have counted the middle component twice. Now what we have to do is to substract from the answer the number of ranges for which the two border points remain the same. This is the meaning of the last term in his recurrence equation.

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

This is boolshit))

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

    Have you coded your solution? I'm sure that it is wrong. Firstly, I think that $$$m_{i, i} \neq m_{i, j}$$$. Secondly, you can't compute the answer by multiplying the probabilities (your last sentence), because they are not independent.

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

For problem D, you don't really need to sort by index. "array d in non-decreasing order". I solved without sorting D.

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

It is very thankful for brilliant tutorial.

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

can somebody explain me problem c and I have seen some solution like (calc(R) — calc(L — 1) + mod) % mod here he is adding mod, why? if we are not adding mod then 6 test case fail.please help me. Thank u

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

    It depends on your language. Languages like C and C++ don't return values between $$$0$$$ and $$$MOD-1$$$ while taking mod of a negative number. Instead they return the 'negative mod'. $$$-5mod4$$$ should be $$$3$$$, but $$$-1$$$ is returned. While $$$-1$$$, is correct, it's not what we want. So, we add an extra $$$MOD$$$ and take mod again to ensure the result lies between $$$0$$$ and $$$MOD-1$$$. Adding an extra mod should always be done if you're subtracting 2 numbers and taking their mods.

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

For problem C, this is my solution https://mirror.codeforces.com/contest/1151/submission/53005511 The solution uses the logic given in the editorial. I have tried placing MOD in all possible location and still not getting the correct answer. Anyone help? :)

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

    Anyone please :)

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

      In your fun(), it's enough if you just calculate the pow(2, i) without the mod. By subtracting, what you're essentially doing is just dividing the variable x by 2. So taking mod on the variable x would affect the loop because modular division is not similar to modular addition or subtraction where you can take mod wherever and it wouldn't affect the answer.

      So, using pow(2, i) on line 39 and removing line 50 would be the way to go.

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

Dalgerok

IN E editorial, Shouldn't it be:

we must find the number of pairs (l,r) such that ai is not on the range [l,r] and ai−1 is on the range [l,r].

instead of:

we must find the number of pairs (l,r) such that ai is on the range [l,r] and ai−1 is not on the range [l,r].

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

The explanation of problem B is not helpful! Can anyone explain it?

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

    first take element from first column from each row and take their XORs. If xor!=0, simply print the index of elements and exit. If xor==0, then iterate all elements of the table. If in a given row, current element is different from element in first column, then , if we replace the first element with this element, our xor will become non-zero.

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

      thanks for this simple and easy explaination. can you plz explain problem C also??

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

        to find sum of numbers from L to R, you need to do (sum of first m numbers in this sequence)- (sum of first L-1 numbers in the sequence). This is a simple observation, you can check this by taking first 10 natural numbers.

        Now, to find sum of first L-1 numbers , you need to count the number of odd no. and number of even nos. till (L-1). To count both, start a loop from i=1 , double it on every iteration while increasing count of odd and even numbers alternatively. But, keep in mind the last count which you will add, which may not be power of 2.

        finally, suppose, you got 'a' odd numbers and 'b' even numbers. then sum= a*a + b*(b+1) (simple AP series sum formula) you can do similar calculation for first M numbers.

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

The last problem is so awesome! By the way, is there some problem that has similar "style" to the last one? I mean, its not dp on the book, it's like... creativeness on how to define dp state?

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

For F, how do we use matrix exponentiation when the dp has more than 1 dimension?

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

Here's my submission for B. https://mirror.codeforces.com/contest/1151/submission/52967808

Could someone explain the judge's verdict of XOR being less than 0 for testcase 24?

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

For the problem D. Why my solution https://mirror.codeforces.com/contest/1151/submission/53019943 is getting runtime error.

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

In Problem B we can also use RANDOM SHUFFLE!!!.
We can Random Shuffle all the elements in each row and then check the xor for each column that whether it is greater than zero or not.
P.S.-I have applied random shuffle 200 times.
Luckily it passes all the tests :P
Here's link to my solution : 53025553

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

    That was just a lucky try. I might get WA on submitting the same solution

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

I have done following in problem C. Function calculates the sum in set till number n.

ev — next even sequence start od — next odd sequence start

then for each iteration, I calculate start and end of that sequence and calculate their sum by AP. It is giving wrong answer on test case 1 1e18. Is there an overflow ? I cannot find the bug in function calc.

code link

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

I have found a solution with O(1) complexity for Problem C. See 53051961

Can anyone tell is it really a O(1) complexity? (I am just new to algorithm and I don't know is it right)

Thank you :)

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

Can someone explain the approach behind E problem ? Whats the logic for calculating f(l,r) ?

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

For problem D .By changing the compare statement, from f>0 to f>=0 my code gets runtime error.

Runtime Error — https://mirror.codeforces.com/contest/1151/submission/53027297

Accepted — https://mirror.codeforces.com/contest/1151/submission/53027346

As to why this happens, I am clueless.

Someone please tell why it started giving runtime error.

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

i still cant understand problem c can anyone explain me?

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

For Problem E — The editorial states "using technique contribution to the sum". What is this technique ??

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

Great Editorial!

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

My solution for Problem C works fine for smaller size of input but it failed for larger value. But, I'm pretty sure that I took the modulo correctly. Tried a lot to debug but failed. Could you please give a look in my code?

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

В заголовке написано №553, но в метках розбор №533, что из этого правильно?)

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

can any one help me with problem C. I am getting wrong answer for big values. https://mirror.codeforces.com/contest/1151/submission/57858024

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

Can someone tell me how to solve B using dp?