I have never performed well in any early morning SRM, and today wasn’t any different. So I will skip any commentary and get straight to solutions that I could figure…

**DIV-2 Easy; TheExperimentDiv2:**

There are N droppers hanging from a ceiling numbered 0 to N-1, each dropping intensity[i] drops per minute. There are M sponges numbered 0 to M-1, each at a distance of (i+1)cm from the ceiling. Each sponge has length L, and its left end is at distance leftEnd[i] from wall of the room. Any drop that falls on a sponge, is completely absorbed. We have to find out how many drops each sponge absorbs per minute.

For each dropper, we need to find out which sponge will receive its drop at first. Any sponge that does, will have intensity of that dropper added to its total drops per minute absorption

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class TheExperimentDiv2 { public: bool isGood(int n, int L, int LE) { float pos = 0.5+n; if(pos>=LE && pos<=LE+L) { return true; } return false; } vector <int> determineHumidity(vector <int> inten, int L, vector <int> lE) { vector<int>sol(lE.size(), 0); for(int i=0;i<inten.size();i++) { for(int j=0;j<lE.size();j++) { if(isGood(i, L, lE[j])) { sol[j] += inten[i]; break; } } } return sol; } }; |

This problem requires us to travel through a grid of NxM cells, and reach a particular cell grid[coinRow][coinColumn], where we start at the bottom of the grid, and can only reach an upper row if we have a ladder of L such that our current row + L can take us to our desired upper row. Of course we can only go to a cell which has a platform and isn’t empty.

Since N and M can be at most 50, and bottom row is a complete platform, we can always reach our desired cell. What we need to find out is the minimum ladder length with which it is possible to do so. We can iterate over lengths of ladder from 0 to 50, and find out if it is possible to reach our destination cell from bottom row using this ladder, using depth/breadth first search.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
class ArcadeManao { public: vector<string>l; int cR; int cC; bool isGood(int L) { vector<vector<int> >v(l.size(), vector<int>(l[0].size(), 0)); queue<pair<int, int> >q; pair<int, int> p = make_pair(l.size()-1, 0); q.push(p); while(!q.empty()) { p = q.front(); q.pop(); if(v[p.first][p.second]) continue; v[p.first][p.second] = 1; if(p.first == cR && p.second == cC) return true; for(int i=0;i<=L;i++) { int r = p.first+i; int c = p.second; if(r>=0 && r<l.size() && l[r][c]=='X') q.push(make_pair(r, c)); r = p.first-i; if(r>=0 && r<l.size() && l[r][c]=='X') q.push(make_pair(r, c)); } if(p.second+1<l[p.first].size() && l[p.first][p.second+1]=='X') q.push(make_pair(p.first, p.second+1)); if(p.second-1>=0 && l[p.first][p.second-1]=='X') q.push(make_pair(p.first, p.second-1)); } return false; } int shortestLadder(vector <string> level, int coinRow, int coinColumn) { l = level; cR = coinRow-1; cC = coinColumn-1; for(int i=0;i<=50;i++) { if(isGood(i)) return i; } return -1; } }; |