Blogs >> Miscellaneous >>
Solutions of Google Code Jam 2008 Qualification Round
I was able to solve two problems (out of three) of the 'Qualification Round' - "A. Saving the Universe" and "B. Train Timetable". I am giving here pseudo code to solve them. Problems can be seen here.
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.
I chose "Python" as a programming language for the coding. My code can be downloaded from the score board of the "Qualification Round", my rank is "2589" and user id is "shail229".
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.
I chose "Python" as a programming language for the coding. My code can be downloaded from the score board of the "Qualification Round", my rank is "2589" and user id is "shail229".
|
|
