Time limit exceeds in this simple program [closed]

Question

Link to problem: https://www.codechef.com/JUNE20B/problems/EVENM

Iam trying to solve a simple problem challenge, but getting TLE.

I had a different approach earlier, so tried this, again with no success.

I know this can be optimized further but can't figure how.

The problem: Print the matrix in a format depending upon the input.

If input is divisible by 2 then in this format:

else in this format:

Time limit: 1 sec

nxn matrix, where 1<=n<=1000

My code:

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int cases = Integer.parseInt(br.readLine());
    for(int i = 0; i < cases; i++) {
        int n = Integer.parseInt(br.readLine());
        if(n%2==1) {
            int cur = 0;
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) {
                    System.out.print(++cur);
                    if(k!=n) System.out.print(" ");
                }
                System.out.println();
            }
        }
        else {
            int first = 0;
            boolean b = true;
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) {
                    if(b) System.out.print(++first);
                    else System.out.print(first--);
                    if(k!=n) System.out.print(" ");
                }
                if(b)b = false;
                else b = true;
                first+=n;
                System.out.println();
            }
        }
    }

According to the judge, this is taking slightly more than 2 seconds, which is double the time expected, so this is totally un-optimized

Answer 1

First off I think your code can be adjusted:

Booleans to keep track of even or odd size of matrix and even or odd numbered rows allows you to use one set of loops and simply change which set of numbers are printed.

To test for odd or even I like (num & 1) if the result is 0 it's even, 1 it's odd. I think using modulus for this is inefficient.

Changing the code to using one loop could look something like this:

static void solution(InputStream sIn, PrintStream sOut) throws IOException {
    Scanner sc = new Scanner(sIn);
    int cases = sc.nextInt();
    for (int c = 0; c < cases; ++c) {
        int size = sc.nextInt();
        boolean evenM = (size & 1) == 0;
        for (int row = 0; row < size; ++row) {
            boolean oddR = (row & 1) == 1;
            for (int col = 0; col < size; ++col) {
                boolean last = col == size - 1;
                int num = (row * size) + col + 1;
                if (evenM && oddR) {
                    num = (num - col) + (size - col) - 1;
                    if (last) {
                        sOut.print(num);
                    } else {
                        sOut.printf("%d ", num);
                    }
                } else if (last) {
                    sOut.print(num);
                } else {
                    sOut.printf("%d ", num);
                }
            }
            sOut.println();
        }
    }
}

All that being said, I think your main problem is Java itself, or the implementation that CodeChef is using. When I port this code to c++ it works just fine and can be submitted successfully.