017 Triunghi

[•Mitza444]

Nu poti sa imi decrii un pic mai detaliat rezolvarea problemei??Chiar nu imi dau seama cum as putea gasi numerele acelea de la baza.( nu sunt grozav la dinamica)

[•pauldb]

Se calculeaza V[ i ] cu cat se modifica suma totala a triunghiului daca incrementezi cu 1 celula a i-a de pe baza. Se observa ca daca incrementezi cu x celula a i-a, atunci suma totala creste cu x*V[ i ]. Vectorul V il poti calcula brute force, simuland efectiv.

Apoi se face o dinamica foarte asemanatoare cu cea de la problema rucsacului, astfel: dp[ i ][ j ] = 1 sau 0 daca (sau nu) se poate obtine suma j cu valorile V[ 1 ], ..., V[ i ], fiecare putand fi folosita de oricate ori.

[•Mitza444]

Am o intrebare.Nu prea am inteles cum faci cu formula de la baza.Deci am un sir V care reprezinta numerele de la baza.Sa presupunem ca avem asa: n=3 si la inceput am pe V la baza numa valori de 1 pe toate pozitiile.O sa am:

Cod:

4
2 2
1 1 1

acestea au suma 11
daca incrementez cu unu pozitia 2:

Cod:

6
3 3
1 2 1

suma este 16,iar tu ai zis ca,creste cu x(adica 1)*V[2]==> creste cu 1,dar creste cu 5
Asta nu inteleg nu ar trebui sa conteze daca numarul care il incrementez i pe pozitia 1 sau n pt.ca atunci nu ar intra in suma finala de acelasi numar de ori ca si un numar care este pe poz dintre 1 si n.

Si daca am determinat poz de la baza de ce mai trebuie sa fac rucsacu pe ele nu ar trebui sa calculez numai liniile de mai sus??(cum determin triughiu doar cu rucsacu??)
Scuze ca tot intreb,dar chiar nu am inteles.
Multumesc pt. ajutor

[•klamathix]

Se calculeaza V[ i ] cu cat se modifica suma totala a triunghiului daca incrementezi cu 1 celula a i-a de pe baza.

Ai inteles gresit ce reprezinta V-ul.

[•pauldb]

Pentru n = 3, V este [3, 5, 3]. V nu reprezinta vectorul valorilor de la baza, ci cu cat creste suma totala daca incrementezi cu 1 o anume pozitie de la baza. Dupa cum bine ai observat, daca baza devine 1 2 1, suma creste cu 5. La fel, daca baza devine 1 3 1, suma mai creste cu 5 si tot asa.

Acum tot ce trebuie sa mai faci este sa gasesti niste valori A1, ..., AN, cu Ai >= 1, astfel incat A1*V1 + ... + AN*VN = S. Pasul dificil este sa vezi daca aceste valori exista si aici trebuie sa faci dinamica de tip rucsac de care ti-am spus mai sus. Valorile efective le poti reconstitui dupa cum am explicat aici. Avand valorile A1, ..., AN, adica baza triunghiului, este banal sa obtii si rezultatul final.

[•popoiu.george]

Iau TLE pe trei teste cu N*S, se poate optimiza ceva ? Pentru dinamica declar o matrice bitset cu 2 linii, iar pentru reconstituire una cu N linii.

Ar putea sa fie din cauza declararii matricei cu N linii ? Am citit in topicul dat de Paul ca se poate face reconstituirea si cu un vector, dar nu cred ca e de la asta, pentru ca matricea de bitset de reconstituire ocupa doar ~2MB, ceea ce e foarte putin.

[•Mitza444]

Deci nu inteleg de ce nu functioneaza.... .AM determinat vectorul V cu cat creste suma daca incrementezi cu 1.Dupa am facut rucsacul sa vad daca se poate obtine suma.Am retinut intr-o matrice bool daca b[ i ] [ j ] 1 sau 0 daca DP[j]=DP[ j - V[ i ] ]+V[ i ] sau din DP[ j ].Si daca suma de pe DP[ s ]==s suma care o citesc atunci am pornit de la capat si am daca b[ x ][ y ]==1 atunci icrementez poz x de la baza cu unu si y=y-V[ x ],altfel x=x-1.Pe exemplu merge ,dar per total iau doar 10 pct cu 2 teste TLE si restul wrong answer.
P.S.:In triunghiu pe care il afisez apar si 0-uri ,nu am reusit sa fac altcumva.

Cod:

#include<fstream>
using namespace std;
int tri[20][20],V[20],DP[1000001];
bool B[19][1000001];
int nr;
void back(int n,int x){
	nr++;
	if(x-1>=1 && x-1<=n-1 && n-1>=1)
		back(n-1,x-1);
	if(x>=1 && x<=n-1 && n-1>=1)
		back(n-1,x);
}
int main(){
	int n,s,i,j,x,y;
	ifstream f("triunghi.in");
	f>>n>>s;
	f.close();
	V[1]=V[n]=n;
	for(i=2;i<=n-1;i++){
		nr=0;
		back(n,i);
		V[i]=nr;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=s;j++){
			if(DP[j-V[i]]+V[i]>=DP[j])
				B[i][j]=1;
			if(j>=V[i])
				DP[j]=max(DP[j],DP[j-V[i]]+V[i]);
		}
	}
	ofstream g("triunghi.out");
	if(DP[s]!=s)
		g<<"imposibil"<<"\n";
	else{
	x=n;y=s;
	while(x!=1 && y!=1){
		if(B[x][y]==1){
			y=y-V[x];
			tri[n][x]++;
		}
		else{
			x--;}
	}
	for(i=n-1;i>=1;i--)
		for(j=1;j<=i;j++)
			tri[i][j]=tri[i+1][j]+tri[i+1][j+1];
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			g<<tri[i][j]<<" ";
		}
		g<<"\n";
	}
	}
	return 0;
}

