4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Your post has been edited to correct indenation- see code formatting for more information on this topic. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 31 '18 at 16:07
4
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.