infoarena

Am de rezolvat o problema si nu am nici cea mai mica idee cum sa o rezolv in limitele impuse...adica 3 secunde si maxim 20 de mega de memorie. Va rog daca se poate sa imi spuneti si mie "idee principala". O sa postez aici enuntul problemei. Implementarea pe care am incercato eu presupune impartirea ficarui nod in 4 noduri... problema este ca se ajunge la 40 000 de noduri si avand in vedere ca Dijkstra are O(N^2) timpul de executie a fost mult peste 3 secunde. Va multumesc anticipat!




Se da o tabla asemanatoare cu o tabla de sah, de dimensiune NxN. Pe o casuta de pe tabla se afla un zar; zarul are laturile egale
 ca lungime cu laturile casutei si ocupa perfect suprafata acesteia (adica laturile fetei de jos sunt suprapuse peste laturile casutei).
 Pe fiecare fata a zarului este inscriptionat câte un numar întreg între 1 si 100.

Zarul poate fi deplasat de pe o casuta pe una vecina printr-o rotatie de 90° în jurul uneia dintre laturile casutei ocupate.
Prin deplasari succesive, zarul poate ajunge în orice pozitie de pe tabla. Se defineste costul unui astfel de drum ca suma numerelor aflate pe
 fata de jos a zarului, inclusiv cele pentru prima si ultima casuta din traseu.

Dându-se dimensiunea tablei N, cele sase valori de pe fetele cubului, pozitia initiala a acestuia pe tabla si coordonatele unei
 casute pe care acesta trebuie sa ajunga, se cere sa gaseasca si sa se afiseze un drum de cost minim de la casuta initiala la casuta destinatie.

 

Date de intrare (fisierul cub.in):

N // dimensiunea tablei

fata spate stânga dreapta sus jos // cele 6 valori ale numerelor de pe fete

x1 y1 x2 y2 // coordonatele casutelor sursa, respectiv destinatie, cu numerotare de la 1 la N

 

Datele de iesire (fisierul cub.out):

C // costul drumului

L // lungimea drumului, ca numar de casute (inclusiv cea initiala si cea finala)

x1 y1

x2 y2

.....

xL yL // coordonatele casutelor prin care trece drumul

 

Observatie: initial cubul este asezat cu fata “fata” orientata în directia pozitiva a axei Y, fata “sus” în directia pozitiva a axei
 Z si fata “dreapta” în directia pozitiva a axei X.

Toate coordonatele încep de la 1.

 

Limite:

1 <= N <= 100

 

Exemplu:

INPUT:
8
2 1 1 8 1 1
3 2 4 2


OUTPUT:
6
6
3 2
3 1
2 1
2 2
3 2
4 2

Poti sa faci Dijkstra cu heapuri sau cu un arbore de intervale. atunci iti va intra in timp.
mai poti sa faci si Bellman Ford cu coada. Despre
Dijkstra gasesti aici http://infoarena.ro/problema/dijkstra (unde poti sa te uiti la sursele celorlati concurenti, de exemplu pe cea a lui Filip: http://infoarena.ro/job_detail/153886?action=view-source).

Dijkstra cu heapuri suna cam asa:
vei tine un heap (http://en.wikipedia.org/wiki/Heap_%28data_structure%29) H in care vei avea distantele de la sursa la fiecare nod calculat pana la pasul curent (atentie, relatia de ordine trebuie sa fie key(A)<=key(B), pentru ca in varf sa ai minimul dintre toate elementele). cand vrei sa alegi minimul dintre distante nu trebuie decat sa iei nodul care se afla in varful heapului. cand reactualizezi distanta pentru un nod j, il scoti din heap si il reintroduci cu noua distanta. 

Multumesc mult pentru raspuns...mi-a iesit timpul in 7-8 sec pentru un test de 100x10. O sa mai il cizelez si sper sa imi dea in timp.Inca odata multumesc. Profesorul meu spunea totusi ca exita un algorimt care rezolva liniar....ceva gen 1 ms...aveti vro idee?

daca nu ai nici un obstacol, drumul tau o sa aibe costul nr1 * v1 + nr2 * v2 + ... +nr6 * v6, unde v1, v2, ..., v6 sunt valorile de pe cele 6 fete, iar nr1, nr2, ..., nr6 reprezinta numarul de patratele peste care au fost suprapuse respectivele fete. (nri poate sa fie si 0). probabil ca iese ceva din asta :)

Ca idee nu ar trebui sa ruleze atat de prost .... timpul mi se pare exagerat de mare... ai pus optimizarile de rigoare la compilator? Pt linux -O2 -static iar pt Dev C++ si visual trebuie sa fie o casuta prin optiuni.
          Cat despre timp liniar.. Problema se poate face cu 100 de liste.. Vectorul acestor liste este ciclic si lista i reprezinta nodurile cu costul 100 * k + i.. adica multiplu de 100 + i... Si se parcurg listele pana nu mai exista nici o imbunatatire, orice lista procesata este stearsa... Complexitatea este numarul de imbunatatiri care este maxim n * numarul de liste.. maxim 100.. deci complexitate liniara 100 * n.. Ca sa reduci constanta aia de 100 se poate face o structura binara.. adica un aib sau un aint sau un arbore echilibrat.. si are sa iti iasa O(n * log(100)).... Ca sa fie usor de implementat baga un set in loc de arborele echilibrat(set e arbore ros negru implementat direct in stl).Si ai posibilitatea sa folosesti lower_bound..
          In cazul in care nu am fost foarte clar cu explicatia de mai de sus.. Toata idee vine de la faptul ca daca tu vrei sa reactualizezi vecinii unui nod cu costul x tu sigur nu o sa ajungi la costuri mai mari decat 100 + x.... astfel poti sa impingi nodul nou in o lista cu pozitia costului nou si o sa il procesezi cand ajungi la lista aceasta... Dar listele sunt independente intre ele pe segmente de 100.. deci poti sa le refolosesti.
          P.S. pt complexitate liniara mai  poti sa vezi articolul cu nearest neighbour(al lui Mihai Patrascu) si il combini cu ideea de liste si cred ca ar trebui sa fi multumit cu asta

          Am vrut sa pun un link la articol dar nu il gasesc.. poti sa renunti la idee.. partea cu seturile pare super usor de implementat si cred ca aia ar fi cea mai buna solutie. Desi ideea lui Patrascu era faina sa o vezi. Daca cineva gaseste link sa il puna cu incredere sa se vada ideea

Articolul cui???

ce spunea marius mai sus este rezolvarea problemei Car (http://infoarena.ro/problema/car). un articol despre aceasta gasesti aici (http://infoarena.ro/preoni-2005/runda-2/solutii).


L.E.: problema a fost propusa de Cosmin Negruseri. nu stiu sa existe si un articol scris de Mihai Patrascu, deci cei care au aceasta informatie sunt rugati in continuare sa posteze linkul :D

ideea de care zice marius a fost prezentata de mihai patrascu la conferinta de la unibuc. sunt totusi curios daca marius ar implementa chestia aia?? tin minte ca si mie mi s-a parut destul de marfa ideea, dar nu prea m-as grabi sa implementez asa ceva.

           De implementat chestia aia cu nearest neighbour nu as implementao cat timp e o solutie mai usor de implementat cu aceeasi complexitate. Dar vroiam ideea sa se vada ca era super tare. Ma rog.. As vrea sa imi cer scuze, nu stiam ca este problema asta propusa deja... Eu am auzit de ideea asta la o pregatire si nu stiam ca a fost propusa la un concurs.