CPMagical CP Library

Problem solution · Python

CCC 2011 S5 - Switch

CCC 2011 S5 - Switch: a Python solution using sliding window or two pointers. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Sliding window or two pointers
Source
CCCSolutions
Length
112 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Sliding window or two pointers

For CCC 2011 S5 - Switch, the implementation maintains a moving interval and updates only the information that enters or leaves the window.

  1. Choose the invariant that makes a window valid or useful.
  2. Advance the right boundary and add the new element.
  3. Move the left boundary only as needed while maintaining the invariant and updating the answer.

Code notes

  • 112 lines of Python from the credited upstream file ccc11s5.py.
  • The implementation visibly relies on sequence storage.
  • No explicit loop blocks detected.

Complexity

Confirm that neither pointer moves backwards; if so, the scan is usually linear apart from the window’s data-structure operations.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2011 S5 - Switch · PythonPython
Use this to learn the idea, then write your own version.
#  CCC 2011 S5: Switch#  solution by Sumudu Fernando##  We use a dynamic programming approach; this solution is O(N).##  First, we create a set of groups of on lights.##  Considering two such groups, if their span (distance from the left of the#  leftmost group to the right of the rightmost one) is 4 or 5, we can always#  turn off all groups in that span by filling in the blanks.##  Similarly, for spans of 6 and 7, it is possible to clear the span as a block#  as long the middle lights (3rd & 4th for span 6 (eg: 101101),#  or 4th for span 7 eg. 1101001) are off.##  So, if we have such a "clearable" span of length "len"  with "numOnes" lights#  on, it will take "len - numOnes" switches (t) to clear it as a block. #  If the span is less than 4, we may simply take "len" as 4 (which means#  we'll turn on lights outside the span).  ##  in simple terms, determine the number of lights to switch on, t, for a#  group (or groups working right from a starting group) and then the answer is#  the minimum of what we have already for this group (which starts very large)#  and t + the answer we had for the next group to the right.##  suppose we are looking at group 3 (i=3)#  we will look at the groups 3, then 3 and 4, then 3, 4 and 5 (stopping when that#                                  collection gets be be greater than 7 long)#  for group 3, we consider (t + answer for group 4)#  for group 3 and 4, we consider (t + the answer for group 5)#  etc...  taking  the minimum answer. ###  Here is a trace of an example with lights:  111011101000111##  group = [[0, 3], [4, 7], [8, 9], [12, 15]]##  processing the first (rightmost) group (111)#     i= 3  j= 3  numOnes= 3   t = 1  minimumSwitches: [0, 0, 0, 1, 0]##  processing the next group  (1000111)#     i= 2  j= 2  numOnes= 1   t = 3  minimumSwitches: [0, 0, 4, 1, 0]#     i= 2  j= 3  numOnes= 4   t = 3  minimumSwitches: [0, 0, 3, 1, 0]##  next   (11101000111)#     i= 1  j= 1  numOnes= 3   t = 1  minimumSwitches: [0, 4, 3, 1, 0]#       we got the 4 because t = 1 (there are 3 lights on in the first group)#                                  + 3 from the later blocks, ms[2]=3#                   and took the min of INF and 4#     i= 1  j= 2  numOnes= 4   t = 1  minimumSwitches: [0, 2, 3, 1, 0]#       we got the 2 because t = 1 (we are now looking at 11101)#                                  + 1 from the later blocks, ms[3]=1#                   and took the min of 4 and 2##  last  (111011101000111)#     i= 0  j= 0  numOnes= 3   t = 1  minimumSwitches: [3, 2, 3, 1, 0]#     i= 0  j= 1  numOnes= 6   t = 1  minimumSwitches: [3, 2, 3, 1, 0]  INF = 1000000 file = open("s5.6.in", 'r')K = eval(file.readline())lights = []for i in range(0,K):    lights.append(eval(file.readline()))group = []N = 0group.append ([0, 0]) for i  in range (0, K):    if lights[i] == 1:        if group[N][1] == 0:            group[N][0] = i            group[N][1] = i        group[N][1] = group[N][1] + 1    elif group[N][1] != 0:        N = N + 1        group.append ([0, 0])        if group[N][1] == 0:    N = N - 1    group.pop() N = N + 1minimumSwitches = []for i in range(0,N+1):    minimumSwitches.append (0) numL = 0 for i in range(N-1, -1, -1):    minimumSwitches[i] = INF;    numOnes = 0;    # we try every group as the rightmost in the block until we get too far away    j = i    while j < N and ((group[j][1] - group[i][0]) <= 7):        numOnes = numOnes + group[j][1] - group[j][0]        len = max(4, group[j][1] - group[i][0]);        t = len - numOnes         # for spans of 6 and 7 there are certain configurations that cannot be cleared as a block        if len == 6 and lights[group[i][0] + 2] == 1 and lights[group[i][0] + 3] == 1:            t = INF        elif len == 7 and lights[group[i][0] + 3] == 1:            t = INF         minimumSwitches[i] = min(minimumSwitches[i], t + minimumSwitches[j+1])         j = j + 1 print minimumSwitches[0]

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