Skip to content
Programming101
Programming101

Learn everything about programming

  • 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
Programming101
Programming101

Learn everything about programming

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

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

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
©2025 Programming101 | WordPress Theme by SuperbThemes