Exista cumva vreo rezolvare oficiala a acestei probleme (am vazut ca exista o rubrica de solutii pentru runda 10 din 2012, dar nu e completata)? Altfel, ar fi util un indiciu, daca se poate.

Claudiu

Articolul din link-ul cu PDF-ul postat contine in a doua parte (pagina 4 din PDF) un algoritm dedicat pentru matrix chain multiplication. Autoarea pretinde ca ar fi n^2, dupa cum am zis in post-ul precedent. Ideea se bazeaza pe echivalenta problemelor matrix chain multiplication si minimum weight polygon triangulation. Echivalenta dintre aceste doua probleme, ca fapt divers, este prezentata ca un excercitiu si in cartea de probleme a lui Ioan Tomescu (aia din care tot se dadeau mai demult probleme la ONI).

Dupa cum am zis, am incercat sa urmaresc algortimul dedicat dar m-am impotmolit pe exemple.

PS: Algoritmul state-of-the-art pentru matrix chain multiplication cica ar fi asta: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf , care e in n log n. Din cate am observat e citat intr-o sumedenie de alte articole si ma mira ca nu e explicat nicaieri mai in detaliu (chiar si intr-un curs avansat). N-am stat sa-l diger insa, din moment ce sunt prea varza sa-l pricep macar pe cel in O(n^2)

PPS: Petru, am presupus ca macar prima parte din post-ul tau a fost legat de ce am scris eu mai sus .

Salut,

Problema asta cica ar avea o rezolvare in n log n (sau n^2), conform mai multor surse. Cea mai relevanta e asta(0). Am incercat sa urmaresc algoritmul din articol si sa-l aplic manual pe niste exemple (exemplul din articol, precum si exemplul de la problema actuala si testul 2 din atasamente; le-am ales pe astea ca sunt simple si pot fi parcurse manual). Nu am putut sa duc pana la capat algoritmul, in sensul ca explicatiile date de autoare sunt pe alocuri insufieciente, cel putin pentru mine. Poate cineva are mai multa sclipire decat mine.

E destul de greu de gasit pe net orice informatie despre metoda asta. Sunt curios daca articolul e gresit (s-a dovedit a fi incorect) sau daca exista alt motiv pentru care sunt informatii numai despre metoda clasica in n^3. Oricum interesant de dezbatut asta. Si ca tot veni vorba, poate si asta(1) e interesant/de folos cuiva.

Numai bine,
Claudiu

(0) http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/0603055.pdf
(1) http://codeforces.com/blog/entry/8219

Ca fapt divers, si problema Ksecv se poate face doar cu stiva. Nu e nevoie de deque pentru 100p.

Claudiu

Salut,

Ar fi util de mentionat si problema Avioane[0] in lista de aplicatii rezolvabile cu ajutorul unui deque.

Claudiu

• http://www.infoarena.ro/problema/avioane

Salut,

La problema asta am trimis la surse de mi s-a acrit, cu toate optimziarile la care m-am putut gandi:

- Algoritm O(n) (varianta cu determinat subsecventele de lungime L-1 si U) - bifat
- Citire parsata - bifat
- Hash de mana care e vizibil mult mai bun decat unoprdered_map/hash_map etc - bifat (desi sunt gata sa accept ca aici e posibil sa fie buba)

Recunosc ca deja a devenit extrem de frustranta problema asta. Am vazut ca multa lume s-a tot chinuit sa treaca de 80pct. Am vazut de asemenea ca s-a mentionat ca accesul la surse era la un moment dat liber. Daca nu mai e cazul, e dispus cineva sa-mi dea un hint despre cum se poate face problema asta de 100? Chiar am ajuns intr-un punct mort si as fi extrem de recunoscator pentru putin ajutor.

Claudiu

Problema asta ar trebui data ca un exemplu graitor pentru articolul asta:

https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

Un brute cu 2 optimziari interesante scoate timpi semnificativ mai mici decat multe implementari ale solutiei oficiale:

1)

Asta (good):

Cod:

if (sum > flMaxBalans * r * c)
{
    flMaxBalans = (double)sum / (r*c);
}

versus asta (bad):

Cod:

flMaxBalans = max(flMaxBalans, (double)sum / (r*c));

Mi s-a injumatatit timpul de executie cu "optimizarea" asta.

2) Mai putin spectaculoas, a fost sa ma joc cu indicii buclelor. In final mi-a mai scazut timpul de executie pe cel mai greu test cu inca vreo 500ms.

Destul de interesant. Poate ajuta pe cineva...

Claudiu

Regarding 7)

I think we can do it in O(n): We start with a list of n candidates (each person is initially considered as a candidate). We take the first person from the list and do the following:

1) If x (the current person considered) knows y (the next person in the list) then x cannot be a celebrity and we move to y as the next person considered and take y from the list.

2) If x doesn't know y then y cannot possibly be a celebrity so we remove y from the list and continue with step 1) with the next person in the list z.

At the end of this process we will be left with an empty list and a single candidate. For that candidate we check that indeed everybody knows him and that he knows nobody.

Overall number of queries should: N (for the initial steps 1-2) + 2*N (for the last verification step).

And because there are sqrt(n) batches the cost is O(n*sqrt(n)) for the overall preprocessing and for the queries it's sqrt(n) per query since we only need to go through at most sqrt(n) individual update ops before we reach a known "check point" and the the actual value. So overall O(n*sqrt(n) + n*sqrt(n)) = O(n*sqrt(n))...I get it now. Nice problem.

That's pretty neat! Unless I miss my guess this idea has the down side that at one point the lists could, depending on the updates, degenerate into single numbers. But if we work only with batches of sqrt(n) that won't be a problem. Have I understood?

Thanks for the extra hint. From your method I'm assuming that by using ranges (I'll think about how to do that) I can get a linear time instead of quadratic (the "k updates in O(k^2 + n) time" part of your post sort of suggests the contrary). FWIW I was thinking there might be some range related idea to reducing the complexity, but I couldn't figure it out. I'll follow up when I have it solved (unless someone beats me to it).

[Bringing the discussion back to an earlier problem]

After some thinking on this problem I'm still a puzzled how one can beat the worst case O(n^2) for the range reverse/point query problem Cosmin posted earlier. I figured out how you can step through the queries backwards and find what the value at a certain index is in O(how_many_updates_were made). So if we split the operations in batches of sqrt(n), in every batch an query could be answered in at most O(sqrt(n)). Problem is, I can't see how to efficiently precompute, for every batch of size sqrt(n), the cumulative effect of the updates in that batch. I'm thinking this is necessary, since otherwise you end up having O(n) for every query. Anyway, if someone feels like posting any more hints, or just pointing me to the solution directly (publicly or in private), I'd be ever so grateful.

Thinking about this problem I'm still a bit stuck on how you can beat O(n) for the update operation. This is what I've understood so far (indexing from 0):
- reverse(i,j): reverses the order of elements in the interval [i,j]. Ex: A = [1,2,3,4,5,6,7], and reverse(1,4) yields [1,5,4,3,2,6,7]
- query(i): returns the value of A. Ex: Ex: A = [1,2,3,4,5,6,7], query(2) yields 3

My dilemma is that even if I'd split the updates/queries in batches of sqrt(n) just applying a reverse is (worst case) O(n). And as far as I can see reverse operation results depend on previous reverse operation results. Also as far as I could tell the order of reverse operations affects the overall state of A. Any more hints on this, please?

Cosmin,

Any hint on the problem with the reverse and get operations? I'm thinking it could be done with an interval tree (similar to how other problems like the maximum sub-sequence per interval) are done, but I having trouble figuring out how the update can be done on the interval in less than O(n) time.

[Addressing the second problem in the second set]

