5.153. equilibrium

DESCRIPTIONLINKS
Origin

Inspired by the Irish Collegiate Programming Competition 2012 (equilibrium index)

Constraint

πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™Έπ™½π™³π™΄πš‡1,π™Έπ™½π™³π™΄πš‡2,π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½,𝙲𝙾𝙴𝙡1,𝙲𝙾𝙴𝙡2,πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄,π™²πšƒπš

Synonym

πš‹πšŠπš•πšŠπš—πšŒπšŽπš.

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™Έπ™½π™³π™΄πš‡1πšπšŸπšŠπš›
π™Έπ™½π™³π™΄πš‡2πšπšŸπšŠπš›
π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½πš’πš—πš
𝙲𝙾𝙴𝙡1πš’πš—πš
𝙲𝙾𝙴𝙡2πš’πš—πš
πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄πš’πš—πš
π™²πšƒπšπšŠπšπš˜πš–
Restrictions
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯1
π™Έπ™½π™³π™΄πš‡1β‰₯1
π™Έπ™½π™³π™΄πš‡1≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™Έπ™½π™³π™΄πš‡2β‰₯1
π™Έπ™½π™³π™΄πš‡2≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™Έπ™½π™³π™΄πš‡1β‰€π™Έπ™½π™³π™΄πš‡2
π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½β‰₯0
π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½β‰€2
π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1
𝙲𝙾𝙴𝙡1β‰ 0
𝙲𝙾𝙴𝙡2β‰ 0
πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄β‰₯0
π™²πšƒπšβˆˆπšŠπš–πš˜πš—πš_πšπš’πšπš_0,πšŠπš—πš,πšŒπš‘πšŠπš—πšπšŽ,πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’,πš‘πš’πšπš‘πšŽπšœπš_πš™πšŽπšŠπš”,πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ,πš’πš—πšπš•πšŽπš‘πš’πš˜πš—,πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ,πš•πš˜πš—πšπšŽπšœπš_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ,πš•πš˜πš—πšπšŽπšœπš_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπšŽπššπšžπšŽπš—πšŒπšŽ,πš–πšŠπš‘_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš•πš˜πš™πšŽ,πš–πšŠπš‘_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš•πš˜πš™πšŽ,πš–πš’πš—_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš•πš˜πš™πšŽ,πš–πš’πš—_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš•πš˜πš™πšŽ,πš–πš’πš—_πš πš’πšπšπš‘_πš™πšŽπšŠπš”,πš–πš’πš—_πš πš’πšπšπš‘_πšŸπšŠπš•πš•πšŽπš’,πš™πšŽπšŠπš”,πšœπšžπš–_πšŒπšπš›,πšŸπšŠπš•πš•πšŽπš’
Purpose

Given πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,β‹―,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ, enforce the following conditions:

  • π™Έπ™½π™³π™΄πš‡1β‰₯1

  • π™Έπ™½π™³π™΄πš‡2β‰₯1

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½β‰₯0

  • π™Έπ™½π™³π™΄πš‡1β‰€π™Έπ™½π™³π™΄πš‡2

  • 𝙲𝙾𝙴𝙡1β‰ 0

  • π™Έπ™½π™³π™΄πš‡1≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|

  • π™Έπ™½π™³π™΄πš‡2≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½β‰€2

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄β‰₯0

  • 𝙲𝙾𝙴𝙡2β‰ 0

if π™²πšƒπš=πšŒπš‘πšŠπš—πšπšŽ: πšŒπš‘πšŠπš—πšπšŽ(C 1 ,βŒ©πš…π™°πš 1 ,β‹―,πš…π™°πš π™Έπ™½π™³π™΄πš‡1 βŒͺ,β‰ ) πšŒπš‘πšŠπš—πšπšŽ(C 2 ,βŒ©πš…π™°πš π™Έπ™½π™³π™΄πš‡2 ,β‹―,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ,β‰ ) if π™²πšƒπš=πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ: πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ(C 1 ,βŒ©πš…π™°πš 1 ,β‹―,πš…π™°πš π™Έπ™½π™³π™΄πš‡1 βŒͺ,β‰ ) πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ(C 2 ,βŒ©πš…π™°πš π™Έπ™½π™³π™΄πš‡2 ,β‹―,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ,β‰ ) if π™²πšƒπš=πšœπšžπš–_πšŒπšπš›: πšœπšžπš–_πšŒπšπš›(βŒ©πš…π™°πš 1 ,β‹―,πš…π™°πš π™Έπ™½π™³π™΄πš‡1 βŒͺ,=,C 1 ) πšœπšžπš–_πšŒπšπš›(βŒ©πš…π™°πš π™Έπ™½π™³π™΄πš‡2 ,β‹―,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ,=,C 2 ) otherwise : π™²πšƒπš(C 1 ,βŒ©πš…π™°πš 1 ,β‹―,πš…π™°πš π™Έπ™½π™³π™΄πš‡1 βŒͺ) π™²πšƒπš(C 2 ,βŒ©πš…π™°πš π™Έπ™½π™³π™΄πš‡2 ,β‹―,πš…π™°πš |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ)

