HackerRank Jumping Rooks problem solution YASH PAL, 31 July 2024 In this HackerRank Jumping Rooks problem solution, You have Given the configuration of the chessboard and some k, help Nina place k jumping rooks in the chessboard’s free cells such that the number of pairs of rooks that beat each other is minimal. Then print a single integer denoting the number of rooks that beat each other. Topics we are covering Toggle Problem solution in Java.Problem solution in C++.Problem solution in C. Problem solution in Java. import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.List; public class C { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(), K = ni(); char[][] map = nm(n,n); int[][] ud = new int[n][n]; int[][] lr = new int[n][n]; int pud = 0, plr = 0; { int id = -1; for(int i = 0;i < n;i++){ char pre = 0; for(int j = 0;j < n;j++){ if(map[j][i] == '.'){ if(pre != '.')id++; ud[j][i] = id; } pre = map[j][i]; } } pud = id + 1; } { int id = -1; for(int i = 0;i < n;i++){ char pre = 0; for(int j = 0;j < n;j++){ if(map[i][j] == '.'){ if(pre != '.')id++; lr[i][j] = id; } pre = map[i][j]; } } plr = id + 1; } List<Edge> es = new ArrayList<>(); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(map[i][j] == '.'){ es.add(new Edge(ud[i][j], lr[i][j]+pud, 1, 0)); } } } int src = pud + plr, sink = src + 1; for(int i = 0;i < pud;i++){ for(int j = 0;j <= n;j++){ es.add(new Edge(src, i, 1, j)); } } for(int i = 0;i < plr;i++){ for(int j = 0;j <= n;j++){ es.add(new Edge(i+pud, sink, 1, j)); } } out.println(solveMinCostFlow(compileWD(sink+1, es), src, sink, K)); } public static class Edge { public int from, to; public int capacity; public int cost; public int flow; public Edge complement; // public int iniflow; public Edge(int from, int to, int capacity, int cost) { this.from = from; this.to = to; this.capacity = capacity; this.cost = cost; } } public static Edge[][] compileWD(int n, List<Edge> edges) { Edge[][] g = new Edge[n][]; // cloning for(int i = edges.size()-1;i >= 0;i--){ Edge origin = edges.get(i); Edge clone = new Edge(origin.to, origin.from, origin.capacity, -origin.cost); clone.flow = origin.capacity; clone.complement = origin; origin.complement = clone; edges.add(clone); } int[] p = new int[n]; for(Edge e : edges)p[e.from]++; for(int i = 0;i < n;i++)g[i] = new Edge[p[i]]; for(Edge e : edges)g[e.from][--p[e.from]] = e; return g; } // NOT VERIFIED public static Edge[][] compileWU(int n, List<Edge> edges) { Edge[][] g = new Edge[n][]; // cloning for(int i = edges.size()-1;i >= 0;i--){ Edge origin = edges.get(i); Edge back = new Edge(origin.to, origin.from, origin.capacity, origin.cost); edges.add(back); } for(int i = edges.size()-1;i >= 0;i--){ Edge origin = edges.get(i); Edge clone = new Edge(origin.to, origin.from, origin.capacity, -origin.cost); clone.flow = origin.capacity; clone.complement = origin; origin.complement = clone; edges.add(clone); } int[] p = new int[n]; for(Edge e : edges)p[e.from]++; for(int i = 0;i < n;i++)g[i] = new Edge[p[i]]; for(Edge e : edges)g[e.from][--p[e.from]] = e; return g; } public static long solveMinCostFlow(Edge[][] g, int source, int sink, long all) { int n = g.length; long mincost = 0; int[] potential = new int[n]; final int[] d = new int[n]; MinHeap q = new MinHeap(n); while(all > 0){ // shortest path src->sink Edge[] inedge = new Edge[n]; Arrays.fill(d, Integer.MAX_VALUE / 2); d[source] = 0; q.add(source, 0); while(q.size() > 0){ int cur = q.argmin(); q.remove(cur); for(Edge ne : g[cur]){ if(ne.capacity - ne.flow > 0){ int nd = d[cur] + ne.cost + potential[cur] - potential[ne.to]; if(d[ne.to] > nd){ inedge[ne.to] = ne; d[ne.to] = nd; q.update(ne.to, nd); } } } } if(inedge[sink] == null)break; long minflow = all; long sumcost = 0; for(Edge e = inedge[sink];e != null;e = inedge[e.from]){ if(e.capacity - e.flow < minflow)minflow = e.capacity - e.flow; sumcost += e.cost; } mincost += minflow * sumcost; for(Edge e = inedge[sink];e != null;e = inedge[e.from]){ e.flow += minflow; e.complement.flow -= minflow; } all -= minflow; for(int i = 0;i < n;i++){ potential[i] += d[i]; } } return mincost; } public static class MinHeap { public int[] a; public int[] map; public int[] imap; public int n; public int pos; public static int INF = Integer.MAX_VALUE; public MinHeap(int m) { n = m+2; a = new int[n]; map = new int[n]; imap = new int[n]; Arrays.fill(a, INF); Arrays.fill(map, -1); Arrays.fill(imap, -1); pos = 1; } public int add(int ind, int x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); } return ret != -1 ? a[ret] : x; } public int update(int ind, int x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); }else{ int o = a[ret]; a[ret] = x; up(ret); down(ret); // if(a[ret] > o){ // up(ret); // }else{ // down(ret); // } } return x; } public int remove(int ind) { if(pos == 1)return INF; if(imap[ind] == -1)return INF; pos--; int rem = imap[ind]; int ret = a[rem]; map[rem] = map[pos]; imap[map[pos]] = rem; imap[ind] = -1; a[rem] = a[pos]; a[pos] = INF; map[pos] = -1; up(rem); down(rem); return ret; } public int min() { return a[1]; } public int argmin() { return map[1]; } public int size() { return pos-1; } private void up(int cur) { for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){ int d = a[p]; a[p] = a[c]; a[c] = d; int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e; e = map[p]; map[p] = map[c]; map[c] = e; } } private void down(int cur) { for(int c = cur;2*c < pos;){ int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1; if(a[b] < a[c]){ int d = a[c]; a[c] = a[b]; a[b] = d; int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e; e = map[c]; map[c] = map[b]; map[b] = e; c = b; }else{ break; } } } } void run() throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); } public static void main(String[] args) throws Exception { new C().run(); } private byte[] inbuf = new byte[1024]; private int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } } {“mode”:”full”,”isActive”:false} Problem solution in C++. #include <cstdio> #include <vector> #include <queue> #include <cstring> using namespace std; #define INF 1000000000 #define maxn 10002 struct Edge { int from, to, cap, flow, cost; Edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {} }; struct MCMF { int n, m; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n = n; for (int i = 0; i < n; ++i) { G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back(Edge(from, to, cap, 0, cost)); edges.push_back(Edge(to, from, 0, 0, -cost)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BellmanFord(int s, int t, int & cost) { for (int i = 0; i < n; ++i) { d[i] = INF; } memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for (int i = 0; i < G[u].size(); ++i) { Edge & e = edges[G[u][i]]; if (e.cap > e.flow && d[e.to] > d[u] + e.cost) { d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if (d[t] == INF) { return false; } cost += d[t] * a[t]; for (int u = t; u != s; u = edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } return true; } int MincostMaxflow(int s, int t) { int cost = 0; while (BellmanFord(s, t, cost)); return cost; } }; char s[50][51]; int rid[50][50]; int cid[50][50]; int rcnt, ccnt; int r[2500], c[2500]; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 0; i < n; ++i) scanf("%s", s[i]); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (s[i][j] == '#') continue; if (!rid[i][j]) { ++rcnt; int t = j; while (t < n && s[i][t] == '.') { rid[i][t] = rcnt; ++r[rcnt]; ++t; } } if (!cid[i][j]) { ++ccnt; int t = i; while (t < n && s[t][j] == '.') { cid[t][j] = ccnt; ++c[ccnt]; ++t; } } } MCMF mcmf; mcmf.init(rcnt + ccnt + 3); for (int i = 1; i <= rcnt; ++i) for (int j = 0; j < r[i]; ++j) mcmf.AddEdge(0, i, 1, j); for (int i = 1; i <= ccnt; ++i) for (int j = 0; j < c[i]; ++j) mcmf.AddEdge(rcnt + i, rcnt + ccnt + 1, 1, j); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { if (s[i][j] == '#') continue; mcmf.AddEdge(rid[i][j], rcnt + cid[i][j], 1, 0); } mcmf.AddEdge(rcnt + ccnt + 2, 0, k, 0); printf("%dn", mcmf.MincostMaxflow(rcnt + ccnt + 2, rcnt + ccnt + 1)); return 0; } {“mode”:”full”,”isActive”:false} Problem solution in C. #include<stdio.h> #include<stdbool.h> #define maxn 155 #define maxV 24035 #define maxE 96110 bool area[maxn][maxn]; int hnum[maxn][maxn], vnum[maxn][maxn], vdeg[maxn*maxn], hdeg[maxn*maxn], first[maxV], next[maxE], to[maxE], from[maxE], cap[maxE], cost[maxE], ecnt; void add_edge(int u, int v, int _cap, int _cost) { next[ecnt] = first[u]; to[ecnt] = v; from[ecnt] = u; cap[ecnt] = _cap; cost[ecnt] = _cost; first[u] = ecnt; ecnt++; next[ecnt] = first[v]; to[ecnt] = u; from[ecnt] = v; cap[ecnt] = 0; cost[ecnt] = -_cost; first[v] = ecnt; ecnt++; } bool inq[maxV]; int q[maxV], dist[maxV], h[maxV]; int push_flow(int S, int T) { for( int i = 0 ; i <= T ; i++ ) { inq[i] = 0, dist[i] = (int)1e9, h[i] = -1; } int ql = 0, qr = 0; dist[S] = 0; h[S] = -1; q[qr++] = S; inq[S] = 1; while( ql != qr ) { int cur = q[ql]; inq[cur] = 0; ql++; if( ql == maxV ) { ql = 0; } for( int i = first[cur] ; i != -1 ; i = next[i] ) { if( cap[i] > 0 && dist[to[i]] > dist[cur] + cost[i] ) { dist[to[i]] = dist[cur] + cost[i]; h[to[i]] = i; if(!inq[to[i]]) { q[qr] = to[i]; inq[to[i]] = 1; qr++; if( qr == maxV ) { qr = 0; } } } } } if( dist[T] == (int)1e9 ) { return -1; } int cur = T, pcost = 0; while( h[cur] != -1 ) { cap[h[cur]]--; cap[h[cur]^1]++; pcost += cost[h[cur]]; cur = from[h[cur]]; } return pcost; } int main() { int n, k; scanf("%d%d", &n, &k); for( int i = 0 ; i < n ; i++ ) { for( int j = 0 ; j < n ; j++ ) { char u[3]; scanf("%1s", u); if( u[0] == '#' ) { area[i][j] = 0; } else { area[i][j] = 1; } } } int hcnt = 0, vcnt = 0; for( int i = 0 ; i < n ; i++ ) { for( int j = 0 ; j < n ; j++ ) { if(area[i][j]) { if( j == 0 || !area[i][j-1] ) { hnum[i][j] = hcnt++; } else { hnum[i][j] = hnum[i][j-1]; } } } } for( int j = 0 ; j < n ; j++ ) { for( int i = 0 ; i < n ; i++ ) { if(area[i][j]) { if( i == 0 || !area[i-1][j] ) { vnum[i][j] = vcnt++; } else { vnum[i][j] = vnum[i-1][j]; } } } } int S = hcnt + vcnt, T = hcnt + vcnt + 1; ecnt = 0; for( int i = 0 ; i < hcnt ; i++ ) { hdeg[i] = 0; } for( int i = 0 ; i < vcnt ; i++ ) { vdeg[i] = 0; } for( int i = 0 ; i < n ; i++ ) { for( int j = 0 ; j < n ; j++ ) { if(area[i][j]) { hdeg[hnum[i][j]]++, vdeg[vnum[i][j]]++; } } } for( int i = 0 ; i <= T ; i++ ) { first[i] = -1; } for( int i = 0 ; i < hcnt ; i++ ) { for( int j = 0 ; j < hdeg[i] ; j++ ) { add_edge(S, i, 1, j); } } for( int i = 0 ; i < vcnt ; i++ ) { for( int j = 0 ; j < vdeg[i] ; j++ ) { add_edge(i+hcnt, T, 1, j); } } for( int i = 0 ; i < n ; i++ ) { for( int j = 0 ; j < n ; j++ ) { if(area[i][j]) { add_edge(hnum[i][j], vnum[i][j] + hcnt, 1, 0); } } } int res = 0; for( int i = 0 ; i < k ; i++ ) { int z = push_flow(S, T); res += z; } printf("%d", res); return 0; } {“mode”:”full”,”isActive”:false} Algorithms coding problems solutions