Doubt: Can anyone explain to me how this code is working practically while theoretically O(1e4*1e5) should give TLE.
Is there any mathematically reason ?
Thanks for your time.
# | User | Rating |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | SecondThread | 148 |
5 | atcoder_official | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start.
Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.
n<=1e4, arr[i]<=1e4, start, end<1e5
Expected Time & Space Complexity : O(1e5)
class Solution {
public:
int minimumMultiplications(vector<int>& v, int s, int d) {
int n = v.size();
int MOD = 1e5;
queue<pair<int,int>>q; q.push({s,0});
vector<int>vis(1e5); vis[s]=1;
while(!q.empty()){
auto elem = q.front(); q.pop();
int i = elem.first; int res = elem.second;
if(i==d) return res;
for(int j=0;j<n;j++){
int val = (i*v[j])%MOD;
if(!vis[val]) {
vis[val] = 1;
q.push({val,res+1});
}
}
}
return -1;
}
};
Doubt: Can anyone explain to me how this code is working practically while theoretically O(1e4*1e5) should give TLE.
Is there any mathematically reason ?
Thanks for your time.
Given an m x n binary matrix matrix, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 100000));
// First pass: Top-left to bottom-right
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 0) {
dp[i][j] = 0;
} else {
if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
}
}
}
// Second pass: Bottom-right to top-left
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
if (i < n - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
if (j < m - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
}
}
return dp;
}
};
Queries:
Why does it work ? I understood a little by doing some dry runs but still not able to get the complete feel. If you know any other similar problem, please do share it.
I also want to know if there exists more unique/different dp traversals like these to solve particular problems. Eg. maybe a clockwise and anticlockwise traversal.
I also couldn't write the memoized recursive solution, If you can help me with that, that'd be of great help.
Thanks for your time.
How to get the new ideas & When should I look at the editorial. (You can avoid spoilers, not a must read)
I tried hard to solve the Problem G
I've spent 30 minutes trying it, and I'm already out of ideas.
I have a fear of "What if it requires some ideas that i'm unaware of". I'm pretty good at applying known/slightly modified ideas, I have scored 99.9 %ile in my country's university entrance test by just applying the know ideas. I can think of new ideas but they must be somewhat similar to the previous ones.
What I usually try to do is "I will try for another 15-20 minutes then I will try again tomorrow and I will look at the editorial."
Any slight hints/ideas or anything on how to face the situation that I'm facing these days would be greatly appreciated.
In the past one month, my peak went ~ +200. My goal is to get better, even though I haven't given any contests on this (my main) acc, I started with a new account and achieved 1590 rating last contest. I want to get to the master level.
English is not my first language, Sorry If I was not clear in explaining my situation. Sorry for any grammatical mistakes.
Name |
---|