Solution to Chef and Squares challenge, timing out in Java but not in C++

Question

I was solving a problem on codechef (online judge and contest organizer). I was writing my code in Java and was getting TLE at last testcase where as I wrote the same code in C++ and it was accepted. Now I know C++ is faster then java but If anyone could help me optimize my Java code ?

Here is the question

Chef has finished his freshman year in college. As a present, his parents gave him a new problem to solve: Chef has to fill a K x K square grid of integers in a certain way. Let us say that such a grid is valid if:

• Each cell contains an integer from 1 and K (inclusive).
• No integer appears twice in the same row or the same column.

Let F(K) be maximum possible distance between the center of the square and the closest cell that contains 1, among all possible squares with the side length K.

Here, we use the following notions:

• The distance between cell (x, y) and (i, j) is equal to |x-i|+|y-j|.
• The center of a K ×ばつ K square is cell ((K+1)/2, (K+1)/2) for odd K.

Input

The first line of input contains a single integer T denoting the number of test cases. Each test case consists of a single line containing a single odd integer K.

Output

For each test case, print K lines each consisting of K space separated integers giving some square grid where the distance from the center of the grid to the nearest 1 is exactly F(K). If there's more than 1 possible answer output any of them.

Constraints

K_i is odd.

Subtask #1 (10 points):

1 ≤ T ≤ 50
1 ≤ K_i ≤ 5

Subtask #1 (90 points):

1 ≤ T ≤ 10
1 ≤ K_i < 400

Example

Input:

2
1
3

Output:

1
3 2 1
1 3 2
2 1 3

Here is my code in Java

import java.util.*;
import java.io.*;
public class Main { 
 public static void main(String[] args) throws IOException{
 BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
 int t = Integer.parseInt(sc.readLine());
 while(t-- > 0){
 int n = Integer.parseInt(sc.readLine()); 
 int center = (n + 1)/2 ; 
 for(int i = 0; i < n; i++){
 int temp = center;
 for(int j = 0; j < n; j++){
 System.out.print(temp+" "); 
 temp++;
 if(temp > n)
 temp = 1; 
 } 
 center--;
 if(center < 1)
 center = n;
 System.out.printf("%n");
 }
 } 
 } 
}

Here is my code in c++

#include <iostream>
using namespace std;
int main(void){
 int t;
 cin>> t;
 while(t--){
 int n;
 cin>>n;
 int center = (n + 1)/2 ; 
 for(int i = 0; i < n; i++){
 int temp = center;
 for(int j = 0; j < n; j++){
 cout<<temp<<" "; 
 temp++;
 if(temp > n)
 temp = 1; 
 } 
 center--;
 if(center < 1)
 center = n;
 cout<<"\n";
 }
 } 
 return 0;
}

• Loki Astari: add: std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr); At the beginning of main() to make it go faster.
• lord_ozb: This works in java? I am getting a compilation error .
• Loki Astari: No: That is for C++

Answer 1

To me the implementations look identical. But one thing jumps out at me:

If n is big then you will do a lot of string concatenations here: System.out.print(temp+" "); which may look inconspicuous but if n=399, then you will do around 160k useless string concatenations. Try to use a StringBuilder and build all your output into it and then dump it in one go when you're done. Or simply change to:

System.out.print(temp);
System.out.print(' ');

Also I think System.out.format("%n"); is a bit odd why not simply do System.out.println();?

And temp is a really bad variable name. I suggest you change it.

• lord_ozb: I read on stackoverflow that System.out.printf("%n); is faster than System.out.println();. But I am not still sure about it. Anyways thanks a lot for your answer! :)
• lord_ozb: Instead of printing everything I used StringBuilder and then kept on appending everything and then at last printed a single string and it managed to get accepted. Finally I can sleep in peace .

Answer 2

My first observation was the same as @EmilyL.'s: that you're performing unneeded string concatenations. Upon investigation, however, it turned out to be a loser to substitute two invocations of System.out.print() methods for a string concatenation plus one method invocation -- the result ran about 70% slower than the original code for me.

It took a while for the lightbulb to turn on, but that slowdown is a key symptom of the underlying problem: System.out is unbuffered, at least when it's not connected to a terminal. In a comment you described addressing the problem by building the output in a StringBuilder and then printing it all at once. That's a viable mechanism for buffering manually, but cleaner and easier to integrate into your original solution would have been to wrap a buffered stream around System.out and print to that. In other words, at the top of main() add ...

PrintStream out = new PrintStream(new BufferedOutputStream(System.out));

... and everywhere else print to out instead of to System.out(). Doing that cut my run time by more than 50% relative to the original code, for a maximal-size test set.

• Olle Kelderman: bonus: use System.setOut(out) ;) (and I could be wrong, but since you're in a BufferedOutputStream now, I think you'll have to call System.out.flush() at the end)
• Emily L.: I was not aware that System.out is unbuffered. I learned something new today!
• lord_ozb: Using PrintStream out = new PrintStream(new BufferedOutputStream(System.out)); the execution time is 0.36 sec whereas with StringBuilder and System.out.print(); it 0.16 sec. But Thank you for your answer, I learned something new today :)