Se poate renunta la recursivitatea indirecta, arbori dar si la chestia aia pe nivele, folosind o singura functie recursiva. Ideea este ca atunci cand dai de un + sau - sa te comporti la fel cum s-ar deschide o paranteza imediat dupa acel operator de prioritate scazuta, iar cand dai iar de un astfel de operator faci la fel cum s-ar fi inchis paranteza, astfel returnand ceea ce ai calculat deja. In felul asta stii ca intotdeauna * si / vor avea prioritate, deoarece se vor gasi numai intre acele pseudoparanteze.

Esec dupa esec ...
Am testat-o de-am inebunit si pe valori mari (mai mari decat in cerinta) si pe teste ciudate/lungi si totul e ok, apoi ii dau submit imi intra in 3.7s (sub 5 limita) de memorie nici nu mai vorbesc in schimb imi da WA: sursa la shpath.
Folosesc un simplu bfs cu actualizari pe un graf neorientat cu lista de adiacenta (in loc de Dijkstra).

L.E.:Cred ca stiu unde gresesc, dar acum iau sigsev (trebuie sa implementez coada aia calumea, uitam sa adaug nod in coada in momentul cand faceam o actualizare).

Edit2: Da ... cum credeam, idiotul din mine loveste din nou am reparat greseala (http://codepad.org/ahSZrldH) dar iau tle, era si cazul fiindca m-a mancat in cur sa nu bag Dijkstra.

Last edit: Folosind varianta cu limita de 25 de secunde (TSHPATH) nu pot scoate mai putin de 24 secunde (imi trebuie sub 20), varianta fiind asta. Am facut o versiune mult mai optima si mai "atenta", dar in practica se descurca ceva mai prost decat sursa de mai sus.

A iesit pana la urma s-o f*t: http://codepad.org/w4wD8YUl

Zis si facut ... am implementat algoritmul in C (pentru problema Dk mai intai), dar mi-l ia pe 9 ca numar prim, pana si algoritmul in sine de pe pagina lor de wikipedia.
Python putin modificat, dar structura algoritmului e aceeasi:

Cod:

import random
import math
def miller_rabin(n):
  k = 1000
  s =  max(f for f in range(0, int(math.log(n,2))) if (n-1) % 2**f == 0)
  d = (n-1) / 2**s
  for i in xrange(k):
    a = random.randrange(2, n-1)
    x = pow(a, d, n)
    if x == 1 or x == n-1:
      continue
    for r in range(1, s+1):
      if x == s:
        return False
      x = pow(x, 2, n)
      if x == 1:
        return False
      if x == n-1:
        break
  return True
print filter(miller_rabin, range(5, 100, 2))

Si implementarea in C (mai e loc de optimizari): http://pastebin.com/5e8e9dWh

Am verificat si algoritmul din pseudocod cu bazele 2 7 si 61 (care merg corect pe numere sub 4 miliarde) dar mi-l ia si aici pe 9 (posibil si altele) oricum pe problema Dk iau cateva WA in rest numai TLE .

Stie cineva o abordare mai rapida la PRINT decat O(t*(b-a)*sqrt(b)/2) pentru a afisa toate numerele prime dintr-un interval ?

Am incercat asta, dar imi ia cateva secunde pe test numai pentru afisare pe cand mie trebuie sa-mi ia maxim 0.06 in medie sa se incadreze in 9-10 secunde la 150 teste maxim.

Ciur nu cred ca merge nu-ti pun la dispozitie 2gb ram, oricum am vazut best answers si de 2s cu 1.7mb am ramas oO. Am incercat si pe biti (mini ciur + verificare daca e prim cu ultimu bit ... la fel fail).

Merci anticipat!

Nu am nici cea mai mica idee de ce obtin WA pe TMUL (dupa ce trec de asta vreau sa nu scot TLE pe MUL). L-am testat in toate felurile si da bine.

Cod:

#include <stdio.h>
#include <ctype.h>
#define base 1000000000
#define len 9
#define N 1113

unsigned long long first[N], second[N], last[2 * N];

inline void init()
{
    char chr;
    unsigned short cnt;
    unsigned long total;
    first[0] = second[0] = 0;
    cnt = 0;
    total = getchar() - '0';
    while (!isspace(chr = getchar())) {
        if (++cnt != len) {
            total = total * 10 + chr - '0';
        } else {
            first[++first[0]] = total;
            total = chr - '0';
            cnt = 0;
        }
    }
    first[++first[0]] = total;
    cnt = 0;
    total = getchar() - '0';
    while (!(isspace(chr = getchar()) || chr == EOF)) {
        if (++cnt != len) {
            total = total * 10 + chr - '0';
        } else {
            second[++second[0]] = total;
            total = chr - '0';
            cnt = 0;
        }
    }
    second[++second[0]] = total;
}

inline void zfill(unsigned long nr, char str[])
{
    unsigned short cnt = 0, i = 0;
    if (!nr) {
        cnt = 1;
    } else {
        while (nr > 0) {
            ++cnt;
            nr /= 10;
        }
    }
    for (; i < len - cnt; ++i) {
        str[i] = '0';
    }
    str[i] = 0;
}

inline void process()
{
    unsigned long long temp = 0;
    unsigned short i, j;
    char str[10];
    if (!first[1] || !second[1]) {
        putchar('0');
    } else {
        last[0] = first[0] + second[0] - 1;
        for (i = first[0]; i > 0; --i) {
            for (j = second[0]; j > 0; --j) {
                last[i + j - 1] += first[i] * second[j] + temp;
                temp = last[i + j - 1] / base;
                last[i + j - 1] %= base;
            }
        }
        if (temp) {
            printf("%lu", (unsigned long) temp);
        }
        for (i = 1; i <= last[0]; ++i) {
            if (i != 1) {
                zfill((unsigned long) last[i], str);
            } else {
                str[0] = 0;
            }
            printf("%s%lu", str, (unsigned long) last[i]);
            last[i] = 0;
        }
    }
    putchar('\n');
}

int main()
{
    short nr;
    freopen("mul.in", "rt", stdin);
    scanf("%hd\n", &nr);
    while (nr-- > 0) {
        init();
        process();
    }
    return 0;
}

Edit ... am rezolvat, nu aveam grija la mutiplul lungimii bazei si la transport.
http://pastebin.com/iMmPUa4d

Corect, dar scorul il ia de pe spoj (teste, compilare, run totul se face acolo) ... oricum am reusit sa-mi iasa de 1000. Dinamica clasica numai ca pentru generarea solutiei trebuie folosit un vector nu o structura/clasa cum am facut eu. Si apoi pentru fiecare caracter se cauta pozitiile de unde a ramas cautarea anterioara. Desi pare ineficient e mai rapid.

Am vazut ... gege esti boss ... ce optimizari ?
Incercasem si eu ceva sa scot un timp la jumatate + triming dar WA :\.

LE: Asta imi da cel mai bine http://ideone.com/wgLbx 867 ... mai mult nu pot scoate. Totusi nu-mi este de ajuns imi trebuie pentru recruitcoders .

Merci mult.
Am incercat http://pastebin.com/jGjLkMiD dar n-am idee la implementarea cu arbori, iar la generare ma gandeam la un sort+binsearch dar pierd cand caut indicii in lis(). Oricum cam tot acelasi timp e, faza naspa e ca de data asta nu-mi intra deloc in timp, ori conditionez la primul rezultat ori iau TLE pe orice timp il bag in main in if.

Stie cineva un algoritm mai rapid decat dinamica clasica pentru cel mai lung subsir comun ?
Am gasit documentatie pe net, ceva cu bit string sau sortare si cautare binara, dar nu au un amarat de pseudocod sau orice sa inteleg exact cum calculeaza anumite chestii. Sa fie sub O(n*m+n+m) e tot ce ma intereseaza.
-> http://www.spoj.pl/problems/TLCS/

Spargi cache-ul.

Asa si in romana ?

Am doua surse cu o foarte mica diferenta:
Prima sursa good
A doua sursa bad

Diferenta intre good si bad este ca am dat swap la dimensiuni intr-o matrice, adica am inversat liniile cu coloanele schimband de asemenea si rolul indicilor pentru a avea aceleasi rezultate, insa la a doua sursa primesc TLE (time limit exceeded) si nu inteleg de ce fiindca atat ordinul de complexitate, numarul cat si resursele alocate instructiunilor raman aceleasi.
Mai exact din O(g*w) am facut O(w*g).