算法 {差分约束系统,不等式组}

定义

错误汇总

前缀和数组的原数组, 要考虑其全部的限制因素

有一个bool A[]的原数组 (取值0/1), 他对应一个int sum[]的前缀和数组;

我们有关系: A[l, l+1, ..., r] >= k, 即对应不等式: sum[r] - sum[l-1] >= k, 对应差分约束的有向边为: sum[l-1] + k <= sum[r] 即(l-1) -> (r) [w];

这一类关系: 即(l-1) -> (r) [w];

第二类关系 也容易考虑到, 即A[] >= 0, 对应(i-1) -> (i) [0];

但一定不要忘记, 还有一个限制, 即A[] <= 1, 故必须还要有: (i) -> (i-1) [-1], 否则就错了;

算法模板

//{ InequationSystem-Declaration
template< class _Type_Edge, class _Type_Distance>
class InequationSystem{
public:
    const _Type_Distance * Distance;
    //-- variable ends
    InequationSystem( const Graph_Weighted< _Type_Edge> *);
    bool Initialize();
private:
    const Graph_Weighted< _Type_Edge> * graph;
    int points_range;
    _Type_Distance * distance;
    bool * isInQueue;
    int * queue;
    int queue_head, queue_tail;
    int * pathLength;
};
//} InequationSystem-Declaration

//{ InequationSystem-Implementation
//<
// @Brief
// . A edge `a->b (w)` in `graph`, means a inequation `Distance[a] + w <= Distance[b]` (`w` can be any-integer);
// . This algorithm use **SPFA** to get the **Maximal-Distance** for each point, finally `Distance[x] >= 0` if this Inequation-System is solvable
//   . More precisely, `Distance[x]` would be the **Minimal-Value (>=0)** under the whole Inequation-System;
// @Function( Initialize)
// . If return `true` when this Inequation-System is solvable (then the answer is `Distance[]`), otherwise return `false;
// @Hint
// . Cuz the core-algorithm is SPFA, if TimeOut occurs, you can use the next-code in `@Mark_0`;
//   . if( ++ timeOut > points_range * @Unfinished(5/10/15/...)){ return true;}
template< class _Type_Edge, class _Type_Distance> InequationSystem< _Type_Edge, _Type_Distance>::InequationSystem( const Graph_Weighted< _Type_Edge> * _graph)
        :
        graph( _graph){
    distance = new _Type_Distance[ graph->Get_pointsCountMaximum()];
    Distance = distance;
    isInQueue = new bool[ graph->Get_pointsCountMaximum()];
    queue = new int[ graph->Get_pointsCountMaximum() + 1];
    pathLength = new int[ graph->Get_pointsCountMaximum()];
}
template< class _Type_Edge, class _Type_Distance> bool InequationSystem< _Type_Edge, _Type_Distance>::Initialize(){
    points_range = graph->Get_pointsCount();
    memset( distance, 0, sizeof( _Type_Distance) * points_range);
    memset( pathLength, 0, sizeof( int) * points_range);
    for( int i = 0; i < points_range; ++i){ queue[ i] = i;}
    memset( isInQueue, true, sizeof( bool) * points_range);
    queue_head = 0, queue_tail = points_range;
    //--
    int cur, nex, edge;
    while( queue_head != queue_tail){
        //>< @Mark_0
        cur = queue[ queue_head ++];
        isInQueue[ cur] = false;
        if( queue_head > points_range){ queue_head = 0;}
        for( edge = graph->Head[ cur]; ~edge; edge = graph->Next[ edge]){
            nex = graph->Vertex[ edge];
            if( distance[ cur] + graph->Weight[ edge] > distance[ nex]){
                pathLength[ nex] = pathLength[ cur] + 1;
                if( pathLength[ nex] >= points_range){
                    return false;
                }
                distance[ nex] = distance[ cur] + graph->Weight[ edge];
                if( false == isInQueue[ nex]){
                    isInQueue[ nex] = true;
                    queue[ queue_tail ++] = nex;
                    if( queue_tail > points_range){ queue_tail = 0;}
                }
            }
        }
    }
    return true;
}
//} InequationSystem-Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

例题

CSDN-129476594;

@Delimiter

经验总结

题型/算法分析

Cuz this kind of problem must corresponds to a Graph $G$ (an edge $a\to b(w)$ always denotes $V[a]+w\le V[b]$, then calculating the Minimal-Value for every $V[x]$ under the premise $V[all]\ge 0$);
. Although the Normal-SPFA can solve the problem, but it maybe Out-Of-Time, that is, if there is better algorithms, we should always give up the idea of SPFA;
. According to the different characteristics of the Graph, there are the best-method to solving the problem :
+ If $G$ is a $DAG$ (whatever the edge-weight is, positive/zero/negative), see the below-section;
+ If all edges-weight of $G$ are $\ge 1$, see the below-section;
+ If all edges-weight of $G$ are $\ge 0$, see the below-section;

