Any possible account at Nekster (http://www.nekster.com) ?
On Fri, Apr 20, 2012 at 5:25 PM, <[email protected]> wrote: > Today's Topic Summary > > Group: http://groups.google.com/group/google-code/topics > > - can anyone give some idea or hint how should i approach this > problem. how should i procceed... cant get what logic should i apply . Plz > Help..... <#136cf9b465c3caba_group_thread_0> [1 Update] > - What if we remove an edge from a > graph<#136cf9b465c3caba_group_thread_1>[6 Updates] > - which IDE do top scorers use for > C++.<#136cf9b465c3caba_group_thread_2>[3 Updates] > - Tutorials for GMP <#136cf9b465c3caba_group_thread_3> [1 Update] > > can anyone give some idea or hint how should i approach this problem. > how should i procceed... cant get what logic should i apply . Plz > Help.....<http://groups.google.com/group/google-code/t/cdea21ab4fa5922> > > Registered user <[email protected]> Apr 20 05:05PM +0530 > > can anyone give some idea or hint how should i approach this problem. > how should i procceed... cant get what logic should i apply . Plz > Help..... > > > > thnks in advance.. > > Problem: > > Recently, with the release of the ultimate computing device bytePad, a > platform game with the simple name "Rotation Puzzle" immediately > became a phenomenon among Bytelandians. The game is extremely simple, > yet quite additive. Here's the rule: > Given a MxN rectangular grid in which each cell contains a unique > number from 1 to MxN. In each step, the player can pick any 2x2 > subgrid and perform a rotation (whether clockwise or > counterclockwise). > The task is to transform from the initial grid to the final > configuration, using as few steps as possible. > The final configuration is the configuration > 1 2 ... n > n+1 n+2 ... 2n > ... ... ... ... > (m-1)n+1 (m-1)n+2 ... mn > You may have guessed why this game is addictive: it requires a > tremendous visualization skill! > Input > > The first line contains a number T (about 5000), which is the number > of test cases. Each test case has the following form. > The first line contains two numbers M and N (2 <= M, N <= 34). > The next M lines contains the description of the grid. > Each test case's input is separated by a blank line. > It is guaranteed that each input data has a solution. > Output > > For each test case, output the result in the following format. > The first line contains a number K, the number of steps you need to > solve the puzzle. K must not exceed 10000. > Each line of the next K lines contain three numbers c, i, j (c=0 or > c=1, 1<=I < M, 1 <= J < N). (i,j) is the top-left coordinate of the > 2x2 square that is need to be rotated. c=1 if the rotation if > clockwise and c=0 if the rotation is counter-clockwise. > Prints a blank link after each test case's output. > Scoring > > Given m and n, we pick a random positive integer K* and starting from > the final configuration, we perform a random operation K* times to > generate the test case. For each test case, your score is K*/K+1. > Example > > Input: > 2 > > 2 3 > 1 5 2 > 4 6 3 > > 2 3 > 5 6 2 > 1 4 3 > > Output: > 1 > 0 1 2 > > 2 > 1 1 1 > 0 1 2 > > > > What if we remove an edge from a > graph<http://groups.google.com/group/google-code/t/1dd07f765d525347> > > vivek dhiman <[email protected]> Apr 20 09:49AM +0530 > > Hi all geeks > > So I have a simple question. > > Suppose you have a graph G(V,E). > You are supposed to find the shortest path from a vertex 's' to vertex > 'e' > for 'n' different cases. > > In each case one of the edges 'Ei' (any one edge) of the graph will be > blocked/deleted only for that case and we have to find the shortest > path in > the graph with that edge removed. > > Guys finding the shortest path is easy. But how can I make the algo so > fast > that even if I remove one of the edges my algo should still be very > fast. > O(n log n) or faster. > Remember we are not deleting the edges permanently. We are just > temporary > removing one edge per case. > In each case only one edge is removed. > Suppose we blocked one edge E in one case. We have to find the shortest > path for the graph. > In next case, we will reconnect the last edge and we will block/remove > a > new edge. And again for this new case we have to find the shortest > path. > > Another way of understanding the problem is suppose there are cities > connected to each other. > And every day one of the roads gets blocked because of heavy rain. > what is > the shortest path every day from city s to e. > Also one more important thing to note that each road can be used only > once. > But there could be more than 1 direct road from city a to city b. > > FInd the shortest path distance from city s to e on a day when all > direct > roads from city f to city h are blocked. If there is no connecting path > return -1 > > Thanks and Regards > Vivek Dhiman > > > > > vivek dhiman <[email protected]> Apr 20 10:16AM +0530 > > Hi all geeks > > So I have a simple question. > > Suppose you have a graph G(V,E). > You are supposed to find the shortest path from a vertex 's' to vertex > 'e' for 'n' different cases. > > In each case one of the edges 'Ei' (any one edge) of the graph will be > blocked/deleted only for that case and we have to find the shortest > path in > the graph with that edge removed. > > Guys finding the shortest path is easy. But how can I make the algo so > fast that even if I remove one of the edges my algo should still be > very > fast. O(n log n) or faster. > Remember we are not deleting the edges permanently. We are just > temporary removing one edge per case. > In each case only one edge is removed. > Suppose we blocked one edge E in one case. We have to find the shortest > path for the graph. > In next case, we will reconnect the last edge and we will block/remove > a new edge. And again for this new case we have to find the shortest > path. > > Another way of understanding the problem is suppose there are cities > connected to each other. > And every day one of the roads gets blocked because of heavy rain. what > is the shortest path every day from city s to e. > Also one more important thing to note that each road can be used only > once. > > There is only one road from one city to another > > Find the shortest path distance from city s to e on a day when all > direct roads from city f to city h are blocked. If there is no > connecting > path return -1 > > Thanks and Regards > Vivek Dhiman > > > > > Luke Pebody <[email protected]> Apr 20 06:38AM +0100 > > Here's a start for you. Find the shortest route. This works as an > answer if you remove any edge not in that route. Now you just have to solve > it for any removed edges that are in that route. > > > > > > > > vivek dhiman <[email protected]> Apr 20 12:18PM +0530 > > ok.. > So if an edge is removed from existing path.Do i have to again find the > shortest path ? > > > -- > Regards > Vivek Dhiman > > > > > Andrey Ponomarev <[email protected]> Apr 20 12:29PM +0400 > > Hypothesis 1: after eliminating one edge e' the shortest path from a > to b must contain vertex v, such that > neighter sp(a,v), nor sp(v,b) contain e' in the original graph, if > there is such. (Here sp stands for 'shortest path') > Hypothesis 2: if v is some vertex of the modified graph, such that > neighter sp(a,v), nor sp(v,b) contain e' in > the original graph, the shortest path from a to b in the modified > graph is len(sp(a,v)) + len(sp(v,b)). > > If both hypotheses are true then you may try following. In the > original graph build 2 shortest path trees: > one from a and one from b with edges reversed. The first tree let you > at O(1) find len(sp(a,v)), аnd > the second let you at O(1) find len(sp(v,b)). When you have an edge > (v1, v2) removed you should walk > tree1 from v2 and tree2 from v1 and mark all vertices you pass by. > Then you should find one unmarked > vertex with the minimum sum of len(sp(a,v)) + len(sp(v,b)) - it will > be the shortest path and it took O(n). > > 20 апреля 2012 г. 10:48 пользователь vivek dhiman > > > > > Registered user <[email protected]> Apr 20 02:14PM +0530 > > i think if u mark the path which u want to block as visited beforehand > then u may get it, m not sure but i think it should work. > > or if possilbe give the sample input / output cases , den i may solve > it.... > > > > > which IDE do top scorers use for > C++.<http://groups.google.com/group/google-code/t/c3549a71cbbce86a> > > Mohamed Bilal <[email protected]> Apr 19 05:34PM +0530 > > That's nice Luke :) !! > > I use notepad++ in windows. It has nice support for c++ and all popular > languages. > > > > > -- > Regards, > > A.Mohamed Bilal > QA Engineer > GlobalScholar > > > > > Registered user <[email protected]> Apr 19 06:11PM +0530 > > thnks Bilal. > > others.. > i mean is there any IDE (for C++ ) that gives suggestion while coding > like netbeans do. > > > > > > vivek dhiman <[email protected]> Apr 19 06:34PM +0530 > > dev cp or eclipse > > On Thu, Apr 19, 2012 at 6:11 PM, Registered user > > -- > Regards > Vivek Dhiman > > > > Tutorials for > GMP<http://groups.google.com/group/google-code/t/a50277333c5d154> > > Mohamed Bilal <[email protected]> Apr 19 05:35PM +0530 > > Hi, > > Can anyone lists some popular and easy to learn tutorials for using GMP > with C++?? > > -- > Regards, > > A.Mohamed Bilal > QA Engineer > GlobalScholar > > > > You received this message because you are subscribed to the Google Group > google-code. > You can post via email <[email protected]>. > To unsubscribe from this group, > send<[email protected]>an empty message. > For more options, > visit<http://groups.google.com/group/google-code/topics>this group. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" 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. > -- Abhishek -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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.
