Problem 2. Air Cownditioning

Problems and Contests
#1

Link: USACO

Hi,
I was working on the Problem 2 of December 2021 Bronze, and I was wondering why my code is not passing all test cases.

It is only passing 9/10.

This is my code:

#include <bits/stdc++.h>
using namespace std;

bool checkZeros(int array[], int size) {
    for (int i = 0; i < size; i++) {
        if (array[i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n = 0;
    cin >> n;

    char mode;
    int p[n];
    int t[n];
    int d[n];
    int target[n] = { 0 };
    vector<int> indexes;
    vector<char> modes;
    int moves = 0;

    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    for (int i = 0; i < n; i++) {
        d[i] = p[i] - t[i];
    }
    
    while (true) {
        for (int i = 0; i < n; i++) {
            if (d[i] > 0) {
                mode = '-';
                d[i]--;
                indexes.push_back(i);
                modes.push_back(mode);
            }

            else if (d[i] < 0) {
                mode = '+';
                d[i]++;
                indexes.push_back(i);
                modes.push_back(mode);
            }

            else {
                continue;
            }
        }
        if (checkZeros(d, n)) {
            break;
        }
    }

    for (int i = 0; i < indexes.size(); i++) {
        if (indexes[i] + 1 == indexes[i + 1] && modes[i] == modes[i + 1]) {
            continue;
        }

        else {
            moves++;
        }
    }

    cout << moves;    
}

I am really confused why. Please let me know.
Thanks!

1 Like
#2

When the lines

    indexes.push_back(i);
    modes.push_back(mode);

were commented out in your code, and the cout << moves replaced with cout << 5 for debugging purposes, test case 10 results tle.
When your code ran without edits, the test case showed ‘!’, representing exception or memory limit exceeded, so most likely your code was meant to time out, however reached the memory limit first.
This is reasonable, as it is possible to have an output of 10,000 at maximum. Looking at your code, this would make the max. time complexity around 10^9, which would time out. So it seems your algorithm will need some optimization.

Hope it helps!