So a while back I started doing practice problems in Topcoder for practice. Yesterday at work I noticed that there was one this weekend so I thought why not? The competitive Topcoder match is 1 hour and 15 minutes long, that doesn’t take much out of the day 🙂

Everything started okay, I logged in about 10 minutes before the coding match started. I’m lucky I woke up on time, I didn’t set an alarm..it’s the weekend! I registered and started waiting with everyone else. However when it wouldn’t let me open a match due to timeouts, I refreshed the page. After which I couldn’t login in to Topcoder.com for somewhere between 10-15 minutes after the coding phase had begun. This was frustrating, but I marched forward!

**Problem 1:**

Given an ordered collection of coins represented by a string whose state is either ‘H’ or ‘T’, a coin is interesting if one it’s neighbour is a different state. e.g. “HHH” has 0 interesting coins, “HTH” has 3 interesting coins.

Method signature:

1 |
int countCoins(std::string state); |

My solution felt really clumsy, it takes up a lot of code to check edge cases but maybe it’s necessary. The main strategy I took was to loop through string from 2nd element to second last element and compare neighbours.

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 |
#include<string> class CoinFlipsDiv2 { public: int countCoins(std::string state) { int num_coins_interesting = 0; int number_of_states = state.length(); if(number_of_states == 1) { return 0; } if ((number_of_states > 1)) { for(int i=1; i<number_of_states-1; i++) { auto coin_state = state[i]; if (coin_state != state[i-1] || coin_state != state[i+1]) { num_coins_interesting++; } } } if ((number_of_states > 1) && (state[0] != state[1])) { num_coins_interesting++; } if((number_of_states > 1) && (state[number_of_states-1] != state[number_of_states-2])) { num_coins_interesting++; } return num_coins_interesting; } }; |

**Problem 2:**

Two robots start in positions given by (x1, x1) and (x2,y2) respectively. You are given a string that represents movements that each robot will take e.g., “LRU” means that each robot will move left and then right and then down. Return “Explosion” if there is the possibility that the two robots will cross paths, “Safe” otherwise.

Method signature:

1 |
std::string canExplode(int x1, int y1, int x2, int y2, std::string directions); |

My strategy was to keep a list of all positions of each robot and then check to see if Robot1 ever has a position that Robot2 also had. This passed all but one of the unit tests… I might spend some time tonight debugging it.

EDIT: Oh my… I misread the problem statement…What I said above was my abbreviation of the statement, but it turns out that the robot might skip subsets of instructions.. so unfortunately the code below solves the wrong problem..

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 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <algorithm> #include <string> #include <vector> class ExplodingRobots { public: std::string canExplode(int x1, int y1, int x2, int y2, std::string directions) { robot1_positions.push_back({x1, y1}); robot2_positions.push_back({x2, y2}); robot1_current_position = {x1, y1}; robot2_current_position = {x2, y2}; for (auto elem: directions) { if(elem == 'U') { robot1_current_position.second++; robot2_current_position.second++; } if(elem == 'R') { robot1_current_position.first++; robot2_current_position.first++; } if(elem == 'L') { robot1_current_position.first--; robot2_current_position.first--; } if(elem == 'D') { robot1_current_position.second--; robot2_current_position.second--; } robot1_positions.push_back(robot1_current_position); robot2_positions.push_back(robot2_current_position); } for(auto elem: robot1_positions) { if(std::find(robot2_positions.begin(), robot2_positions.end(), elem) != robot2_positions.end()) { return "Explosion"; } } return "Safe"; } std::vector<std::pair<int, int>> robot1_positions; std::vector<std::pair<int, int>> robot2_positions; std::pair<int, int> robot1_current_position; std::pair<int, int> robot2_current_position; }; |

This could do with some obvious refactoring, but time constraints really push you to write code fast. Knowing that I misread the problem makes me feel better, since I was bewildered as to why one of the unit tests was failing. If I were to redo the problem I wouldn’t iterate through every position but rather since every sequence defines a rectangle of possible positions, it is enough to see if the intersection of the rectangles that each robot generates has a non zero intersection.

**Problem 3:**

Given a sequence of n integers, we can compute the bitwise XOR of each pair of integers. This will give us a list of n^2 integers. Your goal in this task is to reverse this process: you will be given the list of n^2 integers and you have to count all sequences of length n that would produce it.

Method signature:

1 |
int countLists(std:::vector<int> sequence, int m) |

where each integer in the sequence is less than m.

Unfortunately there was only 1 minute left in the competition when I opened this problem. But I’ll give a shot at the problem solving portion. Here is an example of the integers 5 and 3 whose bitwise XOR produce 6

0101

0011 XOR

—–

0110

but this could also be produce by:

1101

1011 XOR

—–

0110

1100

1010 XOR

—–

0110

0100

0010 XOR

—–

0110

So I think the strategy is to track the 0’s in the bitwise XOR. The integer m will give you the maximum number of bits, so if m was 8, only 4 bits would be used, 16, 5 bits would be used etc. So for every pair, there are 2^(max bits – (number of zeros in result of xor)) combinations. Store this result for every pair and multiply them together..or something along those lines 🙂 Following this logic somewhere would likely be fruitful.

Conclusion:

I was nervous trying this, but now I feel addicted and look forward to the next event!