Life Is All About Balance

sayeef006 Criterion 2022 Round 17

We can check if the array is already balanced by storing 4 arrays, prefix minimum, prefix maximum, suffix minimum and suffix maximum. We will go to all indices i(1i<N)i(1 \leq i < N) and check if F(B)F(B) equals F(C)F(C) using our pre-computed arrays. If the array is already Balanced, the answer is 0.

Otherwise, we can always do 1 operation to make the array Balanced. Let us pick i = 2i~=~2, so we get B={A1,A2}B = \{A_1, A_2\} and C={A3,A4,..,AN}C = \{A_3, A_4,..,A_N\}. We can select j=2j = 2 and set the value of A2A_2 to A1+F(C)A_1+F(C) and then F(B)F(B) will equal F(C)F(C).

Author’s solution: https://ideone.com/UqT1Cw

Statistics

68% Solution Ratio
serotoninEarliest, 3M ago
Sumaya_1703110Fastest, 0.0s
serotoninLightest, 4.2 MB
serotoninShortest, 632B
Toph uses cookies. By continuing you agree to our Cookie Policy.