I think the following approach might work:

Let dp(i)(j) = the probability  of reaching a state with i untied lace ends and j cycles.

During an operation, two ends are chosen at random and tied together, so they won't be used in the future. This takes us to a state with i-2 untied ends.

Now, there is a 1/(i-1) (or something similar) probability that the two freshly tied ends will close a cycle, and an (i-2)/(i-1) probability that no new cycle will appear.

Therefore we can move to state (i-2)(j+1) with probability P and to (i-2)(j) with probability 1-P.

The trivial state is dp(2*n)(0) = 1.

Încearcă acum.

Încearcă acum.

Ti-am trimis un PM cu explicatiile din sursa mea.
Sper sa te ajute.

Incearca sa renunti la cateva apeluri ale functiei.

De fiecare data cand faci o impartire in 4 cadrane, in loc sa repeti impartirea in mod succesiv pentru fiecare dintre ele (complexitate pentry query O(2^n)), poti sa reapelezi doar pentru cadranul in care se afla elementul cautat (complexitate O(log (2^n)) = O(n * log 2) = O(n)).

Observa ca fiecare cadran initial contine un interval compact de valori. Pentru cazul din exemplu: [1, 4], [5, 8], [9, 12], [13, 16].
Daca ai de cautat un element care se afla in cadranul 3, poti sari peste 2 cadrane (adica 8 valori), fara sa le mai parcurgi, si iti ramane sa cauti doar in intervalul/cadranul imediat urmator.

Pentru simplitate, considera ca ai scazut valoarea 8 din fiecare element al cadranului ales. in modul asta, cadranul o sa obtina exact structura initiala a tablei (valoarea 1 in coltul stanga-sus, 2^dim in coltul dreapta-jos, si aceeasi ordine de numerotare), ceea ce iti simplifica impartirea urmatoare.

Solutia o sa fie suma tuturor valorilor scazute astfel, pana in punctul in care ajungi la un cadran de dimensiune 1.

Am rezolvat problema acum un an; daca am omis sau gresit ceva, o sa corectez.

Reborn
Putem utiliza o structura de date (de exemplu, arbore de intervale sau set) pentru a determina pentru fiecare casa care e cea mai din dreapta pozitie unde poate fi reinviat Tsuna folosind o singura arma.

Se poate rezolva etapa asta mai simplu dpdv. al implementarii, aplicand o interclasare a intervalelor in sir:

Cod:

sort(v.begin(), v.end(), cmp);

for(x=1, y=0; x<=n; x++) {
        while(y < int(v.size()) && v[y].first <= x) R = max(R, v[y++].second); //R = cel mai mare capat drept de pana acum
        rightmost[x] = (R < x)? 0:R;
}

Se poate lua 100 cu Lee. Din ceva motiv, primesc eroare de compilare pe sursa ta (incepand cu eroare la linia l[0] = 0, l[n+1] = 0, unde l e tablou bidimensional). Iti atasez sursa mea, in caz ca te ajuta:

Cod:

#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#include <cstring>
#define nmax 80
using namespace std;

struct node {
	int x, y;
};

int xs[] = {-1,  0, 0, 1};
int ys[] = { 0, -1, 1, 0};

int n, m, dist[nmax][nmax];
bool seen[nmax][nmax];
string a[nmax];

queue <node> Q;
node S, D;
//S - sursa, D - destinatie, T - nod curent, W - vecin

bool inside(node X) { return (X.x >= 0 && X.x <= n+1 && X.y >= 0 && X.y <= m+1); } //interior sau bordura

void bfs() {
	node T, W;
	while(!Q.empty()) {
		T = Q.front();
		Q.pop();
		seen[T.x][T.y] = true;

		if(T.x == D.x && T.y == D.y) break; //am ajuns la destinatie prematur, ma opresc

		for(int i=0; i<4; i++) {
			W.x = T.x + xs[i]; //am muchie T -> W
			W.y = T.y + ys[i];

			if(inside(W) && !seen[W.x][W.y]) {
				dist[W.x][W.y] = dist[T.x][T.y] + 1; 
				seen[W.x][W.y] = true;

				if(W.x >= 1 && W.x <= n && W.y >= 1 && W.y <= m && a[W.x-1][W.y-1] == 'X') continue;
				//^ daca ma aflu intr-un 'X', nu il bag in coada (pentru ca nu pot continua drumul <prin> el)

				Q.push(W);
			}
		}
	}
	while(!Q.empty()) Q.pop(); //in caz ca am intrerupt manual cautarea, arunc ce-o ramas in coada
}


int main() {
	ifstream f("inginer.in");
	ofstream g("inginer.out");

	f>>n>>m;
	for(int i=0; i<n; i++) f>>a[i];
	while(1) {
		f>>S.x>>S.y>>D.x>>D.y;
		if(!(S.x | S.y | D.x |D.y)) break;

		for(int i=0; i<=n+2; i++)
			for(int j=0; j<=m+2; j++) seen[i][j] = false, dist[i][j]=0;
		
		Q.push(S);
		bfs();

		g<<dist[D.x][D.y]<<"\n";
	}	

	return 0;
}

