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

Автор AkiLotus, история, 3 недели назад, По-английски
README: Notice about solutions

2032A - Circuit

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1
Hint #2A
Hint #2B
Tutorial
Solution (C++)
Solution (Python 3)
Feedback

2032B - Medians

Author: Kuroni
Development: AkiLotus
Hinter: Kuroni
Editorialist: AkiLotus, Kuroni

Hint #1
Hint #2A
Hint #2B
Tutorial
Solution (C++)
Solution (Python 3)
Feedback

2032C - Trinity

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1
Hint #2A
Hint #2B
Hint #2C
Hint #3
Hint #4
Hint #5
Tutorial
Solution (C++)
Solution (Python 3)
Feedback

2032D - Genokraken

Author: AkiLotus
Development: AkiLotus
Hinter: AkiLotus
Editorialist: AkiLotus, Kuroni

Hint #1
Hint #2
Hint #3A
Hint #3B
Hint #4
Hint #5
Tutorial
Solution (C++)
Solution (Python 3)
Feedback

2032E - Balanced

Author: thanhchauns2
Development: thanhchauns2, Sagita_Phoenix
Hinter: AkiLotus
Editorialist: Kuroni, AkiLotus

Hint #1
Hint #2
Hint #3
Hint #4
Hint #5
Hint #6
Hint #7
Hint #8
Tutorial
Solution (C++)
Solution (Python 3)
Alternative tutorial (Kuroni, rephrased by AkiLotus)
Feedback

2032F - Peanuts

Author: MofK
Development: MofK, AkiLotus
Hinter: AkiLotus
Editorialist: MofK, AkiLotus

Hint #1
Hint #2
Hint #3
Hint #4
Tutorial
Solution (C++)
Solution (Python 3)
Feedback
Разбор задач Codeforces Round 983 (Div. 2)
  • Проголосовать: нравится
  • +84
  • Проголосовать: не нравится

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

Problem D can be solved in $$$\mathcal{O}(n)$$$ with a queue quite easily as well, which is implemented directly into the stl so it's easier. The idea stays the same, just replace the double linked list with a queue

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

    I believe there is an even lighter ( implementation wise ) sol to D. I keep track of the next parent to be considered ( stored in variable bp initiated at N-2 ) and the current node ind ( initiated at N-1) who's parent we're looking for, we (decrement ind iff bp is its parent) and decrement bp at each iteration till its 0

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

Tutorial of D definitely proves that the problem setter group had Asian influence ..

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

W contest.

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

For D, there also exists n — 3 query soln instead of 2 * n — 6 query solution.

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

    Here is the solution.

    def query(a, b):
        print(f'? {a} {b}')
        f = bool(int(input()))
        return f
    
    t = int(input())
    for _ in range(t):
        n = int(input())
        parent = [0] * n
        minParent = n - 2
        # for each value of minParent, from n-2 to 2, query will be called exactly once
        # => n-2 - 2 + 1 = n-3 times
        
        for x in range(n - 1, 1, -1):
            while minParent > 1:
                if not query(x, minParent):
                    break
                minParent -= 1
            parent[x-1] = minParent
            minParent -= 1
            if minParent < 1:
                break
        print("!", *parent[:-1])
    
»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

can someone pls prove the fact that the smallest two elements will always have to be continuous in the original array as well ? I am refering to problem C here

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

    what do you mean by continuous?

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

    it is evident that when the array is sorted, let's say a_1 <= a_2, ...., <= a_n, then of course, when you choose a_1 and a_2, and let's just say there exists a number a_k so that a_1, a_2, a_k are the sides of a non degen triangle, then a_1, a_3, a_k is still acceptable (with 3 < k) because the triangle equality still holds. In other words, the way we choose 2 consecutive elements has set a lower bound to all the answers with bigger number.

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

another solution to E, although after reading the alternate solution, I think that is better

we can apply operation [-1,-1,1,1] to index i (e.g. a[i]--,a[i+1]--,a[i+2]++,a[i+3]++) by applying operation [-1,-2,-1] to i, and [1,2,1] to i+1

