Find number of ways to create a string

Given a set of K distinct characters.
Find the number of ways to create a string of length N.
Given that-
1.No 2 adjacent character should be same
2.Odd positions can be filled by any one of the K characters.
3.Even positions can be filled by any character from a-z.

Since answer can be large print it in modulo 10^9+7.
Constraints:-
1<=N<=10^5
0<=K<=26

Example:-
N=2,K=1
a

Output:-
25

5 Likes

From hackerearth right,:roll_eyes::slightly_smiling_face:

2 Likes

yes, I am so bad at combinatorics.:confused:

1 Like

Me toooo ( kha jaao 20 char ko ),:stuck_out_tongue_winking_eye:

3 Likes

just do dp,
where dp[i][j] , is the number of ways to create a string of length i , taking j’th charater

2 Likes

I think this problem can be easily solved using DP, mostly because of the 1st condition.

Lets denote memo[len][last] as the number of strings with length len and that end in letter last.

Now, we can build the number of strings that end in last according to the parity of len:

  1. If len is odd, then last must belong to the k valid characters
  2. If len is even, then last can be any character.

The only condition left is the 1st one, which means that:

memo[len][last] = \sum\limits_{before \in \Sigma, before \neq last} memo[len-1][before]

Where \Sigma is the english alphabet.

But this makes us to make an extra iteration over all before values (therefore, our complexity would be O(n\Sigma^{2})), but this can be avoided by noticing this:

memo[len][last] = (\sum\limits_{before \in \Sigma} memo[len-1][before] ) - memo[len-1][last]

But how does this help? In fact, we can preprocess the sum value at the end of procesing the length len and storing it in the value prevSum, so for the next iteration we’ll have:

memo[len][last] = prevSum - memo[len-1][last]

Finally, our answer would be the number of strings with length n that can end in any character, thus

ans = \sum\limits_{c \in \Sigma} memo[n][c]

Our complexity will be O(n\Sigma).

C++ Code

2 Likes

Be sure to take more at every calculation…

there were test cases involved hence we required constant time ans, i did dp got tle

This is a DP + combinatorics problem.
For first position you have k choices. After that,
1.) For even there are two cases:
a) if the previous character was from the given k characters, you have k-1 choices
b) if the previous character was other than the given k characters, you have 26-k choices.
2.) For Odd there are two cases:
a) if the previous character was from the given k characters, you have k-1 choices
b) if the previous character was other than the given k characters, you have k choices.

Complexity: O(N) per test case
C++ code

1 Like

My solution was without using dp. By observing carefully(and of course doing the combinatorics stuff), we get the relation depending upon n and k. For even length string, it is 25 * k * (p^(n/2 - 1)) and for odd length string it is (p^(n/2)) * k where p is (k-1) * (k-1) + k * (26-k).
My 100AC solution.
http://pasted.co/db0cb844

Complexity: O(logn) for each test case. (for modular exponentiation).

It would be better if you could explain how you reached that formula.

Can you tell me what the number of testcases ?

The number of testcase T was between 1 and 250

1 Like

So my lovely dp wont work. Let me cry.

1 Like

So, I tried to explain how I reached at that formula. Not an elegant one, but I tried. :slight_smile:


5 Likes

Well O(N*T) = 2.5 * 10^7
This should pass 1 second time limit but we will get TLE due to too many modulo operations.

You derived eqn after such a long work in a 2- hour contest where there were 2 more problems to be solved… Kudos to you!!! Any tips for noobies like me to improve math?

1 Like

yeah I follow @karangreat234 and other legendary coders. I am a complete noob and that’s how I’m learning. You can do the same. :upside_down_face::slightly_smiling_face:

2 Likes

just to make matter worse time limit was 0.5 seconds.
Enjoy!!:stuck_out_tongue_winking_eye:

O(N) solution gave AC verdict during contest

2 Likes