Nu cred ca te ajuta prea mult observatia asta, pentru ca se obtin cel mult 10^9 resturi modulo M. Ai avea complexitatea O(M * T).

Operatorul "++" iti incrementeaza (aduna 1) la obiectul asupra caruia il aplici.
Poate fi folosit in 2 moduri, prefix (++dim) sau postfix (dim++).
Diferenta e ca "++dim" il incrementeaza pe dim, dupa care il transmite ca pozitie in vector. Pentru dim = 4, digit[++dim] indica spre digit[5].
"dim++" il transmite mai intai ca pozitie, dupa care il incrementeaza. Pentru dim = 4, digit[dim++] indica spre digit[4], dupa care dim devine 5.

Poti folosi in cazul de fata si "dim++", dar o sa ai de parcurs la final intervalul dim-1 -> 0 in loc de dim -> 1.

@SebiSebi: da, cu dequeul din STL. Cu RMQ se puteau obtine timpi de 3-4 ori mai mici.

@vladtarniceru: la mine, un log vine de la sortare, unul de la map-ul in care tin diferentele coordonatelor.

@Alex: La Ninja, poti folosi 2 arbori de intervale + lazy propagation ca sa afli in timp logaritmic, pentru orice interval [a, b], cate lingouri incep undeva in interiorul intervalului, si cate se termina in interval.
Nu stiu sigur cum se pot numara lingourile aflate in intregime intr-un interval dat, pe baza informatiilor furnizate de aint.

La Plagiat am si eu tot O(N*N*logN + N*logN)

Cod:

dim = 0;
while(n) {
  if(n%2 == 1) digit[++dim] = n % 10;
  n /= 10;
}

for(int i=dim; i>=1; i--) cout<<digit[i]<<" ";

digit[] - vectorul in care tii cifrele impare
dim - ultima pozitie ocupata din digit[]
De fiecare data cand numarul curent ii impar (-> are ultima cifra para), se adauga ultima cifra pe urmatoarea pozitie libera din vector.
Cifrele sunt eliminate de la dreapta la stanga, deci le tiparesti in ordine inversa, de la dim (=ultima pozitie) la 1 (prima).

Prima structura, "a=9,0,-1" cred ca poate fi inlocuita de o structura de tipul "pentru valorile lui a de la 9 la 0, parcurse din -1 in -1" (9, 8, ..., 0).
In C ar arata cam asa: for(int a=9; a>=0; a--)

A doua structura poate fi inlocuita cu ce zici tu doar daca si ea efectueaza un numar cunoscut de pasi, probabil ca n si k scad cu o unitate la fiecare pas.
In cazul asta, o poti inlocui cu "pentru i = 1 -> min(n, k)", pentru ca bucla se opreste prima data cand se verifica una dintre conditiile "n<=0" si "k<=0".

Pentru testul 1 nu exista solutie.

Daca la vreun pas, suma curenta > valmax, atunci sol = 0.

Punctul b) coincide cu problema determinarii secventei crescatoare de lungime maxima, care se rezolva prin metoda programarii dinamice:

Iti propui sa construiesti un sir dp() cu semnificatia dp(i) = lungimea maxima a unei secvente care incepe pe pozitia i, si este crescatoare.
Pe pozitia n exista o singura secventa (de lungime 1), deci dp(n) = 1 (asta e subproblema elementara).
Pentru orice alt indice i, care ia valori de la n-1 la 1, construiesti dinamica pe baza recurentei:
1) dp(i) = 1, daca v(i) > v(i+1)
2) dp(i) = 1 + dp(i+1), daca v(i) <= v(i+1)

Recurenta se interpreteaza asa:
1) daca valoarea curenta o depaseste pe cea din dreapta, inseamna ca nu pot construi o secventa cu ambele (nu ar fi crescatoare); construiesti deci secventa formata doar din elementul curent.
2) daca valoarea curenta nu o depaseste pe cea din dreapta, inseamna ca poti alatura elementul curent secventei optime care incepe cu elementul urmator (adica dp(i+1)) si obtii o secventa mai mare cu un element decat cea care incepe vecinul din dreapta.

La final cauti maximul din dp(), gasesti capetele secventei respective, calculezi media.

In cel mai rau caz, ai de generat C(50, 25) = 126.410.606.437.752 configuratii (de ordinul 10¹⁴).
Pentru C(50, 7) = 99.884.400 ~= 100 de milioane de configuratii, procesorul meu are nevoie de 2.7 secunde, excluzand tiparirea (cu tiparire, mi se executa in 91 s).
Presupunand ca timpul de executie creste liniar in functie de numarul de operatii (nu-i chiar asa), ar trebui o limita de 3.417.036 secunde ~= 40 de zile.

