Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Maximum Area problem solution

YASH PAL, 31 July 2024
In this HackerEarth Maximum Area problem solution While walking around Hackerland, Marichka found a large square grid of size N . N consisting of unit squares of size 1 . 1. Now Marichka wants to explore it as much as possible.
In one move Marichka can move to the cell which shares an edge with cell, where Marichka currently is. It will take her aij (1 <= aij <= 10^6) minutes, where (i,j) is the coordinates of the cell where Marichka moved. Marichka defines her exploration level as the maximum row number for all cells she visited multiplied by maximum column number for all cells she visited. Marichka always starts her exploration in the cell with coordinates (1,1). Your task is to help Marichka maximize this score. Marichka is limited in time, so she can’t spend more than T minutes exploring the grid.
HackerEarth Maximum Area problem solution

HackerEarth Maximum Area problem solution.

#include <bits/stdc++.h>
#define PB push_back
#define LL long long
using namespace std;
const int INF = 1000 * 1000 * 1000;
LL d[151][150 * 150];
int N , T;
LL a[150][150];
int dx[4] = {1 , 0 , -1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
bool inRange(int x , int y)
{
return x >= 0 && x < N && y >= 0 && y < N;
}
void dijkstra(int idx , vector<int> start)
{
//vector<int> d (n, INF), p (n);
//d[s] = 0;
priority_queue < pair<LL,int> > q;
for(auto x : start)
{
d[idx][x] = 0;
q.push (make_pair (0, x));
}
while (!q.empty()) {
int v = q.top().second; LL cur_d = -q.top().first;
q.pop();
if (cur_d > d[idx][v]) continue;
int row = v / N;
int column = v % N;
for(int dir = 0; dir < 4; dir++)
{
int nR = row + dx[dir] , nC = column + dy[dir];

if(!inRange(nR , nC))
continue;
int to = nR * N + nC , len = a[nR][nC];

if (d[idx][v] + len < d[idx][to]) {
d[idx][to] = d[idx][v] + len;
q.push (make_pair (-d[idx][to], to));
}
}
}
}
int main()
{
cin >> N >> T;
//Setting initial distances to INFININTY
for(int i = 0; i <= N; i++)
for(int j = 0; j < N; j++)
for(int k = 0; k < N; k++)
d[i][j * N + k] = INF;
//Reading the array a
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> a[i][j];
//Running the dijkstra from the starting point
vector<int> start;
start.PB(0);
dijkstra(0 , start);
//Running N dijstras from every column
for(int i = 0; i < N; i++)
{
vector<int > v;
for(int j = 0; j < N; j++)
v.PB(i * N + j);
dijkstra(i + 1, v);
}
//Updating answer using results from previous dijkstras
int ans = 0;
int ans2 = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
{
if(d[0][i * N + j] <= T)
ans2 = max(ans2 , (i + 1) * (j + 1));
for(int k = 0; k < min(N , 50); k++)
{
if(d[0][i * N + j] + d[k + 1][i * N + j] <= T)
{
ans = max(ans , (k + 1) * (j + 1));

}

}
}
cout << max(ans2 , ans2);
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 150;
int n, t, d[2][maxn][maxn], a[maxn][maxn];
int xs[] = {0, 0, +1, -1}, ys[] = {-1, +1, 0, 0};
struct State{
int x, y, d;
bool operator <(const State &o) const{
return d < o.d;
}
};
set<State> s;
void dij(int d[maxn][maxn]){
while(s.size()){
auto [x, y, di] = *s.begin();
s.erase(s.begin());
for(int i = 0; i < 4; i++){
int nx = x + xs[i], ny = y + ys[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < n && d[nx][ny] > di + a[nx][ny]){
s.erase({nx, ny, d[nx][ny]});
d[nx][ny] = di + a[nx][ny];
s.insert({nx, ny, d[nx][ny]});
}
}
}
}
int ans;
void solve(){
memset(d[0], 63, sizeof d[0]);
s.insert({0, 0, d[0][0][0] = 0});
dij(d[0]);
for(int i = 0; i < n; i++){
memset(d[1], 63, sizeof d[1]);
for(int j = 0; j < n; j++)
s.insert({i, j, d[1][i][j] = d[0][i][j]});
dij(d[1]);
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(d[1][j][k] <= t)
ans = max(ans, (k + 1) * (i + 1));
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> t;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> a[i][j];
solve();
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
swap(a[i][j], a[j][i]);
solve();
cout << ans << 'n';
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes