Question: Flipkart, Online Assessment | E-Commerce Company | Online Video streaming platform | Space Agency | 13th August 2023
4
Entering edit mode

11
Entering edit mode

itna difficult kyun hai bc

Entering edit mode
3

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.

anonymous
• 50
Entering edit mode
0
void solve() { int n,m; cin>>n>>m; vector> v(n,vector(m)); cin>>v; vectorptrs(n); //used to maintain next pointers under consideration for each of the n shelves setproductrange; //Used to store one item from each shelf in our range under consideration for(int i=0;i=n) break; productrange.insert({v[shelfst][ptrs[shelfst]],shelfst}); ptrs[shelfst]++; } cout<
Manmeet
• 0
Entering edit mode
0
void solve() { int n,m; cin>>n>>m; vector> v(n,vector(m)); cin>>v; vectorptrs(n); //used to maintain next pointers under consideration for each of the n shelves setproductrange; //Used to store one item from each shelf in our range under consideration for(int i=0;i=n) break; productrange.insert({v[shelfst][ptrs[shelfst]],shelfst}); ptrs[shelfst]++; } cout<
Manmeet
• 0
Entering edit mode
0

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.

anonymous
• 50
5
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
0

hi

Aman
• 0
Entering edit mode
0

arre tori maai ke chodo... jab aata nhi h to laand liye soln daal deta hai sab ladka ka test kharab kar deta h madarchod

Aman
• 0
1
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

1
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});

}

}

Entering edit mode
0

i wrote the same code, 8/12 tc were only passing

Manmeet
• 0
Entering edit mode
1

for me it was showing 9/10 test cases passed

Ghost
• 80
0
Entering edit mode

Does anyone know the solution of question no -> 2