A good array

4

9 votes
Greedy Algorithms, Algorithms, Basics of Greedy Algorithms, Greedy algorithm
Problem

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:

  1.  Choose any index $$1≤i≤N$$ and if it is currently 0, then convert it to 1 for X coins.
  2.  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\)

Time Limit: 1
Memory Limit: 256
Source Limit:
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.

Editor Image

?