In primul rand, buna ziua.
Ieri m-am hotarat sa ma apuc de niste programare serioasa, astfel incat am inceput sa iau arhiva de probleme la rost si am dat peste problema flip.
Dupa ceva munca, a rasarit un algoritm care functioneaza pe toate cazurile prezentate aici pe forum insa problema e ca iau doar 30 de puncte din cauza rezultatelor eronate, ceea ce mi se pare ciudat, deci m-am hotarat sa va cer ajutorul.

Ideea de implementare a fost discutata si mai devreme pe forum asa ca o sa prezint un pseudocod simplu

backtracking dupa numar de linii
daca iteratorul depaseste returnez sol
in caz contrar
pentru linia normala (not flipped)
pentru fiecare coloana verific daca valoarea flipped este mai mare decat val normala
in cazul in care val normala este mai mare, adaug la total si trec la urmatoarea coloana
in cazul in care val flipped este mai mare, adaug la total, inmultesc val coloanei cu -1 si trec la urmatoarea coloana

pentru linia inmultita cu -1, acelasi lucru, doar ca... in cazul in care totalul liniei inmultite cu -1 este mai mare decat totalul liniei normale, modific matricea

orice ajutor este binevenit, mai jos este linkul catre ultima verificare
http://infoarena.ro/job_detail/648742

As vrea sa va multumesc pentru ajutor. Pana la urma a functionat cum trebuie programelul, astfel incat am scapat. Mai am de facut un word cu descrierea si e gata. Inca o data, multumesc celor de pe forumul Infoarena.

Cu ajutorul vostru, am dat gata procedura de inserare (am mai pus un if sa nu mi se compare cu NULL), deci multumesc voua 

Acum, stergerea imi pune mici probleme. Ideea e sa gasesc nodul in arbore, apoi sa il cobor ca frunza si mai apoi sa il sterg simplu cu un delete sau sa il fac NULL. Problema e ca primesc acelasi vechi segmentation fault care ma bantuie de 2 zile incoace, uitati codul :

void stergere(arb &r, int x)
{ if (x > r->inf)
     stergere (r->dr,x);
  else if (x < r->inf)
     stergere (r->st,x);
  else
  {if ((r->st == NULL) && (r->dr == NULL))
      {delete (r);r = NULL;}
   else
       {if (r->st->pr > r->dr->pr)
          rotst(r);
        else
           rotdr(r);
        stergere(r,x);
       }
  } 
 }

ar trebui sa ridic conditia cu fiu stanga si fiu dreapta sus ?

[if (r->st->pr > r->pr)]

Pai, am mai multe lucruri de spus acum. Un debug mi'a mai lamurit putin mintea dar totusi am nevoie de ajutor ca de aer, poate si din cauza ca peste 2 zile trebuie sa prezint proiectul.
Dupa cum am zis, un debug a fost foarte util si mi'a mai limpezit putin mintea, am descoperit intr-un fel problema la inserare.

Prima data, inserez radacina, apeland :

scanf ("%d",&x) ; nou(r,x) , unde nou creaza un nod in arbore

Dupa aceea, elementele le introduc utilizand in programul principal un While :

While (x != 0)
{scand ("%d",&x); ins(r,x);}

problema apare atunci cand introduc a doua valoare, adica :

Se apeleaza functia ins :

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);
ordonare (r);
 }

totul merge bine pana cand se ajunge la "Ordonare (r)"

void ordonare(arb &r)
{if (r->st->pr > r->pr)
    rotdr(r);
 if (r->dr->pr > r->pr)
    rotst(r);
  }

eroarea "Segmentation fault" apare in locul marcat cu rosu si boldit. Cel mai probabil, comparatia nu se face de la radacina, ci de la r-ul din functie (r->st; r->st->dr; etc). Articolul punea functia de ordonare exact in locul in care am plasat-o si eu, iar daca fac ordonare dupa, cum am incercat, arborele nu se echilibreaza cum trebuie.

Oricine are vreo idee, va rog postati. Eu raman la ideea cu aruncatu laptopului. Multumesc pentru asistenta acordata pana acum.   

nou imi creaza un nod in arbore si seteaza fiul stanga si fiul dreapta ca NULL

Cod:

void nou(arb &r,int x)
{  r = new nod; r->inf = x; r->pr = rand (); r->st = r->dr = NULL; }

si totusi logica pare sa fie buna, problema este ca nu functioneaza corect procedurile de inserare si procedura de stergere ... care sunt inspirate din articol. Eu unu mai am putin si imi arunc laptopu' pe geam 

Pff... da, ai dreptate )... cred ca e de la oboseala. Totusi, nu imi pot da seama de problema de la inserare. Orice parere si/sau solutie e binevenita

m'am uitat prin ce e acolo, singura problema e ca arborele pare sa aibe probleme la rotatii, cand se face echilibrarea. Inserez radacina, apoi la urmatorul nod apare eroare. Ideea e ca nu imi pot da seama unde anume am gresit. Iarasi, apar mici probleme in procesul de stergere. Uitati secventa de cod :

Pentru insert :

Cod:

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);
ordonare(r);
 }

Pentru delete :

Cod:

void stergere(arb &r, int x)
{ if (x > r->inf)
     stergere (r->dr,x);
  else if (x < r->inf)
     stergere (r->st,x);
  else
  {if ((r->st == NULL) && (r->dr == NULL))
      {r == NULL; delete r;}
   else
       {if (r->st->pr > r->dr->pr)
          rotst(r);
        else
           rotdr(r);
        stergere(r,x);
       }
  }  
 }

Procedurile sunt inspirate dupa articolul despre treaps... singura problema e ca logica pare a fi buna. Astfel incat m'am hotarat sa cer sfatul unor experti

De ceva vreme incerc sa codez un "Random search tree". Documentatie am gasit asa si asa... si multe lucruri nu am reusit sa le inteleg , am cautat si in multe carti si tot cam in bezna ma aflu. Asta e lista de proceduri pe care o am la momentul de fata... dupa 12 ore de lucru, m'am hotarat sa cer ajutor... macar sa reusesc sa inteleg ce e cu el deci, a bit of help, please  

Cod:

typedef struct nod *arb;
struct nod{int inf,pr;arb st,dr;};


void rotst(arb &r) // Se roteste r->dr catre stanga
{arb x = r->dr;
 r->dr = x->st;
 x->st = r;
 r = x;    
 }
 
void rotdr(arb &r) // Se roteste r->st catre dreapta
{arb x = r->st; 
 r->st = x->dr;
 x->dr = r; 
 r = x;
 }

void ordonare(arb &r)
{if (r->pr < r->st->pr)
    rotdr(r);
 if (r->pr > r->dr->pr)
    rotst(r);
  }

void citire(int &x)
{printf ("info : ");
 scanf ("%d",&x);
 }

void nou(arb &r,int x)
{  r = new nod; r->inf = x; r->pr = rand (); r->st = r->dr = NULL;}

void ins(arb &r,int x)
{if (r == NULL)
    nou (r,x);
 if (x < r->inf)
    ins (r->st,x);
 else
 if (x > r->inf)
    ins (r->dr,x);

 }

void afis(arb r)
{if (r != NULL)
    {afis (r->st); printf ("%d (prioritate : %d )\n",r->inf,r->pr); afis (r->dr);}
 }
 
void stergere(arb &r)
{if ((r->st != NULL) && (r->dr != NULL))
    if (r->st->pr > r->pr)
        rotst(r);
    else
        rotdr (r);
else
    delete(r);
        
 }