12390 - Distributing Ballot Boxes
Moderator: Board moderators
12390 - Distributing Ballot Boxes - Time Limit Error
Hi guys.
I spent a lot of time to trying solve this porblem. And I always get TLE.
I use Java.
My benchmark says that my solution spend 1.5 sec to just read data( maximum available file size - 500000 cities).
So Is it posible to solve this problem by Java?
I spent a lot of time to trying solve this porblem. And I always get TLE.
I use Java.
My benchmark says that my solution spend 1.5 sec to just read data( maximum available file size - 500000 cities).
So Is it posible to solve this problem by Java?
Re: 12390 - Distributing Ballot Boxes - Time Limit Error
Solved ^)
I was using Scanner - It is too slow
I was using Scanner - It is too slow

12390 - Distributing Ballot Boxes
Hi
I solved this problem within priority queue. But is is too slowly.
I have trying a lot of different approaches but without any results.
I believe there is known algorithm, but I don't know which one?
I solved this problem within priority queue. But is is too slowly.
I have trying a lot of different approaches but without any results.
I believe there is known algorithm, but I don't know which one?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12390 - Distributing Ballot Boxes - how to solve
dichotomic search
Check input and AC output for thousands of problems on uDebug!
Re: 12390 - Distributing Ballot Boxes - RUNTIME ERROR
Thanks,
I have re-written my solution, but I get RE now. Why?
I have re-written my solution, but I get RE now. Why?
Code: Select all
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
try {
int cities;
int boxes;
String line;
while ((line = reader.readLine()) != null) {
if (line.contains("-1 -1")) {
break;
}
if (line.trim().isEmpty()) {
continue;
}
StringTokenizer tokenizer = new StringTokenizer(line);
cities = Integer.valueOf(tokenizer.nextToken().trim());
boxes = Integer.valueOf(tokenizer.nextToken().trim());
int[] populationArray = new int[cities];
long totalPopulation = 0;
for (int i = 0; i < cities; i++) {
int population = Integer.valueOf(reader.readLine().trim());
populationArray[i] = population;
totalPopulation += population;
}
Arrays.sort(populationArray);
int a = (int) (totalPopulation / boxes);
int index;
int fromIndex = 0;
while ((index = getIndex(populationArray, a, fromIndex)) - fromIndex != 0) {
a = getExpectedValue(index, populationArray, boxes - index);
fromIndex = index;
}
int max = 0;
if (fromIndex != 0) {
max = populationArray[fromIndex - 1];
}
for (int i = fromIndex; i < populationArray.length; i++) {
int population = populationArray[i];
int buckets = (int) Math.round((double) population / a);
int maxPopulation = population / buckets;
if (population % buckets != 0) {
maxPopulation++;
}
if (maxPopulation > max) {
max = maxPopulation;
}
}
writer.write(String.format("%d\n", max));
}
writer.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
private static int getExpectedValue(int index, int[] populationArray, int boxes) {
long total = 0;
for (int j = index; j < populationArray.length; j++) {
total += populationArray[j];
}
return (int) (total / boxes);
}
private static int getIndex(int[] totalPopulation, int a, int fromIndex) {
int lo = fromIndex;
int hi = totalPopulation.length - 1;
int index = 0;
while (hi - lo > 0) {
index = lo + (hi - lo) / 2;
int city = totalPopulation[index];
if (city > a) {
hi = index - 1;
} else {
lo = index + 1;
}
}
return index;
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12390 - Distributing Ballot Boxes - how to solve
My guess would be a divide by zero.
Check input and AC output for thousands of problems on uDebug!
Re: 12390 - Distributing Ballot Boxes - how to solve
I have no idea how it could be division by zero.
I can't think , what case may lead to this state.
Perhaps there is other reason of RE
I can't think , what case may lead to this state.
Perhaps there is other reason of RE

-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12390 - Distributing Ballot Boxes - how to solve
Your RE is caused by division by zero on line 70. There is a test case in the judge's input that causes buckets to be zero.
Check input and AC output for thousands of problems on uDebug!
Re: 12390 - Distributing Ballot Boxes - how to solve
Could you please provide this sample, here on by the private message
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 12390 - Distributing Ballot Boxes - how to solve
I don't have the judge's input. I skimmed your code and guessed that there might be a divide by zero causing RE. To confirm this, I modified your code, submitted it, and made it produce a TLE if buckets equals zero right before line 70.
Check input and AC output for thousands of problems on uDebug!