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 rewritten my solution, but I get RE now. Why?
I have rewritten 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!