Join Us
Loading Similar Posts
Entering edit mode
1. (100 points)
You are given an array of size N and you can perform M number of operations.
In each operation you can insert an element in the array. Perform the operations such that the MEX of the array becomes maximum.
Note - MEX of an array is the smallest non-negative integer NOT present in the array.
Constraints
1<=N<=1e5
1<=M<=1e15
0<=A[i]<=N
Example -
Input:
M=5
A[]=4 1 6 0 0 2 4
Output: 10
2. (200 points)
You work as an Uber driver in a city with lots of hills. Each hill has a different altitude. Your job is to drive passengers around the city while dealing with these hilly areas.
You can only move from one hill to another adjacent hill but not the diagonal hill. The altitude of each hill is represented by a n*n matrix hills. The time taken to reach the hill is same as the altitude of the hill.
You can reach any adjacent hill in zero time if the hill's altitude is lower than the altitude of the current hill but you must stay within the boundaries of the city during your travel.
Your task is to find the minimum time required to reach the bottom-right hill(n,n), if you start at the top-left hill (0, 0).
Example -
Input: hills = [[0,1],
[4,3]]
Output: 3
3. (300 points)
In a distant land, nestled among rolling hills and ancient forests, lies the Enchanted Kingdom, a realm of magic and wonder. Within this mystical land, there is a square grid with dimensions n by m, where each square is denoted by (x, y), representing the x-th row from the top and y-th column from the left. In this grid, a special character known as the Seeker, with its extraordinary ability move through the grid, starts at position (x1,y1) and must find its way to a distant square at position (x2, y2) after K moves, where each move involves the Seeker being placed in a square that shares either the same row or the same column as its current position. The Seeker must not remain in the same square throughout the moves. Can you determine the number of valid sequences of moves the Seeker can make to reach the target position? Please provide the answer modulo 998244353.
Constraints:
The dimensions of the grid satisfy ≤ 10^9.
The number of moves K satisfies 10^6.
1 ≤ x1, x2 ≤ n and 1 ≤ y1, y2 ≤ m.
Example -
Input:
n: 3
m: 4
k: 3
startingPosition: [1, 2]
endingPosition: [2, 3]
Output: 9
Explanation
There are 9 possible sequence of reaching [2,3] from [1,2]
- [1,2] -> [1,4] -> [2,4] -> [2,3]
- [1,2] -> [1,3] -> [3,3] -> [2,3]
- [1,2] -> [1,4] -> [1,3] -> [2,3]
- [1,2] -> [1,1] -> [1,3] -> [2,3]
- [1,2] -> [1,1] -> [2,1] -> [2,3]
- [1,2] -> [2,2] -> [2,1] -> [2,3]
- [1,2] -> [3,2] -> [3,3] -> [2,3]
- [1,2] -> [2,2] -> [2,4] -> [2,3]
- [1,2] -> [3,2] -> [2,2] -> [2,3]
Entering edit mode
3) Observe that the total moves should be k, so say we take "x" moves in the row and "y" moves in the column s.t (x+y==k) ,then the contribution should be (number of ways_to_row*number of ways_to coln)*k!(Since we can arrange so there's a k factorial).
Number of ways to reach required row is (grid_size(row)-k)!. llarly for the case of coln.
Entering edit mode
1.
#include<bits/stdc++.h>
using namespace std;
void __solve() {
int n, m; cin >> n >> m;
vector<int>a (n);
for (int i = 0; i < n; i++) cin >> a[i];
sort (a.begin(), a.end() );
a.erase (unique (a.begin(), a.end() ), a.end() );
int mex = -1;
for (int i = 0; i < a.size(); i++) {
if (a[i] - mex > 1) {
int diff = a[i] - mex - 1;
int x = min (diff, m);
m -= x; mex = mex + x + 1;
} else mex = a[i];
}
if (m > 0) mex += m;
cout << mex + 1 << endl;
}
int main() {
int T = 1; //cin >> T;
while (T--) __solve();
}
2.
#include<bits/stdc++.h>
using namespace std;
vector<int>dx = {-1, 0, 1, 0};
vector<int>dy = {0, -1, 0, 1};
int main() {
int n; cin >> n;
vector<vector<int>>a (n, vector<int> (n) ), dist (n, vector<int> (n, INT_MAX) );
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
dist[0][0] = 0;
set<array<int, 3>>pq;
pq.insert ({0, 0, 0});
while (!pq.empty() ) {
auto [d, r, c] = *pq.begin();
pq.erase (pq.begin() );
for (int i = 0; i < 4; i++) {
int x = r + dx[i], y = c + dy[i];
if (x >= 0 and x<n and y >= 0 and y < n) {
int add = (a[x][y] < a[r][c] ? 0 : a[x][y]);
if (d + add < dist[x][y]) {
dist[x][y] = d + add;
pq.insert ({dist[x][y], x, y});
}
}
}
}
cout << dist[n - 1][n - 1];
}
no you can move in any 4 directions it will cover only 2 directions left and down