2
\$\begingroup\$

The problem is to find the number of increasing sub-sequence of a string with only digit characters. Answer may be very large, so output it modulo 10^9+7.

I have been able to get a O(n) solution using segment trees. However , the the code is quite inefficient owing to loops with constant but large runtime. How can I make the code more efficient ?

The link to the exact problem statement is http://www.spoj.com/problems/LARSUBP/

#include <stdio.h>
#include <string.h>


typedef struct Tree_node
{
    int M[10][10] ; 
    // M[i][j] = Number of sub-sequences starting with i and ending with j in the interval low to high in which it is called . 
} TN ;


//Declaration of global variables

char number[50000] ;//Stores the input string
TN Tree[100000] ;//The array Tree[] is used to store the nodes of the segment tree
long long int convert ; //Other variables
int k1 , k2, i , j; 



void Build_Tree( int node , int low , int high) ;

int main()
{
    // t is the number of test cases
    // N is the length of input string
    int t , N , counter ; 

    //Stores the number of increasing sub-sequences
    long long int answer ;

    //No of test cases
    scanf("%d",&t) ; 

    for(counter=0;counter<t;counter++)
    {
        scanf("%s",number) ; 
        N = strlen(number) ; 

        // Calling the build tree function 
       Build_Tree(1,0,N-1) ; 

        // Calculation of increasing sub-sequences using the Tree . 
        answer = 0 ;
       for(i=0;i<10;i++)
       {
           for(j=i;j<10;j++)
           {
              answer = answer + Tree[1].M[i][j] ; 
              answer= answer % 1000000007 ; 
           }
       }
       answer = answer %1000000007 ; 
       printf("%lld\n",answer) ; 

    }
    return 0 ; 
} 

void Build_Tree( int node , int low , int high)
{

 // node stores the index of the Tree-node to be evaluated
 // low and high define the interval which we are considering

    int mid ;   

    // Initialization of M[][]
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            Tree[node].M[i][j] =0 ; 

        }
    }

    if(low==high)
    {
        // Base case 
        int temp = number[low]- '0' ; 
        Tree[node].M[temp][temp] = 1 ; 
    }
    else
    {
        mid = (low+high)/2 ; 
        Build_Tree(2*node , low , mid) ; // Building the subtree of left child
        Build_Tree(2*node+1 , mid+1 , high) ; // Building the subtree of right child


    // Combining the information 
    // No. of increasing sub-sequences starting with i and ending withj from low to highequal to sum of 
    // 1.increasing sub sequences starting with i and ending with j from low to mid
    // 2.increasing sub sequences starting with i and ending with j mid+1 to high
    //3. all increasing sub-sequences starting with i and ending with k1 from low to mid multiplied by increasing sub sequences starting with k2 and ending with j from mid+1 to high where k1 < k2 . 

        for(i=0;i<10;i++)
        {
            for(j=i;j<10;j++)
            {
                convert = Tree[2*node].M[i][j] + Tree[2*node+1].M[i][j] ; 
                convert = convert % 1000000007 ; 
                Tree[node].M[i][j] = convert ; 

                if(i==j)
                {
                    continue ;
                }
                else
                {

                    for(k1=i;k1<j;k1++)
                    {
                        for(k2=k1+1;k2<=j;k2++)
                        {
                            convert = Tree[node].M[i][j] + Tree[2*node].M[i][k1] * Tree[2*node+1].M[k2][j] ;
                            convert = convert % 1000000007 ;
                            Tree[node].M[i][j] = convert ; 

                        }
                    }
                }

            }
        }


    }



}
\$\endgroup\$
3
\$\begingroup\$

\$\newcommand{\sub}[1]{\text{sub}_{#1}}\$ This is more of an alternative algorithm than a review on your code (at least for now), but it seems like both could be helpful.

A good algorithm results from solving a slightly more informative version of the problem, which is simpler to decompose:

\$\sub{s}^n\$ is the number of subsequences of \$s\$ that are ordered and end with the digit \$n\$.

\$\sub{s}\$ can be stored in a 10-long array, the sum of which solves your original problem:

$$ \left[\ \sub{s}^0;\ \text{sub}_s^1;\ \text{sub}_s^2;\ \ldots;\ \text{sub}_s^9\ \right] $$

Clearly, for the empty string \$\varnothing\$, we have

$$ \text{sub}_\varnothing = \left[\ 0;\ 0;\ 0;\ \ldots;\ 0\ \right] $$

The interesting trick is that extending a string \$s\$ with digit \$d\$ is a simple update

$$ \sub{sd}^n = \begin{cases} \sub{s}^n & \text{if}\;n \ne d\\ 1 + \sum_{i=0}^{n} \sub{s}^i & \text{if}\;n = d \end{cases} $$

as the paths for subsequences that don't end in \$d\$ are unchanged and the subsequences that do end in \$d\$ are \$d\$ itself, \$d\$ added to the end of any prior subsequence that ends in a digit less than \$d\$, or any of the prior subsequences that did end with the digit already.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.