HackerRank Accessory Collection Problem Solution

In this post, we will solve HackerRank Accessory Collection Problem Solution.

Victoria is splurging on expensive accessories at her favorite stores. Each store stocks A types of accessories, where the ith accessory costs i dollars (1 ≤ i ≤ A). Assume that an item’s type identifier is the same as its cost, and the store has an unlimited supply of each accessory.
Victoria wants to purchase a total of L accessories according to the following rule:
Any N-element subset of the purchased items must contain at least D different types of accessories.
For example, if L = 6, N = 3, and D = 2, then she must choose 6 accessories such that any subset of 3 of the 6 accessories will contain at least 2 distinct types of items.
Given L. A. N. and D values for T shopping trips, find and print the maximum amount of
money that Victoria can spend during each trip: if it’s not possible for Victoria to make a
purchase during a certain trip, print SAD instead. You must print your answer for each trip
on a new line.
Input Format
The first line contains an integer. T. denoting the number of shopping trips. Each of the T subsequent lines describes a single shopping trip as four space-separated integers corresponding to L. A. N. and D. respectively.

Output Format

For each shopping trip, print a single line containing either the maximum amount of money Victoria can spend; if there is no collection of items satisfying her shopping rule for the trip’s L, A, N, and D values, print SAD instead.

Sample Input

2
6 5 3 2
2 1 2 2

Sample Output

24
SAD

Explanation
Shopping Trip 1:
We know that:
Victoria wants to buy L = 6 accessories.
The store stocks the following A = 5 types of accessories: {1, 2, 3, 4, 5}.
For any grouping of N = 3 of her L accessories, there must be at least D = 2 distinct types of accessories.
Victoria can satisfy her shopping rule and spend the maximum amount of money by purchasing the following set of accessories: {3, 4, 5, 5, 4, 3}. The total cost is
3+4+5 +5 +4+3 = 24, so we print 24 on a new line.
Shopping Trip 2:
We know that:
Victoria wants to buy L = 2 accessories.
The store stocks A = 1 type of accessory: {1}.
For any grouping of N = 2 of her L accessories, there must be at least D = 2 distinct types of accessories.
Because the store only carries 1 type of accessory, Victoria cannot make a purchase satisfying the constraint that there be at least D = 2 distinct types of accessories. Because Victoria will not purchase anything, we print that she is SAD on a new line.

HackerRank Accessory Collection Problem Solution

Accessory Collection C Solution


#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int T; 
    scanf("%d",&T);
    for(int a0 = 0; a0 < T; a0++){
        int L; 
        int A; 
        int N; 
        int D; 
        scanf("%d %d %d %d",&L,&A,&N,&D);
        if (D == 1) {
            printf("%lld\n", (long long)A*L);
            continue;
        }
        int max, min, i, q, r;
        long long count, result = 0;
        max = (N-1)/(D-1);
        if ((L-(N-1)+max-1)/max+D-1 > A) {
            printf("SAD\n");
            continue;
        }
        min = (L-(N-1)+A-(D-1)-1)/(A-(D-1));
        for (i=max; i>=min; i--) {
            q = (L-(N-1))/i;
            r = (L-(N-1))%i;
            count = (long long)(A-(D-1+q))*r + (long long)(A-(D-1+q)+1+A-1)*(D-2+q)/2*i + (long long)A*(N-1-i*(D-2));
            if (count <= result) {
                break;
            }
            result = count;
        }
        printf("%lld\n", result);
    }
    return 0;
}

Accessory Collection C++ Solution

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

long long sumrange(long long a, long long b) {
  long long res1 = (b * (b + 1)) / 2;
  long long res2 = (a * (a - 1)) / 2;

  return res1 - res2;
}

long long process(long long l, long long a, long long n, long long d) {

  if (a < d)
    return -1; /// Less then d different items to pick from

  /// The first d-1 most expensive items will sum up to n-1

  /// Let x be the frequency of (d-1) item
  /// All items on left of (d-1) have higher or same frequency
  /// And on right have equal frequency, except for the last one

  /// What are the possible values of x?

  if (d == 1)
    return l * a; /// To avoid divison by zero on next line

  long long upperlimit = (n - 1) / (d - 1);

  long long res = 0;

  for (int x = 1; x <= upperlimit; x++) {

    /// If (d-1) index has value x, then all the values on left will be x
    /// Except for the first one

    /// Sum of first (d-1) items should be equal to n, and each item should have
    /// at least equal to x value

    long long extra =
        ((n - 1) - (d - 1) * x); /// The extra frequency of first item

    /// If we remove the extra, all items can have at most x frequency

    if (extra + a * x < l)
      continue;

    long long temp = extra * a;

    /// Number of items bought with frequency x
    long long num = (l - extra) / x;

    long long subtotal = sumrange(a - num + 1, a);
    temp += subtotal * x;

    /// Possible that there is a last cell with less than x frequncy

    if ((l - extra) % x != 0) {
      long long last = (l - extra) % x;
      temp += last * (a - num);
    }

    if (temp > res)
      res = temp;
  }

  if (res == 0)
    res = -1;
  return res;
}