|𝙲𝙾𝙴𝙡1Β·C 1 -𝙲𝙾𝙴𝙡2Β·C 2 |β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄

Example
(4,4,3,6,2,2,4,2,1,1,0,πšœπšžπš–_πšŒπšπš›)
(-2,5,-2,6,-1,0,-3,5,-7,6,-1,7,0,5,5,0,1,1,0,πšœπšžπš–_πšŒπšπš›)
(-2,5,-2,6,-1,0,-3,5,-7,6,-1,7,0,11,11,0,1,1,0,πšœπšžπš–_πšŒπšπš›)
(0,3,2,6,2,2,5,8,7,6,7,3,5,7,2,1,1,0,πš™πšŽπšŠπš”)
(0,5,3,8,2,2,5,5,8,7,2,7,3,7,7,0,1,1,0,πšŒπš‘πšŠπš—πšπšŽ)

The first example, πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–(〈4 1 ,4 2 ,3 3 ,6 4 ,2 5 βŒͺ,2,4,2,1,1,0,πšœπšžπš–_πšŒπšπš›), holds since:

  • π™Έπ™½π™³π™΄πš‡1=2β‰₯1,

  • π™Έπ™½π™³π™΄πš‡2=4β‰₯1,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2β‰₯0,

  • π™Έπ™½π™³π™΄πš‡1=2β‰€π™Έπ™½π™³π™΄πš‡2=4,

  • C 1 =4 1 +4 2 =8,

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2,

  • π™Έπ™½π™³π™΄πš‡1=2≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=5,

  • π™Έπ™½π™³π™΄πš‡2=4≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=5,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2≀2,

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0β‰₯0,

  • C 2 =6 4 +2 5 =8,

  • |1Β·8-1Β·8|β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0.

Figure 5.153.1. Illustration of the first example of the Example slot
ctrs/equilibrium-1-tikz

The second example, πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–(〈-2 1 ,5 2 ,-2 3 ,6 4 ,-1 5 ,0 6 ,-3 7 ,5 8 ,-7 9 ,6 10 ,-1 11 ,7 12 ,0 13 βŒͺ,

5,5,0,1,1,0,πšœπšžπš–_πšŒπšπš›), holds since:

  • π™Έπ™½π™³π™΄πš‡1=5β‰₯1,

  • π™Έπ™½π™³π™΄πš‡2=5β‰₯1,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0β‰₯0,

  • π™Έπ™½π™³π™΄πš‡1=5β‰€π™Έπ™½π™³π™΄πš‡2=5,

  • C 1 =-2 1 +5 2 -2 3 +6 4 -1 5 =6,

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0,

  • π™Έπ™½π™³π™΄πš‡1=5≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=13,

  • π™Έπ™½π™³π™΄πš‡2=5≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=13,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0≀2,

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0β‰₯0,

  • C 2 =-1 5 +0 6 -3 7 +5 8 -7 9 +6 10 -1 11 +7 12 +0 13 =6,

  • |1Β·6-1Β·6|β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0.

Figure 5.153.2. Illustration of the second and third examples of the Example slot
ctrs/equilibrium-2-tikz

