Here is a solution for the problem 534B - Covered Path

Here is my submission in Python: 10688757.

At least that's how I understood the problem by reading other people's solutions here. The only problem with that interpretation though is that there is a sudden jump in the velocity at times 1, 2, ..., t-1, so the velocities look like step functions. This would mean that the acceleration at those times is infinite. Did I misinterpret the problem?

I submitted the problem 20C - Dijkstra? with two different Java compilers. The results are as follows:

Java 7: 7625239 Time: 466 ms Memory: 12400 KB

Java 8: 7625386 Time: 1184 ms Memory: 8500 KB

I expected Java 8 to be faster. However, to my surprise the program runs more than two times slower under Java 8 than under Java 7 which really surprised me! Does anyone have an explanation for this or experienced something similar?

Abstract

Below I will describe how to avoid TLE (timelimit exceeded) when sorting an array in Java. I will describe two methods.

Introduction

When trying to sort an array in Java it is convenient to use Arrays.sort():

long[] arr = {5,3,4,2,1};
Arrays.sort(arr);
// after sorting print arr

However, this method uses quicksort if the array contains elements of primitive datatype such as long or int. Quicksort has on average a runtime of , but keep in mind that the worst-case runtime is O(n²) for arrays that are almost sorted. As a consequence you can get a TLE (timelmit exceeded) by the online judge. Below are two methods that avoid this issue.

Method 1: Use objects (wrapper class)

We will use the wrapper class Long of the primitive datatype long. Given an array long[] arr we will introdue an array Long[] arr_obj. While long[] arr is sorted with quicksort Long[] arr_obj is sorted with mergesort which has a worst-case runtime of . In Java an array with objects is sorted with mergesort when using Arrays.sort().

long[] arr = {5,3,4,2,1};
int n = arr.length;
Long[] arr_obj = new Long[n];
for(int i=0; i<n; ++i){
   arr_obj[i] = new Long(arr[i]);
}
Arrays.sort(arr_obj);
// after sorting print arr_obj

Method 2: shuffling the array before quicksort

We can still use quicksort but in order to avoid the worst-case runtime of O(n²) for an almost sorted array we will first shuffle it and then apply quicksort.

long[] arr = {1,2,3,5,4};
shuffleArray(arr);
Arrays.sort(arr);
// after sorting print arr

The function shuffleArray() is given by

void shuffleArray(long[] arr){
        int n = arr.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n-i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }   
}

References

[1] [More On Shuffling An Array Correctly](http://blog.ryanrampersad.com/2012/03/more-on-shuffling-an-array-correctly/) – blog post by Ryan Rampersad.

[2] [Why java Arrays use two different sort algorithms for different types?](http://stackoverflow.com/questions/3707190/why-java-arrays-use-two-different-sort-algorithms-for-different-types) (discussion on stackoverflow.com)

[3] Java doc on [quicksort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(long[])) and [mergesort](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])).

My submission for 283A - Cows and Sequence did not pass the system test because it was not efficient enough, in particular I had to update the first a_i elements by adding x_i. Later, Akshai told me how to avoid this.

Example:

Suppose you have the sequence 0,1,2,3,4,5 and you have to add x = 7 to the first a = 3 elements. What you do is you store an array "added_X" that keeps track of the added x values. added_X is initialized with 0. We will also keep a variable "sum" that keeps track of the total sum of elements in the sequence array.

sequence: 0,1,2,3,4,5
added_X:  0,0,0,0,0,0
sum=15

Now, we somehow have to add x=7 to the first a=3 elements. We could change the sequence array but instead we store that information in the added_X array by setting added_X[a-1]+=x where added_X is 0-indexed:

sequence: 0,1,2,3,4,5       // not changed
[actual]: 7,8,9,3,4,5       // <-- not stored and only shown for illustration purposes
added_X:  0,0,7,0,0,0        // added_X[a-1]+=x, i.e. added_X[2]+=7 
sum=sum+(x*a)=15+(7*3)=36   // change sum

Now, to illustrate why the array "added_X" is so useful, we will remove the last elements.

1) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 36-5-0 = 31
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0=0

With this last operation we carry the information about the added x values to the left because we know that all numbers to the left in the sequence have been increased by x.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2,3,4 
[actual:] 7,8,9,3,4       
added_X:  0,0,7,0,0       
sum=31

2) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 31-4-0 = 27
added_X[last-1] = added_X[last-1] + added_X[last] = 0+0 = 0

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2,3 
[actual:] 7,8,9,3       
added_X:  0,0,7,0       
sum=27

3) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 27-3-0 = 24
added_X[last-1] = added_X[last-1] + added_X[last]

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1,2 
[actual:] 7,8,9       
added_X:  0,0,7       
sum=24

The next removal will make clear why the array added_X is so useful

4) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 24-2-7 = 15
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0,1 
[actual:] 7,8       
added_X:  0,7   // <--- Note how "information" is passed to the left       
sum=15

5) Remove last element: Perform the following operations:

sum = sum - sequence[last] - added_X[last] = 15-1-7 = 7
added_X[last-1] = added_X[last-1] + added_X[last] = 0+7 = 7

With this last operation we carry the information about the added x values to the left.

Updated (last elements of sequence and added_X have been removed):

sequence: 0 
[actual:] 7       
added_X:  7   // <--- Note how "information" is passed to the left       
sum=7

Note: The case where we have to append an element k to the sequence can be dealt as follows:

1. First, we just append k to the sequence array.

2. Second, we set sum=sum+k.

3. Third, we append 0 to the added_X array.

Abstract

In the following I will describe how to read the input in Java. We will examine the Scanner class and then write our own class for faster input reading.

Using the Scanner class

We can read the input using the Scanner class:

import java.util.*;
 
public class Main{
   public static void main(String[] args) {
      // Use the Scanner class
      Scanner sc = new Scanner(System.in);  
      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String
      */
    }
}

Using the BufferedReader class

However, the Scanner class is slow and may cause a "timelimit exceeded". We can read the input faster with the BufferedReader class. The class "MyScanner" below uses a BufferedReader. The same method names as in the Scanner class have been chosen, e.g. to read the input as an integer we still can use nextInt().

import java.io.*;
import java.util.*;
 
 
public class Main{
   public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));
      
      // Start writing your solution here. -------------------------------------
   
      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String

      int result = 3*n;
      out.println(result);                    // print via PrintWriter
      */

      // Stop writing your solution here. -------------------------------------
      out.close();
   }

     

   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }

   }
   //--------------------------------------------------------
}

References

1. FastScanner class used by xenoslash.

2. Faster input for java – An article by James Brucker

3. ReadLine in Java

If you know of a simpler/better method for input reading in Java, please post it below.

Edit 1 (30 August 2014)

I added PrintWriter for a faster output.