Jestliže vniřní bod hrany XkXk+1 je viditelný z bodu v na C, z definice viditelnosti vyplývá, že celá hrana XkXk+1 je viditelná z tohoto bodu. Z toho a z konvexnosti M vyplývá, že z bodu v na kružnici C je viditelný úsek MV(v)=XiXi+1 U Xi+1Xi+2 U ... U Xj-1Xj z obvodu M. Tento úsek je jednoznačně určený uspořádáanou dvojicí indexů (i,j) (dále budeme pod (i,j) rozumět buď uspořádanou dvojici, nebo úsek obvodu M, z kontextu bude jasné, který význam máme na mysli). Naopak, každý vrchol Xi je viditelný z oblouku ziki, kde zi je průsečík polopřímky XiXi-1 s C, ki průsečík polopřímky XiXi+1 s C. Navrhneme algoritmus, který určí body zi, ki, uspořádá je na kružnici C a tím rozdělí C na 2m oblouků s konstantními množinami viditelnosti (některé oblouky mohou být i jednobodové). Pro každý oblouk určíme i MV - úsek (i,j). MV pro koncové (tj. styčné) body oblouků určíme tak, že porovnáme množiny viditelnosti sousedících oblouků a MV styčného bodu je větší z nich. Výsledkem části a) bude cyklický seznam koncových bodů oblouků s příslušnými uspořádanými dvojicemi (i,j) (tj. pro v na daném oblouku je MV(v)=(i,j)); první, resp. druhé prvky těchto dvojic budou v seznamu uspořádány proti směru hodinových ručiček.
Abychom nemuseli třídit, budeme procházet průsečíky proti směru hodinových ručiček. Jestliže přejdeme přes zj, MV se rozšíří o Xj-1Xj. Jesliže přejdeme přes kj, z MV vypadne hrana XiXi+1. Daný průsečík se poté stane koncovým bodem oblouku. Cyklus nastartujeme tím, že ve směru hodinových ručiček nalezneme vrchol Xi, který není viditelný z bodu z1, ale Xi+1 ještě ano. Potom oblouk začínající v bodě z1 má MV=(i+1,1). Za zvláštní pozornost stojí pouze případ zj=ki, tehdy dostaneme jednobodový oblouk s MV=MV(ki)=MV(zj)=(i,j). Algoritmicky to znamená, že při uspořádání ma zj přednost před ki.
V části b) stačí určit minimální počet oblouků (dvojic), jejichž množiny viditelnosti pokrývají obvod M. Budeme hledat takový minimální seznam (nemusí být určen jednoznačně). Vstupem algoritmu bude cyklický seznam L uspořádaných dvojic z části a); koncové body oblouků nebudeme potřebovat. Nechť dalsi(d) je dvojice následující za dvojicí d=(d.i,d.j) v seznamu L. Ke každé dvojici d z L určíme dvojici nejdal(d), pro kterou platí mezi(d.i,nejdal(d).i,d.j) and not mezi(d.i,dalsi(nejdal(d).i),d.j).
Je jasné, že jestliže se v minimálním seznamu vyskytne d, tak existuje minimální seznam obsahující d a nejdal(d) a neobsahující dvojice z L mezi nimi - z dvojic dalsi(d), dalsi2(d), ..., nejdal(d) musí být alespoň jedna v minimálním seznamu; seznam zůstane minimálním, jestliže ji nahradíme dvojicí nejdal(d). V případě d'=dalsik(d), nejdal(d)=nejdal(d') hodnotu nejdal(d') změníme na nedefinovanou.
K dokončení algoritmu si všimněme, že minimální seznam musí obsahovat dvojici d pokrývající X1, tj. platí mezi(d.i,1,d.j). Pro každé takové d postupně vypočítáme nejdal(d), nejdal2(d), ..., dokud nenajdeme nejmenší takové k, že nejdalk(d) pokrývá d.i . Jestliže přitom narazíme na nedefinovaný ukazatel nejdal^l(d), pak existují posloupnosti d, nejdal(d), ..., nejdall-1(d) a d', nejdal(d'), ..., nejdall-1(d') stejné délky bez společných prvků (kdyby měli společný prvek, již dříve by bylo nejdall'(d) nedefinované), přičemž d i d' pokrývají X1, d' je před d v seznamu L a hodnota nejdall(d) je nedefinovaná, protože by se měla rovnat hodnotě nejdall(d). To znamená, že existuje minimální seznam neobsahující d: podseznam d,... nahradíme podseznamem d', ... a tedy můžeme výpočet pro dáné d ukončit.
Časová složitost je lineární, neboť každým definovaným ukazatelem nejdal se projde nanejvýš jednou a stejně tak nedefinované se testují nejvýše jednou.
P-III-2
f7=ac-bd, f8=ad+bc, tedy komplexní číslo f7+f8i je součin komplexních čísel
(a+bi) a (c+di).
Lineární algoritmus pro vstup a, b, c, d využívající právě jedno násobení
dokáže spočítat pouze polynomy tvaru:
(*) v1 (t1 a + t2 b + t3 c + t4 d) (u1 a + u2 b + u3 c + u4 d) + v2 a + v3 b + v4 c + v5 d)
a z řešení úlohy P-I-3 víme, že výraz ac-bd není tohoto tvaru, tj. se nedá
spočítat lineárním algoritmem multiplikativní složitosti 1. Analogicky
se dokáže obdobné tvrzení pro výraz ad+bc.
Sporem nyní dokážeme, že na současný výpočet ac-bd a ad+bc potřebujeme
alespoň 3 násobení. Kdyby se tyto výrazy daly vypočítat pomocí 2 násobení,
nechť p1 je výsledek 1. násobení, p2 2. násobení:
a c - b d = r1 p1 + r2 p2 + r3 a + r4 b + r5 c + r6 d
a d + b c = s1 p1 + s2 p2 + s3 a + s4 b + s5 c + s6 d
a r2 <> 0 <> s2 (neboť na výpočet ac-bd i ad+bc potřebujeme 2 násobení).
Odečteme r2-násobek 2 rovnice od s2-násobku první a dostaneme:
s2 a c - s2 b d - r2 a d - r2 b c =
( s2 r1 - r2 s1 ) p1 + ( s2 r3 - r2 s3 ) a +
( s2 r4 - r2 s4 ) b + ( s2 r5 - r2 s5 ) c +
( s2 r6 - r2 s6 ) d
Tedy výraz s2 a c - s2 b d - r2 a d - r2 b c se dá vypočítat pomocí jediného
násobení a je proto tvaru (*) s v1 <> 0. Porovnáním koeficientů dostáváme:
(1) t1 u1 = 0
(2) t2 u2 = 0
(3) t3 u3 = 0
(4) t4 u4 = 0
(5) t1 u2 + t2 u1 = 0
(6) v1 ( t1 u3 + t3 u1 ) = s2
(7) v1 ( t1 u4 + t4 u1 ) = -r2
(8) v1 ( t2 u3 + t3 u2 ) = -r2
(9) v1 ( t2 u4 + t4 u2 ) = -s2
(10) t3 u4 + t4 u3 = 0
přičemž v1, s2 a r2 jsou různé od 0. Díky symetrii (*) a (1) můžeme přepokládat
u1 = 0 a postupně dostaneme t1 <> 0 <> u3 ze (6), u2 = 0 z (5), u4 <> 0 ze (7),
t3 = t4 = 0 ze (3) a (4), t2 <> 0 z (8) a tedy s2 = v1 t1 u3, -r2 = v1 t1 u4,
-r2 = v1 t2 u3 a -s2 = v1 t2 u4 a získáváme spor:
0 > -s22 = ( v1 t1 u3 ) ( v1 t2 u4) = ( v1 t1 u4 ) ( v1 t2 u3 ) = r2^2 > 0
Tedy dvojice výrazů ac-bd a ad+bc se nedá spočítat pomocí 2 násobení.
P-III-3
Nejprve si všimneme, že při hledání optimální platby se stačí omezit
na takové platby, při kterých pro každé i xi=0 nebo
yi=0, neboť nemá smysl,
aby plátce dával mince, které mu příjemce opět vrátí. Platbou tedy budeme
rozumět n-tici celých čísel u1, u2, ..., un
(kladné ui znamená, že plátce dal
ui mincí hodnoty qi, záporné ui znamená, že příjemce vrátil -ui mincí této hodnoty).
Dále si uvědomme, že se stačí zabývat obnosy dělitenými q1 - jiné obnosy danými mincemi nevyplatíme.
Označme ti= ( ( qi+1 /qi ) - 1 ) / 2, tj. qi+1/qi = 2 ti + 1, ti >= 1 pro 1 <= i < n. Předpokládejme q1 | X a budeme uvažovat platby U s vlastností u1q1 + u2q2 + ... = X.
Následující pozorování ukazuje, že platba U s vlastností (*) je jednoznačně určena:
Důkaz:
Jestliže by U<>U', pak vezmeme nejmenší i0 takové, že ui0 <> ui0'.
Jistě je i0 < n, jinak by obnosy zaplacené
U a U' nebyly stejné. Potom:
ui0qi0+...+unqn=ui0'qi0+...+un'qn
Odečteme a vytkneme qi0:
(ui0 - ui0') qi0 = K qi0 ( 2 ti0 + 1 )
Vzhledem k (*) |ui0 - ui0'| <= 2 ti0, tedy K = 0 a ui0 = ui0', což je spor.
Samotný algoritmus funguje takto: vyjdeme z platby U = ( X/q1, 0, ..., 0 ). K ní zkonstruujeme podle pozorování 1 platbu U', splňující podmínku (*). Je-li Uopt optimální platba, zkonstruujeme k ní platbu Uopt' s vlastností (*), která je také optimální. Podle pozorování 2 pak U'=Uopt', tedy U' je optimální.
Položíme X1=2n-1X2n-1, ..., Xi=2n-iX2n-i, Xn=X a chceme tedy nalézt X tak, aby X -> 2n-1X2n-1. Ale 2n-1X2n-1=7n-1(2n-1X) a stačí tedy použít Craigův zákon s M=7n-1, A=2n-1: existuje X s vlastností X -> M(AX). Řešením je například X=7n-1572n7n-1572.