Discussion @ 1260. Nudnik Photographer @ Timus Online Judge

tbtbtb91 How to slove it?? Any hints? [24] // Problem 1260. Nudnik Photographer 1 Apr 2004 19:16

Gheorghe Stefan Re: How to slove it?? Any hints? [21] // Problem 1260. Nudnik Photographer 2 Apr 2004 02:44

let A[i][j] be the number of i permutations that start with j and we jump 2. The recurrence is:
a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]

tbtbtb91 Re: How to slove it?? Any hints? [19] // Problem 1260. Nudnik Photographer 3 Apr 2004 13:31

I use the same methon...But I got Wa????

timgreen Re: How to slove it?? Any hints? [18] // Problem 1260. Nudnik Photographer 3 Apr 2004 13:35

We can do it more easyly!
Just think of this:
1 2 ... means N - 1;
1 3 2 4 means N - 3;
1 3 5 7...6 4 2 only 1;
1 3 4 2 (only N == 4);
So we can DP;

VladG Re: How to slove it?? Any hints? [16] // Problem 1260. Nudnik Photographer 3 Apr 2004 14:30

test

Pavlov Yuriy Re: How to slove it?? Any hints? [15] // Problem 1260. Nudnik Photographer 3 Apr 2004 20:04

You can using this:

Initilization:
a[1]:=1;
a[2]:=1;
a[3]:=2;

And solve:
a[i]:=a[i-1]+a[i-3]+1;

So, your answer in a[n]

tbtbtb91 Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 3 Apr 2004 20:14

I konw why I was WA...... Very thanks!!!!

Valentin Mihov Re: How to slove it?? Any hints? [4] // Problem 1260. Nudnik Photographer 10 Apr 2004 02:03

Well, actually I decovered this formula after writing brute force algorithm. I am wondering how it could be proven.

Any ideas?

Edited by author 10.04.2004 02:04

Sandro Re: How to slove it?? Any hints? [3] // Problem 1260. Nudnik Photographer 29 May 2004 19:43

But Timgreen had almost proved it.

young master Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 19 Jun 2004 22:06

write the permutations down and look it carefully as hard as you can and you'll find out sth useful for you associated with the informations provided above by all the upper friends...

₦Å_̅Ϊ_̅ύ®@₤ Re: How to slove it?? Any hints? [1] // Problem 1260. Nudnik Photographer 29 Nov 2007 01:41

Can somebody give tests? for exmaple for 6,10,55... Thanks.

manishmmulani 6,10,55 tests // Problem 1260. Nudnik Photographer 2 Jan 2008 01:40

for 6 , ans = 9
for 10, ans = 46
for 55, ans = 1388937263

hello Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 17 May 2004 16:21

I don't understand your formula .
Could you explain ?

Maigo Akisame (maigoakisame@yahoo.com.cn) The proof of a[i]=a[i-1]+a[i-3]+1; [6] // Problem 1260. Nudnik Photographer 24 Aug 2004 20:46

Take i=5 for example

The permutations are:

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 3 2 4 5
1 3 5 4 2

a[i-1] stands for the first four, beginning with '1 2'. If you ignore 1, you have the same prob for N=i-1.
a[i-3] stands for the fifth, beginning with '1 3 2 4'. If you ignore 1, 3, 2, you have the same prob for N=i-3.
And a special case (the last) -- all the odds in increasing order, followed by all the evens in decreasing order. The is what the +1 in the formula means.

Good luck!

Ayhan Aliyev Re: The proof of a[i]=a[i-1]+a[i-3]+1; [1] // Problem 1260. Nudnik Photographer 3 Jun 2006 23:01

thanks for explanation.

it4.kp Another method // Problem 1260. Nudnik Photographer 17 Aug 2006 15:10

I used another method to solve this.

Suppose we have N numbers.
We will care about five possible configurations:

K(n) ... n n-1 ...
T(n) ... n-1 n ...
E(n) ... n-2 n
P(n) ... n n-1
S(n) ... n-1 n

here K(n) is the number of correct configurations of the first type and so on.

It's clear that the answer for N will be K(N)+T(N)+E(N)+P(N)+S(N).

So, what we need to do is understand how to get K(n+1),T(n+1)... from K(n),T(n),...

And it is very easy to see that following is true:

K(n+1) = T(n)
T(n+1) = K(n)+P(n)
E(n+1) = P(n)
P(n+1) = S(n)
S(n+1) = S(n)+E(n)

Ankit Mehta Re: The proof of a[i]=a[i-1]+a[i-3]+1; [3] // Problem 1260. Nudnik Photographer 26 Apr 2012 23:44

I don't know if we can call this a proof. This is an observation I guess.

Maigo Akisame (maigoakisame@yahoo.com.cn) wrote 24 August 2004 20:46

sylap Another idea [2] // Problem 1260. Nudnik Photographer 2 May 2013 19:14

My idea is : (a bit complicated)

definition :

dp[x][0][0] = [...] , x , x-1 , [...]
dp[x][0][0] = [...] , x-1 , x-1 , [...]
dp[x][1][0] = [...] , x , x-1
dp[x][1][0] = [...] , x-1 , x
dp[x][1][0] = [...] , x-2 , x
(dp[x][i][j] is number of sequences satisfying the corresponding rule)

recurrence :

dp[i][0][0] = dp[i-1][0][1];
dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][0];
dp[i][1][0] = dp[i-1][1][1];
dp[i][1][1] = dp[i-1][1][1] + dp[i-1][1][2];
dp[i][1][2] = dp[i-1][1][0];

answer (to be printed is) :

dp[n][0][0] + dp[n][0][1] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]

proof :

left for you :)

Edited by author 02.05.2013 19:18

neko13 Re: Another idea [1] // Problem 1260. Nudnik Photographer 12 Aug 2013 17:24

I have observed the answers.I found that a[i]=a[i-1]+a[i-2]-a[i-5];
I still don't know why!

mjolner Re: Another idea // Problem 1260. Nudnik Photographer 13 Aug 2013 21:37

Above has been shown:
a[i] = a[i-1] + a[i-3] + 1

this holds for each i, then also:
a[i-2] = a[i-3] + a[i-5] + 1

So
a[i-2] - a[i-3] - a[i-5] = 1

and (substitute this result in the first equation)
a[i] = a[i-1] + a[i-3] + a[i-2] - a[i-3] - a[i-5]

which reduces to
a[i] = a[i-1] + a[i-2] - a[i-5]

Zaven Musailov Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 5 Dec 2008 17:56

Can you explain your formul?how should I use it!)

webeseit Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 12 Nov 2018 11:39

cool, note that we can unite 3rd and 4th cases as one case when n >= 4.

ConanKudo Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 14 Jul 2008 22:22

my formula is:
a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1
But i don't understand your formula?
Could you explain??

Edited by author 14.07.2008 22:25

Горыныч Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 9 Apr 2004 18:10

I've solved it with help of asympthotic. Starting from 20 - 25-th member (it can be found recursively) - a[i] ~ a[i-1]*(a[i-1]/a[i-2])

Pegasus Re: How to slove it?? Any hints? // Problem 1260. Nudnik Photographer 1 Sep 2013 16:32

I use dfs to find the regular for some test
n = 1 2 3 4 5 6 7 8 9 10 11
ans= 1 2 2 4 6 9 14 21 31 46 68
then I found f[n] = f[n-1] + f[n-2] - f[n-5]
then I got AC.

Discussion of Problem 1260. Nudnik Photographer