Anyone with experience, please advice. The naive solution to this question is obviously O(n^2), now my question is: (1) usually naive solution can work within time limit ? (2) if it can work for small data set, do you go ahead with the large data set or you will spend some time try to optimize it first, which would mean you have less time for other questions? (3) or all the questions in code jam is designed in such a way that naive approach will fail, thus we must always strive for more efficient algorithm, e.g. O(n*log(n))?
On Fri, Aug 14, 2009 at 9:48 AM, Hawston LLH <[email protected]> wrote: > K = 13, mean total you have 13 cards: 1,2,...,13design an algorithm to > sort them in "perfect" way: 1, 11, 2, 8, 7, 3, 13, 9, 6, 4, 15, 14, 12, 10, > 5 > then check the index and output corresponding numbers (not all of the above > list but the intended ones only) : 2 (3rd number), 8 (4th number), 13 (7th), > 4 (10th) > > > > On Thu, Aug 13, 2009 at 11:46 AM, Shoubhik <[email protected]> wrote: > >> >> >> >> Problem >> >> Mousetrap is a simple card game for one player. It is played with a >> shuffled deck of cards numbered 1 through K, face down. You play by >> revealing the top card of the deck and then putting it on the bottom >> of the deck, keeping count of how many cards you have revealed. If you >> reveal a card whose number matches the current count, remove it from >> the deck and reset the count. If the count ever reaches K+1, you have >> lost. If the deck runs out of cards, you win. >> >> Suppose you have a deck of 5 cards, in the order 2, 5, 3, 1, 4. You >> will reveal the 2 on count 1, the 5 on count 2, then the 3 on count 3. >> Since the value matches the count, you remove the 3 from the deck, and >> reset the count. You now have 4 cards left in the order 1, 4, 2, 5. >> You then reveal the 1 on count 1, and remove it as well (you're doing >> great so far!). Continuing in this way you will remove the 2, then the >> 4, and then finally the 5 for victory. >> >> You would like to set up a deck of cards in such a way that you will >> win the game and remove the cards in increasing order. We'll call a >> deck organized in this way "perfect." For example, with 4 cards you >> can organize the deck as 1, 4, 2, 3, and you will win by removing the >> cards in the order 1, 2, 3, 4. >> >> Input >> >> The first line of input gives the number of cases, T. Each test case >> starts with a line containing K, the number of cards in a deck. The >> next line starts with an integer n, which is followed by n integers >> (d1,d2, ...), indices into the deck. >> >> Output >> >> For each test case, output one line containing "Case #x: " followed by >> n integers (k1,k2, ...), where ki is the value of the card at index di >> of a perfect deck of size K. The numbers in the output should be >> separated by spaces, and there must be at least one space following >> the colon in each "Case #x:" line. >> >> Limits >> >> Small dataset >> >> T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K. >> >> Large dataset >> >> T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K. >> >> Sample >> >> INPUT >> >> 2 >> >> 5 >> 5 1 2 3 4 5 >> >> 15 >> 4 3 4 7 10 >> >> >> OUTPUT >> >> Case #1: 1 3 2 5 4 >> Case #2: 2 8 13 4 >> >> >> >> http://code.google.com/codejam/contest/dashboard?c=agxjb2RlamFtLXByb2RyEAsSCGNvbnRlc3RzGJH6AQw#s=p2 >> >> The above is the 'cut-out' from the "MOUSETRAP" problem which appeared >> in Google Code Jam 2008 ROUND 1B >> >> I would request all of you to go through it first. >> >> I could not understand the the difference between 'K' and 'n' >> consequently test cases.(see the second input case 4 3 4 7 10, the >> OUTPUT consists of 2 8 13 4 ) From where did these numbers come . im >> confused . please help. >> >> >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
