×

Funny gnomes tutorial

 0 Can anyone give me the tutorial of this qstn https://www.codechef.com/AUG16/problems/SHAIKHGN I cant find any where asked 28 Aug '16, 18:15 3★nil96 180●7●18●45 accept rate: 5%

 4 You are given an adjacency matrix A. Ak(i,j) of Kth power of an adjacency matrix denotes number of paths of length k from node i to node j. Now you don't really need a count of these paths but just weather there is any path. So what you really need is if Ak(x,j) is greater than 0 or not. So in simple terms you can represent your Adjacency matrix in bitset format where a bit is 1 if Ak(i,j) is greater than 0 else its set to 0. Now all you need to do is matrix powering which is n-cube and is slow... to lower down the complexity even more you can use something called a 4-russian algorithm One extra thing to remember is that you need not calculate all the rows for kth power but only the one row for xth row in query. Also you can precalculate A^2, A^4... A^536870912 as it will be needed at query time calculation for all the queries. My solution answered 30 Aug '16, 11:01 21●2 accept rate: 0%
 -4 package main; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main{ static int n; static int[][] g; static int[][] fv_time; static boolean[] visited; static Map> cycle_times; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; n=Integer.parseInt(br.readLine()); g=new int[n][n]; for(int i=0;i(); for(int i=0;i()); } for(int i=0;i stack=new ArrayList<>(); stack.add(i); dfs(i,stack,0); stack.remove(stack.size()-1); //System.out.println(stack.size()); //System.out.println(last_visited.size()); } }  for(int i=0;i ids=new TreeSet<>(); for(int j=0;jk || fv_time[x-1][j]<0) continue; int r=k-fv_time[x-1][j]; if(r==0){ ids.add(j); continue; } //System.out.println("r:"+r+" "+k+" "+fv_time[x-1][j]); TreeSet ts=cycle_times.get(j); Iterator it=ts.iterator(); while (it.hasNext()){ int cy_len=it.next(); //System.out.println("cylen:"+cy_len); if(r%cy_len==0){ ids.add(j); break; } } } //System.out.println("Query:"+(i+1)); if(ids.size()==0){ System.out.println(0); System.out.println(-1); } else{ System.out.println(ids.size()); Iterator it=ids.iterator(); int j=0; while (it.hasNext()){ if(j==0){ System.out.print((it.next()+1)); j++; }else System.out.print(" "+(it.next()+1)); } System.out.println(); } } } static void dfs(int vertex,ArrayList stack,int curr_time){ for(int j=0;jnew_time) fv_time[stack.get(i)][j]=new_time; } dfs(j,stack,curr_time+1); stack.remove(stack.size()-1); }else{ boolean found=false; int index=-1; for(int i=stack.size()-1;i>=0;i--){ if(stack.get(i)==j){ found=true; index=i; } } if(found){ int cycle_len=stack.size()-index; for(int i=stack.size()-1;i>index;i--){ int c=cycle_len-1; for(int k=i-1;k>=index;k--){ if(fv_time[stack.get(i)][stack.get(k)]>c) fv_time[stack.get(i)][stack.get(k)]=c--; } cycle_times.get(stack.get(i)).add(cycle_len); } cycle_times.get(stack.get(index)).add(cycle_len); }else{ int new_time=curr_time+1; for(int i=0;inew_time) fv_time[stack.get(i)][j]=new_time; } for(int k=0;k(new_time+fv_time[j][k])) fv_time[stack.get(i)][k]=new_time+fv_time[j][k]; } } } } } } } }  } answered 28 Aug '16, 18:52 0★kiruba17 -3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,631
×1,911
×1,655
×1,401
×1,217

question asked: 28 Aug '16, 18:15

question was seen: 1,552 times

last updated: 30 Aug '16, 20:15