AkiLotus's blog

By AkiLotus, history, 4 weeks 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
  • +84
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +6 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

  • »
    »
    3 weeks 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

»
3 weeks 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 ..

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

W contest.

»
3 weeks 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.

  • »
    »
    3 weeks 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])
    
»
3 weeks 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

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

    what do you mean by continuous?

  • »
    »
    3 weeks 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.

»
3 weeks 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

»
3 weeks 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://mirror.codeforces.com/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://mirror.codeforces.com/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 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    wice city

  • »
    »
    3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Why was n forced odd in E?

  • »
    »
    3 weeks 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

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

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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'}$$$?

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

          okay yeah makes sense thanks

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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

Finally Pupil

»
3 weeks 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

»
3 weeks 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.

»
3 weeks 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$$$).

»
3 weeks 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

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

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

so great tutorial with lots of hints!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks 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...

»
3 weeks 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 ;

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

It was a really great contest, thank you

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

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

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

  • »
    »
    3 weeks 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 weeks 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 weeks 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]$$$.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks 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 weeks 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.

»
3 weeks 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!

»
2 weeks ago, # |
Rev. 5   Vote: I like it +5 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

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

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]

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

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

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

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

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

    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.