Skip to content

Instantly share code, notes, and snippets.

@yssharma

yssharma/AggressiveCowsSpoj.java

Created August 31, 2016 09:14
Show Gist options
  • Save yssharma/451c926e575f357979613a2fe0abe438 to your computer and use it in GitHub Desktop.
Save yssharma/451c926e575f357979613a2fe0abe438 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
AggressiveCowsSpoj.java
package practice.search;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* Created by ysharma on 8/30/16.
*/
/*
1
5 3
1
2
8
4
9
N (2 <= N <= 100,000)
6
10 3
1 2 9 8 4 4 8 9 2 1
5 3
1 2 8 4 9
20 3
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
3 3
0 1000000000 500000000
20 4
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
20 5
9 8 7 10 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 20
output:
3
3
9
500000000
6
4
Find the minimum of maximum distance between C cows in N barns
Another example of uniform distribution problem.
Cow need to be kept max distance apart from each other. whats the min of the distances now.
*/
@SuppressWarnings("Duplicates")
public class AggrCows {
public void doit(){
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next());
while(N-- > 0){
int barns = Integer.parseInt(sc.next());
int cows = Integer.parseInt(sc.next());
List<Integer> l = new ArrayList();
while(barns-- > 0){
l.add(Integer.parseInt(sc.next()));
}
Collections.sort(l);
int sum = max(l);
// Since distance are limited we can try all distances
// And check if we can find a valid arrangement for the distance
// Brute force top to bottom to find first success
for(int i=sum; i> 0; i--){
if(checkPossible(l, i, cows)){
System.out.println(i);
break;
}
// Find if we can find an arrangement with cows atleast i distance apart
// Now notice:
// If we can find an arrangement to place cows i distance apart
// every value less than i should also be possible
// In fact all the values will be possible until we reach a value
// where the condition breaks
// We can use this fact to binary search the solution rather
// than brute forcing the solution.
}
}
}
public void doitBetter(){
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.next());
while(N-- > 0){
int barns = Integer.parseInt(sc.next());
int cows = Integer.parseInt(sc.next());
List<Integer> l = new ArrayList();
while(barns-- > 0){
l.add(Integer.parseInt(sc.next()));
}
Collections.sort(l);
int low = 0;
int high = max(l);
int mid;
int lastSuccess = -1;
while(low <= high){
mid = (low + high) / 2;
if(checkPossible(l, mid, cows)){
lastSuccess = mid;
low = mid + 1;
} else{
high = mid - 1;
}
}
System.out.println(lastSuccess);
}
}
public boolean checkPossible(List<Integer> l, int distance, int cows){
int lastPosition = l.get(0);
int cowsPlaced = 1;
for(int i=1; i < l.size(); i++){
if(cowsPlaced == cows){
return true; // All cows have been placed // done //
}
if(l.get(i) - lastPosition >= distance){
cowsPlaced++;
lastPosition = l.get(i); // update last cows' location
}
}
return cowsPlaced == cows;
}
public int max(List<Integer> l){
int max = Integer.MIN_VALUE;
for(int i : l){
if(i > max){
max = i;
}
}
return max;
}
public static void main(String[] args) {
new AggrCows().doitBetter();
// new AggrCows().doit();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment