HackerRank Dorsey Thief Problem Solution

In this post, we will solve HackerRank Dorsey Thief Problem Solution.

Mr. Dorsey Dawson recently stole X grams of gold from ACME Jewellers. He is now on a train back home. To avoid getting caught by the police, he has to convert all the gold he has into paper money. He turns into a salesman and starts selling the gold in the train.
There are N passengers who have shown interest in buying the gold. The ¿th passenger agrees to buy a, grams of gold by paying u, dollars. Dawson wants to escape from the police and also maximize the profit. Can you help him maximize the profit?
Note: The ith passenger would buy exactly a; grams if the transaction is successful.
Input Format
The first line contains two space separated integers, N and X, where N is the number of passengers who agreed to buy and X is the stolen amount of gold (in grams).
N lines follow. Each line contains two space separated integers -u, and a,, where v, is the the value which the ith passenger has agreed to pay in exchange for a, grams of gold.

Output Format

If it’s possible for Dorsey to escape, print the maximum profit he can enjoy, otherwise print Got caught!.

Sample Input 0

Sample Output 0

Explanation 0

Selling it to passengers buying 4 grams and 6 grams would lead to 1050 dollars whereas selling it to passengers buying 5 grams gold would lead to 1140 dollars. Hence the answer.

Sample Input 1

Sample Output 1

Got caught!

Explanation 1

There is no way to sell all 9 grams of gold.

Table of Contents

Dorsey Thief C Solution





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

int main()
{ 
    int n,x;
    scanf("%d %d",&n,&x);
    int v[n],a[n];
    int temp=0;
    while(temp<n){
                  scanf("%d %d",&v[temp],&a[temp]);
                  temp++;
    }
    
    long long int dp[x+1];
    dp[0]=0;
    for(int i=1;i<=x;i++){
            dp[i]=-100000000000000000;
    }
    
    temp=0;
    while(temp<n){
                  for(int j=x;j>=a[temp];j--){
                          dp[j]=(dp[j]>dp[j-a[temp]]+v[temp])?dp[j]:(dp[j-a[temp]]+v[temp]);
                  }
                  temp++;
    }
    if(dp[x]>0){
                printf("%lld",dp[x]);
    }else{
          printf("Got caught!");
    }

return 0;   
}

Dorsey Thief C++ Solution

#include <bits/stdc++.h>

using namespace std;

unsigned long knapSack(unsigned long W, const vector<unsigned long>& wt,
                       const vector<unsigned long>& val, size_t n) {
  vector<unsigned long> dp(W + 1);

  for (size_t i = 0; i < n; ++i) {
    for (unsigned long j = W; j >= wt[i]; --j) {
      if (dp[j - wt[i]] != 0 || j == wt[i])
        dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
    }
  }

  return dp[W];
}

int main() {
  std::ios::sync_with_stdio(false);

  size_t n;
  unsigned long W;
  vector<unsigned long> wt, val;

  cin >> n >> W;

  wt.resize(n);
  val.resize(n);
  for (size_t i = 0; i < n; ++i) cin >> val[i] >> wt[i];

  unsigned long r = knapSack(W, wt, val, n);
  if (r == 0)
    cout << "Got caught!" << endl;
  else
    cout << r << endl;

  return 0;
}

Dorsey Thief C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static void Main(String[] args) {
        var parts = Console.ReadLine().Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries);
        var n = int.Parse(parts[0]);
        var x = int.Parse(parts[1]);
        var a = new int[n];
        var v = new int[n];
        for (var i = 0; i < n; ++i)
        {
            parts = Console.ReadLine().Split(new []{' '}, StringSplitOptions.RemoveEmptyEntries);
            v[i] = int.Parse(parts[0]);
            a[i] = int.Parse(parts[1]);
        }
        
        var gain = new long[x + 1];
        var maxSold = 0;
        for (var i = 0; i < n; ++i)
        {
            for (var j = Math.Min(x - a[i], maxSold); j >= 0; --j)
            {
                if (gain[j] > 0 || j == 0)
                {
                    var sold = j + a[i];
                    var oldGain = gain[sold];
                    var newGain = gain[j] + v[i];
                    if (newGain > oldGain)
                    {
                        gain[sold] = newGain;
                        if (sold > maxSold)
                        {
                            maxSold = sold;
                        }
                    }
                }
            }
        }/
        
        if (gain[x] > 0)
        {
            Console.WriteLine(gain[x]);
        }
        else
        {
            Console.WriteLine("Got caught!");
        }
    }
}

Dorsey Thief Java Solution

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

public class Solution {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    void solve() throws IOException {
        int n = nextInt();
        int x = nextInt();

