KAN's blog

By KAN, 7 months ago, translation, In English,

1119A - Ilya and a Colorful Walk

Author, preparation: 300iq.

Editorial

1119B - Alyona and a Narrow Fridge

Author, preparation: KAN.

Editorial with bonuses

Aleks5d invites you to compete in the shortest solution challenge for this problem. His code (155 bytes):

Code
Authors during the contest

1119C - Ramesses and Corner Inversion

Author, preparation: 300iq.

Editorial

1119D - Frets On Fire

Author, preparation: cyand1317.

Editorial
Code

1119E - Pavel and Triangles

Author: gen, preparation: 300iq.

Editorial

1119F - Niyaz and Small Degrees

Author, preparation: 300iq.

Editorial

1119G - Get Ready for the Battle

Authors: Aleks5d, KAN; preparation: Aleks5d.

Editorial

1119H - Triple

Author, preparation: RDDCCD.

Editorial
 
 
 
 
  • Vote: I like it
  • +133
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +88 Vote: I do not like it

Problem F: AC 4

Problem G: AC 7

Problem H: AC 5

...

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

Thanks for the fast editorial!

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

Passed G with the following solution.

Increase $$$hp_1$$$ such that $$$n$$$ is divisor of $$$\sum hp_i$$$. $$$m$$$ times choose greedily maximum group size such that it's possible to attack with this group without affecting the answer and then simulate this attacks randomly.

Any idea why this solution works?

»
7 months ago, # |
  Vote: I like it +84 Vote: I do not like it

It seems that someone is curious about what I've done on problem A. Let me describe what has happened.

Contest starts ---> Open problem A ---> A little difficult? ---> I can solve it by binary search in O(nlogn) !

===== One hour later =====

Oh my god!!!

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

    This look like funny What is your rank?I want to see your submission history

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

      You can get into his homepage and click the points on the rating graph. One point stands for one contest. Clicking one will lead you to his rank in that contest.

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

        Finally i find it ,thank you

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

How to solve B in O(nlogn) or O(nlog^2 n)?

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

    For $$$O(n\log^2 n)$$$, we can binary search the answer. For $$$O(n\log n)$$$...maybe some interesing sortings? (Radix sort?)

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

      I think, binary search gives $$$O(n \log n)$$$. Because $$$\sum^n i 2^i = O(n 2^n)$$$.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    You only need to sort the array once if you also keep the original indices of each bottle. Then binary search the answer.

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

      With binary search reducing the number of sorts does not seam to give advantage complexity-wise. It is $$$O(n \log n)$$$ regardless.

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

    binary search + sort -> solved in O(n log^2 n)

    sort in decreasing order and record the position of each value , then do binary search -> solved in O(n log n)

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

      p_b_p_b Could you post the solution for O(n log n) approach to problem B?

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

    Can you please explain I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct? Similarly in example 1 — suppose there are 2 shelves one shelf has a bottle of size 5 and 4-second shelf has a bottle of size 1 and 2 therefore answer would be 4?

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

      You cannot pick arbitrary bottles from the input. You need to pick k bottles from the beginning of the line. Therefore in example 1: "2 3 5" is ok, but "2 3 5 4" is too much, so the answer is 3. In example 2: "9 1 1 1" is ok, but "9 1 1 1 1" is too much, so the answer is 4.

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

    would anyone post O(nlogn) solution for me please?

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

    we can use set instead of vector(or array) to solve in O(nlogn) as when we are inserting the elements they are inserted in a sorted manner and we continuosly subtract the height of the bottles ....when the result becomes negative we can just print the answer

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

Dear authors,

Please add your solutions with the editorial.

Sometimes it's hard to implement just by reading the explanation.

»
7 months ago, # |
  Vote: I like it +35 Vote: I do not like it

I did problem B in 125 bytes (including an LF) in Ruby. I tried to squeeze author's Python solution and it became 125 bytes as well. So to me seems like a notorious coincidence.

