# Techgig Code Gladiators 2023 Semi Final Problems Discussion

Hi. This thread is for discussion on problems in code gladiators '23.

Can anyone share approach for second problem in semi finale?
Problem name: Reconstructing Arrays .

My approach: 1D Dynamic Programming.
If string is “1234” , then
I created tree like :

``````                                       1234
1                    12             123             **1234**
2        23    **234**       3      **34**           **4**
3 **34**      **4**                 **4**
``````

and counted all leafs with end as last element as that path is one array.
my code:

``````
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <list>
#include <deque>
#include <vector>
#include <algorithm>
#include <iterator>
const long long MOD = 1000000007;
const long double PI = 3.141592653589793238;
const long long inf = 1000000000000000000;
const long long small_inf = INT_MAX;
using namespace std;

bool strictly_greater(string a,string b){

if(a.size() > b.size())
return true;
if(a == b)
return false;
if(a.size() == b.size()){
for(long long int i = 0; i < a.size();i++){
if ((a[i] - '0') > (b[i] - '0'))
{
return true;
}

}

}
return false;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
long long int t,n,ans=0,i,m,j;

string s,s1;
cin>>n>>m;
string m_value = to_string(m);
cin>>s;
if(s.size() == 1){
cout<<1;
return 0;
}
if(n == 2){
string f ;
f+=s[0];
f+=s[1];
int starter1 = stoi(f);
if(starter1 > m)
cout<<1;
else
cout<<2;
return 0;
}
//string initial_string = s[2];
unsigned long long int dp[n];
if(s[1] == '0' && s[2] == '0')
{
dp[0] = dp[1] = 0;
}
else if(s[1] == '0')
{
dp[0] = 0;
string f ;
f+=s[0];
f+=s[1];
int starter = stoi(f);
if(starter > m)
dp[1] =0;
else
dp[1] = 1;
}
else if(s[2] == '0')
{
dp[0] = 1;
dp[1] = 0;
}
else
{
dp[0] = 1;
string f ;
f+=s[0];
f+=s[1];
int starter = stoi(f);
if(starter > m)
dp[1] =1;
else
dp[1] = 2;
}
int flg=1;
for(i=2;i<n ;i++){

//cout<<initial_string<<"\n";
dp[i] = dp[i-1] ;
string initial_string;
initial_string+= s[i];
for(j=i-1;j>=0;j--){

initial_string = s[j] + initial_string;
//cout<<"initial string is "<<initial_string<<"\n";

if(initial_string[0] == '0')
continue;
if(strictly_greater(initial_string,m_value))
{
flg=0;
break;
}
if(j==0)
{
if(strictly_greater(initial_string,m_value))
{
int jh=0;

}
else
{
dp[i] = (dp[i] + 1) % 1000000007;
//cout<<"here";
}
}

else
dp[i] = (dp[i] + dp[j-1]) % 1000000007 ;
}
//dp[i] = (dp[i] + 1) % 1000000007;
}
//for(auto e:dp)
//cout<<e<<" ";
cout<<dp[n-1] % 1000000007;
return 0;
}

///////////////////

**PS: Contest is ended.**
``````