Happy Birthday Infoarena 2014

[•pepsiM4A1]

La PscPld2D, nu sunt doar 24 de submatrici palindromice?

[•SebiSebi]

Sunt 25 de matrici palindrom 1x1, o matrice 3x3 si una 5x5.

[•Kira96]

Ne-am plans ca romanii fura probleme, dar aparent si indienii fac asta, avem spioni pe infoarena? 
http://www.codechef.com/JAN15/problems/XRQRS
http://www.infoarena.ro/problema/kthvalue

[•florin.elfus]

Indienii au luat meditatii de la romani, care sunt recunoscuti pe plan mondial, la furat de probleme 

[•freak93]

Soluție trebuie modificata foarte puțin pentru problema de la codechef . O sa mai aștept pana pun soluția la kthvalue sa se termine runda de codechef.

[•Kira96]

De fapt, aia de pe codechef e mai usoara aparent

[•freak93]

De fapt, sunt la fel . Variatii foarte mici ale aceleiasi structuri, si cea de pe codechef, si kthvalue.

[•Kira96]

Cand adaugati problemele in arhiva? 

[•freak93]

Done

[•xtreme77]

Se va posta si articolul cu solutii ? 

[•CosminRusu]

Se va posta si articolul cu solutii ? 

Chiar asa, as fi si eu foarte curios de solutia la Kthvalue.

[•Kira96]

Ok, o sa pun aici solutia la kthvalue cu alb, pentru cei ce nu doresc spoiler.


In primul rand sa consideram posibile doar urmatoarele operatii: se adauga la sfarsit un element, se sterge ultimul element, query l,r,k
sa se afle al klea element din intervalul [l,r]. Problema asta se poate rezolva in MlogN, unde M=numarul de operatii si N=valoarea maxima a unui numar. Puteam stoca intr-o trie, dupa x adaugari sa zicem, toate cele x numere adaugate (tria va avea doar 0 si 1, daca nu stiti cum faceti asta, cititi problema xormax ). Acum, daca am putea mentine cate o trie pentru starea sirului de numere dupa x adaugari, adica o trie pentru fiecare prefix al sirului, problema ar fi rezolvata : parcurgem simultan tria pentru prefixul [1,r] si cea pentru prefixul [1,l-1] si daca scadem din frecventa primei trii, pe cea a celei de-a 2a aflam practic cum arata tria pentru intervalul [l,r]. Acum, putem sa facem un "dfs" simultan pe cele 2 trii si vedem daca mergem pe ramura cu bitul 0 sau cu bitul 1. Acum, la problema noastra trebuie sa facem cateva modificari. Poate se realizeaza mai usor dar o sa va zic cum am facut eu :
Mentinem 2 astfel de trii, una pentru adaugari in fata, cealalta pentru adaugari in spate. Problema s-ar pune atunci cand stergem un element dintr-o parte si acea trie e deja goala, dar cand intervine acest caz "resetam" tria cu numarul 0 din partea opusa, adica incrementam ordinul triei considerate 0.In fine, destul de smechera problema, GG propunatorilor.