Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 839. Optimal Marks  (Citit de 12988 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Decembrie 12, 2007, 16:00:39 »

http://www.spoj.pl/problems/OPTM/

Ce se cere e mark[x1] ^ mark[y1] + mark[x2] ^ mark[y2] + ... minima. Cum ^ se face la nivel de bit, rezolvand suma anterioara pentru fiecare bit obtin rezultatul optim. Ce nu stiu e cum sa rezolv mark[x1'] ^ mark[y1'] + mark[x2'] ^ mark[y2'] + ... unde elementele pot lua valorile 0, 1, unele fiind fixate, si suma sa fie minima ?
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #1 : Decembrie 12, 2007, 18:08:54 »

Problema la care ai redus-o se poate rezolva determinand o taietura minima (http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem) intr-un graf. Sper sa-ti fie de folos acest hint Smile
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #2 : Decembrie 13, 2007, 19:24:05 »

Ai zis prea mult. Tongue
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
mariusdrg
Client obisnuit
**

Karma: 70
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #3 : Februarie 10, 2009, 18:32:09 »

A implementat cineva solutia aceasta la problema(flux)? Implementarea mea ia tle... si pe calculatorul meu nu merge decat pana la vreo 200 de noduri in 6 secunde... deci diferenta e destul de mare.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #4 : Februarie 10, 2009, 22:30:26 »

Mie îmi merge în 0.31s.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
mariusdrg
Client obisnuit
**

Karma: 70
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #5 : Februarie 10, 2009, 22:32:46 »

Cu flux normal .. adica nimic special ?adica cu edmonds karp? Shocked.. Mersi fain , am sa mai incerc atunci si maine sa mai implementez o data.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #6 : Februarie 11, 2009, 12:17:40 »

Da, cu algoritmul lui Edmonds Karp.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines