6
\$\begingroup\$

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 ith plant is Hi.

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 <= 105
0 <= A, B <= 108
1 <= Hi <= 103


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.

\$\endgroup\$
  • 3
    \$\begingroup\$ What's the winning criterion? \$\endgroup\$ – acrolith Sep 21 '16 at 18:07
  • 1
    \$\begingroup\$ Don't be discouraged just check out some other challenges based on their input format and winning criterion, the underlying problem is interesting. \$\endgroup\$ – ThreeFx Sep 21 '16 at 18:15
  • 5
    \$\begingroup\$ Also, @AlexA. is male. \$\endgroup\$ – flawr Sep 21 '16 at 18:16
  • 4
    \$\begingroup\$ Please reconsider the input format. Usually we are not so restrictive. People want to use the native format of their favorite language. "Any reasonable format" is a good way to go. \$\endgroup\$ – nimi Sep 21 '16 at 19:51
  • 2
    \$\begingroup\$ Maybe I am missing something or your provided output example and the challenge do not match exactly. do you want the minimal cost to create a palindrome or the palindrome itself? (or both?) \$\endgroup\$ – nyro_0 Sep 22 '16 at 8:17
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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,:]
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ No, the challenge is to output the minimum amount of energy required to create a palindrome from the plant heights. \$\endgroup\$ – R. Kap Sep 22 '16 at 8:32
  • \$\begingroup\$ okay, updated my answer :) \$\endgroup\$ – nyro_0 Sep 22 '16 at 8:43
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.