vovuh's blog

By vovuh, history, 17 months ago, In English,

1102A - Integer Sequence Dividing

Tutorial
Solution 1
Solution 2

1102B - Array K-Coloring

Tutorial
Solution

1102C - Doors Breaking and Repairing

Tutorial
Solution

1102D - Balanced Ternary String

Tutorial
Solution (Vovuh)
Solution (PikMike)

1102E - Monotonic Renumeration

Tutorial
Solution

1102F - Elongated Matrix

Tutorial
Solution 1
Solution 2
 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey PikMike , can you explain your solution for D ? I was thinking on similar lines but messed it up in placing 1's.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I thought of it the following way. You start with either a single amount greater than or a single amount less than (the both zeros case is trivial).

    Case 1: Replace some of characters x with other characters. I just assumed that if the character to replace with is smaller than x then you should replace some prefix of x occurrences and if it's greater than x then suffix of occurrences. It should be easy to prove. Then the order of applying functions matters only if x = 0 or x = 2 (determining the order is trivial).

    Case 2: Replace some character with character x. Following the same ideas you also determine when prefix/suffix is the best and the order of application.

    The code itself is really self-explanatory. I believe that the proof is the hardest part of it.

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

Hey Vovuh , can you explain about E? What are the possible answers for 4 1 3 3 7

There should be only three 3 closed subsegments. So answer = 2^2 = 4 But possible arrays for b is - 0 0 0 0 - 0 0 0 1 - 0 1 1 1 I can'