Blogs >> Technology >>
Solutions for Google code jam ,2008
A. Saving the Universe:
Step 1: num_switches = -1.
Step 2: If incoming_queries is empty then return num_switches else goto Step 3.
Step 3: If there is any engine in search_engines, which is not present in incoming_queries then return (num_switches + 1) else goto Step 4.
Step 4: Find the engine in the incoming_queries such that it's index (index of the first occurrence) is more than the index of other engines in the incoming_queries. Store the index of this engine in max_index.
i.e. max_index = MAX{index(engine) : index(engine) is the index of the engine in incoming_queries where engine belongs to search_engines}
Step 5: Remove queries of index 0 to max_index-1 from incoming_queries, goto Step 2.
B. Train Timetable
Step 1: Converts all the times in minutes while storing. For trips from A to B, store all the departure times in a list departs_from_A and arrivals times in a list ready_at_B, similarly for trips from B to A, store all the departure times in a list departs_from_B and arrivals times in list ready_at_A.
Step 2: Add turnaround time in the each entry of ready_at_A and ready_at_B.
Step 3: Sort all the four lists in ascending order.
Step 4: fromA = 0 and fromB = 0
Step 5: If departs_from_A is empty then goto Step 9 else goto Step 6.
Step 6: If ready_at_A is non-empty and first entry of departs_from_A >= first entry of ready_at_A then remove the first element from ready_at_A and goto Step 8 else goto Step 7.
Step 7: fromA = fromA + 1
Step 8: Remove the first element from departs_from_A and goto Step 5.
Step 9: If departs_from_B is empty then goto Step 13 else goto Step 10.
Step 10: If ready_at_B is non-empty and first entry of departs_from_B >= first entry of ready_at_B then remove the first element from ready_at_B and goto Step 12 else goto Step 11.
Step 11: fromB = fromB + 1
Step 12: Remove the first element from departs_from_B and goto Step 9.
Step 13: return fromA and fromB.
Step 1: num_switches = -1.
Step 2: If incoming_queries is empty then return num_switches else goto Step 3.
Step 3: If there is any engine in search_engines, which is not present in incoming_queries then return (num_switches + 1) else goto Step 4.
Step 4: Find the engine in the incoming_queries such that it's index (index of the first occurrence) is more than the index of other engines in the incoming_queries. Store the index of this engine in max_index.
i.e. max_index = MAX{index(engine) : index(engine) is the index of the engine in incoming_queries where engine belongs to search_engines}
Step 5: Remove queries of index 0 to max_index-1 from incoming_queries, goto Step 2.
B. Train Timetable
Step 1: Converts all the times in minutes while storing. For trips from A to B, store all the departure times in a list departs_from_A and arrivals times in a list ready_at_B, similarly for trips from B to A, store all the departure times in a list departs_from_B and arrivals times in list ready_at_A.
Step 2: Add turnaround time in the each entry of ready_at_A and ready_at_B.
Step 3: Sort all the four lists in ascending order.
Step 4: fromA = 0 and fromB = 0
Step 5: If departs_from_A is empty then goto Step 9 else goto Step 6.
Step 6: If ready_at_A is non-empty and first entry of departs_from_A >= first entry of ready_at_A then remove the first element from ready_at_A and goto Step 8 else goto Step 7.
Step 7: fromA = fromA + 1
Step 8: Remove the first element from departs_from_A and goto Step 5.
Step 9: If departs_from_B is empty then goto Step 13 else goto Step 10.
Step 10: If ready_at_B is non-empty and first entry of departs_from_B >= first entry of ready_at_B then remove the first element from ready_at_B and goto Step 12 else goto Step 11.
Step 11: fromB = fromB + 1
Step 12: Remove the first element from departs_from_B and goto Step 9.
Step 13: return fromA and fromB.
|
|
