The problem has very short solution. Also it is possible solve it using more familiar approach (using dfs or bfs).
public class RainyRoad {
public String isReachable(String[] road) {
for (int i = 0; i < road[0].length(); ++i) {
if (road[0].charAt(i) == 'W' && road[1].charAt(i) == 'W')
return "NO";
}
return "YES";
}
}
Div2 950 - MagicalSquare
I wrote solution with very big complexity O(N ^ 6). But it passed all tests.
public class MagicalSquare {
String R[], C[];
String A[][] = new String[3][3];
Long dp[][][][] = new Long[3][51][51][51];
long rec(int l, int i1, int i2, int i3) {
if (l == 3) {
if (i1 == C[0].length() && i2 == C[1].length() && i3 == C[2].length()) return 1;
return 0;
}
if (dp[l][i1][i2][i3] != null) return dp[l][i1][i2][i3];
String s1 = C[0].substring(i1);
String s2 = C[1].substring(i2);
String s3 = C[2].substring(i3);
String cur = R[l];
int len = cur.length();
long res = 0;
for (int i = 0; i <= len; ++i) {
String t3 = cur.substring(i);
if (!s3.startsWith(t3)) continue;
for (int j = 0; j <= i; ++j) {
String t1 = cur.substring(0, j);
String t2 = cur.substring(j, i);
if (!s2.startsWith(t2)) continue;
if (!s1.startsWith(t1)) continue;
res += rec(l + 1, i1 + t1.length(), i2 + t2.length(), i3 + t3.length());
}
}
return dp[l][i1][i2][i3] = res;
}
public long getCount(String[] rowStrings, String[] columnStrings) {
this.R = rowStrings;
this.C = columnStrings;
return rec(0, 0, 0, 0);
}
}
I wrote simple brute force solution with O(N^6) complexity which surprisingly do not became time limit. Of course there is more faster solution which uses inclusion–exclusion principle. It has O(N^4) complexity.
public class DropCoins {
public int getMinimum(String[] board, int K) {
int res = Integer.MAX_VALUE;
int n = board.length;
int m = board[0].length();
for (int i1 = 0; i1 < n; ++i1)
for (int i2 = i1; i2 < n; ++i2)
for (int j1 = 0; j1 < m; ++j1)
for (int j2 = j1; j2 < m; ++j2) {
int cnt = 0;
for (int i = i1; i <= i2; ++i)
for (int j = j1; j <= j2; ++j)
if (board[i].charAt(j) != '.')
++cnt;
if (cnt != K) continue;
int t1 = i1;
int t2 = n - 1 - i2;
int t = Math.min(2 * t1 + t2, 2 * t2 + t1);
t1 = j1;
t2 = m - 1 - j2;
t += Math.min(2 * t1 + t2, 2 * t2 + t1);
res = Math.min(res, t);
}
if (res == Integer.MAX_VALUE) return -1;
return res;
}
}
Div1 525 - Rumor
import java.io.*;
import java.util.*;
public class Rumor {
int n, know, g[], mask;
int res = Integer.MAX_VALUE;
int check(int use) {
int knowA = know, knowB = know;
int giveA = 0, giveB = 0;
int cnt = 0;
while (knowA != mask || knowB != mask) {
if (++cnt >= res) return -1;
int newKnowA = 0, newKnowB = 0;
for (int i = 0; i < n; ++i) {
if (testBit(giveA, i) && testBit(giveB, i)) continue;
if (!testBit(knowA, i) && !testBit(knowB, i)) continue;
String s = "";
if (!testBit(giveA, i) && testBit(knowA, i)) s += 'a';
if (!testBit(giveB, i) && testBit(knowB, i)) s += 'b';
if (s.length() == 0) continue;
char ch;
if (s.length() == 2) {
if (testBit(use, i)) ch = s.charAt(0);
else ch = s.charAt(1);
} else ch = s.charAt(0);
if (ch == 'a') {
newKnowA |= g[i];
giveA |= 1 << i;
} else {
newKnowB |= g[i];
giveB |= 1 << i;
}
}
if ((knowA | newKnowA) == knowA && (knowB | newKnowB) == knowB) return -1;
knowA |= newKnowA;
knowB |= newKnowB;
}
return cnt;
}
private boolean testBit(int use, int i) {
return ((use >> i) & 1) == 1;
}
public int getMinimum(String knowledge, String[] graph) {
n = knowledge.length();
mask = (1 << n) - 1;
g = new int[n];
for (int i = 0; i < n; ++i) {
if (knowledge.charAt(i) == 'Y') {
know |= 1 << i;
}
for (int j = 0; j < n; ++j) {
if (graph[i].charAt(j) == 'Y')
g[i] |= 1 << j;
}
}
for (int use = 0; use < (1 << n); ++use) {
int t = check(use);
if (t == -1) continue;
res = Math.min(res, t);
}
if (res == Integer.MAX_VALUE) return -1;
return res;
}
}
Div1 950 - MonochromePuzzle
public class MonochromePuzzle {
public int getMinimum(String a[]) {
int n = a.length;
for (int i = 0; i < n; ++i) {
int c = 0;
for (int j = 0; j < n; ++j) {
if (a[i].charAt(j) != a[j].charAt(i)) return -1;
if (a[i].charAt(j) == '#') ++c;
}
if (c != 3) return -1;
}
int p[] = null;
for (int i = 1; i < n; ++i) {
p = check(a, 0, i);
if (p != null) break;
}
if (p == null) return -1;
int res = Integer.MAX_VALUE;
for (int tt = 0; tt < 3; ++tt) {
for (int i = 0; i < n / 2; ++i) {
int x = get(p);
res = Math.min(x, res);
rshift(p, 0, n / 2);
lshift(p, n / 2, n);
}
reverse(p, 0, n);
for (int i = 0; i < n / 2; ++i) {
int x = get(p);
res = Math.min(x, res);
rshift(p, 0, n / 2);
lshift(p, n / 2, n);
}
reverse(p, 0, n / 2);
reverse(p, n / 2, n);
for (int i = 0; i < n / 2; ++i) {
int x = get(p);
res = Math.min(x, res);
rshift(p, 0, n / 2);
lshift(p, n / 2, n);
}
reverse(p, 0, n);
for (int i = 0; i < n / 2; ++i) {
int x = get(p);
res = Math.min(x, res);
rshift(p, 0, n / 2);
lshift(p, n / 2, n);
}
if (n != 8) break;
int np[] = new int[8];
np[0] = p[0];
np[1] = p[3];
np[2] = p[4];
np[3] = p[7];
np[4] = p[6];
np[6] = p[2];
np[7] = p[1];
np[5] = p[5];
for (int i = 0; i < 8; ++i) p[i] = np[i];
}
return res;
}
private void reverse(int p[], int lo, int hi) {
int n = (hi - lo) / 2;
for (int i = 0; i < n; ++i) {
int tmp = p[lo + i];
p[lo + i] = p[hi - i - 1];
p[hi - i - 1] = tmp;
}
}
private void lshift(int p[], int lo, int hi) {
int tmp = p[lo];
for (int i = lo; i + 1 < hi; ++i) {
p[i] = p[i + 1];
}
p[hi - 1] = tmp;
}
private void rshift(int p[], int lo, int hi) {
int tmp = p[hi - 1];
for (int i = hi - 1; i > 0; --i) {
p[i] = p[i - 1];
}
p[0] = tmp;
}
private int get(int p[]) {
int n = p.length;
boolean use[] = new boolean[n];
int res = 0;
for (int i = 0; i < n; ++i) {
if (use[i]) continue;
int cur = i;
int c = 0;
while (!use[cur]) {
use[cur] = true;
++c;
cur = p[cur];
}
if (c >= 2) res += c - 1;
}
return res;
}
private int[] check(String a[], int u, int v) {
if (a[u].charAt(v) != '#') return null;
int n = a.length;
int p[] = new int[n];
int left = 0, right = n - 1;
p[left++] = u;
p[right--] = v;
boolean use[] = new boolean[n];
use[u] = use[v] = true;
int pu = u, pv = v;
for (int k = 1; k < n / 2; ++k) {
boolean ok = false;
for (int i = 1; !ok && i < n; ++i) {
if (use[i]) continue;
for (int j = 1; !ok && j < n; ++j) {
if (use[j] || i == j) continue;
if (a[i].charAt(j) != '#') continue;
if (a[i].charAt(pu) != '#') continue;
if (a[j].charAt(pv) != '#') continue;
if (k == n / 2 - 1) {
if (a[i].charAt(u) != '#') continue;
if (a[j].charAt(v) != '#') continue;
}
ok = true;
p[left++] = i;
p[right--] = j;
use[i] = use[j] = true;
pu = i;
pv = j;
}
}
if (!ok) return null;
}
return p;
}
}
No comments:
Post a Comment