Skip to content

Solving Angry Children 2 problem

March 9, 2014

Hacker rank problem 

Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of the K children in the village (each packet may contain different number of candies). To avoid a fight between the children, he would like to pick K out of N packets such that the unfairness is minimized.

Suppose the K packets have (x1, x2, x3,….xk) candies in them, where xi denotes the number of candies in the ith packet, then we define unfairness as

image1

where |a| denotes the absolute value of a.

Input Format
The first line contains an integer N.
The second line contains an integer K. N lines follow each integer containing the candy in the ith packet.

Output Format
A single integer which will be minimum unfairness.

Constraints
2<=N<=105
2<=K<=N 
0<= number of candies in each packet <=109

Sample Input #00

7
3
10
100
300
200
1000
20
30

Sample Output #00

40

Explanation #00

Bill Gates will choose packets having 10, 20 and 30 candies.So unfairness will be |10-20| + |20-30| + |10-30| = 40. It will be minimum as compared to any other distribution which can be verified .

Sample Input #01

10
4
1
2
3
4
10
20
30
40
100
200

Sample Output #01

10

Explanation #01

Bill Gates will choose 4 packets having 1,2,3 and 4 candies. So, unfairness will be |1-2| + |1-3| + |1-4| + |2-3| + |2-4| + |3-4| = 10

 

1) First attempt, which did not pass all the test cases: 

package main
import (
“fmt”
“sort”
“math”
)

func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var N int
fmt.Scan(&N)
var K int
fmt.Scan(&K)

arr := make([]int, N)
for i:=0; i<N; i++ {
fmt.Scan(&arr[i])
}
sort.Ints(arr)
//fmt.Printf(“N: %v, K: %v\n”, N, K)
//fmt.Printf(“arr: %v\n”, arr)

prev_sz_dp := make([]int, N)
// DP comes here in size
for sz:=2; sz<=K; sz++ {
for i:=0; i<=N-sz; i++ {
j:= i+sz-1
for k:=i; k<i+sz-1; k++ {
prev_sz_dp[i] += int(math.Abs(float64(arr[j] – arr[k])))
}
}
}

//fmt.Printf(“prev_sz_dp: %v\n”, prev_sz_dp)

min:=-1
for i:=0; i<=N-K; i++ {
if min == -1 || min > prev_sz_dp[i] {
min = prev_sz_dp[i]
}
}

fmt.Printf(“%v\n”, min)

}

2) Second attempt

I introduced some math bit as shown in the comment. 

package main
import (
“fmt”
“sort”
“math”
)

func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var N int
fmt.Scan(&N)
var K int
fmt.Scan(&K)

arr := make([]int, N)
for i:=0; i<N; i++ {
fmt.Scan(&arr[i])
}
sort.Ints(arr)
//fmt.Printf(“N: %v, K: %v\n”, N, K)
// fmt.Printf(“arr: %v\n”, arr)

//prev_sz_dp := make([]int, N)

// loop for the starting point of a K set, shifting by 1 to the right
minUnFairness := int64(-1)
for st:=0; st < N-K; st++ {
// Math bit
// I understand (after some thinking) that the formula to get the
// unfairness is
// unfairness = nl * diff * nr
// where nl is no. of elements on left side of an element in a given K set
// nr is no. of elements on the right side of the given element
// diff is the diff beween the given element and its prev (left) element)
unfairness := int64(0)
for i := st+1; i<st+K; i++ {
diff := int(math.Abs(float64(arr[i] – arr[i-1])))
unfairness += int64( (i-st) * diff * (st+K-i))
}
// fmt.Printf(“unfairness at %v : %v\n”, st, unfairness)
if minUnFairness == -1 || minUnFairness > unfairness {
minUnFairness = unfairness
}
}

fmt.Printf(“%v\n”, minUnFairness)

}

Now 8 out of 15 pass. But 7 still time out. 
I think I need to add some Dynamic programming (DP) bit. 

Oh and I did not mention. I purchased a few test cases using hackos. Hackos are points which you have already earned by solving problems. And you can buy some more test cases other than those 2 provided as part of the problem to help improve your solution. Thereby making it pass more (ideally all) test cases. 

3) Third attempt with trying to use more mathematics 

