CSES - Number Spiral - Java TLE

Question

My java code for CSES Introductory problem Number Spiral gives TLE for large inputs, like

Input :

100000
170550340 943050741
121998376 943430501
689913499 770079066
586095107 933655238 ...
(First line/number being the number of inputs)

My code is as below:

import java.util.*;
public class numberSpiral {
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 long testN = scanner.nextLong();
 long r=0,c=0;
 while(testN-- > 0){
 r = scanner.nextLong();
 c = scanner.nextLong();
 if (c > r) {
 if (c % 2 == 0) {
 System.out.println(((c - 1) * (c - 1)) + 1 + (r - 1));
 } else
 System.out.println(((c) * (c)) - (r - 1));
 } else {
 if(r % 2 == 0){
 System.out.println(((r) * (r)) - (c - 1));
 } else
 System.out.println(((r - 1) * (r - 1)) + 1 + (c - 1));
 }
 }
 }
}

It works for small inputs. I can't figure out how to optimize it better to reduce time. Time limit is: 1.00 s

Answer 1

I assume you refer to https://cses.fi/problemset/task/1071/ . Your Algorithm itself is fine as far is i can tell.

The Problem is the large amount of inputs that need to need to be read(Testcases=100000), which Scanner cant provide within the 1s time limit. A BufferedReader should offer the performance needed for this.(See https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ for more information). The same might apply to System.out.println in which case it would be better to use a BufferedWriter

Answer 2

usually calculation is faster than branching, so you may also try this:

 if (c > r) {
 int even = c % 2
 System.out.println(((c - 1*even) * (c - 1*even)) + 1*even + (r - 1));
 } else {
 int odd = 1-(r % 2)
 System.out.println(((r - 1*odd) * (r - 1*odd)) + 1*odd + (c - 1));
 }