We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Definite Random Walks
Definite Random Walks
Sort by
recency
|
7 Discussions
|
Please Login in order to post a comment
Here is my solution in java, C++ HackerRank Definite Random Walks Solution
Here is the solution of Definite Random Walks Click Here
Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-definite-random-walks-problem-solution.html
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.InputMismatchException; import java.util.Map;
public class G2 { InputStream is; PrintWriter out; String INPUT = ""; // String INPUT = "7 3 1\r\n" + // "4 2 7 2 4 3 5 \r\n" + // "0 1 0 "; // String INPUT = "4 2 1\r\n" + // "1 4 2 3 \r\n" + // "748683265 249561089"; // 1 2->4->3->2 // String INPUT = "4 2 2\r\n" + // "2 3 1 3 \r\n" + // "0 1 "; // 1/4 1/4 1/2 // 1/2 1/4 1/4 // String INPUT = "3 1 2\r\n" + // "1 3 1 \r\n" + // "1 "; // String INPUT = "4 5 1\r\n" + // "2 3 2 4\r\n" + // "332748118 332748118 332748118 0 0";
// tr("phase 0"); long[] made = make(ps, K, n+1, 1);
// tr("phase 1"); long[] rets = new long[n]; int[][] maps = makeBuckets(tclus, n); for(int i = 0;i < n;i++){ if(maps[i].length > 0){ int[] map = maps[i]; int[] lpar = new int[map.length]; int p = 0; for(int x : maps[i]){ if(sres.incycle[x]){ lpar[p++] = -1; }else{ lpar[p++] = Arrays.binarySearch(map, f[x]); } } long[] res = solve(parentToG(lpar), lpar, made, H, Arrays.binarySearch(map, i)); for(int j = 0;j < res.length;j++){ if(!sres.incycle[map[j]]){ rets[map[j]] += res[j]; } } } } // tr("phase 2");
// tr("phase 3"); // for(int j = made.length-1-1;j >= 0;j--){ // made[j] += made[j+1]; // if(made[j] >= mod)made[j] -= mod; // }
// tr("phase 4");
// tr(g, root); // tr(marked);
// tr("fdep", fdep, marked); long[] ced = convoluteSimply(rfdep, Arrays.copyOf(di, lmaxdep+1), mod, 3); for(int j = i;j != -1;j = par[j]){ ret[j] += ced[lmaxdep-dep[j]]; } } }
// public static final int[] NTTPrimes = {1012924417, 1004535809, 998244353, 985661441, 975175681, 962592769, 950009857, 943718401, 935329793, 924844033}; // public static final int[] NTTPrimitiveRoots = {5, 3, 3, 3, 17, 7, 7, 7, 3, 5};
// long Q = (u&(1L<<32)-1)*J&(1L<<32)-1; long Q = (u<<32)*J>>>32; dst[t] = (u>>>32)-(Q*P>>>32)+P; } } if(i < h-1){ for(int k = 0;k < 1<= P)dst[i] -= P; } for(int i = 0;i < n;i++){ int rev = Integer.reverse(i)>>>-h; if(i < rev){ long d = dst[i]; dst[i] = dst[rev]; dst[rev] = d; } }
// dw = dw * dw % P; if(i < h-1){ for(int k = 0;k < 1<= P)dst[i] -= P; } for(int i = 0;i < n;i++){ int rev = Integer.reverse(i)>>>-h; if(i < rev){ long d = dst[i]; dst[i] = dst[rev]; dst[rev] = d; } }
}
I think I have a Java implementation of an algorithm, but it's getting hammered in matrix multiplies where the elements are "BigMod" objects representing integers modulo 998244353, with addition, multiplication, inverse,... I'm wondering if the problem is brain leakage -- I know my algorithm is O(nNodes ** 3), maybe there's a better algorithm. On the other hand, if this really is the bound, is it worthwhile to rewrite in C/C++ or Python? Another angle would be to use a proper matrix package and converting operation results by % 998244353. Is there some way to import external (git-accessible) libraries into a Hackerrank workspace?