I’m recently doing this problem, taken directly and translated from day 1 task 3 of IOI 2010, “Quality of life”, and I encountered a weird phenomenon.

I was setting up a 0-1 matrix and using that to calculate a prefix sum matrix in 1 loop:

for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;} b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j]; } }

and I got TLE (time limit exceeded) on 4 tests (the time limit is 2.0s). While using 2 for loop seperately:

for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (a[i][j] < x) {lower[i][j] = 0;} else {lower[i][j] = 1;} } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j]; } }

got me full AC (accepted).

As we can see from the 4 pictures here:

TLE result, picture 1 : https://i.stack.imgur.com/9o5C2.png

TLE result, picture 2 : https://i.stack.imgur.com/TJwX5.png

AC result, picture 1 : https://i.stack.imgur.com/1fo2H.png

AC result, picture 2 : https://i.stack.imgur.com/CSsZ2.png

the 2 for-loops code generally ran a bit faster (even in accepted test cases), contrasting my logic that the single for-loop should be quicker. Why does this happened?

Full code (AC) : https://pastebin.com/c7at11Ha (Please ignore all the nonsense bit and stuff like `using namespace std;`

, as this is a competitive programming contest).

- Note : The judge server, lqdoj.edu.vn is built on dmoj.ca, a global competitive programming contest platform.

## Answer

If you look at assembly you’ll see the source of the difference:

- Single loop:

{ if (a[i][j] < x) { lower[i][j] = 0; } else { lower[i][j] = 1; } b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + lower[i][j]; }

In this case, there’s a data dependency. The assignment to `b`

depends on the value from the assignment to `lower`

. So the operations go sequentially in the loop – first assignment to `lower`

, then to `b`

. The compiler can’t optimize this code significantly because of the dependency.

- Separation of assignments into 2 loops:

The assignment to `lower`

is now independent and the compiler can use SIMD instructions that leads to a performance boost in the first loop. The second loop stays more or less similar to the original assembly.