748 Toys

[•DITzoneC]

Aici puteţi discuta despre problema Toys.

[•anna_bozianu]

Va rog sa imi clarificati si mie cateva nelamuriri legate de enuntul problemei toys.

1. Care este considerat momentul 0?
     a ) momentul in care primim configuratia.
     b ) momentul in care s-a luat prima jucarie din camera luand in consideratie atat copii care duc o jucarie cat si pe cei care au dus deja o jucarie
     c) momentul in care a luat jucaria copilul care cara o jucarie si este cel mai aproape de camera in momentul primirii configuratiei.


2. Cate jucarii sunt in sufragerie la momentul primirii configuratiei?
    a ) M jucarii
    b ) M-N jucarii deoarece fiecare copil a luat deja cate o jucarie pe care a dus-o sau urmeaza sa o duca in camera.
    c ) M-K unde K= numarul de copii care se indreapta spre camera cu o jucarie in mana.

3. ( stupid question ) Gigel cara jucarii ?

[•stef2n]

Imi cer scuze ca nu am timp sa recitesc problema si sa te lamuresc, dar stiu ca si eu am avut ceva neclaritati la momentul ei si o precizare a lui ditzone m-a lamurit: http://forum.portal.edu.ro/index.php?showtopic=62740&view=findpost&p=529784

[•anna_bozianu]

Am inteles ca problema se reduce la determinarea unui element dintr-un sir atunci cand este cunoscuta poz = pozitia sa dupa sortare. Exista pentru aceasta problema un algoritm liniar?
Eu pierd un singur test ( testul 9 ) pe care obtin TLE. Am incercat in trei moduri.
 I. Sortez sirul (heap-sort)
 II. Construiesc un maxheap din primele poz elemente pe care il updatez daca e cazul cu celelalte.
      (aici am incercat sa folosesc si minheap in cazul in care poz > n/2 )
 III. Consider val = prima valoare din sir. Mut in alt sir elementele strict mai mari, pastrez in sir elementele strict mai mici contorizand cate am mai mari si cate am mai mici. Pe cele egale le ignor dar stiu ca egale=toate-mici-mari.
      Dupa ce fac parcurgerea am trei variante.
      a) poz<=mici Atunci reiau rationamentul pe sirul celor mici.
      b) mici < poz <= mici + egale Atunci problema e rezolvata
      c) poz > mici + egale. Atunci reiau rationamentul pe sirul celor mari micsorand poz cu mici + egale.


Exista ceva mai eficient. Daca da pls, teach me. 

P.S. 10x Stefan.

[•stef2n]

Cea mai buna rezolvare este cu statistici de ordine (vezi Cormen): pe cazul mediu este liniar, pe cel mai defavorabil tot N * log N (dar un algoritm randomizat nu prea atinge cazul asta). Pe scurt, te folosesti de functia de partitionare de la quicksort.

[•pauldb]

Exista si functia in STL pentru asta: nth_element().

[•anna_bozianu]

Am incercat si cu functia nth_element(). Din pacate testul 9 tot TLE da.

[•alex_unix]

Deci avem 5 copii si 100 de jucarii ramase in camera lui Gigel. Holul ce trebuie parcurs are lungimea 101. Copii sunt asa :

1 : d = 84 si t = 1, inseamna ca va lasa jucaria in camera in 101 - 84 timp, si se va intoarce sa ia una noua dupa ce parcurge holul inapoi, adica 17 + 101 = 118
2 : d = 56 si t = 1, deci lasa jucaria in camera in 101 - 56 si apoi se intoarce in sufragerie. 45 + 101 = 146
3 : d = 43, t = 0, ia alta jucarie din sufragerie in 43
4 : d = 65, t = 0, ia alta jucarie din sufragerie in 65
5 : d = 2, t = 1, ajunge in camera in 99 si se intoarce in 101 => 200

M-am gandit ca solutia reprezinta timpul in care este adusa a 100-a jucarie. Fiecare aduce pe rand cate o jucarie, in ordinea distantei calculate anterior. Cum 100 % 5 e 0, am dedus ca cel numerotat cu 5 va aduce ultima jucarie (adica ultimul in ordinea distantelor). Fiecare a carat 20 de jucarii, deci el va parcurge de 19 ori holul dus-intors si o data dus.
200 + 20 * 202 - 101 (drumul de intoarcere dupa ultima jucarie nu il mai pun) = 4139 
Va rog frumos, poate cineva sa imi dea un hint unde gresesc ? 

L.E. Data viitoare ma dau cu capu' de un perete inainte sa pun o intrebare pe forum  . Enuntul este formulat destul de clar, nu am fost eu atent
Doar in cazul in care cineva va mai avea neclaritatile mele : copilul 1 duce ultima jucarie in camera in 185 + 20 * 202 - 101 = 4124

[•lucky1992]

Buna seara! Poate sa-mi spuna si mie cineva de ce nu imi intra in timp la testele 8 si 9. Am folosit atat nth_element cat si implentarea manuala si tot nu intra in timp. Va multumesc!

[•visanr]

Incearca sa lucrezi cat mai mult cu int, din cate vad ai long long cam peste tot si asta incetineste foarte mult.

[•lucky1992]

Am inlocuit cat se putea long long cu int, iar pt. inmultirea cu nr.mari faceam unde trebuia cast la long long. Imi trece testul 8, dar la 9 tot nu imi intra in timp. S-ar putea sa fie din cauza functiei nth_element ?

[•visanr]

Nu e din cauza functiei nth_element, asa fac si eu. Eu pun long long la variabila unde tin raspunsul, in rest am int.

[•lucky1992]

Asa am facut si eu printre primele variante: aveam o singura variabila de tip long long in care puneam raspunsul. Din pacat imi dadea 30 pct.( dar totusi imi intra in timp la testul 9    ). Apoi cand faceam X,Y,Z si V long long ( sau le lasam int si faceam cast la long long ) imi treceau toate testele mai putin 9. Deja sunt confuz pt. ca algoritmul eu cred ca il gandesc corect, insa ma cam bat tipurile de date folosite  .

[•marius135]

  Am marit un pic limita de timp sper sa nu mai fie probleme cu testele 8-9.