My idea is rather simplistic: find the maximum number of the form 10^x <= n!. We can apply log10 to either side and get something like x <= log10(n!). Expanding this we get x <= log10(1) + log10(2) + ... + log10(n). Playing around with  a small program (http://codepad.org/IwdMLjcr) I noticed the result seems to be always something like floor(log10(1) + log10(2) + ... + log10(n)) + 1 I don't have any proof correctness on this but it seems to work . Am I at least close?

[Addressing the 1st problem in the second set]

My idea is to drop the first egg from a floor N (where 2<=N<=100) and see if it breaks. We have two possible outcomes:

a) The egg breaks at story N, so we have 1 egg left and we know that between 0 and N-1 it can either break or not. Since we only have 1 egg left we simply iterate through all N-1 stories and see where it breaks. Total drops is N in the worst case.
b) The egg does not break so we have we can apply the same scheme again considering story N+1 as our "base" level. So we just drop the egg again from the 2*N-how_many_times_weve_tried floor and apply case a) if it breaks or repeat b) if it does not.

The idea is that we always drop the egg from one story less than the previous try if it doesn't break during our previous attempt. Let's say we drop it from the 10th floor initially. If the egg doesn't break we drop it next time from the 19th, the next time from the 27th...etc. This works because if the egg should happen to break during one of our tries we only need N-(how_many_times_we_tried_before) steps to find out where the egg actually breaks with our second egg.
So for N=10, we can cover 10+9+...+2+1 = 55 floors like this. Now the trick is to find the smallest N for which we can cover 100 floors. So 1+2+..+N <= 100 => N*(N+1)/2 <= 100. Intuitively solving this I get N=14. So we need a minimum of 14 tries to cover all 100 stories (it actually covers 105).

Hope this is good...

Here's my idea for the case where the switch's state is initially known (off):

- The prisoners nominate one prisoner that will declare that all of them have visited the switch room
- Every prisoner except the nominated one follows these rules, when entering the switch room:
       a) If the prisoner has ever turned the switch off-to-on before he leaves the switch unchanged (in whatever state it was when he entered the room)
       b) If the switch is on, the prisoner leaves it unchanged.
       c) If the switch is off and the prisoner has never turned it off-to-on, the he turns it on and leaves.
- When the nominated enters the room he checks if the switch is off. If it is he does nothing and leaves. If it is on he turns it off and leaves. When the nominated prisoner has counted P-1 times that the switch was found in an on state he can declare that all prisoners have been to the switch room.

My idea is that each prisoner only turns the switch on once and only the nominated prisoner can switch it off.Thus the nominated prisoner can always be sure that when he finds the switch in an on state it was turned on by a different prisoner than the others before.

In mod normal nu ar trebui sa fie nici o problema chiar si intr-un program multi threaded. Cat timp instructiunile alea se executa in ordinea din exemplu in fiecare thread, nu prea vad cum ar putea a=b=0 la final. Macar una ar trebui sa fie diferita de 0. Dar daca compilatorul decide sa schimbe ordinea instructiunilor si sa ai ceva gen:

Cod:

{ X = Y = 0 }
parallel
  a := X
  Y := 1
and
  b := Y
  X := 1

atunci ajungi sa ai a=b=0. Bine, fara vreun motiv anume nu cerd ca se apuca compilatorul sa modifice arbitrar ordinea instructiunilor tale. Poate daca are impresia ca optimizeaza ceva (ordinea instructiunilor afecetaza viteza in functie de cati cicli de procesor dureaza fiecare instructiune, sau ceva de genul). Si cum nu prea are de unde sti ca afecteaza logica programului in multi threaded execution, posibil sa se intample, I don't know.

Just my 2 cents.

Hmm, tare faza cu random walk. Problema asta e legata cumva si de Gambler's ruin problem?

Hmm nu prea am generalizat foarte bine pentru ca in enunt era p nu 1/p probabilitatea. Dar putems a notam k = 1/p => p = 1/k si ajungem tot in generalizarea de mai sus.

Claudiu

[0.5612803]

Salut,

