infoarena

Aici puteţi discuta despre problema Iepuri (http://infoarena.ro/problema/iepuri).

Care e algoritmul de ridicare la putere in timp logaritmic al unei matrice?
Spune-mi si mie, te rog, numele. Sa stiu ce caut, ca pana acum nu l-am gasit pe nicaieri.

Multumesc!

Pai nu e valabil doar la matrici :). E foarte simplu:

Ca sa calculezi a^100, inmultesti a^99 cu a sau a^50 cu a^50 sau orice alta combinatie. Daca a este numar, nu prea conteaza ce alegi, fiindca dimensiunea lui a creste cu exponentul, dar daca dimensiunea lui a nu depinde de exponent cel mai bine e a^50 * a^50.

Sau a^64 * a^32 * a^4. Deci pe a^100 il gasesti din 2 inmultiri si inca 6 [ca sa gasesti a^64]. Deci 9 in total. Daca tot inmulteai cu a, il gaseai dupa 99 de inmultiri.

Calculeaza A, A^2, A^4, ... etc., fiecare ridicand-o la patrat pe precedenta. Inmulteste astea in functie de descompunerea binara a exponentului. ex: A ^ 14.

14 = 1110 = 2 ^ 3 + 2 ^ 2 + 2 ^ 1, deci A ^ 14 = A ^ 8 * A ^ 4 * A ^ 2.

Bafta.

Ce spune greco se poate rezuma la definitia recursiva a puterii:
     
A^B = A^(B-1) daca B este impar
si
A^B = (A^(B div 2))*(A^(B div 2)) daca B este par (si aici daca il memoram pe A^(B div 2) si nu-l calculam de doua ori obtinem timp logaritmic)

Silviu

bineinteles, algoritmul functioneaza pentru orice operatie asociativa.

Multumesc pt ajutor. Merge acum.

Am si eu o mare dilema la problema asta...

Am facut prima oara cu matrici si am luat 0 (Raspuns gresit la toate). Apoi am incercat sa testez rezolvarea cu matrici folosind inca o rezolvare, cu forta bruta. Imi mergeau toate testele, asa ca m-am hotarat sa trimit varianta cu forta bruta sa vad cate puncte obtin: tot 0. NU inteleg ce se intampla, am pus peste tot '\n',nu pun spatii aiurea, deci nu vad unde ar fi problema!!
Am folosit si faza cu "%"...


Va rog sa ma ajutati ca mai e o luna pana la bac si eu fac Iepuri de 2 zile

 ](*,) ...

Vezi ca sunt mai multe teste intr-un fisier, sigur reintializezi variabilele dupa fiecare test?

Eu acuma trec a 11-a asa ca nu stiu matrici. Ma gandeam daca se poate rezolva gasind forma generala a termenului l[n] in functie de l[0],l[1] si l[2]. Eu am calculat cateva l

• dar nu observ nici o forma generala. Intrebarea mea este: are rost sa mai caut forma generala sau nu se poate decat cu matrici?  :-k

Nu cred ca poti face logaritmic fara matrici ... liniar rezolvi cu recurenta de ordinu 2. Ca sa gasesti formula generala a unei recurente de ordinu 2 parca tot prin a 11-a se facea. Vezi aici de recurente liniare http://mathworld.wolfram.com/LinearRecurrenceEquation.html , dar chestia asta nu te prea ajuta pentru ca trebuie sa ridici numere reale la puteri mari si pierzi precizie. Dar oricum inmultirea unei matrici nu e chestie complicata, ai putea lua un manual si sa te uiti pe acolo ce se intampla.

Care e smecheria cu inmultirea de matrice? Ca nu ma prind deloc.

cauta intrun manual de clasa a 11-a. Eu acolo am gasit si e destul de simplu de inteles cum se inmultesc 2 matrici.

stiu sa inmultesc matrici, dar nu-mi dau seama cum sa folosesc treaba asta in problema

Citeste articolul cu solutia problemei :
http://info.devnet.ro/articole.php?page=art&art=40&artpage=1

spor la implementat :)

merci mult. n-am stiut ca e de la preONI.

Nu-si gaseste careva 2 minute libere sa explice faza cu inmultirea unei matrici, sau whatever ai nevoie sa rezolvi asta de 100? Cred ca i-ar ajuta si pe altii. Multumesc.