In cazul in care se cerea intervalul cel mai apropiat de X care sa fie valid, cred ca ar functiona o solutie bazata pe ciurul lui Eratostene.
Pentru peluza infinita poti sa te folosesti de aproximarea densitatii numerelor prime: alegand la intamplare un numar din intervalul [1, N], probabilitatea ca el sa fie prim ii de aprox. 1 / ln(N). Pentru N foarte mare, ai sanse bune sa gasesti solutia cu un random.

Momentan nu gasesc nimic mai bun; ma astept ca solutia oficiala sa coincida cu ce am facut noi in concurs. Ramane de vazut.

Peluza Sud are doar 10¹⁵ locuri. Astfel, vă rugăm ca locurile pe care le alegeţi să se afle în intervalul [X + 1, 10¹⁵].

Restrictia asta iti permite sa afisezi o solutie <universala>, care poate fi gasita destul de usor (http://en.wikipedia.org/wiki/Prime_gap).
Solutia ramane corecta.

Implementarea recursiva nu necesita folosirea unei stive, deci ai cod mai scurt (de ~2 ori, vezi wiki).
Pana acum nu am intalnit nicio situatie in care sa am probleme cu dfs-ul recursiv.

In caz ca ti se pare mai usor, poti sa folosesti metoda iterativa, si o sa obtii doua implementari foarte similare la DFS si BFS (doar se inlocuieste stiva cu o coada).

Presupune prin absurd ca tu cunosti deja solutia ca fiind X, si vrei sa o verifici (adica sa faci o explorare a hartii astfel incat sa nu te apropii niciodata la o distanta mai mica de X, fata de vreun dragon).

Odata ce gasesti o modalitate de a verifica un anumit X si de a afla astfel daca valoarea respectiva poate fi solutie sau nu, tot ce iti ramane de facut e sa *cauti* cel mai mare X care verifica conditia.

Cautarea binara e corecta pentru ca functia f(x) = {1 daca x e solutie, 0 daca x nu e solutie) este monotona.
Cu alte cuvinte, exista un X maxim care poate fi solutie, astfel incat valorele {1, 2, ..., X-1, X} sunt si ele solutii valide (adica exista cel putin un traseu bun de la sursa la destinatie pentru fiecare valoare din lista) si pentru nicio valoare mai mare decat X nu exista niciun traseu.
Practic, distantele minime valide pe care le poti alege se termina brusc.

Pentru fiecare drum posibil de la sursa la destinatie, se ia in considerare punctul de pe traseu in care distanta dintre barbar si un dragon oarecare este minima.
Trebuie gasit un drum care maximizeaza distanta asta.

Pentru exemplu, chiar daca la inceput mergi in stanga sau in sus, oricum ai continua traseul pana la destinatie, tot te apropii la cel putin 2 unitati fata de un dragon.

Nu exista niciun drum in care sa fii permanent la o distanta >= 3 fata de orice dragon, deci solutia optima e 2.

Cod:

#include <iostream>
#include <fstream>
using namespace std;

int n;
string s, sol = "";

int count(string s) {
	int ret = 0;
	for(int i=0; i<s.size(); i++) if(s[i]>='A' && s[i]<='Z') ret++;
	return ret;
}	

int main() {
	ifstream f("siruri.txt");

	f>>n;
	f.get();
	for(int i=1; i<=n; i++) {
		getline(f, s);
		if(count(s) >= count(sol)) sol = s;
	}

	cout<<sol<<"\n";
	return 0;
}

Poti reduce un pic din densitatea codului prin folosirea unei functii care returneaza direct valoarea cautata, fara sa apelezi la variabile auxiliare (acel &nr1), si prin copierea directa a stringurilor-solutie (sol = s, fara parcurgere).

Din punctul de vedere al dimensiunii, ambele surse is relativ scurte. Mi se pare cam greu sa le reduci si mai mult dimensiunea, fara sa pierzi din claritate.

Din punctul de vedere al eficientei, ambii algoritmi ruleaza in O(n * lungime_medie), cu toate ca eu am o constanta ceva mai mare (pentru ca apelez la fiecare pas functia count() de doua ori, pentru sirul curent si pentru solutia curenta).

Cred ca cel mai bine e sa scrii cod curat si lizibil, a.i. sa intelegi exact ce face fiecare bucata din el, decat sa sacrifici asta pentru a reduce dimensiunea.

Poti incerca (daca ai la dispozitie vreun exemplar din CLRS) capitolul The Role of Algorithms, in care se descriu notiunile de eficienta si complexitate-timp, in sectiunea 1.2 Algorithms as a technology.

Aici gasesti o lista cu diferite complexitati intalnite frecvent, si algoritmii clasici care se incadreaza in fiecare (in Cormen exista un tabel asemanator, dar lipsesc algoritmii).

Cred ca cea mai consistenta sursa din care poti invata e tutorialul despre Computational Complexity de pe Topcoder: Partea 1 si Partea a 2-a.

Spor!