You are not logged in. Please login at www.codechef.com to post your questions!

×

Funny gnomes tutorial

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

nil96's gravatar image

3★nil96
18071845
accept rate: 5%


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

link

answered 30 Aug '16, 11:01

wodahs_cc's gravatar image

6★wodahs_cc
212
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<integer,treeset<integer>> 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<n;i++){ st="new" stringtokenizer(br.readline());="" for(int="" j="0;j&lt;n;j++)" g[i][j]="Integer.parseInt(st.nextToken());" }="" fv_time="new" int[n][n];="" visited="new" boolean[n];="" cycle_times="new" hashmap<="">(); for(int i=0;i<n;i++){ for="" (int="" j="0;j&lt;n;j++)" fv_time[i][j]="Integer.MAX_VALUE;" visited[i]="false;" cycle_times.put(i,new="" treeset<="">()); } for(int i=0;i<n;i++){ arrays.fill(visited,false);="" if(!visited[i]){="" visited[i]="true;" fv_time[i][i]="0;" arraylist<integer=""> 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<n;i++){
        for (int j=0;j<n;j++)
            if(fv_time[i][j]==Integer.MAX_VALUE)
                fv_time[i][j]=-1;
    }

    for(int i=0;i<n;i++){
        System.out.print((i+1)+": ");
        for (int j=0;j<n;j++){
            System.out.print(fv_time[i][j]+" ");
        }
        System.out.println();
    }
    System.out.println("Cycles");
    for(int i=0;i<n;i++){
        TreeSet arl=cycle_times.get(i);
        System.out.print((i+1)+": ");
        Iterator it=arl.iterator();
        while (it.hasNext())
            System.out.print(it.next()+" ");
        System.out.println();
    }

    int m=Integer.parseInt(br.readLine());
    for(int i=0;i<m;i++){
        st=new StringTokenizer(br.readLine());
        int k=Integer.parseInt(st.nextToken());
        int x=Integer.parseInt(st.nextToken());
        TreeSet<Integer> ids=new TreeSet<>();
        for(int j=0;j<n;j++){
            if(fv_time[x-1][j]>k || 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<Integer> ts=cycle_times.get(j);
            Iterator<Integer> 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<Integer> 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<Integer> stack,int curr_time){
    for(int j=0;j<n;j++){
        if(g[vertex][j]==1){
            if(!visited[j]){
                visited[j]=true;
                stack.add(j);
                int new_time=curr_time+1;
                for(int i=0;i<stack.size();i++,new_time--){
                    if(fv_time[stack.get(i)][j]>new_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;i<stack.size();i++,new_time--){
                        if(fv_time[stack.get(i)][j]>new_time)
                            fv_time[stack.get(i)][j]=new_time;
                    }
                    for(int k=0;k<n;k++){
                        if(fv_time[j][k]!=Integer.MAX_VALUE){
                            new_time=curr_time+1;
                            for(int i=0;i<stack.size();i++,new_time--){
                                if(fv_time[stack.get(i)][k]>(new_time+fv_time[j][k]))
                                    fv_time[stack.get(i)][k]=new_time+fv_time[j][k];
                            }
                        }
                    }
                }
            }
        }
    }
}

}

link

answered 28 Aug '16, 18:52

kiruba17's gravatar image

0★kiruba17
-3
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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