now, we can apply operation [-1,0,1] to index i by applying operation [-1,-1,1,1] to indexes i,i+2,...,until i-1

we can apply operation [-1,1] to index i by applying operation [-1,0,1] to indexes i,i+2,... until i-1

now applying operation [-1,1] keeps the sum constant, so we just need apply arbitrary operations [1,2,1] until (sum of a)%n==0 which is always possible

289298093

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

Alternate solutions for E

Write the equations A[i+1] + V[i] + 2 * V[i+1] + V[i+2] = T. [eqn1] Taking differences, (A[i+2] — A[i+1]) + (V[i+3] + V[i+2]) — (V[i+1] + V[i]) = 0 [eqn2]

Solution 1. https://codeforces.net/contest/2032/submission/289289897 Write W[i] = V[i] + V[i+1]. eqn2 is W[i+2] = W[i] + A[i+1] — A[i+2], so we can fill all W[i]'s in terms of W[0], and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0]. Now we want to solve for V in terms of W, which is easy by taking alternating sums of V[i+1] = W[i] — V[i].

Solution 2. https://codeforces.net/contest/2032/submission/289297804 Notice a solution for T=0 implies a solution for T=4k (V[i] += k). So, guarantee a solution for T=0 by first shifting A, then we can assume T=0. Now V[0] and V[1] determine V. By chasing eqn1, we will get 2 equations and 2 unknowns.

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

For C, I sorted then binary search on the minimum number of elements to reassign. 289211192

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

    I thought about binary search during the race, but I didn't finish it

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

    Could you please explain what you did inside the binary search? I used binary search too but i only kept comparing the sum of two values with the last element, which got WA for the test case "1 1 1 2". I understood that my approach was wrong but confused about the correct one. TIA.

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

Why was n forced odd in E?

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

    if n is even operation doesnt change the parity of the difference between sum of even and odd position elements. so if the parity is odd there is no solution

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

      Yes, then you would output -1 according to the statement

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

        It's actually possible.

        For example n=6:

        you can do the operation +1 to any element

        0 0 0 0 0 0 4 2 0 0 0 2 4 3 2 1 0 2 4 3 3 2 1 2 4 3 3 3 3 3

        n=4 answer is -1 if a[0] % 2 != a[2] % 2 or a[1] % 2 != a[3] % 2

        n=2 answer is -1 if a[0] != a[1]

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

in problem C whats the proof that ax and ay should be consecutive elements of the array in sorted order ? suppose we have x as operations needed using consecutive a[i] and a[i+1] lets say max we can reach is j , now if we let ax to be a[i] and ay to be a[i+2] then j can be much more than the original isnt if we have a[i]+a[i+2]>a[i]+a[i+1]? whats the proof that checking with consecutive elements does the job? AkiLotus

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

    Without that condition, you can't ensure that all triplets are valid.

    One counterexample: $$$[3, 4, 5, 7]$$$. If you used $$$a_i$$$ and $$$a_{i+2}$$$ for pivoting, you'd conclude that $$$0$$$ operations are required, which is not true, as $$$(3, 4, 7)$$$ are invalid.

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

      For your example i will consider the array two minimums be 3,5 now j will reach 7 so we have 3,5,7 max so total ops needed is 4-3=1 because i will change the one (i have not taken) like 4 between 3 and 5 to ay that is 5, so that validity is maintained.

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

        I see, you wanna pick $$$a_i$$$ and the range $$$[a_{i+2}, a_j]$$$. Then... why don't you simply pivot $$$a_{i+1}$$$ and $$$a_{i+2}$$$ for a clearly not-lower upper bound $$$a_{j'}$$$?

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

          okay yeah makes sense thanks

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

          i try ie for 3,3,4,5,7,7 and it should be ans=1,but the standard ans is 2 .[3,3,5,7,7] is valid for the ans,isn't?

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

            oh,sorry,i get the wrong of my solution,it is clear.

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