若$G$ 为$DAG$, 最优算法为拓扑序

Link

--

The optimal-method is:

ASSERT( the problem must be Consistent/Solvable);
V[] = 0;
for( c : $(the topological-sequence of G){
	ASSERT( V[c] is the answer of `c`);
	for( n : $(the adjacent-points of `c`)){
		w = the weight of the edge;
		V[ n] = max( V[n], max( V[c] + w, 0)); //< find the Maximal-Distance of `n` from any start-point in the DAG, and also ensure `V[all]` always `>= 0`;
	}
}
1
2
3
4
5
6
7
8
9

若所有边权$\ge 1$, 最优算法为拓扑序

AcWing-1192. 奖金

$G$ such that all edges-weight are $\ge 1$, an edge denotes an equality $a+w\le b$ where $w\ge 1$;
+ The problem is Inconsistent if and only if $G$ is not a DAG;
. Otherwise (i.e., Consistent), let $Dist[x]$ be the Maximal-Distance from any start-point in the DAG to $x$; finally, the answer is $Dist$ (that is, the Minimal-Value under the condition $Dist[x]\ge 0$);

若所有边权$\ge 0$, 最优算法为SCC

AcWing-368. 银河

$G$ such that all edges-weight are $\ge 0$, an edge denotes an equality $a+w\le b$ where $w\ge 0$;
+ The problem is Inconsistent if and only if There is an Non-Zero edge within a $SCC$ of $G$;
. Otherwise (i.e., Consistent), let $G1$ be the DAG after shrinking all $SCC$s of $G$, $Dist[x]$ where $x\in G1$ be the Maximal-Distance from any start-point in the DAG $G1$ to $x$; finally, the answer of $a$ equals to $Dist[A]$ where $A\in G1$ is the SCC of $a\in G$ (that is, the Minimal-Value under the condition $\forall a\in G,\ge 0$);
. Note that, any edge $a\to b(w)$ in $G$ where $a,b$ not belongs to the same $SCC$, should corresponds to an edges $A\to B(w)$ in $G1$ where $A,B$ denotes the $SCC$; equivalently, we can choose a Maximal-Edge $a\to b(w)$ as the unique-edge $A\to B$

@Delimiter( below are the old-interpretation)

If $w\ge 0$ for all $xi+w\le xj$, as we know, it forms a Directed-Graph, and we should calculate Greatest-Path with the origin $Dist[all]=0$;
1 Inconsistent (there exists a Positive-Circuit) $\iff$ there exists a edge $>0$ in a SCC;
. Proof $p\to q$, a Positive-Circuit must belongs to a SCC;
. Proof $q\to p$, due to all edges $\ge 0$, a circuit that contains a $>0$ edge in a SCC, the sum of this circuit must $>0$;
. As a lemma, if it is consistent, all edges in a SCC are $0$.
2 The maximal-distance of a point $a$ $\iff$ the maximal-distance of a SCC (to which the point $a$ belongs) in the DAG (after shrinking-SCC);
. Now, all edges in a SCC are $0$ (so, the $Dist[]$ of all points in a SCC are the same), all edge in DAG $\ge 0$; the maximal-distance of a point $a$, must with the form $s\to ...\to a$, it is equivalent to its corresponding DAG-Path $S\to ...\to A$ (cuz any edge within a SCC is $0$); therefore, we calculate the Maximal-distance on a DAG;

Total cost: $O(n+m)\ast 2$

Tarjan_SCC< int> tarjan( &G); //< all edges in `G` are `> 0`
tarjan.Initialize();
//{
for( int i = 0; i < n; ++i){
    for( int j, z = G.Head[ i]; ~z; z = G.Next[ z]){
        j = G.Vertex[ z];
        if( (tarjan.Scc_id[ i] == tarjan.Scc_id[ j]) && (G.Weight[ z] != 0)){
            cout<< "Inconsistent";
            return;
        }
    }
}
//}
auto DAG = tarjan.Build_DAG();
DAG_Tools< int> dag_tool( DAG);
dag_tool.IfIsDAG_andThen_getTopologySequence();
vector< int> Dist( DAG->Get_pointsCount(), 0);
for( int i = 0; i < DAG->Get_pointsCount(); ++i){
    int c = dag_tool.Topological_Sequence[ i];
    FOR_EDGES_( c, nex, wth, DAG->)
        Dist[ nex] = max( Dist[ c] + wth, Dist[ nex]);
    }
}

