November 3, 2020 2020 TCO Algorithm WildCard Round Editorials
PizzaEatingGame
Used as: Division One – Level One:
| Value | 300 |
| Submission Rate | 31 / 34 (91.18%) |
| Success Rate | 24 / 31 (77.42%) |
| High Score | lyrically for 288.88 points (5 mins 37 secs) |
| Average Score | 244.01 (for 24 correct submissions) |
Hint: dp[l][r]
A typical dynamic programming on range problem. First choose which slice you want to pick at the first turn. The first move leads to an array, instead of a circle.
Let dp[l][r] = the score that the person who has the turn will get if the game is played on range [l, r).
dp[l][r] = max l <= j < r a[j] + (sum[l][j] – dp[l][j]) + (sum[j + 1][r] – dp[j + 1][r]), where sum[i][j] is sum of a[i]’s in range [l, r).
To make the implementation easier, one can make a copy of the array and append to it.
Time complexity is O(N^3).
The code by lyrically nicely describes the solution:
constexpr int INF = 1001001001;
int N;
int A[1010];
int dp[1010][1010];
struct PizzaEatingGame {
int eat(vector <int> olives) {
N = olives.size();
for (int i = 0; i < N * 2; ++i) {
A[i] = olives[i % N];
}
for (int i = 0; i <= N * 2; ++i) {
fill(dp[i], dp[i] + N * 2 + 1, -INF);
dp[i][i] = 0;
}
for (int w = 1; w <= N; ++w) {
for (int i = 0; i + w <= N * 2; ++i) {
const int j = i + w;
for (int k = i; k < j; ++k) {
dp[i][j] = max(dp[i][j], A[k] - dp[i][k] - dp[k + 1][j]);
}
}
}
int mx = -INF;
for (int i = 0; i < N; ++i) {
mx = max(mx, A[i] - dp[i + 1][i + N]);
}
int sum = 0;
for (int i = 0; i < N; ++i) {
sum += A[i];
}
const int ans = (sum + mx) / 2;
return ans;
}
};
BiddingWars
Used as: Division One – Level Two:
| Value | 700 |
| Submission Rate | 9 / 34 (26.47%) |
| Success Rate | 9 / 9 (100.00%) |
| High Score | maroon_kuri for 601.86 points (11 mins 52 secs) |
| Average Score | 469.51 (for 9 correct submissions) |
Hint: dp[n – 1] = 0, dp[n – 2] = inf, calculate dp[n – 3], dp[n – 4], …, dp[0].
Let’s calculate dp[v] = the largest non-negative real number r such that if Bob starts with strictly less than r dollars, Alice can force a win, when the initial vertex is v.
dp[n – 1] = 0, dp[n – 2] = inf.
Let’s calculate dp[n – 3], dp[n – 4], …, dp[0]. This way, when we want to calculate dp[v], for each u such that v has an edge to u, dp[u] is calculated.
Focus on calculating dp[v]. Let W = max dp[u] where v has an edge to u. Let L = min dp[u] where v has an edge to u.
There is a case that could be handled easily, W = inf. So there exists a vertex like u such that dp[u] = inf. Let’s prove that dp[v] = L + 1. If Alice has 1 dollar and Bob has less than L + 1 dollars, Alice can bid on 1 dollar. If Bob bids on less than 1 dollar, he will lose. Alice moves the token to u. If Bob bids on more than or equal to 1 dollar, at the best case he moves the token to the vertex which it’s dp is equal to l. He’ll lose again. Because after this turn he has less than L dollars.
Let’s handle the general case. Consider she wants to bid on x. It’s easy to show that there is two optimal cases for Alice:
- Win the bid and move the token to vertex which it’s dp is equal to W. So (1 – x) / dp[v] <= 1 / w. It means that the ratio of Alice remaining money (1 – x) to Bob money (dp[v]) should be less than or equal to 1 / w, which is the ratio of the best vertex Alice can move the token to.
- Lose the bid and Bob will move the token to vertex which it’s dp is equal to L. So 1 / (dp[v] – x) <= 1 / L.
Because we want to maximize dp[v], we convert <= to =. Now we have two unknowns (x and dp[v]) and two equations that when solved, leads to: dp[v] = (w + wl) / (w + 1) = l + (w – l) / (w + 1).
Code by Egor:
double findMax(int n, vector<int> f, vector<int> t) {
vector<int> graph(n);
for (int i = 0; i < f.size(); i++)
graph[f[i]].push_back(t[i]);
vector<double> r(n);
r[n - 2] = numeric_limits<double>::infinity();
r[n - 1] = 0;
for (int i = n - 3; i >= 0; i--) {
double w = 0;
double l = numeric_limits<double>::infinity();
for (auto& to : graph[i]) {
w = max(w, r[to]);
l = min(l, r[to]);
}
if (__builtin_isinf(w)) {
r[i] = l + 1;
continue;
}
double alpha = (w - l) / (w + 1);
r[i] = l + alpha;
}
return __builtin_isinf(r[0]) ? -1 : r[0];
}
OddCycleDetector
Used as: Division One – Level Three:
| Value | 900 |
| Submission Rate | 18 / 34 (52.94%) |
| Success Rate | 7 / 18 (38.89%) |
| High Score | ksun48 for 555.35 points (26 mins 4 secs) |
| Average Score | 420.62 (for 7 correct submissions) |
Hint: Theory problem. Find vertex-biconnected components of the graph and for each of them check if it’s bipartite or not.
Many users got accepted using finding random odd length cycles. But Let’s describe the deterministic solution.
Find vertex-biconnected components of the graph. If a component is bipartite, no vertex in it can be in an odd length cycle.
We prove that all other vertices are in at least one odd length cycle. Consider a graph H which is biconnected and not bipartite. So it has at least one odd length cycle. Let c1 and c2 be two arbitrary selected vertices in the odd cycle.
Let’s prove that for each vertex like v in H, it’s in at least one odd length cycle. Add a virtual vertex x to H and connect it to c1 and c2. The graph is still biconnected. It’s a known fact about biconnected graphs that between each two vertices, there are two vertex disjoint paths between them. So between v and x there are two vertex disjoint paths, p1, p2. Let d1 be the first vertex in p1 which lies in the odd cycle, let d2 be the first vertex in p2 which lies in the odd cycle.
There are two paths lying on the odd cycle between d1 and d2. One of them is odd-length and the other is even-length. Now, depending on the sum of length of distance of v and d1 (on p1) and distance of v and d2 (on p2) we can choose a suitable path between d1 and d2 to make an odd-length cycle containing v.
To find vertex-disjoint paths between v and c1 and also v and c2, we can use max-flow.
Here is the code by misof:
import java.math.*;
class Edge {
int source, destination, capacity, residue;
Edge(int s, int d, int c, int r) { this.source = s; this.destination = d; this.capacity = c; this.residue = r; }
};
class MaxFlow {
int N;
ArrayList<Integer>[] V;
ArrayList<Edge> E;
MaxFlow(int N) {
this.N = N;
this.V = new ArrayList[N];
for (int n=0; n<N; ++n) this.V[n] = new ArrayList<Integer>();
this.E = new ArrayList<Edge>();
}
void add_arc(int s, int d, int c) {
int e = E.size();
V[s].add(e);
V[d].add(e+1);
E.add( new Edge(s,d,c,c) );
E.add( new Edge(d,s,c,0) );
}
int[] findEar(int source) {
int flowSize = 0;
int sink = N-2;
while (true) { // use BFS to find augmenting paths
int[] from = new int[N];
for (int n=0; n<N; ++n) from[n] = -1;
int[] Q = new int[N];
int qs=0, qf=0;
Q[qf++] = source;
from[source] = -2;
while (qs < qf) {
int where = Q[qs++];
for (int e : V[where]) {
int dest = E.get(e).destination; if (from[dest] != -1) continue;
int res = E.get(e).residue; if (res == 0) continue;
from[dest] = e;
Q[qf++] = dest;
if (dest == sink) break;
}
if (from[sink] >= 0) break;
}
if (from[sink]==-1) {
if (flowSize != 2) return new int[0]; // SHOULD NOT HAPPEN
int realN = (N / 2) - 1;
boolean[][] inAnswer = new boolean[realN][realN];
for (Edge e : E) if (e.source % 2 == 1 && e.destination % 2 == 0 && e.source != N-1 && e.destination != N-2 && e.residue == 0) {
int x = e.source / 2;
int y = e.destination / 2;
if (x != y) inAnswer[x][y] = inAnswer[y][x] = true;
}
int[] degree = new int[realN];
for (int a=0; a<realN; ++a) for (int b=0; b<realN; ++b) if (inAnswer[a][b]) ++degree[a];
int start = 0;
while (degree[start] != 1) ++start;
int[] path = new int[realN];
path[0] = start;
int pc = 1;
while (true) {
for (int n=0; n<N; ++n) if (inAnswer[ path[pc-1] ][n] && (pc == 1 || path[pc-2] != n)) { path[pc++] = n; break; }
if (degree[path[pc-1]] == 1) break;
}
int[] answer = new int[pc];
for (int i=0; i<pc; ++i) answer[i] = path[i];
return answer;
}
// construct a maximum set of augmenting paths in the graph given by from[]
for (int e : V[sink]) {
int where = E.get(e).destination; if (from[where]==-1) continue; // no path leads here
int res = E.get(e).capacity - E.get(e).residue; if (res == 0) continue; // can't push anything more
// walk the path and determine the delta
int canPush = res;
int curr = where;
while (true) {
if (from[curr] == -2) break;
canPush = Math.min( canPush, E.get( from[curr] ).residue );
curr = E.get( from[curr] ).source;
}
// walk the path again and update capacities
flowSize += canPush;
E.get(e ).residue += canPush;
E.get(e^1).residue -= canPush;
curr = where;
while (true) {
if (from[curr] == -2) break;
E.get( from[curr] ).residue -= canPush;
E.get( from[curr]^1 ).residue += canPush;
curr = E.get( from[curr] ).source;
}
}
}
}
};
public class OddCycleDetector {
public String checkData(String[] G) {
int N = G.length;
if (N < 1 || N > 50) return "N must be between 1 and 50, inclusive.";
for (int n=0; n<N; ++n) if (G[n].length() != N) return "Each element of G must contain N characters.";
for (int a=0; a<N; ++a) {
if (G[a].charAt(a) != 'N') return "For each i, G[i][i] must be 'N'.";
for (int b=0; b<N; ++b) {
if (G[a].charAt(b) != 'Y' && G[a].charAt(b) != 'N') return "Each character in G must be either 'Y' or 'N'.";
if (G[a].charAt(b) != G[b].charAt(a)) return "For each i and j, G[i][j] must be equal to G[j][i].";
}
}
return "";
}
int N;
boolean[][] G;
int[][] bcc; // for each edge its BCC#
int[] bcc_visited, bcc_vstack, bcc_estack;
int bcc_cur, bcc_cur_time, bcc_vsize, bcc_esize;
int search(int v) {
bcc_visited[v] = ++bcc_cur_time;
int result = bcc_visited[v];
for (int n=0; n<N; ++n) {
if (!G[v][n]) continue;
if (bcc[v][n] != -1) continue;
bcc_vstack[bcc_vsize++] = v;
bcc_estack[bcc_esize++] = n;
bcc[n][v] = -2;
int r;
if (bcc_visited[n] == 0) r = search(n); else r = bcc_visited[n];
if (r >= bcc_visited[v]) {
int a, b;
do {
a = bcc_vstack[--bcc_vsize];
b = bcc_estack[--bcc_esize];
bcc[a][b] = bcc_cur;
bcc[b][a] = bcc_cur;
}
while (a!=v || b!=n);
++bcc_cur;
}
result = Math.min(result,r);
}
return result;
}
void compute_bcc(String[] _G) {
N = _G.length;
G = new boolean[N][N];
for (int a=0; a<N; ++a) for (int b=0; b<N; ++b) G[a][b] = (_G[a].charAt(b) == 'Y');
bcc_cur = 0;
bcc_cur_time = 1;
bcc_vstack = new int[2*N*N]; bcc_vsize = 0;
bcc_estack = new int[2*N*N]; bcc_esize = 0;
bcc = new int[N][N];
for (int a=0; a<N; ++a) for (int b=0; b<N; ++b) bcc[a][b] = -1;
bcc_visited = new int[N];
for (int n=0; n<N; ++n) if (bcc_visited[n] == 0) search(n);
System.out.println("N = " + N + " number of BCCs = " + bcc_cur);
}
boolean[] getBCC(int bcc_id) {
boolean[] answer = new boolean[N];
int edges = 0;
for (int a=0; a<N; ++a) for (int b=0; b<N; ++b) if (bcc[a][b] == bcc_id) {
++edges;
answer[a] = answer[b] = true;
}
int vertices = 0;
for (boolean x : answer) if (x) ++vertices;
System.out.println(" BCC "+bcc_id+" with "+vertices+" vertices, "+(edges/2)+" edges");
return answer;
}
boolean[] currentBCC;
int[] color, depth, dfsparent, oddCycle;
boolean terminate;
void dfs(int bcc_id, int where, int parent) {
dfsparent[where] = parent;
for (int n=0; n<N; ++n) {
if (!G[where][n]) continue;
if (bcc[where][n] != bcc_id) continue;
if (color[n] == 1 - color[where]) continue;
if (color[n] == color[where]) {
// found an odd cycle
int cl = depth[where] - depth[n] + 1;
oddCycle = new int[cl];
oddCycle[0] = where;
for (int i=1; i<cl; ++i) oddCycle[i] = dfsparent[ oddCycle[i-1] ];
terminate = true;
return;
}
color[n] = 1 - color[where];
depth[n] = 1 + depth[where];
dfs(bcc_id, n, where);
if (terminate) return;
}
}
void getOneOddCycle(int bcc_id) {
currentBCC = getBCC(bcc_id);
int start = 0;
while (!currentBCC[start]) ++start;
color = new int[N];
for (int n=0; n<N; ++n) color[n] = -1;
color[start] = 0;
dfsparent = new int[N];
depth = new int[N];
depth[start] = 0;
terminate = false;
oddCycle = new int[0];
dfs(bcc_id, start, -1);
System.out.print(" BCC "+bcc_id+" odd cycle:"); for (int x : oddCycle) System.out.print(" "+x); System.out.println();
}
public String checkAnswer(String[] _G, int[] contestantsAnswer, int[] referenceAnswer) {
compute_bcc(_G);
for (int x : contestantsAnswer) if (x < -1 || x >= N) return "Wrong answer: Each element of the return value must be between -1 and N-1, inclusive.";
int separators = 0;
for (int x : contestantsAnswer) if (x == -1) ++separators;
if (separators != N-1) return "Wrong answer: The return value must contain exactly N-1 copies of the value -1.";
int[] indices = new int[N+1];
indices[0] = -1;
for (int j=1, i=0; i<contestantsAnswer.length; ++i) if (contestantsAnswer[i] == -1) indices[j++] = i;
indices[N] = contestantsAnswer.length;
int[][] pieces = new int[N][];
for (int n=0; n<N; ++n) pieces[n] = new int[ indices[n+1] - indices[n] - 1 ];
for (int n=0; n<N; ++n) for (int i=0; i<pieces[n].length; ++i) pieces[n][i] = contestantsAnswer[ indices[n]+1+i ];
boolean[] isOnCycle = new boolean[N];
for (int bcc_id=0; bcc_id < bcc_cur; ++bcc_id) {
getOneOddCycle(bcc_id);
if (oddCycle.length == 0) continue;
for (int n=0; n<N; ++n) if (currentBCC[n]) isOnCycle[n] = true;
}
for (int n=0; n<N; ++n) if (isOnCycle[n] && pieces[n].length == 0) return "Wrong answer: Did not find an existing odd cycle.";
for (int n=0; n<N; ++n) if (pieces[n].length > 0) {
if (pieces[n].length < 3) return "Wrong answer: Returned certificate must have at least three vertices.";
if (pieces[n].length % 2 == 0) return "Wrong answer: Returned certificate must have an odd number of vertices.";
if (pieces[n].length > N) return "Wrong answer: Returned certificate must not have a repeated vertex.";
for (int a=0; a<pieces[n].length; ++a) for (int b=0; b<a; ++b) if (pieces[n][a] == pieces[n][b]) return "Wrong answer: Returned certificate must not have a repeated vertex.";
for (int a=0; a<pieces[n].length; ++a) {
int x = pieces[n][a], y = pieces[n][ (a+1) % pieces[n].length ];
if (!G[x][y]) return "Wrong answer: Returned certificate is not a valid cycle.";
}
boolean contains = false;
for (int x : pieces[n]) if (x == n) contains = true;
if (!contains) return "Wrong answer: Returned certificate for a vertex does not contain that vertex.";
}
return "";
}
public int[] detect(String[] _G) {
compute_bcc(_G);
ArrayList<Integer>[] certificates = new ArrayList[N];
for (int n=0; n<N; ++n) certificates[n] = new ArrayList<Integer>();
for (int bcc_id=0; bcc_id < bcc_cur; ++bcc_id) {
getOneOddCycle(bcc_id);
if (oddCycle.length == 0) continue;
for (int n=0; n<N; ++n) if (currentBCC[n] && certificates[n].size() == 0) {
// construct certificate for n
boolean onCycle = false;
for (int x : oddCycle) if (x == n) onCycle = true;
if (onCycle) {
for (int x : oddCycle) certificates[n].add(x);
continue;
}
// n lies outside the one cycle, find two paths to it
MaxFlow MF = new MaxFlow(2*N + 2);
for (int i=0; i<N; ++i) MF.add_arc(2*i, 2*i+1, 1); // capacity on vertices
boolean[] onOddCycle = new boolean[N];
for (int x : oddCycle) { onOddCycle[x] = true; MF.add_arc(2*x+1, 2*N, 1); } // cycle -> sink
for (int a=0; a<N; ++a) for (int b=0; b<N; ++b) if (!onOddCycle[a]) if (G[a][b]) if (bcc[a][b] == bcc_id) MF.add_arc(2*a+1, 2*b, 1); // edges not on cycle
MF.add_arc(2*N+1, 2*n+1, 2); // start
int[] ear = MF.findEar(2*N+1);
int prvy = 0; while (oddCycle[prvy] != ear[0]) ++prvy;
int druhy = prvy, dopredu = 0; while (oddCycle[druhy] != ear[ear.length-1]) { ++dopredu; druhy=(druhy+1) % oddCycle.length; }
if ((ear.length + dopredu) % 2 == 0) {
// chceme toto
for (int x : ear) certificates[n].add(x);
for (int i=(druhy+oddCycle.length-1) % oddCycle.length; i!=prvy; i = (i+oddCycle.length-1)%oddCycle.length) certificates[n].add(oddCycle[i]);
} else {
// chceme druhe
for (int x : ear) certificates[n].add(x);
for (int i=(druhy+1) % oddCycle.length; i!=prvy; i=(i+1)%oddCycle.length) certificates[n].add(oddCycle[i]);
}
}
}
ArrayList<Integer> answer = new ArrayList<Integer>();
for (int n=0; n<N; ++n) {
if (n > 0) answer.add(-1);
for (int x : certificates[n]) answer.add(x);
}
int[] finalAnswer = new int[ answer.size() ];
for (int i=0; i<finalAnswer.length; ++i) finalAnswer[i] = answer.get(i);
return finalAnswer;
}
}
Guest Blogger
