Div2 - 250 ShippingCubes
Div2 - 500, Div1 - 250 Magic Diamond
public class ShippingCubes {
public int minimalCost(int N) {
int r = Integer.MAX_VALUE;
for (int i = 1; i <= N; ++i) {
if (N % i != 0) continue;
for (int j = 1; i * j <= N; ++j) {
if (N % (i * j) != 0) continue;
r = Math.min(r, i + j + N / i / j);
}
}
return r;
}
}
Div2 - 500, Div1 - 250 Magic Diamond
public class MagicDiamonds {
boolean isPrime(long n) {
if (n < 2)
return false;
for (long i = 2; i * i <= n; ++i)
if (n % i == 0)
return false;
return true;
}
public long minimalTransfer(long n) {
if (n == 3) return 3;
if (!isPrime(n)) return 1;
return 2;
}
}
Div2 - 1000 MultiplesWithLimit
import java.util.*;
public class MultiplesWithLimit {
String correct(String s) {
int len = s.length();
if (len < 9) return s;
return s.substring(0, 3) + "..." + s.substring(len - 3) + "(" + len + " digits)";
}
public String minMultiples(int N, int[] fb) {
Arrays.sort(fb);
Queue<Integer> q = new LinkedList<Integer>();
int d[] = new int[N + 1];
int p[] = new int[N + 1];
int pi[] = new int[N + 1];
Arrays.fill(d, Integer.MAX_VALUE);
Arrays.fill(p, -1);
for (int i = 1; i < 10; ++i) {
if (Arrays.binarySearch(fb, i) >= 0) continue;
if (d[i % N] != Integer.MAX_VALUE) continue;
q.add(i % N);
d[i % N] = 1;
pi[i % N] = i;
}
while (!q.isEmpty()) {
int x = q.poll();
if (x == 0) {
String ans = "";
for (; x != -1; x = p[x]) {
ans = (char)('0' + pi[x]) + ans;
}
return correct(ans);
}
for (int i = 0; i < 10; ++i) {
if (Arrays.binarySearch(fb, i) >= 0) continue;
int nx = (x * 10 + i) % N;
if (d[nx] == Integer.MAX_VALUE) {
d[nx] = d[x] + 1;
p[nx] = x;
pi[nx] = i;
q.add(nx);
}
}
}
return "IMPOSSIBLE";
}
}
Div1 500 - LongestSequence
At first let's find out when we can build infinity sequence. Assume max is item from C array which has maximum absolute value. If we can build sequence from 2*max element, which satisfies given restrictions then obvious we can build sequence of length 3*max, 4*max an so on. So how we can check would we can build sequence of arbitrary length. Let us consider example C = {-2, 3}. Fix some sequence length and check it. For example fix length = 3. We want find out same array A of size 3 which satisfied given restriction. We can consider array of partials sums S, where S[i] = A[1] + A[2] + ... + A[i]. Its size equals size of array A. In this way sum A[i] + A[i + 1] + ... + A[j] equals S[j] - S[i - 1]. Thus we can take restrictions from array C and write out following equations:
S[2] - S[0] < 0
S[3] - S[1] < 0
S[3] - S[0] > 0
Transform these equations in such manner:
S[2] < S[0]
S[3] < S[1]
S[0] < S[3]
Consider graph which consists from 4 vertexes (from 0 to 3) and add edges which match these equations. Thus we add following edges: (2->0), (3->1), (0->3).
If we find out any cycle then we can't build sequence of length 3 because we become contradiction (if we consider length = 4, we are going to become a graph, which contains a cycle). Otherwise if we don't have a cycle then for prove that there is a suitable sequence of need length we can observe ideas from Cormen book (chapter "Difference contstraints and shortest pahts").
Now when we can check would we can build a sequence arbitrary length, we can with using binary search to find out problem answer.
import java.util.Arrays;
public class LongestSequence {
int C[];
boolean A[][] = new boolean[3000][3000];
int Color[] = new int[3000];
int N;
void addEdge(int u, int v) {
A[u][v] = true;
}
boolean dfs(int u) {
Color[u] = 1;
for (int v = 0; v <= N; ++v) {
if (!A[u][v] || Color[v] == 2) continue;
if (Color[v] == 1) return true;
if (dfs(v)) return true;
}
Color[u] = 2;
return false;
}
boolean check(int n) {
N = n;
Arrays.fill(Color, 0, n + 1, 0);
for (int i = 0; i <= n; ++i) {
Arrays.fill(A[i], 0, n + 1, false);
}
for (int x : C) {
if (Math.abs(x) > n) continue;
for (int i = Math.abs(x); i <= n; ++i) {
if (x < 0) addEdge(i + x, i);
if (x > 0) addEdge(i, i - x);
}
}
for (int i = 0; i <= n; ++i) {
if (Color[i] == 0 && dfs(i)) {
return false;
}
}
return true;
}
public int maxLength(int C[]) {
this.C = C;
if (check(2000)) return -1;
int lo = 0, hi = 2000;
while (hi - lo > 1) {
int mid = hi + lo >> 1;
if (check(mid)) lo = mid;
else hi = mid;
}
return lo;
}
}
Div1 - 1000 AxonometricProjection
import java.util.Arrays;
public class AxonometricProjection {
static final int MOD = 1000 * 1000 * 1000 + 9;
long P[] = new long[50 * 50 + 1];
long P1[] = new long[50 * 50 + 1];
int dp[][] = new int[100][100];
int n2, m2, K;
int C[][] = new int[51][51];
{
for (int i = 0; i < C.length; ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
}
int rec(int n1, int m1) {
if (n1 == 0 && m1 == 0) return 1;
if (dp[n1][m1] != -1) return dp[n1][m1];
long r = 0;
for (int i = 0; i <= n1; ++i) {
for (int j = 0; j <= m1; ++j) {
if (i == n1 && j == m1) continue;
long t1 = rec(i, j);
long t2 = C[n1][i];
long t3 = C[m1][j];
int c1 = (n1 - i) * (m1 + m2) + (m1 - j) * (n1 + n2) - (n1 - i) * (m1 - j);
long t4 = P[c1];
r = (r + t1 * t2 % MOD * t3 % MOD * t4 % MOD) % MOD;
}
}
int c = (n1 + n2) * (m1 + m2) - n2 * m2;
r = (P1[c] - r) % MOD;
if (r < 0) r += MOD;
return dp[n1][m1] = (int)r;
}
public int howManyWays(int v[], int h[]) {
Arrays.sort(v);
Arrays.sort(h);
if (v[v.length - 1] != h[h.length - 1]) return 0;
long ans = 1;
for (K = 1; K <= v[v.length - 1]; ++K) {
int n1 = 0, n2 = 0;
for (int cur : h) {
if (cur == K) ++n1;
if (cur > K) ++n2;
}
int m1 = 0, m2 = 0;
for (int cur : v) {
if (cur == K) ++m1;
if (cur > K) ++m2;
}
if (m1 == 0 && n1 == 0) continue;
P[0] = P1[0] = 1;
int hi = (m1 + m2) * (n1 + n2);
for (int i = 1; i <= hi; ++i) {
P[i] = P[i - 1] * K % MOD;
P1[i] = P1[i - 1] * (K + 1) % MOD;
}
this.n2 = n2;
this.m2 = m2;
for (int i = 0; i <= n1; ++i) {
for (int j = 0; j <= m1; ++j) {
dp[i][j] = -1;
}
}
ans = ans * rec(n1, m1) % MOD;
}
return (int)ans;
}
}
No comments:
Post a Comment