SPOJ FASHION challenge

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?

• It would help if you would copy the assignment text here as a quote, so we don't need to rely on the external link staying up. Jun 2 '17 at 8:27

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.

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.)

• Got any references for the shorter variable name claim? (Which I find hard to believe...)
– mtj
Jun 3 '17 at 4:30
• I would also like to see some source on shorter variable names speeing up the code. And also is StringTokenizer better than String.split()?
– RBz
Jun 5 '17 at 4:47
• @mtj I'm actually a web dev. so for us, a large project, if we run minify tasks on code (which those minify task essentially reduce varible names to one character) and it's faster performance to us. I don't know whether it would be the same for Java. but if the OP try that out, I think the online Judge will reduce process time by a few milliseconds. because the run time discussed in the post is from this particular website. I could be wrong. (when I was in programming competitions, I would never write complicated variable names. because these programs are not for other people to read.) Jun 5 '17 at 19:01
• @RBz, do u notice faster speed with StringTokenizer and shorter variable name? a few years ago, I was on our university prog team, our coach told us these things. I guess I took these advise for granted. Let us know if these things didn't help with your run time. Jun 5 '17 at 19:07

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 {
String line;
String[] linesplit;
int index;

public Scanner(InputStream in) {
}

int nextInt() throws IOException {
if (linesplit == null) {
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--;
}

}
}


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

• If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review Nov 7 '17 at 13:51
• This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review Nov 7 '17 at 14:12
• @Graipher This doesn't seem to be a new question, this seems to be a suggestion for how to improve performance. It's not a good suggestion, but it is a suggestion. Nov 7 '17 at 15:15
• @TobySpeight This seem to be a suggestion for how to improve performance. It's not a good suggestion, but it is a suggestion. Nov 7 '17 at 15:15
• @SimonForsberg Yeah, you might be right. I read it as implicitly asking why this is the case. Nov 7 '17 at 15:16