Blog entries - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I'm trying to solve this problem on LeetCode and my solution is going just a little over the time limit. My idea is to place the first two rooks, then determine the third rook as the maximum rook below them such that it is not on either of their columns. With DP, this should be O(N^3). Using a sparse table on a suffix maximum array should work. However, when I add the sparse table queries to the solution, the code seems to slow down by 5x. This seems a little excessive to me since the query should be O(1).

Is this really just the overhead of a constant time array access or is something else going on?

Full code

class SparseTable{ // https://github.com/ShahjalalShohag/code-library/blob/main/Data%20Structures/Sparse%20Table.cpp
public:
    int N;
    vector<vector<int>> t;
    SparseTable(int x) {
        x++;
        N = x;
        t.resize(x);
        for (int i = 0; i <x; i++) t[i].resize(32,0);
    }
    void build(int n, vector<int>& a) {
      for(int i = 1; i <= n; ++i) t[i][0] = a[i-1];
      for(int k = 1; k < 31; ++k) {
        for(int i = 1; i + (1 << k) - 1 <= n; ++i) {
          t[i][k] = max(t[i][k - 1], t[i + (1 << (k - 1))][k - 1]);
        }
      }
    }
    int query(int l, int r) {
        l++;
        r++;
      int k = 31 - __builtin_clz(r - l + 1);
      return max(t[l][k], t[r - (1 << k) + 1][k]);
    }
};
class Solution {
public:
    int N, M;
    long long inf = 1000000000000;
    long long dp[501][501] = {};
    long long pick (int pos, int a, int j, vector<SparseTable>& st) { // maximum value for third rook after first two are placed
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, st[pos].query(a1, a2));
        }
        if(b1<=b2) {
            ans = max(ans, st[pos].query(b1, b2));
        }
        if(c1<=c2) {
            ans = max(ans, st[pos].query(c1, c2));
        }
        return ans;
    }
    long long dfs(int pos, int a, vector<vector<int>>& v, vector<SparseTable>& st) {
        if(pos>=v.size()) return -inf;
        if(dp[pos][a] != -1) return dp[pos][a];
        long long ans = dfs(pos+1,a,v,st);
        if (a==v[0].size()) { // place first rook
            for (int j = 0; j < v[pos].size(); j++) ans = max(ans, dfs(pos+1, j, v, st)+v[pos][j]);
        }
        else { // place second rook then find third rook position
            for (int j = 0; j < v[pos].size(); j++) {
                if(j==a) continue;
                ans = max(ans, pick(pos+1, a, j, st)+v[pos][j]);
            }
        }
        return dp[pos][a] = ans;
    }
    long long maximumValueSum(vector<vector<int>>& v) {
        N = v.size(), M = v[0].size();
        auto mx = v;
        memset(dp,-1, sizeof(dp));
        for (int j = 0; j < M; j++) {
            for (int i = N-2; i >= 0; i--) {
                mx[i][j] = max(mx[i][j], mx[i+1][j]);
            }   
        }
        vector<SparseTable> st(N, SparseTable(M));
        for (int i = 0; i < N; i++) {
            st[i].build(M,mx[i]);
        }
        return dfs(0, M, v, st);
    }
};

When my function queries the sparse table, the time taken for a N=500 testcase is 2509 ms.

Function

    long long pick (int pos, int a, int j, vector<SparseTable>& st) {
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, st[pos].query(a1, a2));
        }
        if(b1<=b2) {
            ans = max(ans, st[pos].query(b1, b2));
        }
        if(c1<=c2) {
            ans = max(ans, st[pos].query(c1, c2));
        }
        return ans;
    }

But when my function doesn't query the sparse table, the time taken for a N=500 testcase is 515 ms.

Function

    long long pick (int pos, int a, int j, vector<SparseTable>& st) {
        if(pos>=st.size()) return -inf;
        int ans = INT_MIN;
        if(j<a) swap(a,j);
        int a1 = 0, a2 = a-1, b1 = a+1, b2 = j-1, c1 = j+1, c2 = M-1;
        if(a1<=a2) {
            ans = max(ans, ans); // this doesn't do anything, just to illustrate the slowdown
        }
        if(b1<=b2) {
            ans = max(ans, ans);
        }
        if(c1<=c2) {
            ans = max(ans, ans);
        }
        return ans;
    }

Full text and comments »

sandbag's blog