Solutii la concursul acm 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

Ne vom folosi de Meet in the middle făcând un bfs, fiecare nod din graf fiind o stare a gridului, din starea iniţială şi din cea finală pană la distanţa 15. La fiecare pas avem 4 mutări posibile dintre care una ne va duce înapoi deci doar 3 ne interesează. Astfel vom trece prin 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.

Soluţie

Se poate observa că 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). Se poate observa de asemenea că fiecare secvenţă continuă de fire de pe fiecare linie şi coloană va conţine maxim două L-uri. Altfel am putea scurta lungimea cablului cu 2.

C. Power Calculus

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula x ⁿ 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 numerele folosite până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să aplicăm operaţiile asupra ultimului număr şi al unui număr calculat pe parcurs.

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