1

I am trying to prepare for a contest but my program speed is always dreadfully slow as I use O(n). First of all, I don't even know how to make it O(log n), or I've never heard about this paradigm. Where can I learn about this?

For example,

If you had an integer array with zeroes and ones, such as [ 0, 0, 0, 1, 0, 1 ], and now you wanted to replace every 0 with 1 only if one of it's neighbors has the value of 1, what is the most efficient way to go about doing if this must occur t number of times? (The program must do this for a number of t times)

EDIT: Here's my inefficient solution:

import java.util.Scanner;

public class Main {

static Scanner input = new Scanner(System.in);

public static void main(String[] args) {

    int n;
    long t;

    n = input.nextInt();
    t = input.nextLong();
    input.nextLine();

    int[] units = new int[n + 2];
    String inputted = input.nextLine();
    input.close();
    for(int i = 1; i <= n; i++) {
        units[i] = Integer.parseInt((""+inputted.charAt(i - 1)));
    }

    int[] original;

    for(int j = 0; j <= t -1; j++) {
        units[0] = units[n];
        units[n + 1] = units[1];
        original = units.clone();

        for(int i = 1; i <= n; i++) {
            if(((original[i - 1] == 0) && (original[i + 1] == 1)) || ((original[i - 1] == 1) && (original[i + 1] == 0))) {
                units[i] = 1;
            } else {
                units[i] = 0;
            }
        }

    }

    for(int i = 1; i <= n; i++) {
        System.out.print(units[i]);
    }
}

}

Imagine Dragons
  • 59
  • 1
  • 7

3 Answers3

2

This is an elementary cellular automaton. Such a dynamical system has properties that you can use for your advantages. In your case, for example, you can set to value 1 every cell at distance at most t from any initial value 1 (cone of light property). Then you may do something like:

  • get a 1 in the original sequence, say it is located at position p.
  • set to 1 every position from p-t to p+t.

You may then take as your advantage in the next step that you've already set position p-t to p+t... This can let you compute the final step t without computing intermediary steps (good factor of acceleration isn't it?).

You can also use some tricks as HashLife, see 1.

Jean-Baptiste Yunès
  • 34,548
  • 4
  • 48
  • 69
1

As I was saying in the comments, I'm fairly sure you can keep out the array and clone operations.

You can modify a StringBuilder in-place, so no need to convert back and forth between int[] and String.

For example, (note: This is on the order of an O(n) operation for all T <= N)

public static void main(String[] args) {
    System.out.println(conway1d("0000001", 7, 1));
    System.out.println(conway1d("01011", 5, 3));
}

private static String conway1d(CharSequence input, int N, long T) {
    System.out.println("Generation 0: " + input);

    StringBuilder sb = new StringBuilder(input); // Will update this for all generations

    StringBuilder copy = new StringBuilder(); // store a copy to reference current generation
    for (int gen = 1; gen <= T; gen++) {
        // Copy over next generation string
        copy.setLength(0);
        copy.append(input);

        for (int i = 0; i < N; i++) {
            conwayUpdate(sb, copy, i, N);
        }

        input = sb.toString(); // next generation string
        System.out.printf("Generation %d: %s\n", gen, input);
    }

    return input.toString();
}

private static void conwayUpdate(StringBuilder nextGen, final StringBuilder currentGen, int charPos, int N) {
    int prev = (N + (charPos - 1)) % N;
    int next = (charPos + 1) % N;

    // **Exactly one** adjacent '1'
    boolean adjacent = currentGen.charAt(prev) == '1' ^ currentGen.charAt(next) == '1';
    nextGen.setCharAt(charPos, adjacent ? '1' : '0'); // set cell as alive or dead
}

For the two samples in the problem you posted in the comments, this code generates this output. 

Generation 0: 0000001
Generation 1: 1000010
1000010
Generation 0: 01011
Generation 1: 00011
Generation 2: 10111
Generation 3: 10100
10100
OneCricketeer
  • 179,855
  • 19
  • 132
  • 245
  • When the parameters are ("001000000110001", 15, 100000000) it takes 10 seconds, it's not efficient enough. One of the input data is 5449844351151445 generations too... How is it possible to make it more efficient? @cricket_007 – Imagine Dragons Nov 06 '16 at 20:55
  • If you remove the `System.out` statements inside `conway1d`, should be slightly faster. This is just the first approach I thought of, but it is certainly faster than your 84s solution – OneCricketeer Nov 06 '16 at 20:58
  • Well, I don't know C++, but I do know C++ definitely can run faster than Java. – OneCricketeer Nov 06 '16 at 21:04
  • I would only recommend you learn something that would actually be useful to your interests. For example, I don't know C++ because it isn't necessary for my job. – OneCricketeer Nov 06 '16 at 21:14
0

The BigO notation is a simplification to understand the complexity of the Algorithm. Basically, two algorithms O(n) can have very different execution times. Why? Let's unroll your example:

  • You have two nested loops. The outer loop will run t times.
  • The inner loop will run n times
  • For each time the loop executes, it will take a constant k time.

So, in essence your algorithm is O(k * t * n). If t is in the same order of magnitude of n, then you can consider the complexity as O(k * n^2).

There is two approaches to optimize this algorithm:

  • Reduce the constant time k. For example, do not clone the whole array on each loop, because it is very time consuming (clone needs to do a full array loop to clone).
  • The second optimization in this case is to use Dynamic Programing (https://en.wikipedia.org/wiki/Dynamic_programming) that can cache information between two loops and optimize the execution, that can lower k or even lower the complexity from O(nˆ2) to O(n * log n).
Preto
  • 1