hello__world_'s blog

By hello__world_, history, 6 weeks ago, In English

You are given two types of people, type A and type B. You need to place n people of any type but the condition is that no two A type people is close to each other, means [A,A,B,A,B] not possible since two A type person are close to each other. You need to find all the possible arrangement. Print the answer modulo 1e9 + 7.

Constraints

1 <= n <= 100000

Input: 3 Output: 5

Explanation: if n = 3 then possible combinations are [B,B,B] [A,B,B] [B,A,B] [B,B,A] [A,B,A]

So the answer is 5.

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a link to that problem?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The problem is same as finding number of n bit strings without any pair of consecutive ones. For n = 3, all strings:

    000, 001 , 010, 011, 100, 101, 110, 111

    strings satisfying the constraints:

    000, 001, 010 ,100, 101

    So total 5 string are there.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I believe this was asked in Publicis Sapient — Jumpstart,

my approach
something cool
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This problem was also in dynamic programming course, on informatics.msk.ru. If you know russian and want to learn classic dp problems, check the course out.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Could the reasoning be something like this?

    More Details
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • if n = 1 ans = 2
  • if n = 2 ans = 3
  • if n = x ans = f(x-1) + f(x-2)
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

this can be done easily in math. We convert the problem this way: given all the B's already arranged, insert A's into them such that no 2 of them take the same place. It is now obvious that the answer is (number of B)+1 choose number of A places to insert them.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

you can easily solve it with stars and bars,

assume z spaces like __ a1 __ a2 __ a3... __ a4 __ ,

which would be lets say, z = |a| + 1,

so what you have is b1 + b2 + b3 + ... + bz = |b|

here b1,bz >= 0 and b2,b3...b_{z-1} >= 1

so b1 + b2 + b3 + ... + bz = |b| — |a| + 1

for stars and bars we know that ,its (n + k — 1) C (r — 1)

so its (|b| — |a| + 1 + z — 1 ) C (z — 1)

which is (|b| + 1) C (|a|)

we know |b| + |a| = n

(n — |a| + 1) C |a|

you can easily find summation pattern from this

as |a| is in range [0 , n]

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

define mod 1000000007

int main() { int n; cin>>n; vectordp(n+1); dp[0]=1; dp[1]=2; for(int i=2;i<=n;i++) { dp[i]=(dp[i-2]%mod + dp[i-1]%mod)%mod; } cout<< dp[n]; }

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice but easy problem