and calculate the unfairness using avg of a K-1 set, and previously calculated unfairness. This should work the code listing below:

package main
import (
“fmt”
“sort”
“math”
)

func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var N int
fmt.Scan(&N)
var K int
fmt.Scan(&K)

arr1 := make([]int, N)
for i:=0; i<N; i++ {
fmt.Scan(&arr1[i])
}
sort.Ints(arr1)

arr := make([]int64, N)
for i:=0; i<N; i++ {
arr[i] = int64(arr1[i])
}
// fmt.Printf(“N: %v, K: %v\n”, N, K)
// fmt.Printf(“arr: %v\n”, arr)

//prev_sz_dp := make([]int, N)

lval := arr[0]
unfairness := float64(0)

// compute the avg and unfairness of the first set
sum := float64(0)
for i:=1; i<K; i++{

sum += float64(arr[i])
diff := int64(math.Abs(float64(arr[i] – arr[i-1])))
unfairness += float64( int64(i * (K-i)) * diff )
}
avg := sum / float64(K-1)

// fmt.Printf(“unfairness: %v\n”, unfairness)
// fmt.Printf(“avg: %v\n”, avg)
minUnFairness := int64(unfairness)

// loop for the all other k sets by shifting right
// but compute the unfairness optimally (i.e by using avg and left val)
for i:=K; i<N; i++ {
unfairness -= (avg – float64(lval) ) * float64(K-1)
unfairness += (float64(arr[i]) – avg) * float64(K-1)
// fmt.Printf(“unfairness: %v\n”, unfairness)
if unfairness < float64(minUnFairness) {
minUnFairness = int64(unfairness)
}
sum += float64(arr[i] – arr[i-K+1])
avg = sum/ float64(K-1)

lval = arr[i-K+1]
// fmt.Printf(“avg: %v\n”, avg)
// fmt.Printf(“lval: %v\n”, lval)
}

fmt.Printf(“%v\n”, minUnFairness)

}

Submitted the code and ….its good on the timing front. But 3 test cases have wrong answers. Must be some boundary case stuff. 

4) Attempt 4. It was the conversion to and fro float which caused the problem: 

So just using the sum rather than average. Here goes the code which works (and passes all the test cases. Yay!)

package main
import (
“fmt”
“sort”
“math”
)

func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var N int
fmt.Scan(&N)
var K int
fmt.Scan(&K)

arr1 := make([]int, N)
for i:=0; i<N; i++ {
fmt.Scan(&arr1[i])
}
sort.Ints(arr1)

arr := make([]int64, N)
for i:=0; i<N; i++ {
arr[i] = int64(arr1[i])
}
// fmt.Printf(“N: %v, K: %v\n”, N, K)
// fmt.Printf(“arr: %v\n”, arr)

//prev_sz_dp := make([]int, N)

lval := arr[0]
unfairness := int64(0)

// compute the avg and unfairness of the first set
sum := int64(0)
for i:=1; i<K; i++{

sum += arr[i]
diff := int64( math.Abs(float64(arr[i] – arr[i-1])) )
unfairness += int64(i * (K-i)) * diff
}

// fmt.Printf(“unfairness: %v\n”, unfairness)
// fmt.Printf(“avg: %v\n”, avg)
minUnFairness := unfairness

// loop for the all other k sets by shifting right
// but compute the unfairness optimally (i.e by using avg and left val)
for i:=K; i<N; i++ {
unfairness -= sum – lval * int64(K-1)
unfairness += arr[i] * int64(K-1) – sum
// fmt.Printf(“unfairness: %v\n”, unfairness)
if unfairness < minUnFairness {
minUnFairness = unfairness
}
sum += arr[i] – arr[i-K+1]

lval = arr[i-K+1]
// fmt.Printf(“avg: %v\n”, avg)
// fmt.Printf(“lval: %v\n”, lval)
}

fmt.Printf(“%v\n”, minUnFairness)

}

 

Felt really good when it passed all the test cases. They had marked it as easy. But I found it quite tough. 

 

 

Advertisements

From → Uncategorized

One Comment
  1. vinod9600 permalink

    solution for this problem in C is also available on

    http://hackerrank.codingkatta.com/angry-children/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: