Another interesting problem for you smart fellows

[Nineshadow]

 

I came across this for the first time a few weeks ago and today it's crossed my mind randomly.

 

Consider a binary sequence of n bits, with all the bits being initially 0. We define an operation FLIP(L,R) which flips all the bits of the sequence with indexes between L and R ( b_i = !b_i for all L<=i<=R). You're asked to determine the number of possible, different sequences that can be generated using exactly k flip operations, modulo a given arbitrary natural number(not necessarily prime). The initial sequence of bits with value 0 isn't considered in this number.

 

The tests themselves are structured with multiple queries, and as far as the limits go :

• 1<=n,k<=300 000
• mod<=10⁹+7
• queries <= 250
• time : 2 sec
• memory : 65536 kbytes

 

Some of my thoughts :

Spoiler

I'm relatively sure there's some recurrence or dynamic programming or something similar going on here. I'm sure that that the problem is made a bit harder by the fact that the modulo is not necessarily prime, although I haven't found exactly how exactly.

 

So, let's go the usual route. If you consider m[n][k] the number of different sequences of n bits that can be generated with k flips. It would look something like this :

1 1 1 1 1
3 3 3 3 3 
6 7 7 7 7 
10 15 15 15 15 
15 30 31 31 31 
21 56 63 63 63 
28 98 126 127 127
36 162 246 255 255
45 255 465 510 512

(matrix results obtained with brute force, pretty sure they're correct)

Some observations, maybe not all that useful :

• m[1][k]=1 for all k
• m[n][1]=n(n+1)/2
• if k is big enough, then obviously m[n][k] = 2ⁿ -1, it can't get any higher than that. How big you may ask? Well, to me it looks like that would be floor((n+1)/2).
• if n is not even, and let's say x is the smallest k where m[n][k]=2ⁿ-1, then m[n][x-1]=m[n][x]-1 =2*m[n-1][x-1] = 2ⁿ-2= 2*(2^n-1-1).

And oh well, that's about it. I've also thought maybe there's some pattern in the binary representation of these numbers, and that could have been worth a shot so :

00000001 00000001 00000001 00000001 00000001 
00000011 00000011 00000011 00000011 00000011 
00000110 00000111 00000111 00000111 00000111 
00001010 00001111 00001111 00001111 00001111 
00001111 00011110 00011111 00011111 00011111 
00010101 00111000 00111111 00111111 00111111 
00011100 01100010 01111110 01111111 01111111 
00100100 10100010 11110110 11111111 11111111 

But you can't really tell too much, the sample size is too small. Although my mind flew off to Sierpinsky's triangle for some reason, probably because I have a not-so-fond memory of it in a situation like this D: .

 

[NoRomanBatmansAllowed]

23 minutes ago, Nineshadow said:

I came across this for the first time a few weeks ago and today it's crossed my mind randomly.

 

Consider a binary sequence of n bits, with all the bits being initially 0. We define an operation FLIP(L,R) which flips all the bits of the sequence with indexes between L and R ( b_i = !b_i for all L<=i<=R). You're asked to determine the number of possible, different sequences that can be generated using exactly k flip operations, modulo a given arbitrary natural number(not necessarily prime). The initial sequence of bits with value 0 isn't considered in this number.

 

The tests themselves are structured with multiple queries, and as far as the limits go :

• 1<=n,k<=300 000
• mod<=10⁹+7
• queries <= 250
• time : 2 sec
• memory : 65536 kbytes

 

Some of my thoughts :

  Hide contents

I'm relatively sure there's some recurrence or dynamic programming or something similar going on here. I'm sure that that the problem is made a bit harder by the fact that the modulo is not necessarily prime, although I haven't found exactly how exactly.

 

So, let's go the usual route. If you consider m[n][k] the number of different sequences of n bits that can be generated with k flips. It would look something like this :

1 1 1 1 1
3 3 3 3 3 
6 7 7 7 7 
10 15 15 15 15 
15 30 31 31 31 
21 56 63 63 63 
28 98 126 127 127
36 162 246 255 255

(matrix results obtained with brute force, pretty sure they're correct)

Some observations, maybe not all that useful :

• m[1][k]=1 for all k
• m[n][1]=n(n+1)/2
• if k is big enough, then obviously m[n][k] = 2ⁿ -1, it can't get any higher than that. How big you may ask? Well, to me it looks like that would be floor((n+1)/2).
• if n is not even, and let's say x is the smallest k where m[n][k]=2ⁿ-1, then m[n][x-1]=m[n][x]-1 =2*m[n-1][x-1] = 2ⁿ-2= 2*(2^n-1-1).

And oh well, that's about it. I've also thought maybe there's some pattern in the binary representation of these numbers, and that could have been worth a shot so :

00000001 00000001 00000001 00000001 00000001 
00000011 00000011 00000011 00000011 00000011 
00000110 00000111 00000111 00000111 00000111 
00001010 00001111 00001111 00001111 00001111 
00001111 00011110 00011111 00011111 00011111 
00010101 00111000 00111111 00111111 00111111 
00011100 01100010 01111110 01111111 01111111 
00100100 10100010 11110110 11111111 11111111 

But you can't really tell too much, the sample size is too small. Although my mind flew off to Sierpinsky's triangle for some reason, probably because I have a not-so-fond memory of it in a situation like this D: .

 

Looks cool. I'm going to have to start learning dynamic programming (I've never heard of it before).

[Nineshadow]

After some unexpected inspiration, I've noticed this :

m[n][3]=C(n,1)+C(n,2)+...+C(n,6)

m[n][2]=C(n,1)+C(n,2)+C(n,3)+C(n,4)

m[n][1]=C(n,1)+C(n,2)

 

I think...that's it?