Minimum Flip
Tag(s):

Advanced Data Structures, Data Structures, Medium-Hard, Segment tree

Problem
Editorial
Analytics

You are given an array of $N$ numbers.

An operation on the array is defined as :

Select a non-empty subarray of the array and a number $j$. Now flip the $j$-th bit of all the elements of this subarray.

Output the minimum sum of the elements of the given array that can be obtained after doint the above operation at most $K$ times.

Input Format

The first line contains two integers $N$ and $K$ ($1 \le N \le 10^5$, $1 \le K \le 10^9$), denoting the number of elements in the array and the maximum number of operations allowed.

The second line contains $N$ integers $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le 10^6$), the elements of the array.

Output Format

Output the minimum sum of elements that can be obtained by applying the operation at most $K$ times.

SAMPLE INPUT
5 2
5 4 5 1 5

SAMPLE OUTPUT
4

Explanation

In First operation, select subarray [5, 4, 5] and flip their most significant bit. After this operation, array becomes [1, 0, 1, 1, 5].

In Second operations, select last element as subarray and flip its most significant bit. After this operation, array becomes [1, 0, 1, 1, 1].

This is the best we can do in 2 operations. So, the anser is 4.

Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Python > Getting Started
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Data Structures > Advanced Data Structures