Revin cu partea a doua a articolului cu soluţii la problemele de la faza naţională a concursului ACM ICPC. Acestea sunt problemele grele şi au fost rezolvate de puţine echipe. Vă invit să discutaţi soluţiile la comentarii.
Revin cu partea a doua a articolului cu soluţii la problemele de la faza naţională a concursului ACM ICPC. Acestea sunt problemele grele şi au fost rezolvate de foarte puţine echipe. Vă invit să discutaţi soluţiile la comentarii.
h2. 'A. Cubic Eight-Puzzle':http://acm.tju.edu.cn/toj/vcontest/showp9268_A.html
Problema ne dă un grid de $3x3$ acoperit cu 8 cuburi fiecare aşezat într-una din celule. Fiecare are două dintre feţele opuse colorate cu albastru(B) iar celelalte două colorate cu alb(W) şi cu roşu$(R)$. La o mutare poate fi rostogolit unul din cuburi în celula liberă. Problema ne cere să aflăm numărul minim de mutări necesare pentru a ajunge într-o configuraţie dată. Se ştie că iniţial cuburile sunt cu faţa albă in sus iar faţa albastră e în dreapta. Celula goală se află în stânga-jos.
Problema ne dă un grid de $3x3$ acoperit cu 8 cuburi fiecare aşezat într-una din celule. Fiecare are două dintre feţele opuse colorate cu albastru(B) iar celelalte două colorate cu alb(W) şi cu roşu( R ) . La o mutare poate fi rostogolit unul din cuburi în celula liberă. Problema ne cere să aflăm numărul minim de mutări necesare pentru a ajunge într-o configuraţie dată. Se ştie că iniţial cuburile sunt cu faţa albă in sus iar faţa albastră e în dreapta. Celula goală se află în stânga-jos. Dacă numărul de mutări e mai mare de $30$ se va afişa $-1$
*Soluţie* oferită de ==user(user="freak93")==
O primă soluţie ar fi să facem o parcurgere în lăţime din starea iniţială făcând maxim 30 mutări. La fiecare pas avem $4$ mutări posibile dintre care una ne va duce înapoi deci doar $3$ ne interesează. În total vom trece prin $3 ^ 30 ^$ stări.
Pentru a reduce numărul de stări prin care trecem vom folosi 'Meet in the middle':blog/meet-in-the-middle. În loc să pornim o parcurgere doar din sursă, vom porni una şi din destinaţie şi făcând maxim 15 mutări. Astfel vom încerca să întâlnim din sursă un nod vizitat din destinaţie sau invers. Astfel vom vizita doar $2*3 ^ 15 ^$ stări.
h2. 'B. Manhattan Wiring':http://acm.tju.edu.cn/toj/vcontest/showp9268_B.html
În această problemă ni se dă o matrice de $NxM$ ( $N<=9 M<=9$ ) cu unele celule ocupate. Două dintre celulele matricei sunt marcate cu $2$ şi două cu $3$. Trebuie afişată suma minimă a lungimii a două lanţuri care nu se intersectează şi unesc cele două celule cu $2$ şi cele două cu $3$ fără a ieşi din matrice sau a trece prin celulele ocupate.
Recomand citirea 'acestui':http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=22 articol înainte de citirea soluţiei.
O 'problemă':http://www.hsin.hr/ceoi2006/tasks/day2/connect.pdf asemănătoare s-a dat la CEOI 2006. Soluţia ei se găseşte 'aici':http://www.hsin.hr/ceoi2006/tasks/solutions.pdf
*Soluţie*
În scrierea soluţiei m-am inspirat de 'aici':http://f0rth3r3c0rd.wordpress.com/2013/04/25/uva-1214-manhattan-wiring/
Fiecare celulă poate fi în următoarele stări: goală, ocupată cu un cablu vertical/orizontal sau cu un cablu în L(4 stări). Vom calcula lungimea minima a cablurilor poziţionate până la linia $i$ iar cele din $stare$ sunt legate de linia anterioară( $0$ nu există legătură, $1$ există legătură iar cablul va fi legat de $2$, $2$ există legătură iar cablul va fi legat de $3$). Pentru a calcula tanziţiile vom genera cu backtracking starea cablurilor de pe coloana următoare şi vom avea grijă să păstrăm următoarea $stare$ corectă.
h2. 'C. Power Calculus':http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html
h2. 'D. Polygons on the Grid':http://acm.tju.edu.cn/toj/vcontest/showp9268_D.html
Problema ne cere să aflăm numărul minim de operaţii pentru a calcula $x ^n^$ ( $n <= 1000$ ) pornind de la $x$ fără a folosi puteri negative şi făcând înmulţiri cu numere calculate deja. De exemplu $x ^31^$ poate fi calculat cu $7$ înmulţiri:
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^10^ = x ^8^ × x ^2^ , x ^20^ = x ^10^ × x ^10^, x ^30^ = x ^20^ × x ^10^ , x ^31^ = x ^30^ × x$
Acesta poate fi calculat şi cu $6$ operaţii (5 înmulţiri şi o împărţire)
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^16^ = x ^8^ × x ^8^ , x ^32^ = x ^16^ × x ^16^ , x ^31^ = x ^32^ ÷ x$
*Soluţie*
Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de $2000$. Într-o poziţie din coadă vom reţine toate puterile calculate până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să adunăm sau să scădem ultima putere calculată cu una calculată anterior.
==code(cpp) |
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
struct drum{
int lst,sz,cst;
int fol[32];
};
int n=-1,dmin[3005];
void ins(queue<drum> &c,drum fr,int nxt) {
if(nxt<2 || nxt>2000) return;
drum next=fr;
++next.cst;
if(next.cst==dmin[nxt]) {
next.fol[++next.sz]=next.lst=nxt;
c.push(next);
}
if(dmin[nxt]>next.cst) {
dmin[nxt]=next.cst;
next.fol[++next.sz]=next.lst=nxt;
c.push(next);
}
}
int main() {
for(int i=2; i<=1000; ++i) dmin[i]=(1<<30);
queue<drum> c;
drum fr; fr.sz=0; fr.lst=1; fr.cst=0; fr.fol[++fr.sz]=1;
for(c.push(fr);c.size(); c.pop()) {
fr=c.front();
for(int i=1; i<=fr.sz; ++i) {
ins(c,fr,fr.lst+fr.fol[i]);
ins(c,fr,fr.lst-fr.fol[i]);
}
}
while(1) {
cin>>n;
if(n==0) break;
cout<<dmin[n]<<'\n';
}
return 0;
}
==
h2. 'D. Polygons on the Grid':http://acm.tju.edu.cn/toj/vcontest/showp9268_D.html
În această problemă trebuie să aflăm aria maximă a unui poligon cu colţurile în puncte laticeale care are lungimile laturilor date. Poligonul are maxim $6$ laturi iar lungimea maximă a unei laturi e $300$
*Soluţie* oferită de ==user(user="mugurelionut")==
Ideea soluţiei este încercarea tuturor variantelor: se poate fixa o latură ca fiind prima şi îi încercăm toate orientările spre "dreapta-sus": orizontal, vertical, si, eventual, "oblic" dacă se poate aşeza cu capetele într-un punct întreg). Pe urmă variem ordinea celorlalte laturi ( $5!$ ) şi pentru fiecare dintre celelalte laturi încercăm orientările posibile care pastrează convexitatea poligonului. În plus mai trebuie folosită următoarea optimizare: Fixăm cea mai mare lungime ca fiind prima latură. Dacă lungimile rămase nu ne ajung să "închidem" poligonul atunci ne oprim.