Ruby
Python
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    I can do like this. It's 109 bytes

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

      Ok. Now it's 102 bytes.

      Python
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        By my count your solution is 99 bytes. Do you count 2 characters for newlines?

        Also, you can remove 3 additional bytes, giving 96 bytes:

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

          Oh nice! Guess I was too obsessed with functional programming when doing code golf.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 2   Vote: I like it +45 Vote: I do not like it

          By using exec, we can achieve a significant 3 bytes improvement!

          make it only 93 bytes :)

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

Why this is correct for C — If number of cells where A and B doesn't match in every row and column is even then answer is 'Yes' else it's 'No'?

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

    The tutorial says that if the parity in each row and column remains the same, then the answer is yes. We can see that for every position where A and B doesn't match, we try to change it. If we change an even amount of positions in each row and column, then the parity in each row and column remains the same.

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

Can someone explain the proof of problem C?

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

    tutorial means we always choose to operate (1,1,x,y) , every two element in one column can be change in one turn, because one column has (0 or 2 or 4 or 6 or num in odd),one column can be obviously set to the goal via some operations.imagine we have done every column except the first column,because for the sake of setting other column to the goal, and each row also has(0 or 2 or 4...) difference,the element in the first column also must be changed (0 or 2 or 4...)times, whether there exist difference in the first column doesn't change the result , if there exist difference in the first column, it just changed(2-1,4-1,6-1..)times.

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

Simple DP solution for E: 52420096

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

    lol that is not dp

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

    Can you explain solution? please

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

      dp[i] means what is the answer for a[0],a[1]...,a[i] sticks.

      using this dp we can calculate remaining sticks that we didn't use them

      in any triangle before. for update dp[i] we have dp[i-1] triangle before

      plus with any 2 sticks of a[i] and any stick of j (j < i) that we didn't use

      that in any triangle before we can make a new triangle. after it if remaining sticks

      from a[0] to a[i — 1] over, we can use 3 remaining sticks of a[i] and make a new triangle.

      sorry for bad English .

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

        Это нормально, я тоже не очень хорошо знаю англ. Спасибо за обьяснение.

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

IN problem B I was using the greedy approach. My logic:: I was adding all the numbers from 0 to n till the value of h is greater than the current element if not I check for the smallest number taken before this number with which the current element can be paired.

can anyone tell me where my logic is getting wrong? Link to my solution : https://codeforces.com/contest/1119/submission/52409993

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

I have slightly different approach on problem E. Don't know why it is true but it passed the systests. If the number of ones in the initial array is 0 then the answer is $$$sum of all elements / 3$$$(somehow we can take almost everything). If there are ones then we should compute the minimum possible amount of unused ones. Go from the end to the begginng of the array storing current amount of tiles we can use with the ones. If current $$$a_i$$$ is even the we increase this amount by $$$a_i / 2$$$, otherwise, we take one triangle from three tiles of this type and take the rest increasing amount by $$$(a_i - 3)/2$$$. Then the answer if $$$((sum of all elements) - (minimum number of unused ones)) / 3$$$.

Here's my code : 52409622

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

Here's a 112 byte solution to B: 52424010

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

The editorial for problem H is little unclear.

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

    I try to explain from another aspect. Take the polynomial ring $$$Z[a, b, c, d]$$$. For the individual $$$i$$$, let $$$F_i$$$ be the vector of length $$$2^k$$$ where $$$F_i[0] = a$$$, $$$F_i[b_i] = b$$$, $$$F_i[c_i] = c$$$, $$$F_i[b_i \oplus c_i] = d$$$. We can verify $$$\mathrm{FWT}(F_i)$$$ contains only $$$4$$$ elements $$$(a+b+c+d)$$$, $$$(a+b-c-d)$$$, $$$(a-b+c-d)$$$, $$$(a-b-c+d)$$$ in the specified ring. Suppose that we have $$$x$$$, $$$y$$$, $$$z$$$, $$$w$$$ copies of each elements for $$$\mathrm{FWT}(F_i)[k]$$$. Since FWT is a linear transformation, $$$\mathrm{FWT}(\sum_{i} F_i)[k] = (x+y+z+w) a + (x+y-z-w) b + (x-y+z-w) c + (x-y-z+w) d$$$. Thus, we can obtain the value of $$$x$$$, $$$y$$$, $$$z$$$ and $$$w$$$ from $$$\mathrm{FWT}(\sum_{i} F_i)$$$ directly.

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I think editorial proof for problem G is wrong. It states "This way the first $$$i$$$ groups will have size $$$k_i$$$", but that would require the first group to atack every enemy in different steps, which is impossible if the final answer is less than $$$m$$$.

I submitted a solution (52431440) that greedily chooses the biggest possible size for a group that doesn't waste soldiers in any atack (after incrementing the first enemy group health so that total enemy health is a multiple of $$$n$$$). It passes system tests, but I couldn't come up with a proof of its correctness yet.

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

    Well, I think editorial proof can be fixed this way:

    Instead of considering $$$k_1, k_2, ..., k_{m-1}$$$, we should split them in $$$k_{1,1}, k_{1,2}, ..., k_{1, r_1}$$$ and $$$k_{2,1}, k_{2,2}, ..., k_{2, r_2}$$$ and so on $$$k_{z,1}, k_{z,2}, ..., k_{z, r_z}$$$, where for each $$$i$$$, numbers $$$k_{i,1}, ..., k_{i, r_i}$$$ are remaining health points in consecutive enemy groups that are attacked without using all $$$n$$$ soldiers in between. So, we have $$$k_{i,1} + ... + k_{i, j} < n$$$ for every $$$j <= r_i$$$ and now we can proceed with the same idea of the editorial taking numbers:

    $$$k_{1,1},\quad k_{1,1} + k_{1,2},\ ...\ ,\quad k_{1,1} + ... + k_{1,r_1}$$$
    $$$...$$$
    $$$k_{z,1},\quad k_{z,1} + k_{z,2},\ ...\ ,\quad k_{z,1} + ... + k_{z,r_z}$$$
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    And here is a counterexample for my solution:

    12 2
    15 21
    

    It seems tests weren't strong enough as one of the 7 AC solutions for G fails this test.

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

    So I think G is not a good problem.Lots of wrong lemmas of this problem are 'seems corrected and hard to hack'.We need a convincing lemma and natural proof.

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

    Of course we meant $$$k_i$$$ after sorting, this will be clarified soon.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 4   Vote: I like it +20 Vote: I do not like it

      Maybe I wasn't clear. It has nothing to do with sorting, but with the restrictions imposed in the construction of the solution.

      As stated in the editorial, these ' $$$m-1$$$ assumptions of type "some of our groups have total size $$$k_i$$$" ' should instead be $$$z$$$ assumptions (for each $$$i$$$ between $$$1$$$ and $$$z$$$, considering the same notation of my previous comment) of type:

      "Some of our groups have total size $$$k_{i,1}$$$, some of our groups have total size $$$k_{i,2}$$$, ... , some of our groups have total size $$$k_{i,r_i}$$$, and all these $$$r_i$$$ sets of groups should be pairwise disjoint."

      Then we can take the partial sums of the $$$k_{i,j}$$$ 's as in my previous comment, sort everything and get the distribution like in the editorial.

      Anyway, nice problem, I really enjoyed it! :-)

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

        Ok, you're right that there are cases when more than one group of enemy soldiers are destroyed on the same step; then we should modify the assumptions to yours or just directly replace the subsets of groups with prefixes.

        I intentionally didn't dive into these details in the editorial because they can hide the main idea on one hand and because these cases are easy to cover once you get the main idea on the other hand. Probably I should mention them after the solution, though.

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

