Discussion @ 1260. Nudnik Photographer @ Timus Online Judge

How to slove it?? Any hints? tbtbtb91 1 Apr 2004 19:16

Re: How to slove it?? Any hints? Gheorghe Stefan 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]

Re: How to slove it?? Any hints? tbtbtb91 3 Apr 2004 13:31

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

Re: How to slove it?? Any hints? timgreen 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;

Re: How to slove it?? Any hints? VladG 3 Apr 2004 14:30

test

Re: How to slove it?? Any hints? Pavlov Yuriy 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]

Re: How to slove it?? Any hints? tbtbtb91 3 Apr 2004 20:14

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

Re: How to slove it?? Any hints? Valentin Mihov 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

Re: How to slove it?? Any hints? Sandro 29 May 2004 19:43

But Timgreen had almost proved it.

Re: How to slove it?? Any hints? young master 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? ₦Å_̅Ϊ_̅ύ®@₤ 29 Nov 2007 01:41

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

6,10,55 tests manishmmulani 2 Jan 2008 01:40

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

Re: How to slove it?? Any hints? hello 17 May 2004 16:21

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

The proof of a[i]=a[i-1]+a[i-3]+1; Maigo Akisame (maigoakisame@yahoo.com.cn) 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!

Re: The proof of a[i]=a[i-1]+a[i-3]+1; Ayhan Aliyev 3 Jun 2006 23:01

thanks for explanation.

Another method it4.kp 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)

Re: The proof of a[i]=a[i-1]+a[i-3]+1; Ankit Mehta 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

Another idea sylap 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

Re: Another idea neko13 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!

Re: Another idea mjolner 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]

Re: How to slove it?? Any hints? Zaven Musailov 5 Dec 2008 17:56

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

Re: How to slove it?? Any hints? webeseit 12 Nov 2018 11:39

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

Re: How to slove it?? Any hints? ConanKudo 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? Горыныч 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])

Re: How to slove it?? Any hints? Pegasus 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