063 Bombar

[•domino]

Aici puteţi discuta despre problema Bombar.

[•wefgef]

daca am o recurenta de grad 2, cum scot formula?

[•domino]

Nu este nici o formula (cel putin nu cred eu). Daca ai probleme cu limita de timp, atunci incearca sa rezolvi problema "Iepuri" (daca nu stii s-o rezolvi gasesti un articol cu solutia sa pe info.devnet.ro)

[•Cosmin]

E formula de genu a*x^n + b*y^n unde x si y sunt irationale ... deci formula nu te prea ajuta.

[•Cosmin]

Daca vrei sa vezi cum se deduce formula pentru recurente de gradul doi te poti uita aici: http://mathworld.wolfram.com/LinearRecurrenceEquation.html

[•filipb]

Problema cere determinarea nr. de arbori partiali ai unui graf scara cu N noduri pe fiecare rand.. Formula foloseste si numere irationale...
  Da, merge ca in "iepuri" ( pe care inca nu am apucat sa o implementez k lumea  ). Cu ridicarea la putere in timp logaritmic a unei matrici de genu din "iepuri"

                                                                  bubbleSORT

[•Cosmin]

Tu repeti ce s-a zis mai sus sau mi se pare mie? Ori ai gasit acuma problema in Tomescu si nu vezi ca solutia se bazeaza pe rezolvarea unei recurente de gradul 2, adica ce am zis io mai sus ... Si despre iepuri a zis domino in primul post ...

[•filipb]

Ei na... MS MULT! Eu am implementat recurenta ( pe numere mari ) si mi-a luat doar primele 4 teste, la restu' Time Limit Exceeded! Probabil trebuia sa folosesc o baza mai mare... (10000?) O stiam de mult. Si ce? Multe probleme date la baraje si la nationale (chiar si anu asta) sunt din Tomescu.... SI CE?

[•domino]

Ei na... MS MULT! Eu am implementat recurenta ( pe numere mari ) si mi-a luat doar primele 4 teste, la restu' Time Limit Exceeded! Probabil trebuia sa folosesc o baza mai mare... (10000?) O stiam de mult. Si ce? Multe probleme date la baraje si la nationale (chiar si anu asta) sunt din Tomescu.... SI CE?

 
N-ai inteles despre ce e vorba.. ti s-a zis doar ca post-ul tau nu zicea nimic nou fata de ce se zisese deja inainte, asa ca inainte sa post-ezi ceva citeste ce s-a scris deja. Cat despre Tomescu, n-a zis nimeni ca e rau sau ceva de genul, poate chiar o sa facem un articol pe baza problemelor de acolo....  

[•wefgef]

ms mult. am invatat si eu cum sa ridic la putere o matrice in timp logaritmic, doar k am probleme cu implementarea operatiilor pe numere mari.  :cry:

[cristi8]

cum se conjuga verbul "a coace" la perfectul simplu?

eu copsei
tu copseişi
el/ea coapse
noi copserăm
voi copserăţi
ei/ele copseră

[•Dorin]

am probleme cu implementarea operatiilor pe numere mari

citeste o carte  :lol: este una cu psihologia concursurilor de informatica are si operatii pe numere mari  
in legatura cu verbul la persoana a doua nu e  copsesi

[•wefgef]

am auzit de ea. e scrisa de francu, nu?

nu stie nimeni unde as putea-o gasi?

[•vladcyb1]

Da e buna cartea. Eu o am de la PACO. Dar de ce nu te uiti  la articole si o sa gasesti unul scris de domino, parca se numese "Multe shmenuri in C++" si acolo prezinta operatii pe numere mari, idei de la Radu Berinde. E bun articolul !  

[•gogu]

Pentru cei care nu au reusit sa implementeze o ridicare la putere in timp logaritmic, garantez ca merge o implementare directa a recurentei de gradul 2.
Totusi, ca sa intre in timp trebuie sa faci mai multe optimizari la operatiile pe numere mari (de exemplu, folosirea unei baze cat mai mari, cam 10^8, si cand reactualizezi numarul, incearca sa nu faci impartiri).
Asa poti sa intri in 0.5 secunde pe orice test.
Nu ar trebui sa nu merga, pentru ca asimptotic, daca nu folosesti un algoritm  super avansat de inmultire, ca Karatsuba sau FFT, tot O(N^2) ai complexitate.

[•vladcyb1]

Cum ai reusit tu sa implementezi recurentza direct ? Pt n=20000 numaul are cam 1400*9 de cifre daca faci in baza 1 miliard.
 
 Programul arata cam asa:
 for i:=3 to n do v:=numere mari (O(1400))

 => 28 milioane de operatii

 Ziceai de optimizari... Ce optimizari ca nu fac impartiri nimic, doar o adunare pe numere mari...

   

[•gogu]

Vorbeam de impartirile care trebuie sa le faci atunci cand reactualizezi numarul tau mare. O impartire se face de 10 ori mai incet decat o adunare sau inmultire pe numere intregi (e ceva de procesor, nu stiu de ce).
Uite bucata esentiala din sursa mea:

Cod:

procedure calc(var a,b,c:numar);
var i:longint;
begin
for i:=1 to b[0] do c[i]:=x*b[i]-y*a[i]; {recurenta, dar nu zic x si y}
c[0]:=b[0];
for i:=1 to c[0] do
 begin
 while c[i]>=base do
               begin
               inc(c[i+1]);
               dec(c[i],base);
               end;
 if (c[i]<0) then
             begin
             inc(c[i],base);
             dec(c[i+1]);
             end;
 end;
if c[c[0]+1]>0 then inc(c[0]);
end;

Chiar daca e in pascal, cu cateva mici trucuri, sursa imi merge in 0.3 secunde pentru n=20.000.

[•vladcyb1]

 Ma... Tu sigur nu ai facut ceva descantece la liniile alea de cod ? Exact la fel fac si eu, chiar redusesem la un singur for procedura si luam TLE... Am inlocuit cu liniile tale si timpul e sub 0.6...      

[•gogu]

Am irosit cateva ore din viata mea pentru a ajunge la codul asta. E ce se intampla cand esti in vacanta la tara si te plictisesti rau de tot .  

[•wefgef]

si eu cred ca a facut descantece

[•crus]

nu prea ma prind ce e pe aici:
pentru
n=4 va da 54
n=5 va da 189?

[•freak93]

Mie pentru 4 imi da 58 si pentru 5 imi da 229
Imi poate spune cineva daca sunt corecte si acestea si urmatoarele:

Cod:

16->954437182
235-> 67746279303732470299079800993775310454613674971028019766908788186314490859803941408868095282875861796837441649610812260296869722067770248839

Multumesc anticipat!

Foloseste tag-ul [ code ] [/ code ] cand postezi teste.

[•savim]

Mie imi da asa (cu sursa de 100) :

Cod:

16 -> 408855776
235 -> 73804534825890393758958534554281659036254934031449983136927666079997660107220317885305632560044534873988231090645656846779386438574191

Apropo, pentru 4 trebuie sa dea 56 iar pentru 5 raspunsul este 209.

Spor la treaba!

Foloseste tag-ul [ code ] [/ code ] cand postezi teste.

[•freak93]

Ms pentru raspuns. Am luat 100, se pare ca gresisem recurenta.