For the problem D .I just dont udersand why any integer that appers int row i also appers in row i+1.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why when i choose Solution(Rus) it shows Solution(Eng)

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Still can't understand the C solution/proof !

and what's the meaning of the "parity of the matrix" ?

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

    it means no. of 1's in matrix is even or odd like in this 01110 it is odd parity because number of 1's are 3.

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

Why can't the editorial be made easier to understand? Look at the number of people solving problems F,G and H, its hardly 20 people.

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

I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct?

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

    You have to install the first k bottles, so you have to install the first bottle (the one with height 9) and, if you install it, you cannot install more than 4 bottles.

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

I think the explianation of the problem D has someting wrong. Notice that " any integer that appears in row i also appears in row i+1." has ambiguity,because "any integer" euqal to "all integer".Maybe it can be changed into "some integer".

Do you think that it is right????????????????????

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

lovely contest <3

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

From problem D code, I am unable to understand the purpose of "t" array and how is it helping in calculate the result. Can anyone please help me in understanding the code or suggest a simpler solution?

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

    If you understand everything upto the use of the array t in the tutorial's code, then this submission may help you.

    What I did is that I kept the highest possible unique contribution of the rows (except the last row, it can contribute upto the entire length), sorted them (same as the tutorial). Then, for a specific query of length = r-l+1 (say), all I needed was the total contribution. And that is

    (the summation of all the contributions that were $$$\leq$$$ length) + (rest of the elements in the "contributions" array and the last additional row will only contribute length amount).

    Binary search on the contributions array (basically std::upper) and cumulative sum upto that position will give you the first term. I hope this helps. And I am also trying to figure out what the array t does in the tutorial. :(

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

      Your solution was much easier to understand and was very helpful. Thanks.

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

      i am unable to understand how did u found out the contribution of each elelment in range . Please help me understand. cout << summ[ind]+(sz-1-ind)*cov+cov summ[ind]= (max diffrence of s[ind]-s[0] among all rows) +(sz-1-ind)*cov . WHY?? +cov. WHY add cov at last??

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

        By finding the differences of the elements (you need to sort them first) given in the problem.

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

          i edited please look

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

            for the last element which can contribute the entire length no matter what. ( cov means length in my code, just saying in case it confused you.)

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

quick question about C i just wrote a python code for make A to B but it doesn't work like i thought.

def op(grid, sy, sx, ey, ex):
    grid[sy][sx] = 1-grid[sy][sx]
    grid[ey][ex] = 1-grid[ey][ex]
    grid[sy][ex] = 1-grid[sy][ex]
    grid[ey][sx] = 1-grid[ey][sx]


n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
B = [list(map(int, input().split())) for _ in range(n)]
while A!=B:
    for y in range(1, n):
        for x in range(1, m):
            if A[0][0] != B[0][0] or A[y][x] != B[y][x] or A[y][0] != B[y][0] or B[0][x] != A[0][x]:
                op(A, 0, 0, y, x)
»
7 months ago, # |
  Vote: I like it +78 Vote: I do not like it

Here's a simple (?) general approach of solving H for $$$m$$$-tuples (instead of triples) in $$$O(n2^m + (m + k)2^{m + k})$$$. As explained above it suffices to solve the following problem: consider a set $$$t_1, \ldots, t_n$$$ of $$$m$$$-tuples of $$$k$$$-bit numbers. For a $$$k$$$-bit number $$$x$$$, say that the mask $$$y$$$ induced by $$$x$$$ for a tuple $$$t_i$$$ consists of all indices $$$j \in {0, \ldots, m - 1}$$$ such that $$$x$$$ and $$$t_{i, j}$$$ have an odd number of common bits. For each $$$k$$$-bit number $$$x$$$ and each mask $$$y$$$ of size $$$m$$$, we have to find how many tuples have mask $$$y$$$ induced by $$$x$$$.

Recall that multiplication of monomials in $$$\mathbb{Z}[x_0, \ldots, x_{k - 1}]$$$ with relations $$$x_i^2 = 1$$$ behaves the same way as xoring $$$k$$$-bit numbers. Further, WHT of an array $$$A = (a_0, \ldots, a_{2^k - 1})$$$ is the same as $$$k$$$-dimensional Fourier-transform of $$$P_A(x_0, \ldots, x_{k - 1}) = \sum_{i = 0}^{2^k - 1}a_i X(i)$$$, where $$$X(i)$$$ is the product of $$$x_j$$$ such that $$$j$$$-th bit is set in $$$i$$$. In simpler terms, we substitute all combinations $$$1$$$'s and $$$-1$$$'s into $$$P_A(\ldots)$$$ to obtain $$$2^k$$$ numbers; for the $$$j$$$-th number, the value of $$$x_i$$$ is $$$1$$$ if the $$$i$$$-th bit in $$$j$$$ is $$$0$$$, and $$$-1$$$ otherwise. Finally, recall that WHT is linear, and WHT of a product of two functions is the element-wise product of their WHT's (since WHT is basically FFT).

Consider a set of $$$k + m$$$ variables $$$x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}$$$. For a tuple $$$t_i = (t_{i, 0}, \ldots, t_{i, m - 1})$$$, consider a polynomial $$$Q_t(x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}) = \prod_{j = 0}^{m - 1}(1 + X(t_{i, j})y_j)$$$. What are the values of WHT of $$$Q_t$$$? Let's say that values of $$$x_i$$$ correspond to $$$k$$$ bits of a number $$$x$$$, and $$$y_j$$$ determine whether each index $$$j$$$ is included into the mask $$$y$$$. Then, one can observe that $$$1 + X(t_{i, j})y_j$$$ is equal to $$$2$$$ when $$$y_j$$$ matches the parity of the number of common bits of $$$x$$$ and $$$t_{i, j}$$$ (that is, $$$j$$$ is in the mask induced by $$$x$$$). Consequently, $$$Q(t)$$$ is equal to $$$2^m$$$ when $$$y$$$ is induced by $$$x$$$, and $$$0$$$ otherwise. By linearity, the WHT of $$$\sum_{i = 1}^n Q_{t_i}$$$ contains the exact values we wanted to obtain (after division by $$$2^m$$$).

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    is this algorithmic round or International maths olympiad !

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

      If there weren't problems as hard as these then people like Endagorion and tourist would finish all the problems in under 30 minutes, and where's the fun in that ?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        first increase ur rating then give knowledge to otheres .

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

          My rating is low because I spend more time watching other people code than actually learning how to code.

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

            then stop looking other's code , try on ur own ,

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

              Thanks, all my problems fixed.

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

                good , now u should reach the level of petr mitrichev .

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

would you translate following line into more easier english please? i trying to understand this line for like 30hours... but i cannot understand... 'the line starts from anoter perspective...' Now come the queries. Given a fixed value of w, we need to quickly compute (∑n=1i=1min{di,w})+w. From another perspective, this equals the sum of value times the number of occurrences, namely (∑wk=0k⋅count(k))+(∑∞k=w+1w⋅count(k))+w, where count(k) denotes the number of times that integer k occurs in d1…n−1.

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

why did the contest problem's rating not show in the problemset

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

Problem H. How do I prove $$$x-y-z+w=p$$$?

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

    I got it. Just needed to verify that every element after WHT looks like that. Basically, to prove that one needs to know that WHT is matrix-vector multiplication with matrix element $$$(i, j)$$$ being equal to $$$(-1)^{ij}$$$. After that, it is straightforward to show that $$$d$$$ is positive when $$$b, c$$$ have equal sign and negative otherwise ($$$(-1)^{ij}$$$ and $$$(-1)^{ik}$$$ have different signs if $$$j, k$$$ have different parity and then $$$(-1)^{i(j \oplus k)}$$$ is negative).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to apply FFT in 1119E - Pavel and Triangles ? I saw FFT tag in this problem