...

In continuation of the previous post .

I will make a reservation right away: no, I'm not trying to humiliate Java or C ++ with these pictures . Or even to say that such a language is better than some other language. I just want to show that for different tasks different languages ​​are more convenient. In this topic, you can read tips on choosing an IDE for Olympiad programming and there will be a part of cases when Java is more convenient.

IDE

It would seem, what is the IDE? But to what: the computer on which you will write on the ACM will not be yours at all. And quite the same as the other 9000 competitors. And it is quite possible that your favorite, perhaps exotic, development environment will not be there. And there will be this:

• Borland Delphi 7.0 - missing since 2009
• Microsoft Visual Studio 2005 Express Edition, C / C ++
• Java 2 SDK 6.0
• Eclipse
• Far Manager 1.7b5
• MinGW (GNU C / C ++)

So the choice is not great. Morally obsolete version of MS VS and Eclipse. By the way, always the latest version. Well, Far, but this is not IDE. Therefore, I will gain impudence and will write exclusively about Eclipse.

Templates

Perhaps the first thing we were taught was to create a template in Eclipse. Templates allow you to quickly, very quickly create a framework for writing a program. Such that it is enough to write three or four letters on behalf of the template, press a combination of buttons (Ctrl + Spacebar) and find a ready-made framework for the program in the editor window. How to create them, you can read here .
')

Buttons + other buttons (+ more other buttons)

Keyboard shortcuts are what Olympiad users love Eclipse for. You can always press Ctrl + Spacebar and use the great auto-substitution (Visual Studio users know this under the name IntelliSense). You can select the code, press Ctrl + / And pro / uncomment it. You can press Ctrl + Alt + ↓ or ↑ to copy the current line up or down, you can press Ctrl + D to delete the current line ... Or you can go into the settings, find the list of combinations there, and remember the ones you want.

How and when to write in Java

The first thing you need to figure out with the Olympiad programming in Java is to grab a big stack for yourself, for which you can run in a separate thread. The second is to learn how to quickly read and write data. I will provide my current template for Eclipse, providing it with pre-comments. If something is not clear, then I can explain.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;
// ${primary_type_name} - , Eclipse. - .
// , .
public class ${primary_type_name} implements Runnable {
StringTokenizer st; // . -
BufferedReader in ; // -
PrintWriter out ; // , .

public static void main( String [] args) {
new Thread( new ${primary_type_name}()).start(); // , .
}

public void run() {
try {
in = new BufferedReader( new FileReader( "${primary_type_name}.in" ));
out = new PrintWriter( new FileWriter( "${primary_type_name}.out" ));
solve();
} catch (Exception e) {
// - . 9000 , .
System.exit(9000);
} finally {
// .
out .flush();
out .close();
}
}
//
String nextToken() throws IOException {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer( in .readLine());
}
return st.nextToken();
}
// 32-
int nextInt() throws NumberFormatException, IOException {
return Integer.parseInt(nextToken());
}
//...
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(nextToken());
}
//... ?
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(nextToken());
}

void solve() throws NumberFormatException, IOException {
// .
}
}


Fine! Now we are ready to solve our (possibly, the first) Olympiad problem in Java. Choose something simple, but it requires exactly this language. The path will be No. 1196 from Thymus. Read the condition carefully and think a bit about the solution before returning to this article. Suppose for a second that among the readers some clever enthusiast immediately tried to solve the problem; and solve it like this:

int n = nextInt();
int [] teachers = new int [n];
for ( int i = 0; i < n; i ++)
teachers[i] = nextInt();
int m = nextInt();
int result = 0;
for ( int i = 0; i < m; i ++) {
int students = nextInt();
for ( int j = 0; j < n; j ++)
if (teachers[j] == students) {
result ++; break ;
}
}
out .println(result);

Of course, he got TL (Time Limit exceeded) , because his program works for O (n⋅m) . By the way, if the previous statement says nothing to you, it would be good to read about O-symbolism . Our enthusiast decided to think better, read the relevant literature, or looked at different sites (see last post), and found as many as two ways to solve the problem faster. The first one uses the built-in balanced Java binary tree :

int n = nextInt();
TreeSet<Integer> teachers = new TreeSet<Integer>();
for ( int i = 0; i < n; i ++)
teachers.add(nextInt());
int m = nextInt();
int result = 0;
for ( int i = 0; i < m; i ++)
if (teachers.contains(nextInt()))
result ++;
out .println(result);

As you can see, it turned out even less code than in the decision "in the forehead." The second method uses the built-in quick sort and binary search of Java:

int n = nextInt();
int [] teachers = new int [n];
for ( int i = 0; i < n; i ++)
teachers[i] = nextInt();
Arrays.sort(teachers);
int m = nextInt();
int result = 0;
for ( int i = 0; i < m; i ++) {
int students = nextInt();
int pos = Arrays.binarySearch(teachers, students);
if (pos > 0 && pos < teachers.length && teachers[pos] == students)
result ++;
}
out .println(result);

This method is a bit more voluminous, since binarySearch returns either the position of an element in an array, or the place where it should be inserted, if it is not there; but it still goes away completely.
Both solutions obviously work as O (n⋅logn + m⋅logn) = O ((m + n) logn) . And if it is not obvious, then it would be necessary to read about binary trees, quick sorting and binary search.

To be Continued

... Clicking on the "preview" button, I was horrified by the abundance of text, and decided that it was worth splitting this topic into two topics. So wait in the second part of the story about how and when to write in C / C ++ and analysis of the characteristic problem.

* All source code was highlighted with Source Code Highlighter .