12390 - Distributing Ballot Boxes

All about problems in Volume 123. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

12390 - Distributing Ballot Boxes - Time Limit Error

Post by sith » Mon Sep 03, 2012 2:08 pm

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?

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 12390 - Distributing Ballot Boxes - Time Limit Error

Post by sith » Mon Sep 03, 2012 2:37 pm

Solved ^)


I was using Scanner - It is too slow :)

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

12390 - Distributing Ballot Boxes

Post by sith » Tue Sep 04, 2012 2:34 pm

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?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by brianfry713 » Wed Sep 05, 2012 9:50 pm

dichotomic search
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 12390 - Distributing Ballot Boxes - RUNTIME ERROR

Post by sith » Thu Sep 06, 2012 2:40 pm

Thanks,

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;
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by brianfry713 » Thu Sep 06, 2012 11:08 pm

My guess would be a divide by zero.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by sith » Fri Sep 07, 2012 10:00 am

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 :(

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by brianfry713 » Fri Sep 07, 2012 7:57 pm

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!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by sith » Mon Sep 10, 2012 12:57 pm

Could you please provide this sample, here on by the private message

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12390 - Distributing Ballot Boxes - how to solve

Post by brianfry713 » Mon Sep 10, 2012 10:21 pm

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!

Adpa20b!
New poster
Posts: 2
Joined: Wed Apr 01, 2015 6:32 pm

Re: 12390 - Distributing Ballot Boxes

Post by Adpa20b! » Wed Apr 01, 2015 6:36 pm

I have the same problem. Please help.
Ada

Post Reply

Return to “Volume 123 (12300-12399)”