for( int i = 0; i < n; ++i){
    Dist[ tarjan.Scc_id[ i]];  //< the answer of point `i`; (the minimal-value under the condition `all xi >=0 `
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

当答案要求为(满足$xi\le d$的最大值),而非通常的(满足$xi\ge d$的最小值)

The usual question is calculating the minimal-value for every $xi$ under the condition $xi\ge d\forall xi$

---

But when the question is that calculating the maximal-value for every $xi$ under the condition $xi\le d\forall xi$, it also can be solved:

• Continue in the usual setting, calculating the minimal-value for every $xi$ under the condition $xi\ge D\forall xi$ where $D=-1\ast d$;
  supposing that the final answer denoted by $Xi$;
• Return back to the current setting, the maximal-value for $xi$ under the condition $xi\le d\forall xi$ equals $-1\ast Xi$;

不等式恒为$\le$

Whatever the problem is, making sure that every inequality always be the form of $xi+w\le xj$ which corresponds to a edge $xi\to xj$ with weight $w$. (Any Inequalities-System problem can always be solved in this form)

负边不可省略

The Greatest-Path of a point may contains Negative-Edge (e.g., the edges on the path are 10, -1)

差分约束

问题描述

Given a sequence of variables $x1,x2,...,xn$, and a Inequality-Group which consists of a set of relations with the form $xi+c\le xj$ where $c$ is a constant.

The question is, find out the minimal value of every $xi$ under the condition $(allxi)\ge d$ (or find out the minimal sum of $xi$ under the same condition, actually they are the same), (or find out the maximal value of every $xi$ under the condition $(allxi)\le d$, in fact they are also the same). A another view-point see Geometrical description

问题分析

It can be proved that the solution-set is either infinite or empty (no solution / inconsistent) .

For example
. $x1+1\le x2$ implies the solutions $...(-1,\ge 0),(0,\ge 1),(1,\ge 2)...$ (abbr., $(x,>x)$)
. $x1\le x2,x2\le x1$ implies the solutions $...(-1,-1),(0,0),(1,1)...$ (abbr., $(x,x)$)
. $x1+1\le x2,x2+1\le x1$ implies no-solution, that is inconsistent.

As a lemma, if $(c1,c2,c3,...)$ is a solution, then $(c1+k,c2+k,c3+k,...)$ is also a solution. (cuz $xi+w\le xj$ then $xi+w+k\le xj+k$)

---

Cuz $xi<xj$ can transformed to $xi+1\le xj$
$xi>xj\to xj+1\le xi$
$xi=xj\to xj\le xi,xi\le xj$
$xi\ge xj\to xj\le xi$

Consequently, the general form of a relation is $xi+cRxj$ where $R$ can be $=,<,>,\le ,\ge$ and $c$ is a constant.
. But, the relation $xiRc$ where $c$ is a constant is Invalid, it can’t be contained in this system, cuz it not satisfies the form $xi+c\le xj$.
. Moreover, the relation $xi+xj\le c$ is invalid, it corresponds to $xi-c\le -xj$, note this case.

选择$\le ,\ge$而不是$<,>$

Firstly, let’s introduce the notion of Constant-Compare and Variable-Compare.
Constant-Compare: $x<y$ where $x,y$ are both certain constant (e.g., $x=1,y=2$).
. let $a,b,c$ be arbitrary constant, if we have $a<b$ and $b<c$, then there must have $a<c$; more generally, $(a+w1<b,b+w2<c)\to (a+w1+w2<c)$, cuz $a+w1<b<c-w2$, and then $a+w1+w2<b+w2<c$; we call it the property of Transitive. (i.e., we deduced a new relation based on two relations)
Variable-Compare: $x<y$ where $x,y$ are variable, that is the value of $x,y$ has multiple choice.
. let $x,y,z$ be variable, if we have $x<y$ and $y<z$, then it not satisfies the property Transitivity. More precisely, $x<z$ is just a necessity, but not a Necessity-Sufficiency. Cuz based on $x<y,y<z$ we can deduced that $z>x+1$ (cuz the range of $y$ is $[x+1,\infty )$ from $x<y$, the range of $z$ is $[y+1,\infty )$ from $y<z$, so combine them we conclude that the range of $z$ is $[x+2,\infty )$, so, $x<z$ is just a necessity of $x+1<z$ which is the correct-relation. (e.g., $x<y,y<z,z<k$, we have $x+2<k$)
. This maybe some sophisticated, let’s discuss further, the reason why Transitivity must based on Necessity-Sufficiency is that, two relations $R1,R2$ deduced a new relation $R3$, so that $R3$ can totally replace these previous two relations! that is $R1:x+w1<y$ and $R2:y+w2<z$, then we know that $z$ is confined by $R1,R2$ simultaneously, now we want to use just one relation $R3$ to replace the role acted above by $R1,R2$. Therefore, $R3$ must be equivalent to $R1,R2$ (not just necessity). For example, $x<y,y<z$ tells us that $x+1<z$; however the relation $x<z$ deduced by Transitivity tells us $x<z$ which indicates that $z$ can choose $x+1$, but in fact $z$ can’t be $x+1$.

In summary, $<,>$ has the property of Transitivity under Constant-Compare, but not for Variable-Compare.
That is, $(a1+w1<a2,a2+w2<a3,...,am+wm<ak)\to (a1+w1+w2+...+wm<ak$ satisfied only under Constant-Compare (i.e., $ai$ is constant).

---

Let’s see the case of $\le ,\ge$.
You can prove that, the Transitivity $(a1+w1\le a2,a2+w2\le a3,...,am+wm\le ak)\to (a1+w1+w2+...+wm\le ak$ satisfied whichever Constant-Compare or Variable-Compare (i.e., it also satisfied if $ai$ is variable).

Cuz this question is based on Variable-Compare and only $\le \ge$ satisfied the Transitivity, so we should transform all relation to the form $xi+w1\le xj$ ($\ge$ is also usable, we will talk about it below, but the default choice is $\le$)

There is a rule (or stipulation), the constant-value $w$ should always be placed on the left-side, that is the form $x+w\le y$ and $x+w\ge y$. If not, you should move the constant $w$ to the left.

根据不等式组进行建图

We introduced Transitivity above, now we talk about its application.

For a relation $x+w\le y$, cuz it shows a infinite solution set $...(-1,\ge (-1+w)),(0,\ge (0+w)),(1,\ge (1+w)),...$, or abbreviated $(x,\ge (x+w))$; we find that $x$ has infinite choices $...,-1,0,1,...$ and $y$ has also infinite choices $x+w,x+w+1,x+w+2,...$, that is two sides are both infinite. Our device is fixing the left-side, then only the right-side is infinite.
Subsequently, once $x$ has fixed, then the solution/range of $y$ is the form $[a,\infty )$, therefore we can use a single number $a$ to denote the minimal available number of $y$.

If we construct a graph by using a edge $x\to y$ with weight $w$ to represents the relation $x+w\le y$.
e.g., for the fixed $x$, the relations $x+2\le y$ and $x+5\le y$ implies the range of $y$ are $[x+2,...)$ and $[x+5,...)$ respectively, then the answer range of $y$ should be intersection of these two ranges, that is $[x+5,...)$ is the answer, we use a single number $x+5$ to denote the answer. Consequently, we should run the Greatest-Path on this graph.

Conclusion: We set the start-points $Dist[all]=0$, then run a Greatest-Path SPFA on G, if we found a Positive-Loop meaning that it’s No-Solution; otherwise, $Dist[x]$ means that the minimal-available-number of $x$ under the condition $Dist[all]\ge 0$.

Cuz we have stipulated that $xi$ is fixed and $xj$ is confined by $xi$ by the relation $xi+w\le xj$; cuz $xi$ maybe also confined by $xz+w\le xi$, that is $xj$ is confined by two relation, and maybe more;
So, any restriction on $xi$ is a chain $xa+w\le xb,xb+w\le xc,...,xd+w\le xi$, according to the property of Transitivity, it can be combined into $xz+w1+w2+...\le xi$; we found that it corresponds to a path on the graph, i.e., any path $s\to ...\to xi$ means a restriction on $xi$; e.g., two paths $Dist[s1]+w1=d1$ and $Dist[s2]+w2=d2$ means that the range of $xi$ should be $[d1,\infty )$ and $[d2,\infty )$, and then we choose the intersection $max(d1,d2)$ which corresponds to the Greatest-Path.

According to the property of Greatest-Path, if it is Solvable, $Dist[all]\ge 0$ finally. Cuz $Dist[x]$ is unique, the answer solution-set $Dist[...]$ is unique;
e.g., $x+1\le y,y+0\le z,z+0\le y,x+2\le w$, finally we get the solution-set: $Dist[x]=0,Dist[y,z]=1,Dist[w]=2$ which is unique; in other words, under the condition $Dist[all]\ge 0$, the minimal value of $x$ is $0$ which is unique ($0$ maybe also the only available choice of $x$ under this solution-set (i.e., $(x,1,1,2)$ is not a solution-set if $x\ne 0$), but also maybe not (i.e., $(x,1,1,2)$ is also a solution-set for some values $x\ne 0$), it will discussed further in the next section).
As a lemma, under the condition $xi\ge 0$, two statements: 1. find out the minimal-value for every $xi$ and 2. find out the minimal-value of the sum of all $xi$, are equivalent.

---

$x-5\le y$, when we set $x=0$, the range of $y$ is $[-5,\infty )$, but the algorithm will get $Dist[y]=0$ not $-5$; because we have the restriction The value of all variables should $\ge 0$.

---

According to the property of Greatest-Path and set all-points be the start-points with the same $Dist[all]=c$, the answer got above under the condition $xi\ge 0$ can be generalized to the condition $xi\ge d$.
That is, set the start-points $Dist[all]=d$ not $0$, we have $Dist[x]=D[x]+d$ where $D[x]$ is the $Dist[x]$ under the case setting start-points $Dist[all]=0$.

$\le$和$\ge$的等价性

Cuz the Inequality-Group is unchanged, $xi+w\le xj$ can also transformed to $xj-w\ge xi$;
The rules are the same as previous, assuming $xj$ is fixed, then the range of $xi$ is $(\infty ,xj-w]$ (this differs from previous), now the intersection is $min(d1,d2)$ for two ranges $(\infty ,d1]$ and $(\infty ,d2]$, so it corresponds to Least-Path.

That is, transfer all relations to the form $xi+c\ge xj$, set the start-points $Dist[all]=0$, and then run Least-Path (If no Negative-Loop), we will get $Dist[all]\le 0$; e.g., $Dist[x]=k$ means the maximal-available-value of $x$ is $k$ under the condition $\forall xi\le 0$.

So, the maximal-value of $xi$ under the condition $xi\le d$ equals $Dist[x]+d$.

Moreover, there is a conclusion: $D1[x]=-1\ast D[x]$ where $D[x]$ is the $Dist[x]$ (minimal-available-value) under the Greatest-Path of setting start-points $Dist[all]=0$ with the form $xi+w\le xj$, and $D1[x]$ (maximal-available-value) under the Least-Path of setting start-points $Dist[all]=0$ with the form $xi+w\ge xj$.

---

Therefore, the case of $\ge$ could also always transferred to $\le$.
For instance, get the maximal-value under the condition $xi\le d$;
Firstly, we transform all relations to the form $xi+w\le xj$, build a graph, set start-points $Dist[all]=0$, run a Greatest-Path SPFA; finally, $Dist[x]$ is the minimal-value of $x$ under the condition $\forall xi\ge 0$
Secondly, $-1\ast Dist[x]$ means the maximal-value of $x$ under the condition $\forall xi\le 0$;
Further, $-1\ast Dist[x]+d$ is the maximal-value of $x$ under the condition $\forall xi\le d$.

几何解释

If the condition is $\forall xi\ge d$, it means that every number $xi$ in the number-axis should as closely as possible to $d$ from the right-side (i.e., $xi\ge d$) (the condition $\forall xi\le d$ means from the left-side), so that the sum of $|xi-d|$ attains the minimum among other solutions.

做题技巧

Suppose that there is a structure SPFA: Check-Positive-Loop with Start-Distance be $0$ (that is, setting start-points $Dist[all]=0$ and then run Greatest-Path SPFA), then all Inequality-Group problems can be solvable using this same structure.
In other words, if your device for Inequality-Group using a different SPFA which is not SPFA: Check-Positive-Loop with Start-Distance be $0$, then, your device is wrong.

对恒等关系$xi=k$的特殊处理

If there is relation $xi=k$, it can be also solvable using a trick by transfer it to $xi=xj+c$ where $c$ is also a constant, then for the relation $xi=xj+c$ that is valid, it corresponds to two relations $xi\le xj+c$ and $xi\ge xj+c$ which correspond to the standard relations $xi-c\le xj$ and $xj+c\le xi$.

If you ensure that there always exists a point $xj$ such that $Dist[xj]$ always equals to a constant $c$ whatever the graph G (the premise is G is solvable), then $xi=k=k+c-c=c+(k-c)=xj+(k-c)$, that is $xi=xj+(k-c)$ where $k,c$ are knowns, so it can transferred to $xi-(k-c)\le xj$ and $xj+(k-c)\le xi$;

For example, if there is a Zero-Chain that involves all points $x1\to x2\to ...\to xn$ with all edges be $0$, there has a property from Greatest-Path: If G is solvable (no Positive-Loop), then $x1$ must be a real-start-point, that is $Dist[x1]$ always equals $0$. So, we conclude that $Dist[x1]=0$ whatever the graph G is but contains a Zero-Chain and be solvable;
Therefore, a relation $xi=c$ can be transformed to $xi=c+0=x1+c$, then $xi-c\le x1$ and $x1+c\le xi$

转换为前缀和数组时的注意点

If you get a inequality $xl+...+xrRc$, we find that if we transform it to Prefix-Sum-Array, then it corresponds to $S[r]-S[l-1]Rc$ which satisfies the standard inequality form.

Note that, the index of $xi$ should starts at $1$ so that every $xi$ corresponds to two Prefix-Sum. (in other words, $x\mathrm{0...}{x}_{n-1}$$ should move abstractly to $x\mathrm{1...}xn$, then we have a Prefix-Sum $S0,...,Sn$, that is $S1-S0=x0$)
If you use $S0=x0,Si-S_{i-1}=xi$, then for a relation $xl+...xrRc$ where if $l=0$ then it corresponds to a relation with one variable $SrRc$, and corresponds to a relation with two variables $Sr-S_{l-1}Rc$ if $l>0$;
This makes a bit of cumbersome cuz you need handle by cases, and moreover, a relation with just one relation $SrRc$ is not valid.

例题

1169. 糖果

link

There are two types inequalities: $xi\ge 1\forall xi$ and $xiRxj$ where $R$ is $=,<,>,\le ,\ge$ (it can transformed to $xi+w\le xj$). Then calculate the minimal-sum of $xi$.

It is the standard Inequality-Group form, so after the algorithm, you will get the solution-set for the minimal value of $xi\ge 0$, then perform $xi=xi+1$ to making sure $xi\ge 1$;

362. 区间

link

A similar question link which says that the interval has $odd/even$ number of $1$ (Disjoint-Set with Depth can solve it)

Let $Ai$ denotes whether it is $1$ in the position of $i$ where the index of $A$ starts at $1$, then $Ai=0/1$.
We have the relation:
$Ai\ge 0$
$Ai\le 1$
$Al+...+Ar\ge c$ (not satisfy the standard-form)

When involving a sum of interval elements, it usually transferred to Prefix-Sum (there also has a trick that there must exists a empty element in Prefix-Sum $S0$; in other words, $n$ variables $x1,...,xn$, correspond to $n+1$ variables $S0,S1,...,Sn$ when transformed to Prefix-Sum; the reason why doing so is explained in link)

Now
$Si-S_{i-1}\ge 0$
$Si-S_{i-1}\le 1$
$Sr-S_{l-1}\ge c$
which is a standard Inequality-Group.

The answer (the sum of $A1,...,An$) equals $Sn-S0$.

More speaking, when handling with Prefix-Sum, usually it will exists a Zero-Chain, as here $S0\to S\mathrm{1...}\to Sn$ where every edge is $0$, it means that if it is consistent, then $S0$ must be a real-start-point, that is, $Dist[S0]$ must be $0$ in any cases.

1170. 排队布局

link

$n$ points on a line from left to right $x1\le ...\le xn$
It has the relations:
$xi\le x_{i+1}\forall i\in [1,n)$
$xj-xi\le c$ where $j>i$
$xj-xi\ge c$ where $j>i$
It already could be transformed to the standard-form (where has no condition of the $xi\le or\ge d\forall xi$ which is a optional restriction);

After the algorithm, if it returns False that is it is inconsistent; otherwise we got the minimal value $Dist[x]$ for every $x$ such that $xi\ge 0$.

How should we calculate the maximal-distance between $x1,xn$?
After the algorithm, we get $Dist[x1]=0$ and $Dist[x1]\le Dist[x2]\le ...\le Dist[xn]$ (due to the Zero-Chain $x1\to x2\to ...\to xn$), as we discussed in the article above, for this current solution-set $a1,a2,...,an$ where $ai=Dist[xi]$, for any $xi$, there are two cases: 1 maybe the solution-set $a1,...[ai,\infty ),...,an$ is also valid under the condition of without modify $a1$; 2 maybe just a few of solution-sets $a1,...[ai,ai+k],...,an$ are valid under the condition of without modify $a1$.
1 e.g., $n=3$ with $x1\le x2\le x3$ and $x2\ge x3$, we also got the solution-set $(0,0,0)$, we find that $0,x,x$ where $x\in [0,\infty )$ is also a solution.
2 e.g., $n=3$ with $x1\le x2\le x3$ and $x2\ge x3,x1\ge x2$, the solution-set is $(0,0,0)$, however, the range of $xn$ could only be $[0,0]$ not infinite (if $x3=1$, then it must will affect $x1$)
3 e.g., $n=3$ with $x1\le x2\le x3$ and $x2\ge x3,x1\le x2,x2-2\le x1$, the solution-set is $(0,0,0)$, but the solution-set $(0,1,1)$ $(0,2,2)$ are also solution-sets without modify $x1$.

This is, according to $Dist[]$, we could not check that whether the maximal-distance between $x1,xn$ is infinite or not.

Conclusion: The maximal-distance between $x1,xn$ is infinite then there would not exists a path $xn\to ...\to x1$; if exists such path, then the Greatest-Path $Dist[x1]$ with $xn$ be start-point indicates the maximal-distance.
Proof: this path means a relation $xn+w\le x1$ and we already have a relation $x1\le xn$, therefore, $xn-x1\ge 0$ and $xn-x1\le -w$ we found that the distance $xn-x1$ has confined in $-w$ (moreover, $-w$ should $\ge 0$, otherwise it causes a contradiction which means inconsistent)

The Maximal-distance between $x1,xn$ is that, we set $Dist[xn]=0$ as the only start-point, then run Greatest-Path, finally $Dist[0]\ast -1$ is the answer.
Proof: cuz the graph G is unchanged, that is, a edge $a\to b$ with $w$ always denotes a relation $a+w\le b$ (that is no matter to whether the start-points is $[all]=0$ or $[xn]=0$); e.g., there are two paths $d1\le xi$ and $d2\le xi$ then their intersection is $max(d1,d2)$; in other words, the properties satisfies as previous are also valid when the start-point is just $xn$; so, it is still Greatest-Path.
Cuz the Zero-Chain (suppose that $x1$ is accessible for $xn$), so we still the property $Dist[x1]\le ...\le Dist[xn]$, and $xn$ must be a real-start-point due to it it the only start-point and G is solvable, that is $Dist[xn]$ always equals $0$;
Any path $xn\to ...\to x1$ actually means a relation $xn+w\le x1$ (i.e., $xn-x1\le -w$, where $w\le 0$ proved above) which has already shows that the maximum of $xn-x1$ is $w$; but the distance of $x1,xn$ that is $|x1-xn|=max(xn-x1,x1-xn)$, now we got $xn-x1$; we need consider $x1-xn$; this should be linked to the previous information $x1\le xn$, so we have $x1-xn\le 0$; therefore $|x1-xn|=xn-x1$;
One path means the $xn-x1\le -w$ (the maximum-distance is $-w$), but there maybe multiple paths, that is we have $xn-x1\le -w1$, $xn-x1\le -w2$, $...$, (it also represents $x1\ge w1,x1\ge w2,...$), according to the intersection $x1\ge max(w1,w2,...)$, and also the Greatest-Path would get $max(w1,w2,...)$ finally; so finally $Dist[x1]=k$ means that the relations between $x1,xn$ must satisfies $xn-x1\le -k$ (that is, if $xn$ is fixed at $0$, then the longest position which can be chosen by $x1$ is $-k$);

One difference from the previous is that, in the previous $Dist[x]=max(0,allpaths)$ due to every points is a start-point; but in here $Dist[x]=max(allpaths)$ due to there is only one start-point

Minimize_InequalitiesSystem< int, int> check( &G);
check.Initialize();
auto ret = check.Work();
if( false == ret){ //< inconsistent
    cout<< -1;
    return;
}
check.Spfa(); //< set `Dist[xn]=0` with others be `invalid`, run Grestest-Path
int invalid;
memset( &invalid, -0x7F, sizeof( invalid));
if( spfa.Distance[ 0] == invalid){ //< not accessible
    cout<< -2;
    return;
}
cout<< -1 * spfa.Distance[ 0];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

393. 雇佣收银员

link

There are some terms:
we divide one-day into $24$ hour-interval, $[0,1],[1,2],...,[23,0]$; a staff has a start-work-time $x$, means this staff would work with $8$ hour-intervals $[x,x+1],[x+1,x+2],...,[x+7,x+8]$;
$Mi[x]$ denotes there must have at least $Mi[x]$ staffs at the time $[x,x+1]$
$Ma[x]$ denotes there are $Ma[x]$ staffs whose start-work-time is $x$ (that is, you can choose at most $Ma[x]$ at this time)

---

Let’s see a wrong device using Greedy.
Let $A[x]$ be the total staff-count at the time $[x,x+1]$, then we have $A[x]\ge Mi[x]$, these $A[x]$ staffs consists of $a$ staffs whose start-work-time is $x$ and $b$ staffs whose start-work-time is $<x$.
If there exists a point $x$ such that $b=0$ (i.e., $A[x]=a$) and $A[x]=Mi[x]$, let’s stop this idea cuz if we thinking rigorously you will find this is impossible, due to this problem is a Loop not linear, so there would not exists a Start-Point.
Suppose we choose the staffs be $0,7,14,21$, then $A[]=[2,2,2,2,2,1,1,2,1,1,1,1,1,1,2,1,1,1,...]$ and we let $Mi[]=A[],Ma[]>A[]$, we found that there is not a point $x$ such that $A[x]$ equals the staff-chosen-count whose start-time is $x$; ($A[0/7/14/21]=2$ while the staff-chosen-count at that time is $1$; other $A[]>=1$ while the staff-chosen-count is $0$)

---

Let’s see a wrong device using Inequality.
If we define $A[x]$ be the total staff-count at the time $[x,x+1]$ (e.g., if there is a staff whose start-work-time is $a$, then it will cause $A[a],...,A[a+7]$ added by $1$.
Then we would have the next inequalities:
$A[x]\le 0$, $A[x]\ge Mi[x]$, $A[x]\le Ma[x]$
It is very important to realize that the relation $A[x]\le Ma[x]$ is wrong, cuz $A[x]$ is the working-staff-count at time $x$, while $Ma[x]$ is the maximal-staff-count whose start-work-time is $x$. (e.g., $Ma[i]=1,Ma[i+1]=0$, we choose a staff at $i$, but we have $A[i],A[i+1],...,A[i+7]=1$, therefore $A[i+1]>Ma[i+1]$. In fact, this is reasonable)
Actually, it should be corrected by $A[x]\le Ma[x]+Ma[x-1]+...+Ma[x-7]$; it still is complicated due to the definition of $A[x]$; suppose that now we got all $A[0,1,\mathrm{2...},23]$, we still don’t know how many staffs chosen which is the answer asked. It is important to associate your algorithm to the answer that problem-asked.

---

Cuz the answer that question asked is the total-staff-chosen-count, so we define $A[x]$ be the staff-chosen-count whose start-work-time is $x$; this definition is very vital, then the answer is clear that equals the sum $A[]$.
Then we have:
$A[x]\ge 0\forall x\in [0,23]$
$A[x]\le Ma[x]$
${\sum }_{i=x-7}^{x}A[i]\ge Mi[x]$ (note here, only the staffs whose start-time is $x-7,...,x$ would cover the current-time $[x,x+1]$)

Cuz involves the summation, so we need transform to Prefix-Sum; (as we mentioned above, Prefix-Sum must has a empty-element $S[0]$; so $A[0-23]\to S[0-24]$)
Let $A[x]=S[x+1]-S[x]$ (note that, $S[x]$ is Linear that is it equals the sum $A[0]+...+A[x-1]$; although this problem is not Linear but Loop)
So we have
$S[x+1]-S[x]\ge 0$
$S[x+1]-S[x]\le Ma[x]$
$@Tag0$

@Tag0 is very vital, cuz $A[]$ is a Loop, for the sum ${\sum }_{i=x-7}^{x}A[i]$, when $x<7$ it will involves $A[23],A[22]...$; while the Prefix-Sum $S[]$ is Linear that is its Start-Point is $A[0]$; so the transformation here is vital;

So, it becomes:
$S[x+1]-S[x]\ge 0$
$S[x+1]-S[x]\le Ma[x]$
$S[x+1]-S[x-7]\ge Mi[x]ifx\ge 7$
$S[x+1]+(S[24]-S[17+x])\ge Mi[x]ifx<7$

The former $3$ relations fit the standard-form $xi+c\le xj$, while there exists $3$ unknowns $S[x+1],S[24],S[17+x]$ in the last relation, we need to eliminate it to $2$ unknowns
Cuz for all inequalities with the last-form, they share the same unknown $S[24]$.

So we can iterate it to make it a constant (that is, we try multiple Inequality-Systems), suppose $S[24]=c$, now although that inequality fit the standard-form, it is very important that now you have a new relation $S[24]=c$.

According to the trick mentioned above, cuz there is a Zero-Chain $S0\to ...\to S24$, so it is solvable, then $S0$ must be $0$, so $S24=c=c+0=c+S0$, then $S24\le c+s0$, $S24\ge c+S0$;

---

We find that $S24=c$ denotes the answer ($S24$ is the sum of all $A[]$), and cuz the answer is the least number; so $c$ satisfies Binary-Search.

bool Check( int _mid){
    for( int i = 0; i < 7; ++i){
        G->Modify_edge( Edges_0.at( i), Mi[ i] - _mid);
    }
    G->Modify_edge( Edges_1.at( 0), _mid);
    G->Modify_edge( Edges_1.at( 1), -1 * _mid);
    if( false == Spfa->Work()){
        return true;
    }
    return false;
}
//----


for( int i = 0; i < 24; ++i){
    //> A[ i] >= 0 `->` Sum[ i + 1] - S[ i] >= 0
   G->Add_edge( i, i + 1, 0);
}
for( int i = 0; i < 24; ++i){
    //> A[ i] <= Ma[ i] `->` Sum[ i + 1] - S[ i] <= Ma[ i]
    G->Add_edge( i + 1, i, -1 * Ma[ i]);
}
for( int i = 7; i < 24; ++i){
    //> A[ i - 7] + ... + A[ i] >= Mi[ i] `->` S[ i + 1] - S[ i - 7] >= Mi[ i]
    G->Add_edge( i - 7, i + 1, Mi[ i]);
}
Edges_0.clear();
for( int i = 0; i < 7; ++i){
    //> A[ 23 - ?] + ... + A[ 23] + A[ 0] + ... + A[ i] >= Mi[ i] `->` S[ i + 1] + S[ 24] - S[ 17 + i] >= Mi[ i]
    G->Add_edge( 17 + i, i + 1, 0); //< `0` is just a placeholder
    Edges_0.push_back( G->Get_last_edgeId());
}
Edges_1.clear();
//> S[ 24] = C `->` S[ 24] >= S[ 0] + C, S[ 24] <= S[ 0] + C
G->Add_edge( 0, 24, 0);
Edges_1.push_back( G->Get_last_edgeId());
G->Add_edge( 24, 0, 0);
Edges_1.push_back( G->Get_last_edgeId());
//--
Spfa = new SPFA_CheckLoop< int, int>( G);
Spfa->Initialize();
int l = 0, r = n;
while( l < r){
    int mid = (l + r) >> 1;
    if( Check( mid)){
        r = mid;
    }
    else{
        l = mid + 1;
    }
}
if( false == Check( r)){
    cout<< "No Solution" <<endl;
    return;
}
cout<< r <<endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

Redirect-Id

0, 1, 2