Join Us
hi
Entering edit mode
Space Agency
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};
bool isValid(int i, int j, int n, int m, vector<vi> &vis, vector<vi> &grid)
{
if (i >= n || j >= m || i < 0 || j < 0)
return false;
if (vis[i][j])
return false;
return true;
}
queue<pair<int, int>> q;
void bfs(int cnt, int n, int m, vector<vi> &grid, vector<vi> &vis, vector<vi> &cc, vector<vi> &dist, bool f)
{
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
for (int ind = 0; ind < 4; ind++)
{
int newi = i + di[ind], newj = j + dj[ind];
if (isValid(newi, newj, n, m, vis, grid))
{
if(!f && !grid[newi][newj])
continue;
if(f)
dist[newi][newj] = dist[i][j] + 1;
if(!f)
cc[newi][newj] = cnt;
vis[newi][newj] = 1;
q.push({newi, newj});
}
}
}
}
signed main()
{
int n, m;
cin >> n >> m;
vector<vi> grid(n, vi(m));
vector<vi> vis(n, vi(m, 0));
vector<vi> cc(n, vi(m, 0));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
}
}
int cnt = 1;
vector<vi> dist(n, vi(m, -1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (!vis[i][j] && grid[i][j] == 1)
{
q.push({i,j});
cc[i][j]=cnt;
vis[i][j]=1;
bfs(cnt, n, m, grid, vis, cc, dist, false);
cnt++;
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
vis[i][j] = 0;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (cc[i][j] == 1)
{
q.push({i, j});
dist[i][j] = 0;
vis[i][j] = 1;
}
}
}
bfs(cnt, n, m, grid, vis, cc, dist, true);
int mini = INT_MAX;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (cc[i][j] == 2)
mini = min(mini, dist[i][j]);
}
}
cout << mini - 1 << endl;
}
Entering edit mode
Video Streaming
int main()
{
int n, k, ans = INT32_MAX;
cin >> n >> k;
vi v(n);
map<int, vi> mp;
For(i, 0, n)
{
cin >> v[i];
mp[v[i]].push_back(i);
}
for (auto x : mp)
{
if (x.ss.size() < k)
continue;
vi preSum = x.ss;
for (int i = 1; i < x.ss.size(); i++)
{
preSum[i] += preSum[i-1];
}
for (int j = k-1; j < x.ss.size(); j++)
{
int i = j-k+1, mid = (i+j)/2;
int costTOMedian = preSum[j]-preSum[mid] - preSum[mid-1] ;
if(i!=0)
costTOMedian += preSum[i-1];
int costToDist=0;
if(k%2)
{
int temp = (k-1)/2;
costToDist = temp*(temp+1);
}
else
{
int temp = (k-2)/2;
costToDist = temp*(temp+1) + temp + 1;
costTOMedian -= x.ss[mid];
}
ans = min(ans, costTOMedian-costToDist);
}
}
cout << ans;
}
IT PASSES 11/16 TEST CASES
Entering edit mode
Ecommerce Company
signed main()
{
int numShelves, numCells;
cin >> numShelves >> numCells;
vector<vector<int>> productCodes(numShelves, vector<int>(numCells));
for (int i = 0; i < numShelves; ++i)
{
for (int j = 0; j < numCells; ++j)
{
cin >> productCodes[i][j];
}
}
vector<int> shelfPointers(numShelves, 0);
int minRange =INT_MAX;
int minRangeStart = -1, minRangeEnd = -1;
set<pair<int,int>> store;
for (int i = 0; i < numShelves; ++i)
{
store.insert({productCodes[i][0],i});
}
while (true)
{
int minCode =INT_MAX;
int maxCode = INT_MIN;
minCode = store.begin()->first;
maxCode = store.rbegin()->first;
if (maxCode - minCode < minRange)
{
minRange = maxCode - minCode;
minRangeStart = minCode;
minRangeEnd = maxCode;
}
int minPointer = store.begin()->second;
shelfPointers[minPointer]++;
if(shelfPointers[minPointer] == numCells)
break;
store.erase(store.begin()); store.insert({productCodes[minPointer][shelfPointers[minPointer]],minPointer});
}
}
Loading Similar Posts
Approach problem 1: we can set starting element and then search in each list for element greater than equal to this element with min abs diff,but this won't pass all the test cases TC: N*N*K*Log(k), you can optimize this using a priority queue, initially add the first element of all k lists to the priority queue, and check the range every time(mx among all elements in priority queue - pq.top()), remove the smallest element every time and add next element of the same list of which you removed the min element. this would end when one of the list exhausts.
Approach problem 3: use dfs or dsu to know which cells belong to each group, let's say group 1 and group 2. Then do a bfs once from all cells of group1 and then from all cells of group 2 seprately and store them in shortest1 and shortest2,the answer would be min(shortest1+shortest2) for all cells which neither belong to group 1 nor group2.