The third example, πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–(〈-2 1 ,5 2 ,-2 3 ,6 4 ,-1 5 ,0 6 ,-3 7 ,5 8 ,-7 9 ,6 10 ,-1 11 ,7 12 ,0 13 βŒͺ,

11,11,0,1,1,0,πšœπšžπš–_πšŒπšπš›), holds since:

  • π™Έπ™½π™³π™΄πš‡1=11β‰₯1,

  • π™Έπ™½π™³π™΄πš‡2=11β‰₯1,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0β‰₯0,

  • π™Έπ™½π™³π™΄πš‡1=11β‰€π™Έπ™½π™³π™΄πš‡2=11,

  • C 1 =-2 1 +5 2 -2 3 +6 4 -1 5 +0 6 -3 7 +5 8 -7 9 +6 10 -1 11 =6,

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0,

  • π™Έπ™½π™³π™΄πš‡1=11≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=13,

  • π™Έπ™½π™³π™΄πš‡2=11≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=13,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0≀2,

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0β‰₯0,

  • C 2 =-1 11 +7 12 +0 13 =6,

  • |1Β·6-1Β·6|β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0.

The fourth example, πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–(〈0 1 ,3 2 ,2 3 ,6 4 ,2 5 ,2 6 ,5 7 ,8 8 ,7 9 ,6 10 ,7 11 ,3 12 βŒͺ,

5,7,2,1,1,0,πš™πšŽπšŠπš”), holds since:

  • π™Έπ™½π™³π™΄πš‡1=5β‰₯1,

  • π™Έπ™½π™³π™΄πš‡2=7β‰₯1,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2β‰₯0,

  • π™Έπ™½π™³π™΄πš‡1=5β‰€π™Έπ™½π™³π™΄πš‡2=7,

  • the sequence 0 1 3 2 2 3 6 4 2 5 contains 2 peaks,

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2,

  • π™Έπ™½π™³π™΄πš‡1=5≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=12,

  • π™Έπ™½π™³π™΄πš‡2=7≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=12,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=2≀2,

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0β‰₯0,

  • The sequence 5 7 8 8 7 9 6 10 7 11 3 12 contains 2 peaks,

  • |1Β·2-1Β·2|β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0.

Figure 5.153.3. Illustration of the fourth example of the Example slot
ctrs/equilibrium-3-tikz

The fifth example, πšŽπššπšžπš’πš•πš’πš‹πš›πš’πšžπš–(〈0 1 ,5 2 ,3 3 ,8 4 ,2 5 ,2 6 ,5 7 ,5 8 ,8 9 ,7 10 ,2 11 ,7 12 ,3 13 βŒͺ,

7,7,0,1,1,0,πšŒπš‘πšŠπš—πšπšŽ), holds since:

  • π™Έπ™½π™³π™΄πš‡1=7β‰₯1,

  • π™Έπ™½π™³π™΄πš‡2=7β‰₯1,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0β‰₯0,

  • π™Έπ™½π™³π™΄πš‡1=7β‰€π™Έπ™½π™³π™΄πš‡2=7,

  • the sequence 0 1 ,5 2 ,3 3 ,8 4 ,2 5 ,2 6 ,5 7 contains 5 changes,

  • π™Έπ™½π™³π™΄πš‡2-π™Έπ™½π™³π™΄πš‡1=π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0,

  • π™Έπ™½π™³π™΄πš‡1=7≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=12,

  • π™Έπ™½π™³π™΄πš‡2=7≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|=12,

  • π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=0≀2,

  • πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0β‰₯0,

  • The sequence 5 7 ,5 8 ,8 9 ,7 10 ,2 11 ,7 12 ,3 13 contains 5 changes,

  • |1Β·5-1Β·5|β‰€πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0.

Figure 5.153.4. Illustration of the fifth example of the Example slot
ctrs/equilibrium-4-tikz
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
π™Έπ™½π™³π™΄πš‡1>1
π™Έπ™½π™³π™΄πš‡1<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
π™Έπ™½π™³π™΄πš‡2>1
π™Έπ™½π™³π™΄πš‡2<|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
𝙲𝙾𝙴𝙡1=1
𝙲𝙾𝙴𝙡2=1
π™΄π™Ώπš‚π™Έπ™»π™Ύπ™½=1
πšƒπ™Ύπ™»π™΄πšπ™°π™½π™²π™΄=0
See also

root concept: πš‹πšŠπš•πšŠπš—πšŒπšŽ.

Keywords

characteristic of a constraint: automaton with counters.