O sa incerc sa-mi dau si eu cu parerea (disclaimer: nu prea le am cu matematica dar mi s-a aprut interesanta problema, asa ca daca aberez grav va rog nu dati cu pietre prea tare). OK, prima mea idee a fost ca evenimentele (de a face stanga sau dreapta) sunt independente la momente Tx diferite. Adica daca faptul ca furnica a facut stanga sau dreapta la momentul T nu influenteaza probabilitatea ca furnica sa faca ori stanga ori dreapta la momentul T+1. Deci daca am dreptate atunci putem scrie ca probabilitatea ca furnica sa _nu_ moara la icneput este 1 - probabilitatea_de_a_merge_spre_stanga = 1 - 1/3. La momentul 1 presupunand ca furnica a facut dreapta probabilitatea de a nu muri va fi (1-1/3) * (1 - 1/3 * 1/3) sau (1-1/3) * (1-1/9). Am scos acel 1/9 gandindu-ma ca la momentul 1 probabilitatea sa moara este probabilitatea de a face doi pasi spre stanga. De aici probabilitatea sa _nu_ moara vine cam 1-1/(3^2). Inmultind si cu probabilitatea sa nu fi murit la momentul anterior da  (1-1/3) * (1 - 1/(3^2)). Presupunand ca nu s-a rupt filmul corectitudinii mele pana acuma m-am gandit sa generalizez asta si am scos ceva gen:

produs de la n=1 -> +oo din (1 - 1/3^n)

Presupunand din nou ca nu am aberat crunt pana aici, pana acuma a fost matematica destul de elementara (deci rusine sa-mi fie daca am facut praf). De aici incolo sa calculeze limita din produs infinit m-a depasit. Dar am stat ceva si am cautat pe net cum se calculeaza un produs infinit din ceva gen

1 - 1/x^n (sau 1 - 1/p^n in cazul nostru)

si am gasit asta http://mathworld.wolfram.com/TreeSearching.html?affilliate=1 unde pe la Flajolet and Richmond 1992 mentioneaza ceva ce seamana izbitor cu ce am gasit eu. Dupa cateva iteratii imi da ca probabilitatea la infinit ca furnica sa nu moara e ceva gen 0.5612803...

Nu sunt foarte convins ca n-am aberat crunt asa ca va rog sa ma corectati daca gresesc.

Cheers,
Claudiu

Salut,

Se mai pot lua 100p cu limita actuala de timp (poate s-a marit de cand a intrebat lumea desi ma indoiesc). Ideea e sa modifici putin Bellman Ford-ul sa iasa repede cand detecteaza ca exista un ciclu (fail fast). Iar cealalta idee sa sa faci cautarea binara sa inceapa de la o valoarea cat de cat apropiata de costum mediu minim (astfel incat sa faci cat mai putine apeluri catre Bellman Ford). Poti gasi o euristica ceva pentru valoarea de inceput. Eu asa am facut.

Sper sa ajute pe cineva indicatiile,
Claudiu

Scuze, aberam in post-ul anterior. Am inteles eronat ca operatia move inseamna mutarea unuei litere dintr-un cuvant...in acelasi cuvant (si nu din primul in al doilea cum tocmai mi-am dat seama). Astfel similitudinea dintre "ana" si "castane" ar fi 6, eliminand literele 'c', 'a', 's', 't' si 'e' din "castane" si adaugand un 'a'. In total 6 operatii, nu 4 cum credeam, deci nu merge.

Sorry de spam,
Claudiu

Salut,

Am si eu o 1 intrebare legate de problema:

In exemplul problemei nu merge si lantul "ana castane"? Similitudinea ar cam fi 4, eliminand literele 'c', 's', 't' si 'e' din "castane" si mutand 'a' la sfarsit. Sau gresesc la cum gandesc calcularea similitudinii.

Claudiu

Salut,

E interesant ca daca problema se rezolva utilizand algoritmul lui Kosaraju pentru determinarea componentelor tare conexe nu mai este nevoie si de o sortare topologica. Asta deoarece algoritmul lui Kosaraju da lista componentelor tare conexe sortata topologic deja (se poate vedea aici http://infoarena.ro/job_detail/662214, ca solutia merge comparabil o solutie bazata pe algoritmul lui Tarjan + o sortare topologica). Avantajul mare al algoritmului lui Kosaraju este ca este simplu de implementat si afce rezolvarea mai usoara decat o abordare cu Tarjan+sortare topologica.

Anyway, again just my 2 cents. Poate foloseste cuiva alternativa.

Claudiu