Solutii la concursul ACM ICPC 2013 etapa nationala partea a doua

Petru Trimbitas
21 iunie 2013

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.

A. Cubic Eight-Puzzle

Problema ne dă un grid de 3×3 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 •Adrian Budau

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 ³⁰ stări.
Pentru a reduce numărul de stări prin care trecem vom folosi 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 ¹⁵ stări.

B. Manhattan Wiring

Î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 articol înainte de citirea soluţiei.

O problemă asemănătoare s-a dat la CEOI 2006. Soluţia ei se găseşte aici

Soluţie

În scrierea soluţiei m-am inspirat de aici

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ă.

C. Power Calculus

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula x ⁿ ( 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 ³¹ poate fi calculat cu 7 înmulţiri:
x ² = x × x, x ⁴ = x ² × x ², x ⁸ = x ⁴ × x ⁴ , x ¹⁰ = x ⁸ × x ² , x ²⁰ = x ¹⁰ × x ¹⁰, x ³⁰ = x ²⁰ × x ¹⁰ , x ³¹ = x ³⁰ × x
Acesta poate fi calculat şi cu 6 operaţii (5 înmulţiri şi o împărţire)
x ² = x × x, x ⁴ = x ² × x ², x ⁸ = x ⁴ × x ⁴ , x ¹⁶ = x ⁸ × x ⁸ , x ³² = x ¹⁶ × x ¹⁶ , x ³¹ = x ³² ÷ 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.

#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;
}

D. Polygons on the Grid

Î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 •Mugurel-Ionut Andreica

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.