I am trying to do these online competitions where you get the given exercise and are supposed to upload the source file. The site is not in English so I will try to summarize the exercise.
The first line of input states P, the number of problems ( 1 <= P <= 100 ). Subsequently, there are two lines for each problem. The first contains numbers X and Y ( 1 <= X, Y <= 100000) — X being number of elements and Y being the difference I am looking for. On the next line there are X numbers (0 <= N <= 100000) divided by a space. For every problem, I am supposed to print the number of pairs that differ by Y.
As an example input :
2
5 2
1 5 3 4 2
5 4
6 3 6 2 2
Example output:
3
4
I wrote a simple programme that did the thing but when I uploaded the source file I got "time limit exceeded" error. After that I discovered that my program is unable to handle big input. I tried to move on to the next exercise but I discovered almost all of them have big inputs. I tried to improve it myself, then I tried to google it, but sadly I still cannot get past the error. This is the code I ended up with :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 80000
int compare(const void *a, const void *b);
int main(int argc, char const *argv[]) {
char buffer[SIZE];
unsigned int numberOfGames, numberOfStudents, wantedDifference;
unsigned int numberOfDifferentPairs;
unsigned int counter;
size_t i, j;
scanf("%u", &numberOfGames);
while (numberOfGames--) {
scanf("%u %u", &numberOfStudents, &wantedDifference);
scanf("\n");
unsigned long long int *studentsHeights =
(unsigned long long int *)malloc(sizeof(unsigned long long int) * numberOfStudents);
counter = 0;
numberOfDifferentPairs = 0;
studentsHeights[counter] = 0;
while (counter < numberOfStudents) {
fgets(buffer, SIZE, stdin);
size_t stringSize = strlen(buffer);
for (i = 0; i < stringSize; i++) {
if (buffer[i] == ' ' || buffer[i] == EOF || buffer[i] == '\n') {
counter++;
if (counter < numberOfStudents)
studentsHeights[counter] = 0;
} else {
studentsHeights[counter] =
studentsHeights[counter] * 10 + (buffer[i] - '0');
}
}
}
qsort(studentsHeights, numberOfStudents, sizeof(unsigned int), compare);
for (i = 0; i < numberOfStudents - 1; i++) {
unsigned int lastAddition;
if (studentsHeights[i] == studentsHeights[i - 1]) {
numberOfDifferentPairs += lastAddition;
continue;
} else {
lastAddition = 0;
}
for (j = i + 1; j < numberOfStudents; j++) {
if ((studentsHeights[j] - studentsHeights[i]) == wantedDifference) {
numberOfDifferentPairs++;
lastAddition++;
}
}
}
printf("%u\n", numberOfDifferentPairs);
}
return 0;
}
int compare(const void *a, const void *b) {
if (*(unsigned int *)a < *(unsigned int *)b)
return -1;
else if (*(unsigned int *)a == *(unsigned int *)b)
return 0;
else
return 1;
}
I know I am probably doing some trivial mistake but if you could point it out for me I would be really grateful.
There are the variables I used:
- P = numberOfGames
- X = numberOfStudents
- Y = wantedDifference
- N = studentsHeights