Finally Pupil

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

D was very fun, and F seems very interesting as well, thank you for the contest and +100 delta :D

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

Thank you for such detailed Editorial. I wish, other authors could also write editorials in such a way.

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

You can solve problem E by constructing matrix, as this comment pointed out. Its also not necessary to use FFT to solve this. The matrix inverse $$$M^{-1}$$$ is easy to observe, and each element of the inner product $$$(M^{-1}a)_i = -(M^{-1}a)_{i-1} + b_i$$$ where $$$b_i$$$ is a term easy to maintain ($$$b_i = -b_{i-1} + 4a_i$$$).

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

my sol for E:

+[1 2 1] can be converted to +[1 1] by doing these operations:

[start = 1] 1 0 1 0 1 0 ... 1 0 1 0 1 0

(the start is the first index that gets affected by the +[1 1])

this can be performed with a prefix sum on odd/even indices

+[1 1] can be converted to +1 by doing these +[1 1] operations:

[start = 1] 0 1 0 1 0 1 ... 0 1 0 1

solving the problem with +1 is free

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

    Could you explain it a bit more ?

    EDIT: Got the idea, pretty cool. Thanks for sharing

    Main idea is if we can go from +121 to +11 to +1, then we can do so reversely also.

    For +1, we know that number of operations would be Max — A[i], now only thing remains is to find out number of operations if only +11 was allowed. We already know number of operations for +1, now for +11 we do the conversion of +11 to +1.

    Now if we have only +121 type of operations, so every +11 should have come from +121

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

so great tutorial with lots of hints!

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

Alternate solution to D by observation alone with ZERO DATA STRUCTURES knowledge required:

We find parents from max to min node, noting that each parent we look for must be less than the minParent we have assigned thus far. i.e if a previous(greater) node had the parent 4, no new nodes can have the parent 4 or greater, since this violates the tree. We can say is that we will never ask for more than n times, because the minParent decreases by 1 for every query(note that two nodes cannot have the same parent besides zero). So maybe we ask in the worst case for n-2 to 1, which is just n-2. 2n-6<n-2 becomes n<4(which is given), so this solution always works. Hope someone like it!

Now onto understanding the actual editiorial...

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

I feel like this should be the way every editorial should be written with good hints and simple language tutorial . Nice ;

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

It was a really great contest, thank you

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

Can someone hack this Problem C solution? https://codeforces.net/contest/2032/submission/289342682

I'm quite positive this is wrong but can't find a counterexample. Thank you!

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

    I think your solution is correct, because when we meet $$$a[l]+a[r]\le a[i_0]$$$ we must replace either $$$a[l]$$$ with something greater or $$$a[i_0]$$$ with something smaller. But if we again meet $$$a[l]+a[r]\le a[i_1]$$$ where $$$l=i_0$$$ we again must replace either $$$a[l]$$$ with something greater or $$$a[i_1]$$$ with something smaller. So, we can not replace only $$$a[i_0]$$$ to save one operation.

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

      But what about the case 1 1 1 2? Here, we can't increase $$$a[l]$$$ to 2 because 1 2 1 2 wont make a triangle. Instead, we need to decrease $$$a[i_0]$$$

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

        So, what is wrong? You need EITHER increase $$$a[l]$$$ OR decrease $$$a[i_0]$$$. You would need to increase $$$a[l]$$$ only if you further would need to increase $$$a[i_0]$$$.

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

For C, I just want to clarify some terminologies. When is it called sliding window instead of two pointers (or vice versa)? For me C sounded like it's a sliding window problem and not two pointers.

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

    This is just my opinion, for a disclaimer.

    I'll usually call something "sliding window" when it involves a fixed interval/range/subarray, and the updates of the window involves removing the leftmost and adding the rightmost per step.

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

for c i guess for 1st test case value is 2 for 7 1 2 3 4 5 6 7 for this test case 2 is minimum since array can become 7 7 3 4 5 6 7

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

    7 7 3 4 5 6 7 is not valid since 3+4=7. You would have to replace the 3 with something else as well

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