Pare destul de bine explicat in articol (http://infoarena.ro/preoni-2005/runda-1/solutii).
Inmultind matricea respectiva M cu matricea cu o singura coloana (I_n,I_n+1,I_n+2) va rezulta chiar matricea cu o singura coloana (I_n+1,I_n+2,I_n+3). Prin inductie se poate demonstra ca Mⁿ * (I₀,I₁,I₂) = (I_n,I_n+1,I_n+2).

Sunt cateva notiuni elementare de matematica de clasa a 11-a legate de matrici pe care trebuie sa le cunosti pentru a rezolva aceasta problema. Citeste in Cormen la capitolul cu matrici cum se inmultesc, apoi consulta articolul cum a spus si ditzone mai sus si nu ar trebui sa ai probleme in a intelege rezolvarea. Bafta!

La problema asta, am declarat toate variabilele de tip long long unsigned, si luam KBS 11 pe toate testele. Dupa ce am declarat long long [fara unsigned] am luat 100. Faza era, ca pe a doua si a treia linie din matricea finala, imi apareau elemente negative, din cauza faptului k atunci knd efectuam inmultirele intre doua numere mai mari, imi depasea long long`ul kiar daca aplicam operatia modulo 666013. Acest lucru e normal sau e din cauza algoritmului meu?  ???

Nu cred ca ar trebui sa iti apara valori negative :wink: , ai grija la operatia de modulo.

legat de permiterea vizualizarii surselor altora a dus la multi in furt

adik dalalau alexandru mie coleg de scoala este la acelasi profil ca si mine si sunt 100% sigur ca nu are cunostinte destule pentru a rezolva de 100p problema iepuri care a fost data la preoni2005 runda 1 la clasele 11-12

nu mi se pare corect ca altii sa ma intreacs in clasamentul arhivei doar pentru k dau si ei copy paste.

multumesc

Ti-ai raspuns singur la nemultumirea ta: clasamentul arhivei nu este relevant in conditiile in care unele surse sunt publice. :) Si gandeste-te ca 100 de probleme grele rezolvate nu se compara cu 100 de probleme usoare rezolvate si, implicit, acelasi loc in clasament. Asa ca nu e un motiv intemeiat de nemultumire. Daca vrei o masurare de forte, aveti destule probleme nepublice pe care sa le incercati.

Salut ! Am citit articolul cu solutii si am probleme la implemantare...

Am construit M[3][3]:

si a[3][1]

In matricea c[3][1] vreau sa obtin

Produsul il calculez asa:



Insa c[3][1] nu arata bine. Cred ca gresesc la calcularea produsului...Putin ajutor ? :|

Ai pus dimensiunile gresit. In primul rand, nu mergi pana la N, ci pana la 3 (dimensiunea matricii), iar in al doilea rand, j poate lua doar valoarea 0 (a[...][1] iese din matrice dupa cum l-ai definit tu). Intai trebuie ridicata matricea M la puterea N (sa o inmultesti cu ea insasi de N ori sau, ca sa intre in timp, sa faci asta logaritmic), iar abea apoi inmultesti cu acel "a".

PS: Problema asta cere niste cunostinte putin mai avansate de matematica (cam clasa a 11-a, dar poate inveti mai repede). Cred ca din acest motiv nu ai inteles pe deplin rezolvarea problemei sau de ce este corecta metoda.

Am ridicat la putere logaritmic astfel:


Apeland apoi:


Insa matricea mea in loc sa fie:

0 1 0
0 0 1
1 1 1

Este:
0 1 0
0 0 1
0 0 0

1^5==1 , de ce apare 0 ?  :'(

Cum zicea si sima_cotizo mai devreme problema asta necesita niste cunostinte elementare a matricelor de clasa a 11-a. Ridicarea la putere a unei matrice nu inseamna ridicarea la putere a fiecarui element, ci inmultirea ei cu ea insasi de N ori, iar inmultirea a 2 matrice e putin mai complicata decat suna. Motiv pentru care e mai sanatos sa lasi problema asta pentru mai tarziu, ca sa inveti ceva din ea

Salut!
Ce este special la testul 10 de il pic?
M-au uitat si pe sursele utilizatorilor care au luat 100 si nu imi dau seama unde pierde codul meu timp de executie.

Incearca sa pui k, i, j in loc de i, j, k atunci cand inmultesti matricile. Adica pune al treilea for inaintea primului.

Pana la urma problema era la:
 
   for(i=0;(1<<i)<=N-2;i++)

N fiind long long a trebuit sa scriu:
   
   for(i=0;(1LL<<i)<=N-2;i++)

Si am luat 100.

fara long long se ia 0 puncte?

fatall error

Nasoala chestia cu 1LL << i in loc de 1 << i. ](*,)