Skip to content

Instantly share code, notes, and snippets.

@suicide
Created February 3, 2013 19:03
Show Gist options
  • Save suicide/4703177 to your computer and use it in GitHub Desktop.
Save suicide/4703177 to your computer and use it in GitHub Desktop.
Facebook Hacker Cup 2013 Round 1 Card Game... but something is wrong
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
* @author psy
*
*/
public class CardGame {
/**
* @param args
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
List<String> output = new LinkedList<String>();
CardGame game = new CardGame();
int games = Integer.parseInt(in.nextLine());
for (int i = 1; i <= games; i++) {
String nkString = in.nextLine();
String cardString = in.nextLine();
String[] nkArray = nkString.split(" ");
String[] cardArray = cardString.split(" ");
List<Integer> cards = new ArrayList<Integer>();
for (String card : cardArray) {
cards.add(Integer.parseInt(card));
}
int result = game.findMaxSum(Integer.parseInt(nkArray[0]), Integer.parseInt(nkArray[1]), cards);
output.add("Case #" + i + ": " + result);
}
for (String out : output) {
System.out.println(out);
}
}
public int findMaxSum(int n, int k, List<Integer> cards) {
Collections.sort(cards, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
// big first
return o2.compareTo(o1);
}
});
long result = 0;
int cardCounter = 0;
for (Integer value : cards) {
cardCounter++;
if (n - cardCounter < k - 1) {
break;
}
long cardPossCounter = binomCoef(n - cardCounter, k - 1);
result += value * cardPossCounter;
}
return (int) (result % 1000000007L);
}
private long binomCoef(int n, int k) {
if (k > n) {
throw new IllegalArgumentException("k cannot be greater than n");
}
long result = 1;
for (int i = n - k + 1; i <= n; i++) {
result = result * i;
}
for (int i = 1; i <= k; i++) {
result = result / i;
}
return result;
}
}
@shaktisd
Copy link

shaktisd commented Feb 4, 2013

This solution is not working :(

@suicide
Copy link
Author

suicide commented Feb 6, 2013

yep i know... fixing it later... maybe

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment