PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Chaithanya Shyam
Tester: Anshu Garg
Editorialist: Istvan Nagy
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Chess, memoization, dynamic programming
PROBLEM:
There’s an N \times N grid where each cell of the grid contains a positive integer. Let V_{i,j} be the positive integer on the cell positioned i-th rows from the top and j-th columns from the left.
Initially, Alice is at position (A_x, A_y) and Bob is at (B_x, B_y). Both players can move like a chess king on the grid: one step horizontally, vertically or diagonally. They can’t move out of the grid or stay in the same cell.
Alice starts with an initial score of 0. The game proceeds as follows:
- Alice moves to a neighboring cell of her choice (horizontally, vertically or diagonally). Her score increases by the integer on the cell she just moved to.
- If Alice and Bob are in the same cell, then the game ends, else Bob moves to a neighboring cell of his choice.
- If Alice and Bob are in the same cell, then the game ends, else go to step 1.
The goal of Alice is to maximize her score. The goal of Bob is to minimize Alice’s score. Both players play optimally. It can be proven that the game will end in a finite number of iterations.
You need to find the maximum score Alice can achieve.
Note: Over the course of the game, Alice can revisit cells multiple times. She gets the corresponding value added to her score each time she visits it.
EXPLANATION
Maybe our first idea to check a simple approach : what if we want to calculate the best solution for every state of : (\text{Alice position})\times(\text{Bob position}) \times \left\{\text{Alice turn, Bob turn}\right\}. The first issue with this, the space complexity is 2*N^4, what is with N=300 and storing one 64 bit integer for every state, this would require more than 100GB memory. The second problem with this approach when Bob strategy not optimal the same state can occurs multiple times that would lead an infinite loop. So at the first sight its not obvious the game is finite, but the problem description contains a hint that it can be proven its finite, so lets concentrate on Bob task: he wants to catch Alice as fast as he can. To avoid infinite chase, Bob has to “push” Alice to the edge of the board. Let Alice cell a=(a_1, a_2) and Bobs position b=(b_1,b_2).
Definition: The Chebyshev distance between the two positions is : D_C(a,b)=max(|a_1-b_1|, |a_2-b_2|)
When a king wants to go from a cell to another cell the he can do that the number of Chebysev distance steps.
First try for Bob algorithm: Alice wants to collect the numbers from top to bottom then left to right. In case Bob wants to minimize the Chebysev distance in every step. It seems the pursuit can be longer then necessary:
Bob may goes from H1->E1, then he follows diagonally from E1->A5, so after 8 step he still from 3 distance from Alice.
Lets consider an even simpler case, where the starting position of Alice (white) is C8, and Bob (black) is C6. If Alice steps on the 7th rank Bob can catch her at the after his first step. Otherwise Alice can step on the B8 or D8 field, and Bob killer move is to step B7 or D7. The strategy is little bit similar strategy then opposition in chess.
Definition: The Manhattan distance between the two positions is : D_M(a,b)=|a_1-b_1| + |a_2-b_2|
Bob’s strategy: in every step he tries to minimize the Manhattan distance from Alice current position.
Check again the first example (with the new strategy):
It seems with this new strategy Bob can catch Alice at most the 8-th step.
Claim: Bob catches Alice if and only if Alice moves to a cell on the i-th turn such that the Chebysev distance between that cell and Bob’s initial position is less than or equal to i
Proof: Of course if Alice stays on a cell which distance is greater than i than Bob cannot catch her at the actual step.
With the current strategy its enough to prove it only one dimension. Alice stays on a cell a=(a_1, a_2) on the i-th step, and Bob-s starting point b=(b_1, b_2). If |a_1-b_1|<=i then Bob with his strategy already on the a_1 row or in the current step he can step on it.
Remark: it also can happen Alice steps on the same cell as Bob stands on the i-th turn, in this case Bob don’t need to make another step to catch Alice.
Consequences: At latest after the N-1-th step the game is over, so the game is finite.
We can make a state : (\text{Alice position})\times \text{current turn}. In this way the number of different states are less than N^3. From every state Alice has at most 8 different option how to continue. The claim gives us a game ending condition.
TIME COMPLEXITY:
O(N^3) per test case
SOLUTIONS:
Setter's Solution
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> //required
//#include <ext/pb_ds/tree_policy.hpp> //required
//using namespace __gnu_pbds; //required
using namespace std;
//template using ordered_set = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update>;
// ordered_set s;
// s.find_by_order(k); returns the (k+1)th smallest element
// s.order_of_key(k); returns the number of elements in s strictly less than k
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];
#define leftmost_bit(x) (63-__builtin_clzll(x))
#define rightmost_bit(x) __builtin_ctzll(x) // count trailing zeros
#define set_bits(x) __builtin_popcountll(x)
#define pow2(i) (1LL << (i))
#define is_on(x, i) ((x) & pow2(i)) // state of the ith bit in x
#define set_on(x, i) ((x) | pow2(i)) // returns integer x with ith bit on
#define set_off(x, i) ((x) & ~pow2(i)) // returns integer x with ith bit off
#ifdef LOCAL_DEBUG
#define debug(…) logger(#VA_ARGS, VA_ARGS)
#else
#define debug(…) ;
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// auto dist = uniform_int_distribution(l, r);
// use int a = dist(rng) to get a random number between [l,r] inclusive
template<typename …Args>
void logger(string vars, Args&&… values) {
cerr << vars << " = ";
string delim = “”;
(…, (cerr << delim << values, delim = ", "));
cerr << endl;
}
typedef long long int ll;
typedef long double ld;
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!
// highly risky #defines
#define int ll // disable when you want to make code a bit faster
#define endl ‘\n’ // disable when dealing with interactive problems
#define pii pair<int,int>
typedef vector vi;
int ax, ay, bx, by;
int N;
vector vec;
vector<vector> dp;
// dp[i][j][t] = max number of points Alive can get starting from i,j with t moves already played
int f(int i, int j, int t){
if(dp[i][j][t] != -1) return dp[i][j][t];
if(max(abs(i-bx), abs(j-by)) <= t) return 0; //caught
int ans = 0;
for(int dx = -1; dx <= 1; dx++){
for(int dy = -1; dy <= 1; dy++){
if(dx == 0 && dy == 0) continue; // same coordinate
int nx = i + dx, ny = j + dy;
if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // out of bounds
ans = max(ans, vec[nx][ny] + f(nx, ny, t+1));
}
}
return dp[i][j][t] = ans;
}
void solve(){
cin >> N >> ax >> ay >> bx >> by;
ax–;ay–;bx–;by–;
vec.assign(N, vi(N));
for(vi &v: vec) input(v, N);
dp.assign(N, vector<vi>(N, vi(N + 1, -1)));
cout << f(ax, ay, 0) << endl;
}
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
startTime = clock();
// mt19937_64 rnd(time(NULL));
int T = 1;
cin >> T;
for(int t = 0; t < T; t++){
solve();
}
// cerr << "Time taken = " << getCurrentTime() << endl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
const int M = 1000000007;
const int MM = 998244353;
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
#ifdef LOCAL
#define debug(...) debug_out(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 2351
#endif
long long readInt(long long l,long long r,char end){
long long x = 0;
int cnt = 0;
int first =-1;
bool is_neg = false;
while(true) {
char g = getchar();
if(g == '-') {
assert(first == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if(cnt == 0) {
first = g - '0';
}
++cnt;
assert(first != 0 || cnt == 1);
assert(first != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && first > 1)));
}
else if(g == end) {
if(is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l,int r,char end){
string ret = "";
int cnt = 0;
while(true) {
char g = getchar();
assert(g != -1);
if(g == end) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN = 0;
int _runtimeTerror_()
{
int N, ax, bx, ay, by;
N = readIntSp(2,300);
ax = readIntSp(1,N);
ay = readIntSp(1, N);
bx = readIntSp(1, N);
by = readIntLn(1, N);
assert(make_pair(ax, ay) != make_pair(bx, by));
sumN += N;
// cin >> N >> ax >> ay >> bx >> by;
--ax, --ay, --bx, --by;
vector<int> dx = {-1,-1,-1,0,0,1,1,1}, dy = {-1,0,1,-1,1,-1,0,1};
vector<vector<int>> a(N, vector<int>(N,0));
for(int i=0;i<N;++i) {
for(int j=0;j<N;++j) {
if(j == N - 1) {
a[i][j] = readIntLn(1, 1e9);
}
else {
a[i][j] = readIntSp(1, 1e9);
}
}
}
vector<vector<vector<ll>>> dp(N,vector<vector<ll>>(N, vector<ll>(N, -1)));
function<ll(int,int,int)> dfs = [&](int x,int y,int moves) {
if(x < 0 || x >= N || y < 0 || y >= N) {
return 0ll;
}
if(max(abs(bx - x), abs(by - y)) <= moves) {
return a[x][y] + 0ll;
}
assert(moves < N);
if(dp[x][y][moves] != -1) {
return dp[x][y][moves];
}
ll &ans = dp[x][y][moves];
ans = 0;
for(int i=0;i<8;++i) {
amax(ans, dfs(x + dx[i], y + dy[i],moves + 1));
}
ans += a[x][y];
return ans;
};
cout << dfs(ax, ay, 0) - a[ax][ay] << "\n";
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS = 1;
// cin >> TESTS;
TESTS = readIntLn(1,60);
while(TESTS--)
_runtimeTerror_();
cerr << "sumN: " << sumN << "\n";
// assert(getchar() == -1);
return 0;
}
Editorialist's Solution
#include
#include
#include
#include
#include
#include
#include
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
using namespace std;
vector<uint64_t> memo;
vector<vector<uint64_t>> mMap;
int N, BX, BY;
uint64_t calc(int Ax, int Ay, int stepCount)
{
if (max(abs(Ax - BX), abs(Ay - BY)) <= stepCount)
return 0;
int64_t state = Ax + AyN+stepCountN*N;
uint64_t& ans = memo[state];
if (ans)
return ans;
for (int dx = -1; dx < 2; ++dx)
{
int candX = Ax + dx;
if (candX < 0 || candX >= N)
continue;
for (int dy = -1; dy < 2; ++dy)
{
if(dx == 0 && dy == 0)
continue;
int candY = Ay + dy;
if (candY < 0 || candY >= N)
continue;
ans = max<int64_t>(ans, calc(candX, candY, stepCount+1) + mMap[candX][candY]);
}
}
return ans;
}
int main(int argc, char** argv)
{
int T, AX, AY;
cin >> T;
forn(tc, T)
{
cin >> N >> AX >> AY >> BX >> BY;
memo.clear();
memo.resize(N * N * N);
–AX;
–AY;
–BX;
–BY;
mMap.clear();
mMap.resize(N, vector<uint64_t>(N));
for (auto& mi : mMap)
for (auto& mij : mi)
cin >> mij;
uint64_t res = calc(AX, AY, 0);
cout << res << endl;
}
return 0;
}
If you have other approaches or solutions, let’s discuss in comments.!