infoarena

Aici puteți pune întrebări legate de concursul Happy Birthday Infoarena 2014 (http://www.infoarena.ro/happy-birthday-infoarena-2014)!

La problema Ciclu2, un nod se afla intr-un ciclu de lungime 1 daca si numai daca exista o muchie de la el la el insusi?

DA

La ciclu2 care este numarul maxim de intrebari / test?

Numarul maxim de intrebari este 10. Am adaugat restrictia in enunt. Multumim pentru sesizare.

Ciclu2: Puteti sa definiti, va rog, un ciclu simplu? Nu mi-e clar raspunsul la a doua intrebare.

@PlayLikeNeverB4 O muchie nu apare de 2 ori in ciclu.

@Sarac Sau Rege: in ce interval se incadreaza numerele din secventa?

[1,10^9]

Se poate ca intre doua noduri sa existe mai mult de o muchie?

NU

Acel moment cand back-ul merge mai repede ca solutia legit. #ciclu2

Unul din motivele pentru care problema asta nu a fost data intr-un concurs oficial.

La Prefix2
"aaba -> a, b, aa, ab, ba, aab, aba, aaba -> 7"
Sunt 8 acolo, nu 7

Putem afla motivul pentru care PscPld2D nu a fost propusa nicaieri? :)

A fost data la ceva olimpiada straina si a fost explicata la finala Algoritmiadei 2013.

La problema bunicu, numerele in baza 2 sunt date in ordine crescatoare?

@Ozturk Arif: Daca nu se precizeaza atunci nu. (Asta e presupunerea pe care o poti face in general)

La Sarac sau Rege nu e O(n * log VMAX + m) timpul?

P.S.: La acest concurs e incurajata colaborarea intre participanti?

Parerea mea, care se aplica la orice concurs in rulare in general, e ca nu ar trebui sa va spuneti unul altuia solutiile. In felul asta nu castiga niciunul din voi absolut nimic (decat puncte in clasament si sa fim sinceri nu cred ca niste puncte schimba cat sunteti de destepti).

Desi pentru acest concurs mi se pare ok (cel putin la problema kthvalue) ca 2 oameni care nu au rezolvat inca o problema sa-si expuna ideile si sa deduca cum s-ar putea rezolva. Din nou insa, nu sa se dea solutia direct.

Restul comisiei nu stiu ce parere are. Craciun fericit!  :)

Sirurile sunt date in ordine aleatoare.


Nu, complexitatea dorita este O(n log n + m).

Lol, nu ma bagati in seama. VMAX e defapt lungimea maxima a intervalelor, care = n.  :aha:

La problema prefix2 complexitatea optima nu este O(NlogN)?

Defapt e O(N log sigma). Am lasat limita de timp de 3 ori mai larga. Problema cu suffix array e ca sunt destul de incete. Radix sort defapt nu aduce nicio imbunatatire din cauza constantei. Deocamdata un singur om a rezolvat problema cu suffix array.

Ok. Mulțumesc pentru răspuns.

Asa pe final. As vrea sa vad kth value mai facuta asa ca uitati un hint. Complexitatea solutiei este O(N log N)

La PscPld2D, nu sunt doar 24 de submatrici palindromice?

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

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

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

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.

De fapt, aia de pe codechef e mai usoara aparent :)

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

Cand adaugati problemele in arhiva?  :banana:

Done

Se va posta si articolul cu solutii ?  :D :D

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

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.