int main() {
  // freopen("input.txt", "r", stdin );

  int kase;
  scanf("%d", &kase);

  while (kase--) {
    long long l, a, n, d;

    scanf("%lld %lld %lld %lld", &l, &a, &n, &d);

    long long res = process(l, a, n, d);

    if (res == -1)
      printf("SAD\n");
    else
      printf("%lld\n", res);
  }
  return 0;
}

Accessory Collection C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
    static void Main(String[] args) {
        var sb = new StringBuilder();
        int tc = int.Parse(Console.ReadLine());
        while (tc-- > 0) {
            var tmp = Console.ReadLine().Split(' ');
            int L = int.Parse(tmp[0]);  // number of accessories
            int A = int.Parse(tmp[1]);  // types of accessories
            int N = int.Parse(tmp[2]);  // size of choosen subset
            int D = int.Parse(tmp[3]);  // at least different items

            long ans = -1;
            if (D > A) {
                ans = -1;
            } else if (D == 1) {
                ans = Math.BigMul(L, A);
            } else {
                for (int i = L; i >= 1; i--) {
                    long ter = sol(L, A, N, D, i);
                    if (ter > ans) {
                        ans = ter;
                    } else if (ans != -1) break;
                }
            }
            sb.Append(ans == -1 ? "SAD" : ans.ToString()).Append("\n");
        }
        Console.WriteLine(sb.ToString());
    }
    static long sol(long L, long A, long N, long D, long mid) {
        long p = A - D + 1;
        long top = mid + (N - 1 - mid * (D - 1));
        if (top < mid) return -1;

        long sum = mid;
        long gold = mid * p;
        for (long i = A; i > p; i--) { sum += top; gold += i * top; }

        long r = p + 1;
        while (sum > N && r < A) {
            sum += mid - top;
            gold += mid * r - top * r;
            r++;
        }

        if (L < sum) return -1;
        if (L == sum) return gold;

        L -= sum;
        r = p - 1;
        if (r * mid < L) return -1;

        var fix = L / mid;
        var rem = L - fix * mid;
        gold += mid * (q(r) - q(r - fix));
        gold += rem * (r - fix);
        return gold;
    }
    static long q(long n) {
        return n * (n + 1) / 2;
    }
}

Accessory Collection Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    
    static String acessoryCollection(long L, long A, long N, long D) {
        long max=0;
        if(D>N || N>L){
            return "SAD";
        }else if(D==1){
            return String.valueOf(A*L);
        }else{
            long cmid=(N-1)/(D-1);
            for(long mid=cmid;mid>=1;mid--){
                long clarge=N+(mid-1)-((D-1)*mid);
                long n=(L-clarge)/mid;
                long csmall=(L-clarge)%mid;
                if(n>A-1 || (csmall>0 && n==A-1)){
                    break;
                }

                long sum=clarge*A+csmall*(A-n-1)+(((A-1+A-n)*(n) *mid)/2);
                if(sum<max)break;
                max=sum;


            }
        }
        if(max==0){
            return "SAD";
        }else{
            return String.valueOf(max);
        }

    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int T = Integer.parseInt(scanner.nextLine().trim());

        for (int TItr = 0; TItr < T; TItr++) {
            String[] LAND = scanner.nextLine().split(" ");

            long L = Long.parseLong(LAND[0].trim());

            long A = Long.parseLong(LAND[1].trim());

            long N = Long.parseLong(LAND[2].trim());

            long D = Long.parseLong(LAND[3].trim());

            String result = acessoryCollection(L, A, N, D);

            bufferedWriter.write(result);
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Accessory Collection Python Solution

#!/bin/python3

import os
import sys

#
# Complete the acessoryCollection function below.
#
def acessoryCollection(L, A, N, D):
    #
    # Write your code here.
    #
    if D > A or N < D or N > L:
        return "SAD"
    elif D == 1:
        return str (L * A)
    else:
        max = 0
        a2Max = (N - 1) // (D - 1)
        for a2 in range (a2Max, 0, -1):
            a1 = N + (a2 - 1) - a2 * (D - 1)
            n = (L - a1) // a2
            a3 = (L - a1) % a2
            if n > A - 1 or n == A - 1 and a3 > 0: break
            sum = A * a1 + (A - 1 + A - n) * n // 2 * a2 + a3 * (A - n - 1)
            if sum <= max: break
            max = sum
        if max: return str (max)
        else: return "SAD"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    T = int(input())

    for T_itr in range(T):
        LAND = input().split()

        L = int(LAND[0])

        A = int(LAND[1])

        N = int(LAND[2])

        D = int(LAND[3])

        result = acessoryCollection(L, A, N, D)

        fptr.write(result + '\n')

    fptr.close()

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