Hi Giuseppe, To be honest, the small solution is often very complicated compared to the optimal one. This is the case here.
What you are supposed to do is: - consider every state (combination of - - - to +++) as a node of your graph. You start at the node. Mark each node as "unvisited". Make a list of nodes "to_visit" and put the starting state (the state given as the input of your problem) in it, along with a number which is the distance from the starting point. Since this one is the starting point, the distance is 0. Then do the following steps in a loop: - Pick the first item in the list to_visit. If it is already visited, continue the loop. If not, Mark it as visited. - If the state is the state you want (+++) return the distance associated, it is the answer of the problem. - Compute the 10 neighboring states. Those are the states that you obtain if you flip 1,...,10 pancakes. Add 1 to the distance and then add them at the end of the to_visit list with the new distance value. Since you will first visit all the neighboring states before searching deeper in the graph, it is a breadth first search. It guarantees that the fist time you hit the final state is associated with the shortest distance from the starting point. Le dim. 10 avr. 2016 15:13, Fork Security <fsak...@gmail.com> a écrit : > Reading the Contest Analysis[0] from GCJ Qualification 2016, for the > Problem B is said that > > > In the small case we have a stack of at most 10 pancakes. The total > number of possible different states we can get by performing any number of > flips is thus 210= 1024. As this is a small number of states, we can solve > the small test case by performing a breadth first search over this state > space. For N pancakes, this can be implemented to complete within O(N 2**N) > time. > > I don't understand if it's just an hint or a complete solution. > > What does they mean exactly by "breadth first search"ing over all the > possible 1024 state? > > Thanks, > Giuseppe > > --- > [0], https://code.google.com/codejam/contest/6254486/dashboard#s=a&a=1 > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CABuo9_aD0rX_SYjehu1VYwXS3M1KLUiD8ZzZAgArg-F2pYHTnw%40mail.gmail.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CA%2B5pNgL2unX0MiBd3sjKs0FGuYZ95-qxqOyTojaLUXTZ1tFEuA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
