11
\$\begingroup\$

I am solving the following problem on code chef:

\$N\$ Soldiers are lined up for a memory test. They are numbered from 0 to N-1 from left to right.
In the test, there are \$M\$ rounds. In each round, Captain selects one position. Soldier at that position will be numbered 0. All the soldiers to the right of selected position will be numbered one greater than the soldier to his left. All the soldiers to the left of selected position will be numbered one greater than the soldier to his right. eg. if \$N = 6\$ and selected position is 3, then the numbering will be \$[3, 2, 1, 0, 1, 2]\$.

After \$M\$ rounds, Captain asked each soldier to shout out the greatest number he was assigned during the \$M\$ rounds. In order to check the correctness, Captain asked you to produce the correct values for each soldier (That is the correct value each soldier should shout out).

Input
- The first line of the input contains an integer \$T\$ denoting the number of test cases.
- First line of each test case contains two integers, \$N\$ and \$M\$
- Second line of each test case contains \$M\$ integers, the positions selected by Captain, in that order.

Output
For each test case, output one line with \$N\$ space separated integers.

Constraints:
\$1 ≤ T ≤ 10^4\$
\$1 ≤ N ≤ 10^5\$
\$1 ≤ M ≤ 10^5\$
\$1 ≤ \sum{N} ≤ 10^5\$
\$1 ≤ \sum{M} ≤ 10^5\$
\$0 ≤ {Positions\ selected\ by\ captain} ≤ N-1\$

Example

Input

2
4 1
1
6 2
2 3

Output

1 0 1 2
3 2 1 1 2 3

I have solved the problem using Java and my code runs perfectly fine in my PC but unfortunately I am getting Time Limit Exceeded for this code:

import java.io.*;
class ANUARM{
  public static void main(String[] s) throws Exception{
  BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
  int testCases = Integer.parseInt(input.readLine());
  for(int i = 0 ; i < testCases ; ++i){
     String[] num = input.readLine().split(" ");
     int n = Integer.parseInt(num[0]);
     int m = Integer.parseInt(num[1]);
     int[] array = new int[n];
     String[] pos = input.readLine().split(" ");
     for(int j = 0 ; j<m ; ++j){
      int temp = Integer.parseInt(pos[j]);
      for(int k = 0 ; k<n ; ++k){
       int posAquired = temp - k;
        if(k > temp)
         posAquired = k-temp;
         if(posAquired > array[k])
          array[k] = posAquired;
      }
     }
     for(int a : array){
      System.out.print(a+" ");
     }
     System.out.println();
    }
  }
}

First I was using Scanner but I saw in FAQ that Scanner is slow, so I used BufferedReader BUT still I am getting TLE. Can anyone tell me where I can optimize my code as well as the do's-and-don'ts of optimization?

\$\endgroup\$
10
\$\begingroup\$

Scanner is slow compared to BufferedReader but that's not the main bottleneck of this code. (The speed of parsing the input is hardly ever the bottleneck in programming contests.)

The main bottleneck is that for every position shouted out, you iterate over every soldier. The more positions are shouted out, the more wasteful this gets.

Realize that the captain could shout out a million positions, but all that will matter is the minimum and maximum positions. Let's say there are 7 soldiers, and the captain shouts out a 1000 numbers, but always between 3 or 4:

0 1 2 { 3 4 } 5 6

Regardless of how many numbers he shouted, the greatest numbers assigned to soldiers will be:

4 3 2 { 1 1 } 2 3

This logic will simplify the algorithm:

  • Find the min and max number shouted by the captain
  • Iterate over the soldiers (just one pass!), and assign the largest of \$| i - max |\$ and \$|i - min|\$

Simple implementation in Java, given the number of soldiers, and the positions shouted out by the captain:

private int[] solution(int num, int... positions) {
    int[] soldiers = new int[num];
    int max = 0;
    int min = num - 1;
    for (int pos : positions) {
        min = Math.min(min, pos);
        max = Math.max(max, pos);
    }
    for (int i = 0; i < soldiers.length; ++i) {
        soldiers[i] = Math.max(Math.abs(i - max), Math.abs(i - min));
    }
    return soldiers;
}

Unit tests:

@Test
public void testBasic1() {
    assertArrayEquals(new int[]{1, 0, 1, 2}, solution(4, 1));
}

@Test
public void testBasic2() {
    assertArrayEquals(new int[]{3, 2, 1, 1, 2, 3}, solution(6, 2, 3));
}

Last but not least, the original code was poorly formatted and not well decomposed to methods. It's best to separate the parsing and the main logic, to see clearer, so you can focus better on the main implementation. Separating the parsing and the main logic sometimes sacrifices a bit of performance or requires more memory, but in my experience never so much to run out of time / memory. By writing in a clean way you effectively gain more coding time to focus on the real problem, and find the trick to optimize the algorithm.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanx..it worked! \$\endgroup\$ – Nawed Shaikh Oct 20 '14 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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