Why does this code cause a runtime error on Codeforces Contest 79 B?

Question

I was solving a Codeforces problem and encountered a runtime error in my code for a specific test case.

A quick summary of the problem statement is as follows:

• You're given a 2D array of dimensions n x m (n, m <= 40,000).
• k distinct cells are given to be "waste cells".
• Someone starts at the top-left corner, then moves across each row, cyclically planting Carrots, Kiwis, then Grapes in every non-waste cell.
• You're given t queries to find what, if anything, is planted in the cell at index [i][j]. Obviously, 0 <= i < n, 0 <= j < m.

Here is my attempt at solving this problem:

    #include <iostream>

    using namespace std;
    typedef long long ll;
    
    int main() {
        ll n, m, k, t;
        cin >> n >> m >> k >> t;

        ll farm[n][m];
        
        //All cells are initialized to -2 initially.
        for(ll i = 0; i < n; i++)
        {
            for(ll j = 0; j < m; j++)
            {
                farm[i][j] = -2;
            }
        }
        
        // Mark all waste cells with -1
        for(ll i = 0;i < k; i++)
        {
            ll r, c;
            cin >> r >> c;

            farm[r-1][c-1] = -1;
        }
        
        // Label all the cells with either a 0, 1, or 2, corresponding to
        // Carrots, Kiwis, and Grapes respectively.
        ll cc = 0;
        for(ll i = 0; i < n; i++)
        {
            for(ll j = 0; j < m; j++)
            {
                if(farm[i][j] != -1)
                {
                    farm[i][j] = (cc % 3);
                    cc++;
                }
            }
        }
        
        // Process all T Queries
        for(ll p = 0; p < t; p++)
        {
            ll r, c;
            cin >> r >> c;
            r--; c--;
            
            if(farm[r][c] == -1)
                cout << "Waste\n";
            
            if(farm[r][c] == 0)
                cout << "Carrots\n";
            
            if(farm[r][c] == 1)
                cout << "Kiwis\n";
            
            if(farm[r][c] == 2)
                cout << "Grapes\n";
        }
        return 0;
    }

Here is the test-case that's causing a runtime error:

39898 39898 3 1
4567 8901
12345 23456
24680 35679
29292 12121

Can you tell me why the code isn't passing the required test-case? Any alternative solution will also be appreciated. 

Answer 1

Question Summary: Given a N*M grid (N, M <= 40,000) and K (K <= 1000) "waste squares", some person starts at the top-left corner of the grid and cyclically plants Carrots, Kiwis, and Grapes in each non-waste square as they move right across each row. Process T queries (T <= 1000) that ask for the type of crop at index [i][j] of the grid.

Your approach matches up with the simplest solution to this problem: Simply keep an array int farm[n][m] where farm[i][j] contains a number that represents its state. Marking a square as "waste" can be simply done by farm[i][j] = -1, so the time complexity of this is O(K). Then, go through the array from left to right, top to bottom and label each square as a number 1, 2, or 4. After that, if we want to process a query asking for the state of position (i, j), we can simply access farm[i][j], which is a O(1) time operation, so the total time complexity of this algorithm is O(N*M + K + T) (input, marking waste squares, processing queries).

What's the problem with this simple algorithm? The problem is the storage complexity, which is O(N*M). Since N and M can be up to 40,000, N*M can be up to 1,600,000,000, which will definitely exceed the maximum storage of 256 MB. Note that even if we had this much storage, actually going through all N*M squares and pre-calculating the state for every square would still time out, as 1.6 billion operations is way too many for 2 seconds.

One thing to note in Competitive Programming is that this sort of simple solution is almost never what the problem is looking for. The notion of Competitive Programming is rarely just to test one's coding skills, but also to test one's problem solving ability. With this in mind, we make the following observations:

1. We can't store the whole grid at once; that would exceed storage requirements. What we want is clearly some way to calculate the state of farm[i][j] without actually knowing it beforehand.

2. The person plants Carrots, Kiwis, then Grapes in a cyclical order going left to right, then top to bottom. Clearly, this implies the usage of some mod 3 factor to speed up computation. But, it's not that simple. We are given that the person skips waste squares, so the state of farm[i][j] is not simply its position modulo 3.

3. Let's elaborate on Observation #2. Let K be the "planted order" of farm[i][j] (essentially, farm[i][j] is the Kth square in which something is actually planted). If there were no waste squares, then the state of farm[i][j] would just equal K%3. But with waste squares, we can see that the state of farm[i][j] would actually just be (K - the number of squares before farm[i][j] that are waste squares) % 3.

Observation 3 is essentially our answer to this problem. To understand it better, imagine all the squares as a line of plots waiting to be planted. The Kth plot would obviously have state K%3 if there were no waste squares. But what do the waste squares even represent? In this "line" analogy, they can be seen as representing people leaving the line (because they are not in it). What happens if X people leave the line in front of the originally Kth person? Of course, that person turns into the K - Xth person, meaning that their true state would be equal to (K-X)%3.

All that's left in this algorithm is to find some efficient way to compute, for some i, j, the number of "waste squares" behind it. Two ways to do this could be:

1. Keep a list of the waste squares as pairs of integers and sort it. For every i, j, use a binary search on that last to determine how many waste squares we skip up until farm[i][j].
2. Another way could be to just input all the queries, store them, then process them in a sorted order, keeping some variable curr representing the current number of waste squares encountered.

So, overall:

1. We can't precompute the states of all N*M squares in the farm because of storage/time constraints.
2. We observed that the Kth visited square is equal to the K - X square in which something is planted, where X is the number of squares before that Kth square that are waste squares.

This should be enough to write an efficient algorithm for this problem (I'll leave it to you to try to determine the time complexity of the algorithm, but feel free to ask for help if you need it).

Answer 2

cin>>n>>m>>k>>t;
ll farm[n][m];

This is illegal in C++. Automatic arrays must be declared using constant/literal size. If you want to declare an array of dynamic size you'll have to use pointers. I recommend reading up on those as they're essential to good C++ code, but here's the syntax for what you need for now:

cin >> n >> m >> k >> t;
ll* farm = new ll[n][m]; // This will create a dynamic 2D array of n * m
delete [] farm; // Run this at the end of your code or when you're done with the array

What you have right now should not be able to compile. Are you sure you're not getting a compilation error instead of a runtime error?

Also, since you're using such small numbers and you're also just starting out with C++, I'd use type int instead off ll. It doesn't hurt to do what you're doing, but a long long type takes up way more space in memory than an int.

This is really all I can help you with for now. In the future please give as much information as you can in your questions. We need to know what the error is to give you the best help. I hope this solves your issue.