KAN's blog

Codeforces Global Round 2 Editorial
By KAN, 6 years 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

Comments Comments (80)
| Write comment?
»
6 years ago, # |
  Vote: I like it +88 Vote: I do not like it

Problem F: AC 4

Problem G: AC 7

Problem H: AC 5

...

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

Thanks for the fast editorial!

→ Reply
»
6 years 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?

→ Reply
»
6 years 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!!!

→ Reply
  • »
    »
    6 years 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

    → Reply
    • »
      »
      »
      6 years 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.

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

        Finally i find it ，thank you

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years 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?)

    → Reply
    • »
      »
      »
      6 years 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)$$$.

      → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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)

    → Reply
  • »
    »
    6 years 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?

    → Reply
    • »
      »
      »
      6 years 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.

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

        Then why we are sorting in decreasing order...as written in editorial... sorting leads to derrangement of elements..from it's initial position..... please answer because i have literally spend 1 hour on thinking this only..

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

          The problem statement says at the end that you need to look for the largest k: "Alyona is interested in the largest integer k".

          The editorial says "just try all possible k".

          Therefore you need to consider the following cases separately (independent of each other):

          1. k=1 — you need to check if the first bottle fits

          2. k=2 — you need to check if the first 2 bottles fit

          3. k=3 — you need to check if the first 3 bottles fit

          etc.

          When you are checking for example k=3, take the first 3 bottles (from the input array that was not sorted yet), sort them, check if they fit in the fridge.

          When you are checking k=7 forget that you have sorted the 3 bottles for k=3 — start again from scratch: take the first 7 bottles (from the input array that was not sorted yet), sort them and check if they fit in the fridge.

          Does it make sense now?

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

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

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years 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
→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    I can do like this. It's 109 bytes

    Python
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Ok. Now it's 102 bytes.

      Python
      → Reply
      • »
        »
        »
        »
        6 years 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
        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
        • »
          »
          »
          »
          »
          6 years 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
          → Reply
»
6 years 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'?

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the proof of problem C?

→ Reply
  • »
    »
    6 years 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.

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

Simple DP solution for E: 52420096

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

    lol that is not dp

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

    Can you explain solution? please

    → Reply
    • »
      »
      »
      6 years 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 .

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

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

        → Reply
»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's a 112 byte solution to B: 52424010

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

The editorial for problem H is little unclear.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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}$$$
    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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! :-)

      → Reply
      • »
        »
        »
        »
        6 years 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.

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

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

→ Reply
»
6 years 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" ?

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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. :(

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

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

      → Reply
    • »
      »
      »
      6 years 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??

      → Reply
      • »
        »
        »
        »
        6 years 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.

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

          i edited please look

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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.)

            → Reply
»
6 years 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)
→ Reply
»
6 years 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$$$).

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

    is this algorithmic round or International maths olympiad !

    → Reply
    • »
      »
      »
      6 years 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 ?

      → Reply
»
6 years 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.

→ Reply
»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years 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).

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

How to apply FFT in 1119E - Павел и треугольники ? I saw FFT tag in this problem

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

    Did you get the answer to this question? I also don't know how to do it :(

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

Another approach for C: Note that the problem can be restricted to only needing to perform the operation on a $$$2 \times 2$$$ submatrix, as any instance of the operation on bigger submatrices can be reduced to some number of the $$$2 \times 2$$$ operations. Proof: if we denote performing the operation on a $$$2 \times 2$$$ submatrix by the coordinates of its top left cell, performing all operations $$$(i, j)$$$ where $$$i \in [x, x+n-1)$$$ and $$$j \in [y, y+m-1)$$$ is equivalent to performing a single operation on submatrix of size $$$n \times m$$$ with top-left corner $$$(x, y)$$$.

With the problem thus reduced, an easy greedy solution emerges: Compare every position in the two grids in reading order. When encountering any position where $$$A$$$ and $$$B$$$ differ, perform the operation on $$$A$$$ with top-left corner at that position. If that's not possible because the position is on the last column or row, the answer is No.

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

In problem E

Let's take 3 numbers i, j, k such that i < j < k.

Then why taking (i, k, k) and (j, j, j) is giving WA but taking (i, j, j) and (j, k, k) don't? 300iq

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I came on a pilgrimage to the Holy Land. Please don't let IOI have problems with output only.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I came on a pilgrimage to the Holy Land. Please let me have a girlfriend who does problem solving.

→ Reply
»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Hmmm, problem F seems familiar ...

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

Is it just me, or the E problem is too easy to be E. I feel its more like Div2 B.

→ Reply