HackerRank Mandragora Forest Problem Solution

In this post, we will solve HackerRank Mandragora Forest Problem Solution.

The evil forest is guarded by vicious mandragoras. Garnet and her pet must make a journey through. She starts with 1 health point (s) and 0 experience points,
As she encouters each mandragora, her choices are:

Garnet’s pet eats mandragora i. This increments 8 by 1 and defeats mandragora ¿.
Garnet’s pet battles mandragora &. This increases p by 8 x H[i] experience points and defeats mandragora i.
Once she defeats a mandragora, it is out of play. Given a list of mandragoras with various health levels, determine the maximum number of experience points she can collect on her journey.
For example, as always, she starts out with s = 1 health point and p = 0 experience points. Mandragoras have the following health values: H = [3, 2, 5]. For each of the beings, she has two choices, eat or battle. We have the following permutations of choices and outcomes:

Action  s   p
_______ _   __
e, e, e 4   0
e, e, b 3   15
e, b, b 2   14
b, b, b 1   10
b, b, e 2   10
b, e, e 3   9
b, e, b 2   16
e, b, e 3   6

Working through a couple of rows, first, her pet can eat all three and she does not gain any experience points. In the second row, her pet eats the first two to have 1 + 2 = 3 health points, then battles the beast with 5 heatlth points to gain 3 * 5 = 15 experience points. We see that the best option is to eat the beast with 2 points and battle the others to achieve 2 x (3+5)= 16 experience points.
Function Description
Complete the mandragora function in the editor below. It must return an integer that denotes the maximum number of experience points that Garnet can earn. mandragora has the following parameter(s):

H: an array of integers that represents the health values of mandragoras
Input Format
The first line contains an integer. t. denoting the number of test cases. Each test case is described over two lines:

The first line contains a single integer n. the number of mandragoras in the forest.
The second line contains n space-separated integers describing the respective health points for the mandragoras H[H[1], H[2]… H[n]].

Output Format

For each test case, print a single line with an integer denoting the maximum number of experience points that Garnet can earn.

Sample Input

1
3
3 2 2

Sample Output

HackerRank Mandragora Forest Problem Solution

Mandragora Forest C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void merge(long long int arr[],long long int l,long long int m,long long int r)
{
   long long int i, j, k;
   long long int n1 = m - l + 1;
   long long int n2 =  r - m;
 
    /* create temp arrays */
   long long int L[n1], R[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(long long int arr[],long long int l,long long int r)
{
    if (l < r)
    {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
       long long int m = l+(r-l)/2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
 
        merge(arr, l, m, r);
    }
}
int main() {
long long int q;
    scanf("%lld",&q);
    for(long long int i=0;i<q;i++)
        {
      long long int s=1,p=0; 
      long long  int n;
        scanf("%lld",&n);
       long long int a[n],sum = 0;
        for(long long int j=0;j<n;j++){
            scanf("%lld",&a[j]);
            sum+=a[j];}
        mergeSort(a,0,n-1);
        for(long long int j=0;j<n;j++){
            if((s+1)*(sum-a[j])>s*sum){ s++;
                                       sum-=a[j];}                    
            else {
                
                p = s*sum;
                break;
            }
                }
        if(p>sum)
        printf("%lld\n",p);
        else printf("%lld\n",sum);
    }
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

Mandragora Forest C++ Solution

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#include <stdio.h>
#include <cstring>

using namespace std;
typedef long long ll;
typedef long double ld;

ll big = 1000000007ll;


ll n,m,q,d,h,k;
ll T;
vector<ll> A;

int main()
{
   ll c1,c2,c3,c4,c5,c6;
    ll a,b,c,e,g;
    ll y,z;
   // freopen("stupd.txt","r",stdin);
    //freopen("output.txt","w",stdout);


    cin >> T;

    for(c4 = 0; c4 < T; c4++){


        cin >> n;
        vector<ll> A;
        for(c2 = 0; c2 < n; c2++){
            cin >> a;
            A.push_back(a);
        }
        sort(A.begin() , A.end());

        ll sum = 0;
        ll ans = 0;

        for(c1 = n-1; c1 >= 0; c1--){

            ans = max(ans , (c1+2) * sum);
            sum += A[c1];

        }ans = max(ans ,  sum);
        cout << ans << "\n";

    }

	return 0;
}

Mandragora Forest C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    
    static long recur(long[] data, int idx, long power){        
        if(idx >= data.Length)
            return 0;
        
        long fight = 0;

        fight = power*data[idx] + recur(data, idx+1, power);
 
        var eat = recur(data, idx+1, power+1);
        return Math.Max(eat, fight);        
    }
    
    static void Main(String[] args) {
        var t = int.Parse(Console.ReadLine());
        while(t-- > 0)
        {
            Console.ReadLine();
            var data = (Console.ReadLine().Split(' ').Select(Int64.Parse).OrderBy(x => x).ToArray());
            var sum = data.Sum();
            var max = sum;
            for(var i = 1; i < data.Length; i++){
                sum -= data[i-1];
                var yop = sum*(i+1);
                if(yop > max)
                    max = yop;
                if(max < yop)
                    break;
            }
            Console.WriteLine(max);                
        }
    }
}

Mandragora Forest Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            sc.nextLine();
            
            long totalH = 0L;
            List<Long> nums = new ArrayList<Long>();
            String line = sc.nextLine();
            String[] tokens = line.split(" ");
            for (String s : tokens) {
                long nj = Long.parseLong(s);
                nums.add(nj);
                totalH += nj;
            }
            Collections.sort(nums);
            //Arrays.sort(nums);
            long bestScore = 0;
            int eaten = 0;
            long s = totalH;
            
            while (s > bestScore) {
                bestScore = s;
                totalH -= nums.get(eaten);
                eaten += 1;
                s = (1L + eaten) * totalH;
            }
            System.out.println(bestScore);
        }
    }
}

Mandragora Forest JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// Complete the mandragora function below.
function mandragora(H) {
    if(H.length == 1) {
      return H[0];
  }
  
  var whole_sum = BigInt(0);
  var s = BigInt(1);
  var calc = BigInt(0);
  
  var init = new Date().getTime();
  
  H = quickSort(H, 0, H.length - 1)
  
  for(var i=0; i<H.length; i++) {
    whole_sum += BigInt(H[i]);
  }
  
  var p = whole_sum;
  
  for(var i=0; i<H.length; i++) {
      s++;
    whole_sum -= BigInt(H[i]);
    
    calc = whole_sum * s;
    
    if(calc > p) {
        p = calc;
    }
  }
  
  return p.toString();
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const n = parseInt(readLine(), 10);

        const H = readLine().split(' ').map(HTemp => parseInt(HTemp, 10));

        let result = mandragora(H);

        ws.write(result + "\n");
    }

    ws.end();
}

Mandragora Forest Python Solution

T = int(input())
for tc in range(T):
    n = int(input())
    h = list(map(int, input().split()))
    h.sort()
    s = 1
    sm = sum(h)
    P = 0
    for i in range(n):
        if s*sm > (s+1)*(sm - h[i]):
            P+=s*h[i]
        else:
            s+=1
        sm-=h[i]
    print(P)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python