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.**