How to solve in less than O(n2) where N=100000 (length of string) and time limit 1 Sec

[Browni3141]

dhayden wrote:

If the string is 100,000 characters then the prefixes that start with the first character will contribute 100,000! to the result. That's a mighty big number. Suddenly the time to do the arithmetic sounds like it will dwarf the time to find prefix strings.

Most of the time a problem like this will ask for the answer modulo N, where N is a much more manageable number. Otherwise the focus becomes on implementing a bigInt library when that's not the point of the problem. This is part of why I have asked OP to post the original question.

jonnin wrote:

maybe I misread the problem. I read it as all substrings multiplied up, not just the last one?

You've definitely misunderstood something. We're talking about strings and the product of their lengths, not numbers. Also, your algorithm does check every substring. There are 10 substrings for a string of length 4, and your 4 passes find 10 substrings.

I think the brute force algorithm I posted is not too hard to understand. It just iterates over every substring and checks if that substring is a prefix of the input string. If it is then the result is multiplied by the length of that substring.

Anyway, the simplest non-brute force approach recognizes that substrings like 'baab' and 'abaab' don't need to be checked, because 'b' and 'abaa' are not prefixes of the input string.

[jonnin]

oh, yea I missed the lengths. Wrong problem :(

I expanded the terms to show what it was doing, you don't actually expand them to do it. pass 4 (irrelevant now since its the wrong problem) is manipulating 2 values, the previous product and the previous divisor.

[MyCreativityDiedWithEngg]

I am thinking in terms of optimized KMP pattern searching algo

[lastchance]

#include <iostream>
#include <string>
#include <vector>
using namespace std;

using INT = unsigned long long;

const INT M = 1000000007;              // A reasonably big prime number


struct part
{
   int pos;   // current position in a string
   int len;   // current length
};


//==========================================================


INT factorial( int N )                 // factorial( N ) mod M
{
   INT result = 1;
   while ( N > 1 )
   {
      result = ( result * N ) % M;
      N--;
   }
   return result;
}


//==========================================================


INT product( const string &str )
{
   int N = str.size();
   INT result = factorial( N );        // start with the whole string
   vector<part> current, next, final;

   // Start parts at every position with the same first letter as the string ( O(N) )
   char c = str[0];
   for ( int i = 1; i < N; i++ )
   {
      if ( str[i] == c ) next.push_back( { i, 1 } );
   }

   // Now advance characters from the start of the string, trying to extend all parts ( O(N) in a reasonable case)
   for ( int i = 1; i < N && next.size(); i++ )
   {
      current = next;
      next.clear();
      c = str[i];
      for ( part &p : current )
      {
         p.pos++;
         if ( p.pos >= N || str[p.pos] != c )
         {
            final.push_back( p );
         }
         else
         {
            p.len++;
            next.push_back( p );
         }
      }
   }

   // Include len! for all parts
   for ( part p : final )
   {
      if ( p.len > 1 ) result = ( result * factorial( p.len) ) % M;
   }

   return result;
}


//==========================================================


int main()
{
   string s = "abababababababababab";
   cout << "Product = " << product( s ) << '\n';
}


//========================================================== 

Gets the same result as @Browni3141 for "abababababababababab" at any rate.

[Browni3141]

Yeah, that's the algorithm that I was trying to describe, but it's still O(N^2) in the worst case. The makers of these problems have a tendency to throw the worst case at you.

This problem is a little harder than I thought, because I didn't realize a string like "a"*100,000 would break that algorithm. A more powerful algorithm is needed. This problem does interest me after all.

Edit: I guess I didn't really fully describe the algorithm, but it's what I was thinking of, anyway.

[lastchance]

Well,
s = string( 100000, 'a' );
gave ... in the end ...
649112004
but sadly it took a lot longer than 1 second.

I think that probably is the worst possible case - maybe one should look for an algorithm specifically for that?

Or perhaps look for patterns in the starting positions? (Rather obvious 0,1,2,3,4,... for the above case).

Or maybe precompute the factorials? (EDIT: that definitely helps, but can't get it under a second.)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

using INT = unsigned long long;

const INT M = 1000000007;              // A reasonably big prime number
const int N = 100000;                  // maximum string length envisaged


struct part
{
   int pos;   // current position in a string
   int len;   // current length
};


INT fac[1+N];


//==========================================================


INT product( const string &str )
{
   int size = str.size();
   INT result = fac[size];        // start with the whole string
   vector<part> current, next, final;

   // Start parts at every position with the same first letter as the string ( O(N) )
   char c = str[0];
   for ( int i = 1; i < size; i++ )
   {
      if ( str[i] == c ) next.push_back( { i, 1 } );
   }

   // Now advance characters from the start of the string, trying to extend all parts ( O(N) in a reasonable case)
   for ( int i = 1; i < size && next.size(); i++ )
   {
      current = next;
      next.clear();
      c = str[i];
      for ( part &p : current )
      {
         p.pos++;
         if ( p.pos >= size || str[p.pos] != c )
         {
            final.push_back( p );
         }
         else
         {
            p.len++;
            next.push_back( p );
         }
      }
   }

   // Include len! for all parts
   for ( part p : final )
   {
      if ( p.len > 1 ) result = ( result * fac[p.len] ) % M;
   }

   return result;
}


//==========================================================


int main()
{
   // Precompute factorials mod M
   fac[0] = 1;
   for ( int i = 1; i <= N; i++ ) fac[i] = ( i * fac[i-1] ) % M;

// string s = string( 100000, 'a' );   // worst case
   string s = "abababababababababab";
   cout << "Product = " << product( s ) << '\n';
}


//==========================================================  

[MyCreativityDiedWithEngg]

How much time is it taking @lastchance

[lastchance]

MyCreativityDiedWithEngg wrote:

How much time is it taking

Why don't you try it?

[MyCreativityDiedWithEngg]

It will take effort to copy your code and then run it. Why not you do it again? @lastchance

[MikeyBoy]

Yes, it will take effort. You're the one who's trying to solve this problem, so it should be you making that effort. Why do you think people here should do it for you?

[MyCreativityDiedWithEngg]

Why are you getting angry? @MikeyBoy Its ok if you are not able to solve the problem. But I would propose to you to think harder. Not everyone gets it right in the first time

[MikeyBoy]

What are you talking about? I'm not getting angry. Whoever told you you were good at reading minds must have been messing with you.

I just think it's selfish of you to ask other people to give up their time to do work for you, that you could do yourself.

[MyCreativityDiedWithEngg]

Again you are getting angry. I think you should focus your energy more in solving the problem @MikeyBoy

[helios]

Is this that "entitlement" thing I've been hearing about?

[jonnin]

this is possibly the weirdest 'you do this for me' argument I have ever seen. The 'angry' and 'think harder' bit seems like an esl fail, and the rest leaves me ... amused is probably the best word.

[coder777]

MyCreativityDiedWithEngg wrote:

I think you should focus your energy more in solving the problem @MikeyBoy

To be more correct:
I think you should focus your energy more in solving my problem @MikeyBoy
:D

[MyCreativityDiedWithEngg]

This is not my problem @coder777. Since when a programming problem has become an asset. You people are making excuses instead of solving the problem. Not every time you will get cakewalk problems in this forum.

[helios]

I think you're a bit confused about what this forum is. You're acting like you're a paying customer, or like the people here have a responsibility to give you an answer to your problem. If that's actually what you believe, I'm afraid you're completely deluded, or at the very least just grossly mistaken.

[dhayden]

MyCreativityDiedWithEngg, can you post the full text of the problem? At the very least it's probably asking for the answer mod 10 or something.

Running lastchange's program on my computer with string(100000, 'a') takes 3m39s.

[MyCreativityDiedWithEngg]

@helios at least now I know you are not able to solve the problem.