### n00gler's blog

By n00gler, 5 months ago, ,

Google Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.

I invite you to solve some fun and interesting problems on May 26 2019, 09:00 UTC.

Dashboard can be accessed here during the contest. Problem analysis will be published soon after the contest.

• +19

 » 5 months ago, # |   0 The contest has started :) GL & HF
 » 5 months ago, # |   0 How to solve C?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 We can group the dogs by colors. And for each group of same color, we will visit the dogs in increasing distance. That means in a group of size $sz$, there are only $(sz + 1)$ options.Then we can use a standard knapsack dp to calculate the minimum. You can check the code the people on the scoreboard, since the code is very short.P.S: I overestimated the complexity and resubmitted at the last few minutes using another (and also more complicated) solution... Could've been in the first page of the scoreboard...
•  » » 5 months ago, # ^ |   0 Also, I submitted my solution for Visible set to Hidden set after contest finishes and it passed that set too. Complexity is around $O(\frac{N^3}{2^x})$, not sure about x tbh, and it's not a surprise that it passes. It's the same solution as described in the editorial.
 » 5 months ago, # |   +13 Is it possible to do A large without segment merging? :( Such a tedious task.
•  » » 5 months ago, # ^ |   +13 I did it with JAVA's bitset where the nextSetBit() and previousSetBit() functions are farely fast.
•  » » » 5 months ago, # ^ |   +6 Ouch! Maybe I should really start using bitsets. I really hate segment merging.
•  » » » » 5 months ago, # ^ |   +2 Bitset can sometimes help you get OK verdict if you are at the margin of the time limit or memory limit. However, they are risky because they do not affect the asymptotic complexity of your algorithm, they just do constant optimization.Firstly, always think how to improve the asymptotic complexity of the algorithm, only then think about constant optimizations (e.g. bitsets).
•  » » 5 months ago, # ^ |   +12 My solution was to keep a pointer to which cell you should "teleport to" whenever you touch it (for each of the 4 possible directions). The idea is very similar to disjoint-set data structure, because the "find" function needs to compress the pointers (so that after one pass, all the pointers are updated to the "farthest" cell).
•  » » » 5 months ago, # ^ |   0 I forgot how much more time and memory allowance kickstart has compared to other contests. Yeah, I know the dsu approach, but I didn't check the memory limits. That sucks :(
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +8 To clarify, I didn't store every cell in the matrix (which would be much more than the 1GB limit), I used four map> one for each direction.Code is here: Code#include #include using namespace std; int D_find(int pos, map& axis) { if (axis.find(pos) == axis.end()) { return pos; } else { return axis[pos] = D_find(axis[pos], axis); } } pair solve() { int N, R, C, SR, SC; cin >> N >> R >> C >> SR >> SC; string instructions; cin >> instructions; map> N_axis, S_axis, E_axis, W_axis; for (char c: instructions) { if (N_axis[SC].find(SR) == N_axis[SC].end()) { N_axis[SC][SR] = SR - 1; } if (S_axis[SC].find(SR) == S_axis[SC].end()) { S_axis[SC][SR] = SR + 1; } if (E_axis[SR].find(SC) == E_axis[SR].end()) { E_axis[SR][SC] = SC + 1; } if (W_axis[SR].find(SC) == W_axis[SR].end()) { W_axis[SR][SC] = SC - 1; } switch(c) { case 'N': SR = D_find(SR, N_axis[SC]); break; case 'S': SR = D_find(SR, S_axis[SC]); break; case 'E': SC = D_find(SC, E_axis[SR]); break; case 'W': SC = D_find(SC, W_axis[SR]); break; } } return {SR, SC}; } int main() { int T; cin >> T; for (int i=1; i<=T; i++) { auto ans = solve(); cout << "Case #" << i << ": " << ans.first << " " << ans.second << endl; } } 
•  » » » » » 5 months ago, # ^ |   0 Looks like you're referring to sparse DSU for each of the four directions.
 » 5 months ago, # |   +13 Is it only for me or the site is not accepting any submissions now?I'm trying to submit some solution now but the submit button is not working?!!
•  » » 5 months ago, # ^ |   +6 Same
•  » » 5 months ago, # ^ |   +3 Apologies, practice submissions should work now. Analysis for all problems are also available.
 » 3 months ago, # |   0 Where I can find editorial for this round.