The Christmas Swap

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

ImaxRed and ImaxBlue are preparing for Christmas. They have a row of n Christmas lights, each initially either blue or red. They have enough time to do k swap operations. In each swap operation, a single light is switched with an adjacent one. Imaxblue would like to know the length of the longest possible sequence of consecutive blue lights after k or fewer swaps. ImaxRed would like to know the same thing for red lights.

Input Specification

Line 1: Two space separated integers n (1 \le n \le 100\,000) and k (1 \le k \le 100\,000).
Line 2: n integers, either 1 or 0, 1 a representing blue light and 0 representing a red light.

Output Specification

Two integers, the maximum number of consecutive blue lights after k swaps, and the maximum number of consecutive red lights after k swaps.

Sample Input

8 3

Sample Output

5 2


We swap the following pairs (1-indexed): (3, 4), (1, 2), (2, 3) to get 5 consecutive blue lights. (3, 4) allows us to have 2 consecutive red lights. There is no combination that will result in more consecutive lights.


There are no comments at the moment.