AkiLotus's blog

By AkiLotus, history, 9 days ago, In English
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
  • Vote: I like it
  • +80
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    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

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

      That's quite brilliant, though it feels less intuitive to me

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

        put an explanation below big dog

»
4 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 days ago, # |
  Vote: I like it +6 Vote: I do not like it

W contest.

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

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

  • »
    »
    4 days ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    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])
    
»
4 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

    what do you mean by continuous?

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

    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.

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

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

»
4 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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.me/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.me/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.

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

    wice city

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and all coefficients of W[0] are 1. So we can sum all rows of eqn1 to find W[0].

    Could you elaborate more on this line? Thank you.

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

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

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

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

  • »
    »
    33 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Why was n forced odd in E?

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

    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

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

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

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

    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.

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

      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.

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

        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'}$$$?

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

          okay yeah makes sense thanks

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

Finally Pupil

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

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

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

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

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

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$$$).

»
4 days ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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

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

so great tutorial with lots of hints!

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 days ago, # |
  Vote: I like it +15 Vote: I do not like it

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...

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

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

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

It was a really great contest, thank you

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

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

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

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

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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]$$$.

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

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.

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

    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.

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

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

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

    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

»
4 days ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

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

    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

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

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

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

    There is a contradiction in your graph, as the parent of m+3 is m+2, while the parent of m+4 is 3. Clearly, m+2 > 3, while m+3 < m+4.

»
44 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
4 hours ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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