时间戳

首页 > 解决方案 > 为什么此代码会导致 Codeforces Contest 79 B 出现运行时错误？

c++ - 为什么此代码会导致 Codeforces Contest 79 B 出现运行时错误？

问题描述

我正在解决Codeforces 问题，并在特定测试用例的代码中遇到运行时错误。

问题陈述的快速摘要如下：

这是我解决这个问题的尝试：

    #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.

标签： c++c++14

解决方案

问题摘要：给定一个N*M网格 ( N, M <= 40,000) 和K( K <= 1000) “废弃方块”，有人从网格的左上角开始，在每个非废弃方块中循环种植胡萝卜、猕猴桃和葡萄，因为它们向右移动穿过每一行. 处理T查询 ( T <= 1000) 请求网格索引 [i][j] 处的作物类型。

您的方法与此问题的最简单解决方案相匹配：只需保留一个数组int farm[n][m]，其中farm[i][j]包含一个表示其状态的数字。将一个正方形标记为“浪费”可以简单地由 完成farm[i][j] = -1，所以它的时间复杂度是O(K)。然后，从左到右、从上到下遍历数组，并将每个正方形标记为数字 1、2 或 4。之后，如果我们要处理询问位置 (i, j) 状态的查询，我们可以简单地访问farm[i][j]，这是一个O(1)时间操作，所以这个算法的总时间复杂度是O(N*M + K + T)（输入，标记浪费方块，处理查询）。

这个简单的算法有什么问题？问题在于存储复杂度，即 O(N*M)。由于N和M可以 最多40,000，N*M可以 最多1,600,000,000，这肯定会超过最大存储空间 256 MB。请注意，即使我们有这么多的存储空间，实际上遍历所有N*M方格并预先计算每个方格的状态仍然会超时，因为 16 亿次操作对于 2 秒来说太多了。

在竞争性编程中需要注意的一点是，这种简单的解决方案几乎从来都不是问题所要寻找的。竞争性编程的概念很少只是为了测试一个人的编码技能，而是为了测试一个人的解决问题的能力。考虑到这一点，我们提出以下意见：

  1. 我们不能一次存储整个网格；这将超过存储要求。我们想要的显然是某种在farm[i][j]事先不知道的情况下计算状态的方法。

  2. 该人以从左到右，然后从上到下的循环顺序种植胡萝卜，猕猴桃，然后是葡萄。显然，这意味着使用某些mod 3因素来加速计算。但是，事情没那么简单。我们得到这个人跳过了浪费的方块，所以状态farm[i][j]不仅仅是它的位置模 3。

  3. 让我们详细说明观察#2。设K为farm[i][j]（本质上，farm[i][j] 是实际种植某物的第 K 个方格）的“种植顺序”。如果没有废方格，那么 的状态farm[i][j]将等于K%3。但是对于废方格，我们可以看到 的状态farm[i][j]实际上只是(K - the number of squares before farm[i][j] that are waste squares) % 3。

观察 3 本质上是我们对这个问题的回答。为了更好地理解它，把所有的方块想象成一排等待种植的地块。如果没有废弃方块，这个Kth地块显然会有状态。K%3但是这些废物方块究竟代表什么？在这个“线”类比中，它们可以被视为代表离开线的人（因为他们不在其中）。如果X人们在最初的人面前离开会发生什么K？当然，那个人变成了K - X第 th 人，这意味着他们的真实状态将等于(K-X)%3。

这个算法剩下的就是找到一些有效的方法来计算，对于某些人i, j来说，它背后的“浪费方块”的数量。有两种方法可以做到这一点：

  1. 将废物方块列表保留为整数对并对其进行排序。对于每一个i, j，在最后一个上使用二分搜索来确定我们跳过了多少个浪费方块farm[i][j]。
  2. 另一种方法可能是只输入所有查询，存储它们，然后按排序顺序处理它们，保留一些curr表示当前遇到的浪费方块数量的变量。

所以，总的来说：

  1. 由于存储/时间限制，我们无法预先计算N*M农场中所有方格的状态。
  2. 我们观察到K第 th 访问的方格等于K - X种植某物的方格，其中X是在第 th 方格之前的方格数，这些方格K是废弃的方格。

这应该足以为这个问题编写一个有效的算法（我将留给您尝试确定算法的时间复杂度，但如果您需要，请随时寻求帮助）。

推荐阅读