# C++ Grid gravity simulation opzimization (Kattis Falling Apples)

I have a solution for the Kattis Falling Apples problem (link). The input is a grid of R rows (up to 50000) by C columns (up to 10). At each timestep, apples (indicated by 'a') move down one cell into an empty space (denoted by .) or rest upon an obstacle (marked by #).

My solution exceeds time limit only at the last test case. I'm thinking the while loop is the problem, but I have no idea what I could do to optimize it.

#include <iostream>

using namespace std;

int main()
{
int r; // Grid rows
int c; // Grid columns

scanf("%d %d", &r, &c);

char grid[r][c];

// Establish grid
for (int i = 0; i < r; i++) {
char line[c];
scanf("%s", &line);
for (int j = 0; j < c; j++) {
grid[i][j] = line[j];
}
}

// Loop to change
while (true) {
bool change = false;

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {

if (grid[i][j] == 'a' && grid[i + 1][j] == '.') {
grid[i + 1][j] = 'a';
grid[i][j] = '.';
change = true;
}

}
}

if (!change) {
break;
}
}

// Print the grid
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << grid[i][j];
}
printf("\n");
}

return 0;
}

• Your post has been edited to correct indenation- see code formatting for more information on this topic. Jan 31 '18 at 16:07

• Avoid allocating large arrays on a stack. According to the restrictions, grid may take up to half a meg. You are dangerously close to stack overflow.

• Avoid single letter identifiers. Spelling out row and col wouldn't make your program any slower, but it would make it much more readable.

• scanf adds a null terminator to a string. Your char line[c] is one character short. Definite UB.

• The problem statement clearly says that

Merely iterating the gravity rule, a step at a time, will likely take too long on large datasets.

but that is exactly what your code is doing. No optimization may salvage this algorithm. You need to rethink the approach.

I don't want to spell out a solution, but here are few hints:

1. Columns are totally independent. Do one column at a time.

2. Do not drop apples. Count them.

3. It is beneficial to add an artificial row of obstacles at the bottom.