[•PlayLikeNeverB4]

Iau TLE pe trei teste cu N*S, se poate optimiza ceva ? Pentru dinamica declar o matrice bitset cu 2 linii, iar pentru reconstituire una cu N linii.

Ar putea sa fie din cauza declararii matricei cu N linii ? Am citit in topicul dat de Paul ca se poate face reconstituirea si cu un vector, dar nu cred ca e de la asta, pentru ca matricea de bitset de reconstituire ocupa doar ~2MB, ceea ce e foarte putin.

Eu am scos 100 (la limita) cu observatia ca nu e nevoie sa calculez v-ul si rucsacul decat pana la (n+1)/2, deoarece de acolo se repeta in ordine inversa. Declar un bitset de ~n/2 linii si reconstituirea o fac in functie de valorile din bitset.

[•alex_toma]

Primesc TLE pe testele 2 si 5 si nu imi dau seama dc , se poate sa fie ceva cazuri speciale pe care sa nu le fi atins?
Ma poate ajuta cineva?

[•DrumeaV]

Numerele din triunghi.out trebuie sa fie > 0 sau pot fi si = 0?

[•mathboy]

În enunţ se specifică strict pozitive, deci > 0.

[•DorelBarbu]

Eu am luat 70. Iese de 100 si fara observatia ca ruscacul si vectorul v trebuie facute pana la (N+1)/2 ? Sau e alta chichita?

[•krityx]

Eu am un program in O(S*N/2) si iau doar 60p pe el 

[•mihai.alpha]

Ma ajuta si pe mine cineva, pt ca nu imi iese generarea matricii a.i. sa nu existe elem 0
uitati codul:
#include <bits/stdc++.h>
#define min(a, b)(a < b?a:b)
#define maxi(a, b)(a>b?a:b)
FILE *fin, *fout;
int mat[22][22];int b[22][1000001];int DP[1000000];
long long v[20];
int r[1000001];


int main()  {
fin = fopen("triunghi.in", "r");
fout = fopen("triunghi.out", "w");
int n, s;
fscanf(fin, "%d%d", &n, &s);
int i, j, k;

///Generarea vectorului v-cu cat creste elementul de pe pozitia i daca adunam 1 la elementul de pe pozitia i
///se observa ca vectorul v este palindrom
///Ma va ajuta sa scap de TLE
long long sum;
v[0] = n;
v[n - 1] = n;
for(i = 1;i <= n / 2;i++)  {
    sum = 1;
    mat[n] = 1;
    for(j = n - 1;j >= 1;j--)
        for(k = 0;k < j;k++)
            mat[j][k] = mat[j + 1][k] + mat[j + 1][k+1], sum += mat[j][k];
    v = sum;
    v[n - i - 1] = sum;
    memset(mat, 0, 500);
}
//for(i = 0;i <= n - 1;i++)
//    printf("%d ", v);

///acum trebuie sa rezolvam problema rucsacului a.i. sa vedem
///daca exista a[0],...,a[n-1] a.i. a[0] * v[0] +...a[n-1] * v[n-1] = s
       for(i=1;i<=n;i++){
      for(j=i;j<=s;j++){
         if(DP[j-v[i-1]]+v[i-1]>=DP[j])
            b[j]=1;
         if(j>=v[i-1])
            DP[j]=maxi(DP[j],DP[j-v[i-1]]+v[i-1]);
      }
      }
   if(DP!=s)
      fprintf(fout, "imposibil");
    else  {
        int x, y;
        x=n;y=s;
   while(x>=1 && y >= 1){
         //printf("%d %d %d\n", b

• [y], x, y);

      if(b

• [y] == 1){

         y-=v[x - 1];
         mat[n]

• ++;

      }
      else
       x--;
       //if(x == 1)
   }
   //printf("%d %d", x, y);
   for(i=n-1;i>=1;i--)
      for(j=1;j<=i;j++)
         mat[j]=mat[i+1][j]+mat[i+1][j+1];
   for(i=1;i<=n;i++){
      for(j=1;j<=i;j++){
         fprintf(fout, "%d ", mat[j]);
      }
      fprintf(fout, "\n");
   }
    }
fclose(fin)
fclose(fout);
return 0;
}


De asemenea, cum pot sa optimizez(am 4 TLE si 5 WA  )

[•IancuVlad]

totul depinde de primul rand cel mai de jos, baza triunghiului,
daca avem de exemplu N=4 si notam numerele de pe cutiile de la baza triunghiului cu x1, x2, x3, x4 obtinem:
suma bazei este
x1+x2+x3+x4
suma bazei plus cea a nivelului de trei cutii
x1+x2+x3+x4+x1+x2+x2+x3+x3+x4
adica
2x1+3x2+3x3+2x4
iar suma bazei a nivelului cu trei cutii si a nivelului cu doua cutii este
x1+x2+x3+x4+x1+x2+x2+x3+x3+x4+x1+x2+x2+x3+x2+x3+x3+x4
adica
3x1+6x2+6x3+3x4
adica ca sa nu va mai inebunesc cu siruri lungi de adunari, fiecare termen care nu este in margine isi dubleaza numarul de ori de care apare in sir pe masura ce crestem nivelul piramidei(sau al triunghiului dupa caz).
Acum problema e cum facem ecuatia si cum ii gasim solutiile caci sunt patru necunoscute, iar de aici avem exact ce s-a spus mai inainte ca exista solutii multiple