For me to help you I ask again for a link to the original problem, that'd be quite helpful.
About math and standard algorithms, you certainly need a bit of both for the contests. You can start with TopCoder's tutorials: www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static If you want to buy a book, I recommend you go for Cormen's Introduction to Algorithms (CLRS). It's actually an algorithm book, but has lots of proofs that will help you in some mathematical thinking and has some number theory and the like chapters. It's not the easiest to read, but if you're only buying one, buy that one. Other books, some of which might actually be better to start are: - Sedgewick's Algorithm (http://algs4.cs.princeton.edu/home/) - Skina's The Algorithm Design Manual If you really want to get into math, there's Knuth's Concrete Mathematics, but this is certainly not an easy book to read, it's great, but definitely not a starter book. Carlos Guía On Thu, Mar 28, 2013 at 12:25 PM, mandeep <mandeep...@gmail.com> wrote: > ok..i got it..i just want you to check my solution....because when i > submit it online..it shows wrong answer(don't know for what test case).... > And one more thing i find that many of programming problem are > mathematical and it don't use standered algorithm and i'm not good in > mathematical algo..so pls provide some good reference... > thanks a lot > > > > On 28 March 2013 20:30, Carlos Guia <carlos.guia.v...@gmail.com> wrote: > >> I see, that makes sense since that number does grow pretty fast. Well, >> I'm not sure you still have questions, but if you're still struggling, ping >> back after some trying. >> >> You should already have enough information on what to look for to solve >> the first part. >> >> Carlos Guía >> >> >> On Thu, Mar 28, 2013 at 10:19 AM, mandeep <mandeep...@gmail.com> wrote: >> >>> yeah you are right...i used module because after finding this you will >>> also have to find no of ways to choose a captain from a particular >>> path...if u have {1,2} {3,4} {5} then no of ways will be >>> {1,3,5},{1,4,5}{2,3,5},{2,4,5} that is 4...that why i have used module >>> above... >>> >>> >>> On 28 March 2013 18:23, Carlos Guia <carlos.guia.v...@gmail.com> wrote: >>> >>>> Could paste a link top the problem? I see your code is using modulo >>>> 1000000007 arithmetic, I don't expect a connected components problem top >>>> have that requirement as the graph would have to be huge for it to make >>>> sense. >>>> >>>> Reading the original problem might show what actually needs to be done >>>> is anther thing. >>>> >>>> Carlos Guia >>>> On Mar 28, 2013 9:45 AM, "Carlos Guia" <carlos.guia.v...@gmail.com> >>>> wrote: >>>> >>>>> You can DFS or BFS, they run linear time with respect the graph size. >>>>> There are faster ways, the terms Joseph used(combine sets) strongly >>>>> indicates he's hinting on using disjoint-sets (aka. union-find). >>>>> >>>>> Search for: number of connected components >>>>> >>>>> Carlos Guia >>>>> On Mar 28, 2013 9:09 AM, "mandeep" <mandeep...@gmail.com> wrote: >>>>> >>>>>> but DFS will be used to implement this problem???? >>>>>> >>>>>> >>>>>> On 28 March 2013 17:27, Joseph DeVincentis <dev...@gmail.com> wrote: >>>>>> >>>>>>> Start with {1},{2},{3},{4},{5},{6},{7},{8},{9},{10} >>>>>>> When you see 1 2, combine those sets: {1, >>>>>>> 2},{3},{4},{5},{6},{7},{8},{9},{10} >>>>>>> Likewise for 3 4 and 6 7: {1, 2},{3, 4},{5},{6, 7},{8},{9},{10} >>>>>>> When you get 1 4 you combine the two sets containing them: {1, 2, 3, >>>>>>> 4},{5},{6, 7},{8},{9},{10} >>>>>>> >>>>>>> >>>>>>> >>>>>>> On Thu, Mar 28, 2013 at 7:51 AM, mandeep <mandeep...@gmail.com>wrote: >>>>>>> >>>>>>>> Ok..well i forgot to add something here... >>>>>>>> if input is you have 10 elements and those pair who will share the >>>>>>>> same path is >>>>>>>> 1 2,3 4,6 7,1 4 >>>>>>>> then set will be {1,2,3,4},{5},{6,7},{8},{9},{10} that is output >>>>>>>> should be 6.. >>>>>>>> now tell me how to implement this problem... >>>>>>>> thanks a lot... >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>>> On 28 March 2013 03:14, Joseph DeVincentis <dev...@gmail.com>wrote: >>>>>>>> >>>>>>>>> No DFS is needed for the problem you pose here. It can be solved >>>>>>>>> in a single pass through the input. >>>>>>>>> On Mar 27, 2013 5:16 PM, "mandeep khatkar" <mandeep...@gmail.com> >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> Problem:- >>>>>>>>>> Suppose that you are given no. 1 2,2 3,4 5 so here 1,2,3 will >>>>>>>>>> share same path because of transitive relation between them and 4,5 >>>>>>>>>> will >>>>>>>>>> share other route....and even if u are given no. like 1 2,3 4,1 4 >>>>>>>>>> then in >>>>>>>>>> this case 1,2,3,4 will share same path...so you will have to output >>>>>>>>>> total >>>>>>>>>> no of path....i know it includes DFS.but still i am getting some >>>>>>>>>> error in >>>>>>>>>> output...here is my code... >>>>>>>>>> Input:- >>>>>>>>>> 1 2 >>>>>>>>>> 3 4 >>>>>>>>>> 1 4 >>>>>>>>>> 6 7 >>>>>>>>>> Ouput:-2 ({1,2,3,4},{6,7}) >>>>>>>>>> >>>>>>>>>> /* >>>>>>>>>> * To change this template, choose Tools | Templates >>>>>>>>>> * and open the template in the editor. >>>>>>>>>> */ >>>>>>>>>> package chef; >>>>>>>>>> import java.io.BufferedReader; >>>>>>>>>> import java.io.IOException; >>>>>>>>>> import java.io.InputStreamReader; >>>>>>>>>> import java.math.BigInteger; >>>>>>>>>> import java.util.StringTokenizer; >>>>>>>>>> /** >>>>>>>>>> * >>>>>>>>>> * @author Pardeep >>>>>>>>>> */ >>>>>>>>>> public class pathshare { >>>>>>>>>> >>>>>>>>>> public static void main(String a[]) throws IOException >>>>>>>>>> { >>>>>>>>>> BufferedReader br=new BufferedReader(new >>>>>>>>>> InputStreamReader(System.in)); >>>>>>>>>> int t=Integer.parseInt(br.readLine()); >>>>>>>>>> for(int tes=0;tes<t;tes++){ >>>>>>>>>> StringTokenizer st=new StringTokenizer(br.readLine()); >>>>>>>>>> int n=Integer.parseInt(st.nextToken()); >>>>>>>>>> //String ar[]=new String[n+1]; >>>>>>>>>> int pre[]=new int[n+1]; >>>>>>>>>> long val[]=new long[n+1]; >>>>>>>>>> int sto[]=new int[n+1]; >>>>>>>>>> //int relst[]=new int[n+1]; >>>>>>>>>> boolean setflag=false; >>>>>>>>>> boolean visit[]=new boolean[n+1]; >>>>>>>>>> for(int i=1;i<=n;i++) >>>>>>>>>> { >>>>>>>>>> //ar[i]=String.valueOf(i); >>>>>>>>>> pre[i]=i; >>>>>>>>>> visit[i]=false; >>>>>>>>>> val[i]=1; >>>>>>>>>> } >>>>>>>>>> int rel=Integer.parseInt(st.nextToken()); >>>>>>>>>> // int stack[]=new >>>>>>>>>> int[1000000]; >>>>>>>>>> int len=0; >>>>>>>>>> >>>>>>>>>> while(rel>=1){ >>>>>>>>>> setflag=true; >>>>>>>>>> st=new StringTokenizer(br.readLine()); >>>>>>>>>> int e1=Integer.parseInt(st.nextToken()); >>>>>>>>>> //stack[len++]=e1; >>>>>>>>>> int e2=Integer.parseInt(st.nextToken()); >>>>>>>>>> if(!visit[e2]||!visit[e1]) >>>>>>>>>> { >>>>>>>>>> int ch=pre[e2];int ch1=pre[e1]; >>>>>>>>>> if(pre[ch]!=pre[e2]&&visit[e2]){ >>>>>>>>>> pre[e2]=pre[ch]; >>>>>>>>>> ch=pre[e2]; >>>>>>>>>> } >>>>>>>>>> if(pre[ch1]!=pre[e1]&&visit[e1]){ >>>>>>>>>> // System.out.println("upr"); >>>>>>>>>> pre[e1]=pre[ch1]; >>>>>>>>>> ch1=pre[e1]; >>>>>>>>>> } >>>>>>>>>> //System.out.println("pr.."+pre[e1]+" "+pre[ch1]); >>>>>>>>>> if(!visit[e1]&&visit[e2]){ >>>>>>>>>> pre[e1]=pre[e2]; >>>>>>>>>> val[pre[e1]]+=1; >>>>>>>>>> visit[e1]=true; >>>>>>>>>> } >>>>>>>>>> else if(visit[e1]&&!visit[e2]){ >>>>>>>>>> >>>>>>>>>> pre[e2]=pre[e1];//System.out.println("checking...."); >>>>>>>>>> //1 >>>>>>>>>> 2,3 4,1 4 >>>>>>>>>> val[pre[e2]]+=1;visit[e2]=true; >>>>>>>>>> } >>>>>>>>>> else if(!visit[e1]&&!visit[e2]){ >>>>>>>>>> pre[e2]=pre[e1]; >>>>>>>>>> val[pre[e2]]+=1; >>>>>>>>>> visit[e2]=visit[e1]=true; >>>>>>>>>> } >>>>>>>>>> //visit[e2]=visit[e1]=true; >>>>>>>>>> //System.out.println("ar: "+val[pre[e1]]+" "+pre[e1]); >>>>>>>>>> //} >>>>>>>>>> } >>>>>>>>>> else if((visit[e2]&&visit[e1])&&pre[e2]!=pre[e1]){ >>>>>>>>>> val[pre[e1]]+=val[pre[e2]]; >>>>>>>>>> int ch=pre[e2];val[pre[e2]]=1; >>>>>>>>>> while(ch!=pre[e1]){ >>>>>>>>>> pre[ch]=pre[e1]; >>>>>>>>>> ch=pre[ch];//System.out.println("lwr"); >>>>>>>>>> } >>>>>>>>>> pre[e2]=pre[e1]; >>>>>>>>>> // System.out.println("visited.. "+val[pre[e1]]+" >>>>>>>>>> "+pre[e2]); >>>>>>>>>> } >>>>>>>>>> rel--; >>>>>>>>>> } >>>>>>>>>> BigInteger vallen= BigInteger.valueOf(1); >>>>>>>>>> len=0;long mod=1000000007; >>>>>>>>>> long valrel=0;boolean flag=false;long vf=0;boolean zero=false; >>>>>>>>>> //for(int i=1;i<=n;i++) System.out.println(val[i]+" >>>>>>>>>> "+visit[i]); >>>>>>>>>> for(int i=1;i<=n;i++){ >>>>>>>>>> >>>>>>>>>> if(val[i]==1&&!visit[i]){ >>>>>>>>>> >>>>>>>>>> //System.out.println("computing.... 1"); >>>>>>>>>> valrel++;zero=true; >>>>>>>>>> } >>>>>>>>>> else if(val[i]>1&&visit[i]&&vf!=0){ >>>>>>>>>> //System.out.println("computing..O"); >>>>>>>>>> >>>>>>>>>> vallen=vallen.multiply(BigInteger.valueOf(val[i])).mod(BigInteger.valueOf(mod));//System.out.println("m"+vallen); >>>>>>>>>> //System.out.println("l.."+vallen); >>>>>>>>>> valrel++;//len++; >>>>>>>>>> flag=true;zero=true; >>>>>>>>>> } >>>>>>>>>> else if(val[i]>1&&visit[i]&&vf==0){ >>>>>>>>>> vf=val[i];valrel++;flag=true; >>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> } >>>>>>>>>> //if(!flag){ vallen=BigInteger.valueOf(1);vf=1;} >>>>>>>>>> //if(!zero){vallen=BigInteger.valueOf(vf);} >>>>>>>>>> // else >>>>>>>>>> {vallen=vallen.multiply(BigInteger.valueOf(vf)).mod(BigInteger.valueOf(mod));} >>>>>>>>>> >>>>>>>>>> //if(rel==0&&setflag==false){vf=0;vallen=vallen.multiply(BigInteger.ZERO);} >>>>>>>>>> //System.out.println(bg); >>>>>>>>>> System.out.println(valrel); >>>>>>>>>> //System.out.println((valrel%mod)+" "+(vallen%mod)); >>>>>>>>>> }} >>>>>>>>>> } >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> 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/msg/google-code/-/TOYJDXEhq5UJ. >>>>>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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. >>>>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>> >>>>>>>> -- >>>>>>>> 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. >>>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> -- >>>>>> 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. >>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>> >>>>>> >>>>>> >>>>> -- >>>> 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. >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> -- >>> 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. >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> 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. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- > 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. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- 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. For more options, visit https://groups.google.com/groups/opt_out.
