GREEDGRID - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author & Editorialist: Nishank Suresh
Testers: Takuki Kurokawa, Utkarsh Gupta

DIFFICULTY:

2362

PREREQUISITES:

Dynamic programming

PROBLEM:

There is a grid consisting of distinct integers. Two players A and B play a game on it, taking turns moving a token from (1, 1) to (N, M) one step right/down at a time. B moves first.

B can make any available move, while A will always move to whichever neighbor has the higher value.
Let K be the maximum value encountered on the path. If B plays optimally, what is the minimum possible value of K?

EXPLANATION:

First, note that which cell of the grid we are on uniquely defines whose turn it is. For cell (i, j), if (i+j) is even then it is Becky’s turn, and if (i+j) is odd it is Anya’s turn.

With this in hand, the task can be solved using dynamic programming.

Let dp(i, j) denote the minimum possible value of K if the token starts at cell (i, j) and moves towards (N, M). Our answer is dp(1, 1).

Then,

  • If it is Anya’s turn, dp(i, j) = \max(A_{i, j}, dp(next)), where next denotes the unique cell Anya will move to from (i, j), i.e,
    • next = (i+1, j) if A_{i+1, j} \gt A_{i, j+1}
    • next = (i, j+1) otherwise.
  • If it is Becky’s turn, dp(i, j) = \max(A_{i, j}, \min(dp(i+1, j), dp(i, j+1)))

The reasons for these transitions should be obvious:

  • On Anya’s turn, she will definitely move to next. The maximum of the path from (i, j) is thus either A_{i, j} or the maximum of the path from next.
  • On Becky’s turn, the maximum of the path is obviously at least A_{i, j}. Beyond that, she will choose whichever move minimizes the maximum. There are only two possible moves so we just take their minimum.

This can either be implemented as a recursive function with memoization (with the base case being dp(N, M) = A_{N, M}, or an iterative dp where you simply iterate across the grid from bottom to top, left to right.
Either way, the complexity is \mathcal{O}(N\cdot M).

TIME COMPLEXITY

\mathcal{O}(N\cdot M) per test case.

CODE:

Setter's code (C++)
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		vector grid(n, vector(m, 0));
		for (auto &row : grid) for (auto &x : row) cin >> x;
		vector dp(n, vector(m, 0));
		for (int i = n-1; i >= 0; --i) {
			for (int j = m-1; j >= 0; --j) {
				if (i == n-1 and j == m-1) dp[i][j] = grid[i][j];
				else if (i == n-1) dp[i][j] = max(grid[i][j], dp[i][j+1]);
				else if (j == m-1) dp[i][j] = max(grid[i][j], dp[i+1][j]);
				else {
					if ((i+j)%2 == 0) { // Becky
						dp[i][j] = max(grid[i][j], min(dp[i+1][j], dp[i][j+1]));
					}
					else { // Anya
						if (grid[i+1][j] > grid[i][j+1]) dp[i][j] = max(grid[i][j], dp[i+1][j]);
						else dp[i][j] = max(grid[i][j], dp[i][j+1]);
					}
				}
			}
		}
		cout << dp[0][0] << '\n';
	}
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
    string buffer;
    int pos;

    const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    const string number = "0123456789";
    const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string lower = "abcdefghijklmnopqrstuvwxyz";

    input_checker() {
        pos = 0;
        while (true) {
            int c = cin.get();
            if (c == -1) {
                break;
            }
            buffer.push_back((char) c);
        }
    }

    int nextDelimiter() {
        int now = pos;
        while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
            now++;
        }
        return now;
    }

    string readOne() {
        assert(pos < (int) buffer.size());
        int nxt = nextDelimiter();
        string res;
        while (pos < nxt) {
            res += buffer[pos];
            pos++;
        }
        // cerr << res << endl;
        return res;
    }

    string readString(int minl, int maxl, const string& pattern = "") {
        assert(minl <= maxl);
        string res = readOne();
        assert(minl <= (int) res.size());
        assert((int) res.size() <= maxl);
        for (int i = 0; i < (int) res.size(); i++) {
            assert(pattern.empty() || pattern.find(res[i]) != string::npos);
        }
        return res;
    }

    int readInt(int minv, int maxv) {
        assert(minv <= maxv);
        int res = stoi(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    long long readLong(long long minv, long long maxv) {
        assert(minv <= maxv);
        long long res = stoll(readOne());
        assert(minv <= res);
        assert(res <= maxv);
        return res;
    }

    void readSpace() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == ' ');
        pos++;
    }

    void readEoln() {
        assert((int) buffer.size() > pos);
        assert(buffer[pos] == '\n');
        pos++;
    }

    void readEof() {
        assert((int) buffer.size() == pos);
    }
};

template <long long mod>
struct modular {
    long long value;
    modular(long long x = 0) {
        value = x % mod;
        if (value < 0) value += mod;
    }
    modular& operator+=(const modular& other) {
        if ((value += other.value) >= mod) value -= mod;
        return *this;
    }
    modular& operator-=(const modular& other) {
        if ((value -= other.value) < 0) value += mod;
        return *this;
    }
    modular& operator*=(const modular& other) {
        value = value * other.value % mod;
        return *this;
    }
    modular& operator/=(const modular& other) {
        long long a = 0, b = 1, c = other.value, m = mod;
        while (c != 0) {
            long long t = m / c;
            m -= t * c;
            swap(c, m);
            a -= t * b;
            swap(a, b);
        }
        a %= mod;
        if (a < 0) a += mod;
        value = value * a % mod;
        return *this;
    }
    friend modular operator+(const modular& lhs, const modular& rhs) { return modular(lhs) += rhs; }
    friend modular operator-(const modular& lhs, const modular& rhs) { return modular(lhs) -= rhs; }
    friend modular operator*(const modular& lhs, const modular& rhs) { return modular(lhs) *= rhs; }
    friend modular operator/(const modular& lhs, const modular& rhs) { return modular(lhs) /= rhs; }
    modular& operator++() { return *this += 1; }
    modular& operator--() { return *this -= 1; }
    modular operator++(int) {
        modular res(*this);
        *this += 1;
        return res;
    }
    modular operator--(int) {
        modular res(*this);
        *this -= 1;
        return res;
    }
    modular operator-() const { return modular(-value); }
    bool operator==(const modular& rhs) const { return value == rhs.value; }
    bool operator!=(const modular& rhs) const { return value != rhs.value; }
    bool operator<(const modular& rhs) const { return value < rhs.value; }
};
template <long long mod>
string to_string(const modular<mod>& x) {
    return to_string(x.value);
}
template <long long mod>
ostream& operator<<(ostream& stream, const modular<mod>& x) {
    return stream << x.value;
}
template <long long mod>
istream& operator>>(istream& stream, modular<mod>& x) {
    stream >> x.value;
    x.value %= mod;
    if (x.value < 0) x.value += mod;
    return stream;
}

constexpr long long mod = 998244353;
using mint = modular<mod>;

mint power(mint a, long long n) {
    mint res = 1;
    while (n > 0) {
        if (n & 1) {
            res *= a;
        }
        a *= a;
        n >>= 1;
    }
    return res;
}

vector<mint> fact(1, 1);
vector<mint> finv(1, 1);

mint C(int n, int k) {
    if (n < k || k < 0) {
        return mint(0);
    }
    while ((int) fact.size() < n + 1) {
        fact.emplace_back(fact.back() * (int) fact.size());
        finv.emplace_back(mint(1) / fact.back());
    }
    return fact[n] * finv[k] * finv[n - k];
}

int main() {
    input_checker in;
    int tt = in.readInt(1, 3e4);
    in.readEoln();
    int sn = 0;
    while (tt--) {
        int h = in.readInt(1, 5e5);
        in.readSpace();
        int w = in.readInt(1, 5e5);
        in.readEoln();
        assert(1LL * h * w <= 5e5);
        sn += h * w;
        vector<vector<int>> a(h, vector<int>(w));
        vector<int> b;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i][j] = in.readInt(1, h * w);
                (j == w - 1 ? in.readEoln() : in.readSpace());
                b.emplace_back(a[i][j]);
            }
        }
        sort(b.begin(), b.end());
        for (int i = 0; i < h * w; i++) {
            assert(b[i] == i + 1);
        }
        vector<vector<int>> dp(h, vector<int>(w, h * w + 10));
        dp[0][0] = a[0][0];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dp[i][j] = max(dp[i][j], a[i][j]);
                if (i == h - 1 && j == w - 1) {
                    continue;
                } else if (i == h - 1) {
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
                } else if (j == w - 1) {
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                } else if ((i + j) % 2 == 1) {  // anya
                    if (a[i][j + 1] > a[i + 1][j]) {
                        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
                    } else {
                        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                    }
                } else {  // becky
                    dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                }
            }
        }
        cout << dp[h - 1][w - 1] << endl;
    }
    assert(sn <= 5e5);
    in.readEof();
    return 0;
}
1 Like

I was not sure how to ensure k is minimum just only by dp. So I used binary search + dp .
My solution : CodeChef

1 Like

Myself Adarsh Prashar

I am top 0.02% (Globally) Candidate Master(2048) at Codeforces, Guardian (top 0.8%) at Leetcode and 6 Star (2208) at Codechef

About Me - I have a youtube channel in which I upload editorials of leetcode, codeforces and codechef contest.

You can understand my method to solve that.

Greedy Grid Moves (Video Editorial Link) - Greedy Grid Moves Problem E Div2 | Codechef Starters 63 | DP | prashar32 - YouTube
My channel Link - https://www.youtube.com/@prashar32

If you like my video kindly like share and subscribe to my channel

3 Likes

sure brother , i would like to be part , please upload solutions of every contest of codeforces and codechef.

1 Like

I could not assure myself that DP would work here.
In contest, I also did a Binary Search solution, But I used BFS.
predicate(X) tells if we can reach (N,M) without visiting cells > X at all.
So I did a BFS from (1,1) using appropriate transition, ignoring all cells with values > X.

Accepted Code

Time Complexity : O( log(N*M)*N*M )

@prashar32
Can you post a video about how to become a candidate master .
Can you post your screencast of actual contest (of course after the contest), So people could see and learn from your thinking approach and implementation approach, etc.

Thanks for the suggestion @nitinkumar1238. I will try to do this whenever I give a contest.

I not come up with this"First, note that which cell of the grid we are on uniquely defines whose turn it is. For cell (i, j)(i,j), if (i+j)(i+j) is even then it is Becky’s turn, and if (i+j)(i+j) is odd it is Anya’s turn." during the contest.
At Each step i jump two step if possible.

https://www.codechef.com/viewsolution/78976782

Can you explain it a little because your approach seems new for me.