SPOJ FASHION challenge

Question

I just started attempting SPOJ problems. And I'm aware of Java using more memory and time compared to most of the other languages. But even some of the solutions in Java have better results than my accepted code. And it hurts!

Here is my accepted code for FASHION with TIME: 0.41 and MEM: 4284M.The best solution in Java for the same question has TIME: 0.04 and MEM: 1398M.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int i = 0;
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while (testCases > 0) {
            int modelsWithMe = sc.nextInt();
            int[] men = new int[modelsWithMe];
            int[] women = new int[modelsWithMe];
            int hotnessSum = 0;
            for (i = 0; i < modelsWithMe; i++) {
                men[i] = sc.nextInt();
            }
            for (i = 0; i < modelsWithMe; i++) {
                women[i] = sc.nextInt();
            }
            Arrays.sort(men);
            Arrays.sort(women);
            for (i = 0; i < modelsWithMe; i++) {
                hotnessSum = hotnessSum + men[i] * women[i];
            }
            System.out.println(hotnessSum);
            testCases--;
        }

    }
}

I did see a few questions on performance, such as this and this. I am doing a few of it and some are not applicable for this solution's point of view. Here, maybe, I can read the entire line at once and split the string instead of calling nextInt each time and reduce I/O operations. What else can I do to reach the level of efficiency and speed as that of top answers? Best practices may be?

Answer 1

you can abuse the fact that

All hotness ratings are (integers) on a scale of 0 to 10

Just keep track of how many men/women there are of each score. This looks something like this:

int[] men = new int[11];
for (i = 0; i < modelsWithMe; i++) {
    men[sc.nextInt()]++;
}

Then for the score you need to figure out how to combine the pairs given those frequency arrays.

int m = 10;
int w = 10;
while(m >= 0){
    while(men[m] == 0) {
        m--;
    }
    while(women[w] == 0){
        w--;
    }
    hotnessSum += m*w;
    men[m]--;
    women[w]--;
}

This calculation can still be optimised greatly. If you have 21 man score 10 and 30 women score 10 for example, you could add 21*10*10 to the total and reduce the frequencies of both by 21 instead of looping 21 times to achieve the same total. I'll leave turning this into code to you.

Answer 2

In addition to what you mentioned, here are a few things that will improve speed.

Use BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); in stead of scanner.

This way, you read per line and use StringTokenizer.

And in situations where we are trying to minimize run time, your variables such as hotnessSum can be just s. (It's not best practice for software engineering, but if you are competing for run time, shorter variable names definitely will help.)

Answer 3

My guess is that most time is spent in String conversion and or IO. I made a version with the same idea as @Imus, and switched from Scanner to a custom Scanner which uses String.split() and BufferedReader

Current time is 0.28.

Then it occurred to me you don't need to iterate over each bin, but can use the overlapping count and multiply the hotness by that part.

Because bins with size 0 don't count towards the total, we don't need while loops to check for empty bins. Just process them all along.

I re-use existing arrays to prevent object-creation.

I'm pretty sure the main loop is as fast as can be, so the slowness is due to the read-and-parse part of the input.

public class Main {

    public static class Scanner {
        BufferedReader bi;
        String line;
        String[] linesplit;
        int index;

        public Scanner(InputStream in) {
            bi = new BufferedReader(new InputStreamReader(in));
        }

        int nextInt() throws IOException {
            if (linesplit == null) {
                line = bi.readLine();
                if (line == null) {
                    throw new RuntimeException("End of input");
                }
                linesplit = line.split("\\s");
                index=0;
            }
            int i = Integer.parseInt(linesplit[index]);
            index++;
            if (linesplit.length == index)
            {
                linesplit = null;

            }
            return i;

        }
    }

    public static void main(String[] args) throws IOException {
        int i = 0;
        Scanner sc = new Scanner(System.in);

        int testCases = sc.nextInt();

        int[] menHotnessBins = new int[11];
        int[] womenHotnessBins = new int[11];

        while (testCases > 0) {
            int modelsWithMe = sc.nextInt();
            Arrays.fill(menHotnessBins, 0);
            Arrays.fill(womenHotnessBins, 0);

            for (i = 0; i < modelsWithMe; i++) {
                int hotness = sc.nextInt();
                menHotnessBins[hotness]++;
            }
            for (i = 0; i < modelsWithMe; i++) {
                int hotness = sc.nextInt();
                womenHotnessBins[hotness]++;
            }
            int womenHotnessIndex = 10;
            int menHotnessIndex = 10;
            int totalHotness = 0;
            while (modelsWithMe>0) {
                //We now have 2 bins with values.
                int mBinSize = menHotnessBins[menHotnessIndex];
                int wBinSize = womenHotnessBins[womenHotnessIndex];

                int min = Math.min(mBinSize, wBinSize);

                totalHotness += min * (menHotnessIndex * womenHotnessIndex);


                // reduce the hotnessbins by min
                menHotnessBins[menHotnessIndex]-=min;
                womenHotnessBins[womenHotnessIndex]-=min;

                if (menHotnessBins[menHotnessIndex]==0) {
                    menHotnessIndex--;
                }
                if (womenHotnessBins[womenHotnessIndex] == 0) {
                    womenHotnessIndex--;
                }

                modelsWithMe-=min;
            }
            System.out.println(totalHotness);
            testCases--;
        }

    }
}

Answer 4

I'm not sure if this is exactly reason but - when I put the same code with changed name of class this with name Main have better time. It means when I used "public class Main" time was 0.06, and when I used "class MyName" it was 0.08