I think the bottleneck when participating in competitive programming in Java is the limitation of execution time. In some cases, the platform I'm participating in takes 20 to 20 times longer than C ++ 14 and 4 times faster than Python3 (Java8 OpenJDK 1.8.0).
Even though I came up with the logic to solve the problem, I often feel that I can't finish it because the execution time is limited.
Therefore, I would like to share the contents of the tough issues that I recently encountered and the measures and policies for such issues. It is a note of a beginner coder (not humble), so please feel free to comment.
- Given the inputs of 2 or more even numbers A and 1 or more A natural numbers, the center of the set for an odd number of numbers, with each A integer removed by one in the input order. Output the values in order. *
- However ・ It is guaranteed that A is always 10 ^ 5 or less. -It is guaranteed that all inputs are integers. *
- Processing example: * input *6 (==A) 7 1 4 2 6 9 (Entering 1 or more natural numbers given (given as a test case)) *
output
Click here for a description of the median https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%A4%AE%E5%80%A4
From the content of the problem
**-Store the entered value in a numeric array (in Array or ArrayList). ** ** **-Delete elements in order from the array. ** ** **-Sort the array. ** ** ** ・ (A / 2)-Output the first value. ** **
You can see the flow of processing. That means
-Delete elements in order from the array. -Sort the array. ・ (A / 2)-Output the first value. You just have to write the iterative process.
Here is the code I wrote first.
Main.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(s.nextInt());
}
ArrayList<Integer> arrCopy = (ArrayList<Integer>) arr.clone();
for(int j=0;j<n;j++){
/*★*/ arr.remove(j);
/*★*/ Collections.sort(arr);
System.out.println(arr.get((n / 2) - 1));
/*★*/ arr = (ArrayList<Integer>) arrCopy.clone();
}
}
}
However, this code will exceed the execution time in the production environment. Since the List is deleted, sorted, and duplicated for A times at the position of ★, it is out. The ArrayList class has a variable number of elements, but has the property that it tends to run slower than the Array class.
By the way, the content of the task was to output the median value of each. And you have to delete the elements one by one and specify the median, but you shouldn't use ArrayList. …
In fact, the median of this problem, ** no matter how many elements there are, there are two candidates **.
For example
1，2，3，4，5，6
Given the number, even if you remove the numbers one by one from 1 to 6, the median will always be either ** 3 ** or ** 4 **.
When 1,2,3 are deleted, 4 is the median, When 4,5,6 is deleted, 3 is determined as the median.
Here is the code I wrote after taking this into account.
Main.java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int[] sortedArr = new int[n];
for (int i = 0; i < n; i++) {
sortedArr[i] = s.nextInt();
}
int[]originArr=sortedArr.clone();
Arrays.sort(sortedArr);
int firstNum=sortedArr[(n/2)-1];
int secondNum=sortedArr[n/2];
for(int j=0;j<n;j++){
if(originArr[j]<secondNum){
System.out. println(secondNum);
}
else{
System.out.println(firstNum);
}
}
}
}
It is the same up to the point where the entered numbers are stored in the array (although the array class is different). After that, (n / 2)-store the 1st and n / 2nd numbers as int values, respectively. It then compares the deleted number with the smaller number of median candidates and outputs an arbitrary value.
In this code, you don't have to manipulate the array in the output for statement. And even in Java, even if the elements of the array are variable, you can keep the time constraint.
First of all, as a first outlook, it is wrong to assume that the median value in each array after deletion changes dynamically. The factor that made such a premise is the impatience that "I have to write the code quickly and submit it".
I think competitive programming is a special environment for coders, and for most participants I have to write code that works in tough competition times. In other words, it's easy to get impatient because you want to write code quickly.
For those who are accustomed to some extent (those who can answer questions other than those that can answer only a few percent of the total), the required time is more important factor in determining the participant ranking than the number of correct answers to the question. Even more so.
However, in a constrained environment, in addition to participating in competitive programming such as Java in a "disadvantageous" language, ・ Write multiple processes in a repeating sentence, ・ Use convenient classes
rather than, ・ Examine the law regarding the answer ・ Minimize the processing in the repeated statement even if it is used
That is an important strategy, which is also a commandment to me, and I wanted to share it this time.
That is all. If you have any mistakes or other solutions, please let us know in the comments.
Recommended Posts