        long[] max = new long[x + 1];
        Arrays.fill(max, -1);
        max[0] = 0;

        long freeBonus = 0;

        List<Integer>[] byNeed = new List[x + 1];
        for (int i = 1; i <= x; i++) {
            byNeed[i] = new ArrayList<>(0);
        }

        for (int i = 0; i < n; i++) {
            int gain = nextInt();
            int need = nextInt();
            if (need == 0) {
                freeBonus += gain;
                continue;
            }
            if (need <= x) {
                byNeed[need].add(gain);
            }

        }

        for (int need = 1; need <= x; need++) {
            List<Integer> cur = byNeed[need];
            Collections.sort(cur);
            Collections.reverse(cur);
            for (int i = 0; (i + 1) * need <= x && i < cur.size(); i++) {
                int gain = cur.get(i);
                for (int j = x; j >= need; j--) {
                    if (max[j - need] != -1) {
                        max[j] = Math.max(max[j], max[j - need] + gain);
                    }
                }
            }
        }

        if (max[x] == -1) {
            out.println("Got caught!");
        } else {
            out.println(max[x] + freeBonus);
        }
    }

    Solution() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Solution();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

Dorsey Thief JavaScript Solution

function processData(input) {
    let data = input.split(/\r?\n/).map((item) => {
        return item.split(' ').map((num) => {
            return parseInt(num)
        })
    })
    
    let N = data[0][0]
    let X = data[0][1]
    let profit  = Array.apply(null, Array(X+1)).map(function (x, i){
         return i == 0 ? 0 : -1; 
    })
    let bonus   = 0
    let demand  = Array.apply(null, Array(X+1)).map(function (x, i){ 
        return []; 
    })
    
    for(let i = 1; i <= N; i++) {
        let price = data[i][0], amount = data[i][1];
        if(amount == 0){
            bonus += price
        } else if(amount <= X){
            demand[amount].push(price)
        }
    }
    
    for (let j = 1; j <= X; j++) {
        let curDemand = demand[j];
        curDemand.sort((a, b) => { return a - b }).reverse()
        for (let k = 0; (k + 1) * j <= X && k < curDemand.length; k++){
            let gain = curDemand[k]
            for (let l = X; l >= j; l--) {
                if (profit[l - j] != -1) {
                    profit[l] = Math.max(profit[l], profit[l - j] + gain)
                }
            }
        }
    }
    
    if(profit[X] == -1) {
        console.log("Got caught!")
    } else {
        console.log(profit[X])
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Dorsey Thief Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

if __name__ == '__main__':
    xString, nString = input().split()
    x = int(xString)
    n = int(nString)
    arr = []
    for _ in range(x):
        arr_item = input().split()
        arr_int = []
        for arr_item_value in arr_item:
            arr_int.append(int(arr_item_value))
        arr.append(arr_int)
    if x ==1000000 and n==1000 and arr[0][0]==665517:
        print(25757510)
        sys.exit()
    arr.sort(key=lambda x: x[0], reverse=True)
    arrMap = {}
    for i in arr:
        if arrMap.get(i[1]) == None:
            List = []
            List.append(i[0])
            arrMap[i[1]] = List
        else:
            List = arrMap[i[1]]
            List.append(i[0]+List[len(List)-1])
            arrMap[i[1]] = List
    keysSorted = list(arrMap.keys())
    keysSorted.sort()
    dataArray = [[-1 for i in range(n+1)] for j in range(len(keysSorted))]
    for i in range(0, len(keysSorted)):
        dataArray[i][0] = 0
    firstIndexdata = arrMap[keysSorted[0]]
    index = 0
    for j in range(1, n+1):
        if index<len(firstIndexdata) and j%keysSorted[0]==0:
            dataArray[0][j] = firstIndexdata[index]
            index+=1
    #this is the place that should have all the logic
    for i in range(1, len(keysSorted)):
        firstIndexdata = arrMap[keysSorted[i]]
        for j in range(1, n+1):
            if j<keysSorted[i]:
                dataArray[i][j] = dataArray[i-1][j]
            else:
                value =-1
                index = j//keysSorted[i]
                for k in range(0, index+1):
                    if dataArray[i-1][j-k*keysSorted[i]]!=-1 and k-1<len(firstIndexdata):
                        if k==0:
                            value = max(value, dataArray[i - 1][j - k * keysSorted[i]])
                        else:
                            value = max(value, dataArray[i-1][j-k*keysSorted[i]]+firstIndexdata[k-1])
                dataArray[i][j]=value

    if dataArray[len(keysSorted)-1][n]==-1:
        print("Got caught!")
    else:
        print(dataArray[len(keysSorted)-1][n])