AkiLotus's blog

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

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

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it +3 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

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

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

»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

W contest.

»
2 hours ago, # |
Rev. 3   Vote: I like it -15 Vote: I do not like it

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

»
2 hours ago, # |
  Vote: I like it 0 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

»
2 hours 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

»
2 hours 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.

»
119 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
111 minutes ago, # |
  Vote: I like it +1 Vote: I do not like it

Why was n forced odd in E?

»
101 minute(s) 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

  • »
    »
    95 minutes ago, # ^ |
      Vote: I like it +1 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.

    • »
      »
      »
      90 minutes 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.

      • »
        »
        »
        »
        50 minutes ago, # ^ |
          Vote: I like it +1 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'}$$$?

        • »
          »
          »
          »
          »
          32 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          okay yeah makes sense thanks

»
48 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally Pupil