import java.util.*;
public class BearGridRect {
int n, m;
int row(int i) { return i; }
int column(int i) { return n + i; }
int query1(int i) { return 2 * n + i; }
int query2(int i) { return 2 * n + m + i; }
public int[] findPermutation(int tmp_n, int[] r1, int[] r2, int[] c1, int[] c2, int[] cnt) {
n = tmp_n;
m = r1.length;
int s = 2 * n + 2 * m;
int t = 2 * n + 2 * m + 1;
int total = 2 * n + 2 * m + 2;
MinCostMaxFlow f = new MinCostMaxFlow();
f.init(total);
boolean visited[][] = new boolean[n][n];
int cnt_sum = 0;
for(int i = 0; i < m; ++i) {
cnt_sum += cnt[i];
f.add(query1(i), query2(i), cnt[i], 0);
for(int r = r1[i]; r <= r2[i]; ++r)
for(int c = c1[i]; c <= c2[i]; ++c) {
f.add(row(r), query1(i), 1, 0);
f.add(query2(i), column(c), 1, 0);
visited[r][c] = true;
}
}
for(int r = 0; r < n; ++r)
for(int c = 0; c < n; ++c)
if(!visited[r][c])
f.add(row(r), column(c), 1, 1);
for(int r = 0; r < n; ++r)
f.add(s, row(r), 1, 0);
for(int c = 0; c < n; ++c)
f.add(column(c), t, 1, 0);
int[] ans = f.findFlow(s, t);
int total_flow = ans[0];
int total_cost = ans[1];
if(total_flow != n || cnt_sum + total_cost != n) {
int tmp[] = {-1};
return tmp;
}
ans = new int[n];
for(int r = 0; r < n; ++r) {
for(int c = 0; c < n; ++c) {
if(f.flow[row(r)][column(c)] > 0)
ans[r] = c;
for(int i = 0; i < m; ++i)
if(f.flow[row(r)][query1(i)] > 0 && f.flow[query2(i)][column(c)] > 0) {
ans[r] = c;
f.flow[row(r)][query1(i)] = f.flow[query2(i)][column(c)] = 0;
}
}
}
return ans;
}
}
class MinCostMaxFlow { // from http://web.mit.edu/~ecprice/acm/acm08/MinCostMaxFlow.java
boolean found[];
int N, cap[][], flow[][], cost[][], dad[], dist[], pi[];
void init(int N) {
this.N = N;
cap = new int[N][N];
cost = new int[N][N];
}
void add(int from, int to, int ca, int cos) {
cap[from][to] = ca;
cost[from][to] = cos;
}
static final int INF = Integer.MAX_VALUE / 2 - 1;
boolean search(int source, int sink) {
Arrays.fill(found, false);
Arrays.fill(dist, INF);
dist[source] = 0;
while (source != N) {
int best = N;
found[source] = true;
for (int k = 0; k < N; k++) {
if (found[k]) continue;
if (flow[k][source] != 0) {
int val = dist[source] + pi[source] - pi[k] - cost[k][source];
if (dist[k] > val) {
dist[k] = val;
dad[k] = source;
}
}
if (flow[source][k] < cap[source][k]) {
int val = dist[source] + pi[source] - pi[k] + cost[source][k];
if (dist[k] > val) {
dist[k] = val;
dad[k] = source;
}
}
if (dist[k] < dist[best]) best = k;
}
source = best;
}
for (int k = 0; k < N; k++)
pi[k] = Math.min(pi[k] + dist[k], INF);
return found[sink];
}
int[] findFlow(int source, int sink) {
found = new boolean[N];
flow = new int[N][N];
dist = new int[N+1];
dad = new int[N];
pi = new int[N];
int totflow = 0, totcost = 0;
while (search(source, sink)) {
int amt = INF;
for (int x = sink; x != source; x = dad[x])
amt = Math.min(amt, flow[x][dad[x]] != 0 ? flow[x][dad[x]] :
cap[dad[x]][x] - flow[dad[x]][x]);
for (int x = sink; x != source; x = dad[x]) {
if (flow[x][dad[x]] != 0) {
flow[x][dad[x]] -= amt;
totcost -= amt * cost[x][dad[x]];
} else {
flow[dad[x]][x] += amt;
totcost += amt * cost[dad[x]][x];
}
}
totflow += amt;
}
return new int[]{ totflow, totcost };
}
}
That was a bit of spoiler.
Btw, problem 600 can be solved without using mincost-flow, but using an LR-max-flow algorithm (for finding maximum flow when there are lower bounds of flows for each edge).
Problem 600 can be solved with maximum matching (with vertices on each side).
Nice, I didn't expect that. How to do it with matching?
As I see, the first part contains N rows and cnt[i] vertices for each rectangle -- placeholders for columns that are supposed to cover by marked cells in rectangle.
The same holds for the second part, but for columns and rows' placeholders.
Btw, thanks for such interesting problems!!!
What's wrong with the solution using bfs for the 250 pointer ?
There could be O(N2) edges, so the complexity could be O(N3) right?
This can be overcome by breaking out of the BFS as soon as all vertices are visited.
Did that in last minute but failed systest because of integer overflow -_-
Small clarification, this would only speed up BFS in practice right?
I mean, consider some graph with N / 2 nodes with all pairs of edges connected. the rest N / 2 nodes connected as a chain with this main component. Here BFS from any of those nodes in main component will be still O(N2) right?
Yeah, it does not help the asymptotic behavior in the general case. But in this problem, BFS becomes O(N) instead of O(N2), for the same reason the more clever solution works.
Lol there's nothing wrong when you do a bit of optimization such as returning when all of the vertices are in the queue = ))
Why did you set the time limit for the 800-pointer two times the usual 2s?
I tried to write my Java solution to be as slow as reasonably possible. It requires ~2s for the current constraints so I chose 4s to be TL.
But you may ask why I chose high constraints. Well, to not be afraid about O(n3) approach. In hard problems it's a disaster when people get worse complexity accepted so it's very convenient for me to set high constraints. I think that everything would be fine today with lower constraint for n but I also don't see important pros.
My screencast
Slightly unrelated, but what tool are you using for opening problem statement in browser and coding in Dev C++ instead of the arena?
It is really tough to use the arena(UX wise)
Actually, I just started to use Greed and I like it. Previously I used KawigiEdit. There are some nice posts about Greed on Vexorian's blog. For what it's worth, my config is the following:
(replace DOLLAR with dollar signs).
In your code for BearCircleGame, I believe that is a geometric series not an arithmetic series. Please correct me if I'm wrong.
Thanks, corrected now.