_skywalker_'s blog

By _skywalker_, history, 4 years ago, In English

Can someone explain the solution in better way. I have read the tutorial but don't feel like getting it completely. Thank you. 1353E - K-periodic Garland

Tags #dp
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I did it in a slightly different way.

let dp[i] be the minimum number of ways substring s[1:i] can be k-periodic with the ith bulb switched on. Now while evaluating dp[i] we can face 2 situations.

  1. If (i-k)th bulb is off the we can say that in the substring s[1:i] the ith bulb is the only bulb which is on. Then:
dp[i] = (
        (number of ways to switch off all the bulbs from 1 to i-1) + 
        (1 if ith bulb is originally off)
        )

2 If (i-k)th bulb is on, then

dp[i] = (
        dp[i-k] + 
        (number of moves required to switch off all the bulbs between i and i-k) + 
        (1 if the ith bulb is originally off)
        )

at each i I also considered the case that it can be the last bulb which is on and updated the ans accordingly. ans = min(ans, dp[i] + (number of ways to switch off all the bulbs from i + 1 to n))

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

Step 1: Count the number of ones in the given string . Let it be "Ones" Step 2: Split the whole array into k different arrays, such that element i of the original array is now part of (i%k)th array . Now , we have to choose the best of these k arrays . Solving each array We need to find the starting and ending position in this array such that, the difference of ones and zeros is maximum in this range i.e. we need to set minimum number of 0s to 1s. Now, all we need is, number of 0s in this range + number of 1s outside this range + number of 1s in rest of the arrays (it can be counted with the help of "Ones", which we stored in step one. Here is the Implementation