Analysis: Blink by Mark Gordon and Brian Dean

With the length of the simulation being quite large, a direct simulation of the lights for B steps will take too long. However, there are still several ways to do this problem.

The important thing to realize is that there are only 2^N <= 65536 different possible states for all the lights. Let us think of the state of the lights as a the length-N binary representation of an integer, which will be in the range 0..65535. If we take B > 65536 steps, we will certainly visit the same state (say state x) multiple times. If it takes K steps to return to state x from the last time we were in state x, then our sequence of states will form a repeating loop of length K, visiting state x regularly on every Kth step. We can therefore "fast forward" through all these loops by taking the remainder of B divided by K; this won't change our final state.

Since we must revisit the same state in our first 2^N+1 moves, K must also be this small. Therefore if we keep track in an array of length 65536 of the time we visit each state we can detect when we revisit a state and how many steps it took to revisit. After reducing B modulo K we just simulate the rest of the way. An example of this in code is below. For those unfamiliar with the notation, << is a left shift (multiplication by two), so taking 1 << N is multiplying 1 by two N times, which evaluates to 2^N.

#define NMAX 16

int firstOcc[1 << NMAX];
int stateAtT[1 << NMAX];

int main() {
    freopen("blink.in","r",stdin);
    freopen("blink.out","w",stdout);

    int n;
    long long b;
    scanf("%d", &n);
    scanf("%lld", &b);
    int state = 0;
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        if (a == 1) {
            state = state | (1 << i);
        }
    }

    for (int i = 0; i < (1 << n); i++) {
        firstOcc[i] = -1;
    }

    int t = 0;
    firstOcc[state] = 0;
    stateAtT[0] = t;
    while ((long long) t < b) {
        t++;
        int rot = (state << 1);
        rot = (rot | (rot >> n)) & ((1 << n) - 1);
        state = state ^ rot;

        if (firstOcc[state] == -1) {
            firstOcc[state] = t;
            stateAtT[t] = state;
        } else {
            int cyclelen = t - firstOcc[state];
            int t1 = firstOcc[state] + (int) ((b - (long long) firstOcc[state]) % (long long) cyclelen);
            state = stateAtT[t1];
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", (state >> i) & 1);
    }
}

Although not an issue for this problem, the main disadvantage of this approach is that it requires O(2^N) memory. However, the problem can still be solved in O(2^N) time with only constant memory using a cycle detection algorithm like Floyd's Cycle detection (see https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare).

And here is an implementation of Floyd's cycle chasing algorithm:

#define MAXN 1000

int N;

int get_next(int s) {
  return s ^ (s >> 1) ^ (s & 1 ? 1 << N - 1 : 0);
}

int main() {
  freopen("blink.in", "r", stdin); 
  freopen("blink.out", "w", stdout);

  long long B;
  cin >> N >> B;

  int s = 0;
  for(int i = N - 1; i >= 0; i--) {
    int v; cin >> v;
    if(v) s |= 1 << i;
  }

  int s0 = s;
  int s1 = s;
  for(; B > 0; B--) {
    s0 = get_next(s0);
    s1 = get_next(get_next(s1));
    if(s0 == s1) {
      B--;
      break;
    }
  }
  if(B) {
    int rho = 1;
    for(s0 = get_next(s0); s0 != s1; rho++) {
      s0 = get_next(s0);
    }
    B %= rho;
  }
  for(; B > 0; B--) {
    s0 = get_next(s0);
  }
  for(int i = N - 1; i >= 0; i--) {
    cout << (s0 & 1 << i ? 1 : 0) << endl;
  }
  return 0;
}

More surprisingly, this problem can be solved in O(N log B) time (although completely unnecessary to get full points on this problem). To see this it's necessary to realize that f(x^y)=f(x)^f(y), where f(x) denotes the state we move to after state x. Therefore it's necessary to look at the evolution of only a single light. Try looking at the evolution of a single light after 1 step, 2 steps, 4, steps, 8 steps. You should notice a pattern that will lead you to an efficient solution.