PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: carre
Tester: Smelskiy
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Given N particles located at integers positions (x_i,y_i) of a grid and being E the set of pairs of particles located at adjacent positions, the problem ask us to choose a sign to each of the particles’ value p_i in order to maximize the total grid value given by
where h(x_i,y_i) is the value of the cell containing particle i.
QUICK EXPLANATION:
The problem can be transformed to a minimum cut problem where each of the connected components defined by the cut corresponds to the set of particles with the same sign assigned.
EXPLANATION:
Let’s see that we can transform the problem into a minimum cut one.
Consider an undirected graph where each node corresponds to a particle and the edges connect particles located at adjacent cells. The value of the edge connecting particles i and j is given by \lvert p_i\, p_j\rvert. The graph we build this way includes so far the “interactions” between particles (first term of expression 1).
We need to take into account also the contribution of the second term. To do that, let’s consider two additional nodes, s and t, the former connected to every node located at position with non-negative h, the latter connected to every node located at position with non-positive h. The value given to each of these new edges is \lvert p_i \, h(x_i,y_i)\rvert.
As you can see, the values of the edges corresponds to the absolute value of the summands of expression that defines V.
If we define A = E \, \cup \, \lbrace s,t\rbrace , that is, the union of the pairs of adjacent particles and the nodes s and t, we can transform V in the following way
where h_j should be understood as h(x_j,y_j).
Let’s classify our nodes in two sets:
S contains node s and every node to which we assign a positive sign. T contains node t and every node to which we assign a negative sign.
Now V can be expressed as:
Where we have used the fact that only the terms that combine one element of S with one element of T will contribute with negative product. As we have summed these terms at first, we should subtract them twice.
In order to choose signs of J_i's that maximize V, the first term of last expression is irrelevant because it sums up over all nodes and takes absolute values. So, our goal is to minimize the second term, that depends on which particles belong to S and which ones to T.
As we said, the only contributions to the second term come from interactions between one of the nodes of S with one of the nodes of T, and those interactions are represented in our graph by the values of the edges. So, the problem of minimizing the second term of equation 2 is equivalent to the problem of finding a minimum cut that splits the graph in two components.
The Max Flow - Min Cut Theorem states that the minimum cut is equal to the max flow of the network. So we can arrive to the answer of our problem by using Edmond-Karp or Dinic’s algorithms to get the max flow (min cut) and replace it in equation 2.
Finally, in order to find the sign of each particle, once he have calculated the max flow, we can employ DFS over the residual graph to find the nodes that belong to the S component (or T). More specifically, all the nodes that we should associate positive values of p are reachable from s considering only edges with positive residual capacity.
ALMOST A REAL WORLD PROBLEM
With some minor modifications, this problem is used to model ferromagnetic (and antiferromagnetic) behaviours in materials. The V function corresponds to -Energy of the system, the p values to magnetic moments of particles and h to the position-dependent value of an external magnetic field. Maximizing V implies minimizing the energy of the system. A large grid with few particles simulates a diluted ferromagnetic material.
You can further read on the Ising model here.
SUBTASKS
Subtask 1
The value of N is so small that you can try the 2^N combinations of signs and keep the one that maximize V.
Subtask 2
A dynamic programming approach is possible, given the constraints. You can scan the grid from left to right. Every column has 2^P signs combinations, where P is the number of particles in that column (0 \le P \le H).
The dp state dp[i][j] can store the value of V if you consider up to column i and the index j is used to identify each one of the 2^P possible combinations of signs. The transition from column i-1 to column i requires to calculate the value of V for each of the 2^{P_i}*2^{P_{i-1}} combinations of signs.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define dbg(x) cerr << #x"= " << x << endl
const int INF=1E9;
const int GRDSZ=1002; // maximum grid size + 2
const int PARTICLES=201; // maximum particles number + 1
int h[GRDSZ][GRDSZ]; // stores the value's of the cells
int x[PARTICLES]; // stores the columns of the particles
int y[PARTICLES]; // stores the row of the particles
int p[PARTICLES]; // stores the absolute value of the particles
int up[PARTICLES]; // stores the sign given to each particle's value
int H; // height of the grid
int W; // width of the grid
int N; // number of particles
namespace dinic { // dinic's algorithm to find max flow of a network
struct edge {int to, rev, f, cap;};
struct graph {
int NN,src,dest;
vi dist, q, work;
vector<vector<edge> > g;
graph(int n):NN(n){dist.resize(n);q.resize(n);work.resize(n);g.resize(n);}
void add_edge(int s, int t, int cap) {
edge a{t, (int)g[t].size(), 0, cap};
edge b{s, (int)g[s].size(), 0, cap};
g[s].emplace_back(a);
g[t].emplace_back(b);
}
bool bfs() {
dist.assign(NN,-1);
dist[src] = 0;
int qsz = 0;
q[qsz++] = src;
for (int iq = 0; iq < qsz; ++iq) {
int u = q[iq];
for (auto &e : g[u]) {
int v = e.to;
if (dist[v] < 0 && e.f < e.cap) {
dist[v] = dist[u] + 1;
q[qsz++] = v;
}
}
}
return dist[dest] >= 0;
}
int dfs(int u, int f) {
if (u == dest) return f;
for (int &i = work[u]; i < (int)g[u].size(); ++i) {
edge &e = g[u][i];
if (e.cap <= e.f) continue;
int v = e.to;
if (dist[v] == dist[u] + 1) {
int df = dfs(v, min(f, e.cap - e.f));
if (df > 0) {
e.f += df;
g[v][e.rev].f -= df;
return df;
}
}
}
return 0;
}
int mf(int s, int t) {
src = s; dest = t;
int ret = 0;
while (bfs()) {
work.assign(NN,0);
while (int delta = dfs(s, INF))
ret += delta;
}
return ret;
}
};
};
void dfs_up(int node, const dinic::graph &G){
up[node]=1;
for(const auto &e : G.g[node]){
if (e.cap > e.f && up[e.to]==-1)
dfs_up(e.to,G);
}
}
void solve_case(){
dinic::graph G(N+2); // network flow graph (source=0; dest = N+1)
int V=0; // stores de value of the V function as defined in statement
// we will first sum the contributions of abs(h_i * p_i) and abs(p_i * p_j) and then substract the negative ones
for(int i=1;i<=N;++i){
V += abs(h[y[i]][x[i]])*p[i]; // interaction between particle and cell
if (h[y[i]][x[i]] >= 0) // if the cell has non-negative h, connect particle to source
G.add_edge(0,i,h[y[i]][x[i]]*p[i]);
if (h[y[i]][x[i]] <= 0) // if the cell has non-positve h, connect particle to dest
G.add_edge(i,N+1,-h[y[i]][x[i]]*p[i]);
for(int j=i+1;j<=N;++j){ // we scan all other particles to find adjacent (N <= 200, so we can doit in N*N time)
if (abs(y[i]-y[j]) + abs(x[i]-x[j])==1) { // if particles are adjacent, add an edge between them
G.add_edge(i,j,p[i]*p[j]);
V += p[i]*p[j]; // interaction between particles
}
}
}
// find max flow (min cut)
int mincut = G.mf(0,N+1);
V -= 2*mincut; // we remove (twice) the nagative contributions (see editorial)
// let's find the sign of each particle
fill(up,up + N + 1,-1); // initially set all of them to -1 (T component, see editorial);
dfs_up(0,G); // we do dfs starting from source to find all nodes that belong to the S component and assign them sign +1;
// output the results
cout << V << '\n';
for(int i=1;i<=N;++i)
cout << up[i] << " \n"[i==N];
}
void read_case(){
cin >> H >> W >> N;
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j)
cin >> h[i][j];
}
for (int i = 1; i <= N; ++i)
cin >> y[i] >> x[i] >> p[i];
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while (t--) {
read_case();
solve_case();
}
}
Tester's Solution
#include <iostream>
#include <string>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf = 1'000'000'000;
int H, W, n;
int h[1005][1005];
int px[205];
int py[205];
int price[205];
vector<pair<int, int> > v[205];
vector<int> rev[205];
int used[205];
int timer;
int depth[205];
bool positive[205];
void add_edge(int x, int y, int cap) {
v[x].push_back({y, cap});
v[y].push_back({x, cap});
rev[x].push_back((int)rev[y].size());
rev[y].push_back((int)rev[x].size() - 1);
}
int build_graph() {
int result = 0;
for (int i = 0; i <= n + 1; ++i) {
v[i].clear();
rev[i].clear();
used[i] = 0;
}
timer = 0;
for (int i = 1; i <= n; ++i) {
int cur = price[i] * h[px[i]][py[i]];
result += abs(cur);
if (cur >= 0) add_edge(0, i, cur);
else add_edge(i, n + 1, -cur);
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (abs(px[i] - px[j]) + abs(py[i] - py[j]) == 1) {
int cur = price[i] * price[j];
add_edge(i, j, cur);
result += cur;
}
}
}
return result;
}
bool make_bfs() {
for (int i = 0; i <= n + 1; ++i)
depth[i] = -1;
depth[0] = 0;
queue<int> qu;
qu.push(0);
while (!qu.empty()) {
int x = qu.front();
qu.pop();
for (int i = 0; i < v[x].size(); ++i) if (v[x][i].second > 0) {
int to = v[x][i].first;
if (depth[to] == -1) {
depth[to] = depth[x] + 1;
qu.push(to);
}
}
}
return (depth[n + 1] > -1);
}
int push_flow(int x, int flow, int dest) {
if (flow <= 0 || used[x] == timer)
return 0;
if (x == dest) return flow;
used[x] = timer;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (depth[to] > depth[x] && v[x][i].second > 0) {
int fl = push_flow(to, min(flow, v[x][i].second), dest);
if (fl > 0) {
v[x][i].second -= fl;
v[to][rev[x][i]].second += fl;
return fl;
}
}
}
return 0;
}
int find_min_cut() {
int max_flow = 0;
while (make_bfs()) {
while (true) {
++timer;
int cur_flow = push_flow(0, inf, n + 1);
if (cur_flow == 0) break;
max_flow += cur_flow;
}
}
return max_flow;
}
void find_positive(int x) {
positive[x] = true;
for (int i = 0; i < v[x].size(); ++i) {
int to = v[x][i].first;
if (v[x][i].second > 0 && !positive[to])
find_positive(to);
}
return;
}
void check_answer(int answer) {
int result = 0;
for (int i = 1; i <= n; ++i) {
int cur = price[i] * h[px[i]][py[i]];
if (!positive[i]) cur *= -1;
result += cur;
}
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (abs(px[i] - px[j]) + abs(py[i] - py[j]) == 1) {
int cur = price[i] * price[j];
if (!positive[i]) cur *= -1;
if (!positive[j]) cur *= -1;
result += cur;
}
}
}
if (result != answer) assert(false);
}
void solve(int test_id) {
cin >> H >> W >> n;
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
cin >> h[i][j];
}
}
for (int i = 1; i <= n; ++i) {
cin >> px[i] >> py[i];
cin >> price[i];
}
int full_price = build_graph();
full_price -= 2 * find_min_cut();
cout << full_price << '\n';
for (int i = 0; i <= n + 1; ++i)
positive[i] = false;
find_positive(0);
for (int i = 1; i <= n; ++i) {
if (i > 1)
cout << " ";
cout << (positive[i] ? 1 : -1);
}
cout << '\n';
// check_answer(full_price);
return;
}
int main(int argc, const char * argv[]) {
#ifdef __APPLE__
freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tests;
cin >> tests;
for (int i = 0; i < tests; ++i) {
solve(i);
}
return 0;
}
