Alexa and the Tea Plantation

Question

Hey guys, first time poster here. I went on Coderoulette recently and some guy posted this question. I looked around online but it doesn't seem to be anywhere. I figured I would post it here for anyone who is a fan of these types of problems. Enjoy!

---

Alexa is a druid who loves Mathematics! She lives in the land of Alfa, taking care of a tea plantation.
The plantation has N plants and the height of the i^th plant is H_i.

Alexa has developed a recent interest in palindromes. She wants to crop the plants so the height of the plants forms a palindrome (without any reordering). She has 2 spells in her arsenal- the 'Growlith' spell will increase the height of a plant by 1 unit, the 'Shrinkooza' spell will decrease the height of a plant by 1 unit. The 'Growlith' and 'Shrinkooza' spells cost A and B units of magic respectively. Help Alexa find the minimum units of magic, that shall enable her to fulfill her objective.

Input Format

First line contains an integer T. T testcases follow.
First line of each test case consists of 3 space-separated integers N, A and B.
Next line consists of N space-separated integers, the initial height of the plants.

Output Format

Print the answer to each test case on a new line.

Constraints

1 <= T <= 10
1 <= N <= 10⁵
0 <= A, B <= 10⁸
1 <= H_i <= 10³

---

Example

Input

1  
5 2 2  
1 6 2 3 4  

Output

12

Explanation

She can use the 'Growlith' spell on the first plant 3 times and the 'Shrinkooza' spell on the second plant 3 times to form 4 3 2 3 4.

Challenge

Write code that will create a palindrome using the least units of magic possible for N plants.

Scoring

This is code golf. The shortest code in bytes wins.

Answer 1

05AB1E, 20 bytes

WU|vy#‚ø€¥˜Ä2ä`OX*,

Explanation

WU                    # store minimum cost in X
  |v                  # for each testcase
    y#                # convert to list split on spaces
      ‚ø             # zip with its own reverse
         €¥           # deltas of each pair
           ˜Ä         # deep flatten and take absolute value
             2ä       # split into 2 pieces
               `      # flatten (leaves the smaller piece on top of the stack)
                O     # sum
                 X*   # multiply with minimum cost
                   ,  # print

Try it online!

Answer 2

Julia, 88 Bytes

f(l,A,B)=reduce(+,map(abs,map(sum,[zip(-l,reverse(l))...][1:fld(end,2)])))*min([A,B]...)

Explained:

If I am not mistaken, all we have to do is either grow all necessary plants or shrink them (depending on which operations is less expensive)

1. zip input list with a reverse of itself (align corresponding heights)
2. only look at first half of the list (floor when length is odd)
3. sum the differences
4. multiply with minimum cost (A or B)

Example

f([1,6,2,3,4],1,2) -> 6   (grow plant 1 and 4, yields [4,6,2,6,4])
f([1,6,2,3,4],3,2) -> 12   (shrink plant 2 and 5, yields [1,3,2,3,1])

Note:

As there is still a discussion about the input format, I disregarded it for the moment.

Update:

Updated to output energy, as I think that outputing the actual palindrome is more challenging I attach my previous code here (76 Bytes):

f(l,A,B)=reduce(hcat,map(x->sort([x...]),[zip(l,reverse(l))...]))[A>B?1:2,:]

Answer 3

JavaScript (ES6), 70 bytes

f=(a,g,s)=>a.reduce((t,h,i)=>t+Math.abs(a[a.length+~i]-h),0)*(g>s?s:g)/2

Double-counts the differences, but we only need to make half the changes, which is achieved by dividing by 2 at the end.