Cool solution to E:

Let $$$b$$$ be an array of operations such that you "add 1" to the first position.

Let $$$c$$$ be the array of how many operations each position needs (i.e. $$$c_i = max(a) - a_i$$$).

The solution is the coefficients of $$$(\sum_{n=0}^{n-1} b_i x^i) (\sum_{n=0}^{n-1} c_i x^i)$$$, you can use FFT or any similar algorithm.

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

    Details of the solution:

    WLOG, assume the "Add 1" process is applying to the middle element $$$(i.e. a_{\frac{n+1}{2}})$$$ for easier calculation

    Observe that

    For $$$n = 5$$$ the array $$$b$$$ will be $$$[1,0,2,0,1]$$$

    For $$$n = 7$$$ the array $$$b$$$ will be $$$[1,2,0,3,0,2,1]$$$

    For $$$n = 9$$$ the array $$$b$$$ will be $$$[2,1,3,0,4,0,3,1,2]$$$

    For $$$n = 11$$$ the array $$$b$$$ will be $$$[2,3,1,4,0,5,0,4,1,3,2]$$$

    Hence we can guess that for any n. This code can geneate a array that add 1 to the middle element. (I will skip the proof here)

      v[n/2] = n/2;
    
      for (int i = n/2 - 2; i >= 0; i -= 2) {
        v[i] = v[i+2] - 1;
      }
    
      for (int i = n/2 + 2; i < n; i += 2) {
        v[i] = v[i-2] - 1;
      }
    
      for (int i = n/2 - 3; i >= 0; i -= 2) {
        v[i] = v[i+2] + 1;
      }
    
      for (int i = n/2 + 3; i < n; i += 2) {
        v[i] = v[i-2] + 1;
      }
    
    

    Then by rotating the array, we can get the desired $$$b$$$ that add 1 to the first element

    e.g. $$$[2,0,1,1,0]$$$ for n = 5

    My submission in contest : 289280927

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

Problem D. Can someone help me explain why the vertices is indexed in accordance to a BFS?

0
1   2   3 ... m
|   |   |     |
m+1 m+2 m+4   m+5
    |
    m+3

bfs order is (0, 1, 2, ..., m, m+1, m+2, m+4, m+5, m+3), but i dont see controdictions to px <= py iff x <= y

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

AkiLotus hi! for problem c, why's the answer for the tc "1 1 2" one? shouldn't the answer be zero (because no pairwise distinct triplets exist?)

thank you for writing this round, it was fun!

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

I know I'm late, but i have a nice solution for E.

Look at the differences between adjacent elements. If you sum them you get 0 because the array is circular. You can notice that an operation adds [1, 1, -1, -1] to a subarray of the differences. The goal is to make this array 0, to make the original array constant.
After using this operation many times on alternating positions this happens (the parentheses are the center of the operation)

    [0, 0, 1, (1), -1, -1, 0]
    [-1, 0, 1, 1, 0, (0), -1]
    [(0), -1, 0, 1, 0,  0, 0]

With these operations it's possible to move an unit from a point to another at distance -2. Since the length of the array is odd, then it's possible to move an unit to any other cell of the differences array by just repeating this process

290156342

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

can anyone tell me the problem in B no problem in my submission?how could be m is evne when i wrote -1![submission:290879860]

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

    In that test, checker read your $$$m$$$ as $$$2$$$ instead of $$$-1$$$ at the third test case. Try to figure out why.

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

The editorial for C is misleading.

"This means that for every $$$i$$$, we need to find the smallest $$$j>i$$$ that satisfies the condition"

Instead, for every $$$i$$$, we should be finding the greatest $$$j>i$$$ that satisfies the condition, because we are ultimately calculating the minimal value of $$$n-(j-i+1)$$$.

  • »
    »
    80 минут назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Heck, it was indeed an error, thank you for pointing out. The fix should be live after a few minutes (I just built the package again).

    UPD (7min after): Yep, the tutorial was automatically updated.