A good array

Practice

4 (9 votes)

Greedy algorithms

Algorithms

Basics of greedy algorithms

Greedy algorithm

Problem

53% Success 2309 Attempts 20 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given an array $$A$$ which consists of $$N$$ elements. Each element of array is either zero or one. Your task is to convert the given array into a good array with a minimum cost. Good array: In a good array, select any subarray of even length $$M$$ and the sum of elements in the subarray will be $$M/2$$. In order to transform an array to good array, you can perform the following two operations as many times as you want: Choose any index $$1≤i≤N$$ and if it is currently 0, then convert it to 1 for X coins. Choose any index $$1≤i≤N$$ and if it is currently 1, then convert it to 0 for Y coins. Your task is to minimize the cost of transformation of an array to good array. Input format The first line contains $$T$$ denoting the number of test cases. The first line of each test case contains three space-separated integers $$N$$, $$X$$, and $$Y$$. The second line of each test case consists of $$N$$ space-separated integers of array $$A$$. Output format For each test case, print one line denoting the minimum cost to transform array $$A$$ into a good array. Constraints \(1 \leq T \leq 100\) \(1 \leq N \leq 10^4\) \(0 \leq A_i \leq 1\) \(1 \leq X,Y \leq 10^9\)

Sample Input

Sample Output

1
0

Explanation

First test case: Array is [1,1], there is only one subarray which is of even length (2), i.e. complete subarray [1,1], it is not good array because for a subarray of size M i.e 2 in our case, sum must be M/2 i.e 1. But sum is 2 for this subarray, so this does not follow property of good subarray. So here we need convert array to either [1,0] or [0,1], cost is 1 in either case. Second test case: Array is [0,1], there is only one subarray which is of even length (2), i.e. complete subarray [0,1], it is good array because for a subarray of size M i.e 2 in our case, sum must be M/2 i.e 1. Here sum is 2 for this subarray, so this does follow property of good subarray. So we don't need to perform any operation.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor