CareerCup

The correct algorithm would be to check all possibilities of picking K pots in worst case and picking the one with minimum stones among them. Trying to do the problem with any other algorithm is going to fail as there can be an input formed which would make the algorithm fail.

To check all possibilities, it is actually tweaked program of getting all possible kth subset.

The code goes here. Feel free to challenge with any input.

public static int ThirstyCrowProblem(int[] input1,int input2,int input3) {
		int n = input2;
		int k = input3;
		int tempk = 0;

		if(input1 == null || k < 0 || k > input1.length || n <= 0 || input1.length != n) {
			return -1;
		}

		if(k==0) {
			return 0;
		}

		for(int i = 0; i < n; i++) {
			if(input1[i] < 0) {
				return -1;
			} else if (input1[i] == 0) {
				if(++tempk==k) {
					return 0;
				}
			}
		}
		Arrays.sort(input1);
		return minStones(input1,k-tempk,tempk);
	}


    public static int minStones(int[] input, int k, int start) {
    	 List<Integer> minStones = new ArrayList<Integer>();
         minStones.add(Integer.MAX_VALUE);
         minStones(input,k,start,0,minStones);
         return minStones.get(0);
    }
    public static void minStones(int[] input, int k,int start, int stones, List<Integer> minStns) {

      if(k==0) {
          if(stones < minStns.get(0)) {
              minStns.set(0, stones);
          }
          return;
      }

      int[] clone = null;
      for(int i = start; i <= input.length-1-(k-1);i++) {
          if(input[i] == 0) {
              continue;
          }
          clone = input.clone();
          //change clone
          int stns = 0;
          int tempk = 0;
          for(int j = clone.length-1; j >= i;j--) {
              if(clone[j] == 0) {
                  continue;
              }
              if(clone[j] <= clone[i]) {
                  stns+=clone[j];
                  clone[j] = 0;
                  if(++tempk == k) {
                	  break;
                  } else {
                	  continue;
                  }
              }
              stns+=clone[i];
              clone[j] -= clone[i];
          }
          minStones(clone,k-tempk,i,stones+stns,minStns);
      }
    }

int ThirstyCrowProblem(int input1[],int input2,int input3)
{
	int N = input2;
	int K = input3;
	
	if(N < K || K < 1)
	{
		return -1;
	}

	int it = 0;
	int jt = 0;
	for(it=0;it<N;it++)
	{
		if(input1[it] < 0)
		{
			return -1;
		}
	}
	
	
	
	for(it=0;it<N;it++)
	{
		for(jt=0;jt<N-it-1;jt++)
		{
			if(input1[jt] > input1[jt+1])
			{
				int temp = 0;
				temp = input1[jt+1];
				input1[jt+1] = input1[jt];
				input1[jt] = temp;
			}
		}
	}
	
	for(it=0;it<N;it++)
	{
		printf("%d,", input1[it]);
	}
	
	int outTemp = 0;
	for(it=0;it<K;it++)
	{
		outTemp += input1[N-it-1];
	}

	int iVal = input1[K-1];
	int iValPrev = 0;
	int iOut = 0;
	for(it=0;it<K-1;it++)
	{
		if(input1[it] < iVal)
		{
			iOut += (input1[it] - iValPrev)*(N-it);
			iValPrev = input1[it];
		}
		else if((input1[it] == iVal))
		{
			iOut += input1[it] - iValPrev;
		}
	}
	
	for(it=K;it<N;it++)
	{
		if(input1[it] > input1[K-1])
		{
			iOut += input1[K-1] - iValPrev;	
		}
	}
	
	iOut += input1[K-1] - iValPrev;
	
	if(outTemp < iOut)
	{
		iOut = outTemp;
	}
	
	return iOut;
}

int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;

if(N < K || K < 1)
{
return -1;
}

int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}



for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}

for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}

int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}

int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}

for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}

iOut += input1[K-1] - iValPrev;

if(outTemp < iOut)
{
iOut = outTemp;
}

return iOut;
}

1. Sort Oi..
2. Try median of the first K Oi's to split the pots into two sub sets that overflow vs that doesn't..
2. Try recursively the sub problem.. of identifying K/2 pots from the overflow sub problem.. and remaining K/2 from (N-k/2) pots.

3. The algorithm should take nlogn steps..

public static int getMinStones(final int a[], final int k) {

    if ((a.length < k)) {
      return -1;
    }

    Arrays.sort(a);

    // approach 1:
    final int mid = a[k - 1];
    int res1 = (mid * (a.length - k));
    for (int i = 0; i < k; i++) {
      res1 += a[i];
    }

    // approach 2
    int res2 = 0;
    for (int i = a.length - 1; i > (k - 1); i--) {
      res2 += a[i];
    }
    System.out.println("Approach 1 = " + res1 + " Approach 2 = " + res2);
    return Math.min(res1, res2);
  }

Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}

Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.

So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots

Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124

So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.

Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}

Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.

So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots

Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124

So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.

public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
/* Worst Case can happen only when the pots are arranged in descending order of their O value and their o value is distinct. Crow starts from first minimum traversing till last and for n number of pots required
* n passes will be required.
*
*/
if (input1 == null || input3 < 0 || input3 > input1.length
|| input2 <= 0 ) {
return -1;
}
Arrays.sort(input1);
int stones = 0;

int min = 0;
int prevMin = 0;
for (int i = 0; i < input3; i++) {
min = input1[i] - prevMin;
stones += input2 * min;
input2--;
prevMin = input1[i];

}

return stones;

}
Whats wrong in this?
I sorted in reverse order and checked for first, second , and third minimum and so on

The answer is a straightforward summation that can be written in a formula like below:

No. of stones = ∑ (N-i)*[ x_i+1 - ∑ ( x_j) ]

First ∑ runs from i=0 to K
Second ∑ runs from j=1 to i
Underscore means subscript, to indicate "i"th value in an array "x".

Logic and formulation:
1. Create an ascending array "x". This is number of stones required to fill all N pots.
2. K is the number of pots crow wants to fill
3. The crow will start with x_1 in all the pots one by one and as it has the "worst luck", will find the correct pot only in the Nth try. So, number of stones required if K=1 is N*K
4. Now the crow knows that it has wasted (N-1)*K in all the wrong pots. So now all the remaining pots required K less stones to overflow. So the array "x" changes, such that all the values will be x_1 less. This is the crucial part. Changing of the array is taken care of in second summation.
5. Now repeat for the next pot from step 3 from second pot with new array.

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int[] integerArray = {1,2,3,4,5,5,6};
		System.out.println(getMinStones(integerArray, 3));
		
	}
	public static int getMinStones(final int a[], final int k) {

    if ((a.length < k)) {
      return -1;
    }

    Arrays.sort(a);
    int i, last, stones1, stones2,stones, count;
    for (i = k; i < a.length && a[k - 1] == a[i]; i++);
    last = a[i - 1];
    stones1 = 0;
    stones2 = 0;
    for (i = 0; i < k; i++)
    {
    	stones1 += a[a.length - 1 - i];
    }
    for (i = 0, count = 0; count < k; i++)
    {
    	if ((a[a.length - i - 1] > last) )
    	{
    	    stones2 += last;
    	}
    	else
    	{
    	    stones2 += a[a.length - i - 1];
    	    count++;
    	}
    }
    stones = Math.min(stones1, stones2);
    return stones;
    }
 }

import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}
}

import java.io.*;
import java.util.Arrays;
public class CandidateCode 
{ 
    public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
    {
        if(input1.length==input2 && input2 >= input3)
        {
          Arrays.sort(input1);
          int sumval=0;
          for(int i=0;i<input3;i++){
              sumval += input1[i];
          }
          
          int result = (input2-input3)*input1[input3-1]+sumval;
          return result;
          
        }
        else{
            return -1;
        } 
    }
}

import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}
}

import java.io.*;
import java.util.Arrays;
public class CandidateCode 
{ 
    public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
    {
        if(input1.length==input2 && input2 >= input3)
        {
          Arrays.sort(input1);
          int sumval=0;
          for(int i=0;i<input3;i++){
              sumval += input1[i];
          }
          
          int result = (input2-input3)*input1[input3-1]+sumval;
          return result;
          
        }
        else{
            return -1;
        } 
    }

}

Guys try this your code will be solved.

function ThirstyCrowProblem(input1,input2,input3)
{
if(input1.length==input2 && input2 >= input3)
{
input1 = input1.sort(function (a, b) {
return a - b;
});
var sumval=0;
for(var i=0;i<input3;i++){
sumval += input1[i];
}
var result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}

Hi,

I used the below code:
static int ThirstyCrowProblem(int[] input1, int input2)
{
int len = input1.Length;
int minStones = 0;
Array.Sort(input1);
if (input1 == null || input2 <= 0 || input2 > len || len <= 0)
{
return -1;
}

if(input2 == 1 && input1[0] != 0)
{
minStones = len * (input1[0]);
return minStones;
}
int strt = 0;
for (int i = 0; i < input2; i++)
{
if(input1[i] == 0)
{
strt++;

}
}

int s = 0; minStones = (len-strt) * (input1[strt]); int j = 0;
for (int i = strt; i < input2; i++)
{
if(i>strt)
{
//s = s + input1[i - 1]; j = j+input1[i] - s;
minStones = minStones + Math.Abs(input1[i] - input1[i-1]) * (len - i);
}
}

return minStones;
}

static int ThirstyCrowProblem(int[] input1, int input2)
{
int len = input1.Length;
int minStones = 0;
Array.Sort(input1);
if (input1 == null || input2 <= 0 || input2 > len || len <= 0)
{
return -1;
}

if(input2 == 1 && input1[0] != 0)
{
minStones = len * (input1[0]);
return minStones;
}
int strt = 0;
for (int i = 0; i < input2; i++)
{
if(input1[i] == 0)
{
strt++;

}
}

int s = 0; minStones = (len-strt) * (input1[strt]); int j = 0;
for (int i = strt; i < input2; i++)
{
if(i>strt)
{
//s = s + input1[i - 1]; j = j+input1[i] - s;
minStones = minStones + Math.Abs(input1[i] - input1[i-1]) * (len - i);
}
}

return minStones;
}

static int ThirstyCrowProblem(int[] input1, int input2)
{
int len = input1.Length;
int minStones = 0;
Array.Sort(input1);
if (input1 == null || input2 <= 0 || input2 > len || len <= 0)
{
return -1;
}

if(input2 == 1 && input1[0] != 0)
{
minStones = len * (input1[0]);
return minStones;
}
int strt = 0;
for (int i = 0; i < input2; i++)
{
if(input1[i] == 0)
{
strt++;

}
}

int s = 0; minStones = (len-strt) * (input1[strt]); int j = 0;
for (int i = strt; i < input2; i++)
{
if(i>strt)
{
//s = s + input1[i - 1]; j = j+input1[i] - s;
minStones = minStones + Math.Abs(input1[i] - input1[i-1]) * (len - i);
}
}
return minStones; }

// This is a C++ code, but I do not think it will be a problem
// It covers both scenarios (If the crow wants any pots, or pots with different
// Os
int ThirstyCrowProblem(vector < int > input1, int input2)
{
	int size = (int)input1.size();

	// It is impossible to have a number of pots that is negative or above the number of all pots
	if (input2 > size || input2<1) return -1;

	int result = 0;

	// We need to know the lowest number of stones
	// This means the pots with the least Os
	// So, we start by sorting Os, to pick the lowest N (where N is input2)
	sort(input1.begin(), input1.end());
	int max = input1[input2 - 1];
	int lastmax = 0;
	for (int t = 1;t<size;t++)
		if (input1[t] == input1[t - 1])
			input1[t - 1]--;


	int skip = 0;


#ifdef HoneyAndMilk
	// if what we need is the specific pot (like pots with number 1 have honey while pots with number 2 have milk...)
	for (int t = 0;t < size && input1[t] < max;t++) { skip++; result += input1[t]; }
	for (int t = skip;t < size;t++) result += max;
#else
	// if it is ok to have any pot, and the crow knows that all next left pots are of
	// the same O, then it does not need to move back to the first pot in case a smaller
	// amount of stones is required to make a closer pot start overflowing
	for (skip = size - 1;skip > 0 && input1[skip] >= max;skip--)
		result += max;
	for (int t = skip;t > skip - input2;t--)
		result += input1[t];

#endif
	return result;
}

public static int ThirstyCrowProblem(int[] input1, int input2) {
int stones = -1;
if (input2 < 1 || input1 == null || input1.length < 1 || input1.length < input2) {
stones = -1;
} else if ( input1.length == 1) {
stones = input1[0];
} else {
Arrays.sort(input1);
int previous = 0;
stones = 0;
for(int i=0;i<input2;i++) {
stones += (input1[i]-previous) * (input1.length - i);
previous = input1[i];
}
}
return stones;
}

// overflow is k here

sort(array); //ascending order

int lastindex = array.length-1;
int sum = 0;
for(int i=lastindex; i >= lastindex - (overflow - 1); i--)
sum += array[i];


int minsum = sum;
for(int i=lastindex-1; i >= overflow - 1; i--)
{
sum -= array[i+1];
sum += array[i-overflow] + array[i]*(lastindex - i);

if(sum < minsum)
minsum = sum;
}

print(minsum);

#include <iostream>

using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++) /* To check all possibilities*/
{
int i=n-count;
int minvalue=A[i]; /* min among all values in that subarray*/
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}

#include <iostream>

using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++)
{
int i=n-count;
int minvalue=A[i];
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}

I believe it could be solved using greedy strategy.

int ThirstyCrowProblem(int input1[],int input2,int input3)
{
	int N = input2;
	int K = input3;
	
	if(N < K || K < 1)
	{
		return -1;
	}

	int it = 0;
	int jt = 0;
	for(it=0;it<N;it++)
	{
		if(input1[it] < 0)
		{
			return -1;
		}
	}
	
	
	
	for(it=0;it<N;it++)
	{
		for(jt=0;jt<N-it-1;jt++)
		{
			if(input1[jt] > input1[jt+1])
			{
				int temp = 0;
				temp = input1[jt+1];
				input1[jt+1] = input1[jt];
				input1[jt] = temp;
			}
		}
	}
	
	for(it=0;it<N;it++)
	{
		printf("%d,", input1[it]);
	}
	
	int outTemp = 0;
	for(it=0;it<K;it++)
	{
		outTemp += input1[N-it-1];
	}

	int iVal = input1[K-1];
	int iValPrev = 0;
	int iOut = 0;
	for(it=0;it<K-1;it++)
	{
		if(input1[it] < iVal)
		{
			iOut += (input1[it] - iValPrev)*(N-it);
			iValPrev = input1[it];
		}
		else if((input1[it] == iVal))
		{
			iOut += input1[it] - iValPrev;
		}
	}
	
	for(it=K;it<N;it++)
	{
		if(input1[it] > input1[K-1])
		{
			iOut += input1[K-1] - iValPrev;	
		}
	}
	
	iOut += input1[K-1] - iValPrev;
	
	if(outTemp < iOut)
	{
		iOut = outTemp;
	}
	
	return iOut;
}

Maybe I'm missing something but I think it's much simpler than the above solutions.

The main observation is to see that the number of stones in each cell after each "round" where a round ends when a pot overflows.

Input: ov = [3, 1, 5]

Let cs = sorted(ov, reverse=True) --> [1, 3, 5]

Round 0: [0, 0, 0]
Round 1: [1, 1, 1] --> first pot overflows
Round 2 :[x, 1+2, 1+2] --> [x, 3, 3] --> second pot overflows
...and so on until all K pots overflow

[c1, c2, c3, ...c_K, c_K, c_K....]

for a total of

sum(cs[:k]) + (N-K) * c[K-1]

The first term is the sum of the stones for the K pots and the remaining are the stones in the partially filled pots.

The runtime is O(N log N) for the sort. :)

Is it a puzzle or a coding problem??

Greedy: Sort the array, and then place the smallest amount of rocks in all pots, 1 will overflow, remove that pot, repeat till k pots overflow.

#include <iostream>
#include <algorithm>
using namespace std;

int const N = 5;
int const k = 3;
int overflow[N] = {5,58,13,7,6};

int main() {

    // nlogn sort
    sort(overflow, overflow + N);

    int rocks = overflow[0] * N;
    for (int i = 1; i < k; ++i) {

        int potsRemaining = (N - i);
        rocks += (overflow[i] - overflow[i-1]) * potsRemaining;
    }

    cout << "Rocks: " << rocks << endl;
}