Acowdemia(Silver): USACO
Hello Everyone,
for this problem I have read the official solution and understand the logic of it and the math behind it. My method got around half of the test cases correct with most of the other half incorrect because of wrong answers. I am not sure why as the logic is the most optimal. My code is still binary searching on a possible h index. Then starting from the largest in the array and going backwards until you account for the h largest cited papers. For each paper in the loop, add the difference between h and the current number of citations and do this l times as you can cite l papers in one survey. Then adjust the remaining k. I mainly need debugging help on the method I wrote(works)
import java.util.;
import java.io.;
public class Acowdemia {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(st.nextToken());
int[] cites = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
cites[i] = Integer.parseInt(st.nextToken());
} // input reading
Arrays.sort(cites);
int high = n;
int low = 1;
while (low <= high) { // binary search
int mid = (low + high + 1)/2;
if (works(mid, cites, k, l)) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
System.out.println(high);
}
public static boolean works(int mid, int[] citesTemp, int k, int l) {
// mid is the h index i am checking currently
int[] cites = new int[citesTemp.length]; // created a new array to avoid changing the original
for (int i = 0; i < citesTemp.length; i++) {
cites[i] = citesTemp[i];
} // just duplicated the citesTemp
for (int i = cites.length - 1; i >= cites.length - mid; i--) {
// go from largest(backwards) as it is in sorted order
int cur = cites[i];
int dif = mid - cur; // find difference between current citations and the mid(h index value)
if (dif > 0) {
if (k < dif) {
return false; // see if you have enough k(surveys left to do it)
}
k -= dif; // adjust k
for (int j = i; j >= Math.max(0, i - l + 1); j--) {
cites[j] += dif; // then for each of the l left most papers also add k to them as you can do l citations from one survey
}
}
}
return true;
}
}