-4
\$\begingroup\$

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:

enter image description here

else in this format:

enter image description here

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

\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Code Review. The title is of your question is too general and can be applied to a lot of questions present on the site, please change it to describe the problem. If you have a link to the programming challenge please include it, at the moment without looking the code at least for me it is unclear the description of the problem. \$\endgroup\$ – dariosicily Jun 15 at 9:36
  • \$\begingroup\$ (I don't see anything in the algorithm that could be improved to lower asymptotic time.) \$\endgroup\$ – greybeard Jun 15 at 10:41
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.