Обсуждение @ 1260. Фотограф-зануда @ Timus Online Judge

tbtbtb91 How to slove it?? Any hints? [24] // Задача 1260. Фотограф-зануда 1 апр 2004 19:16

Gheorghe Stefan Re: How to slove it?? Any hints? [21] // Задача 1260. Фотограф-зануда 2 апр 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] // Задача 1260. Фотограф-зануда 3 апр 2004 13:31

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

timgreen Re: How to slove it?? Any hints? [18] // Задача 1260. Фотограф-зануда 3 апр 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] // Задача 1260. Фотограф-зануда 3 апр 2004 14:30

test

Pavlov Yuriy Re: How to slove it?? Any hints? [15] // Задача 1260. Фотограф-зануда 3 апр 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? // Задача 1260. Фотограф-зануда 3 апр 2004 20:14

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

Valentin Mihov Re: How to slove it?? Any hints? [4] // Задача 1260. Фотограф-зануда 10 апр 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] // Задача 1260. Фотограф-зануда 29 май 2004 19:43

But Timgreen had almost proved it.

young master Re: How to slove it?? Any hints? // Задача 1260. Фотограф-зануда 19 июн 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] // Задача 1260. Фотограф-зануда 29 ноя 2007 01:41

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

manishmmulani 6,10,55 tests // Задача 1260. Фотограф-зануда 2 янв 2008 01:40

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

hello Re: How to slove it?? Any hints? // Задача 1260. Фотограф-зануда 17 май 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] // Задача 1260. Фотограф-зануда 24 авг 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] // Задача 1260. Фотограф-зануда 3 июн 2006 23:01

thanks for explanation.

it4.kp Another method // Задача 1260. Фотограф-зануда 17 авг 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] // Задача 1260. Фотограф-зануда 26 апр 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) писал(a) 24 августа 2004 20:46

sylap Another idea [2] // Задача 1260. Фотограф-зануда 2 май 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] // Задача 1260. Фотограф-зануда 12 авг 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 // Задача 1260. Фотограф-зануда 13 авг 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? // Задача 1260. Фотограф-зануда 5 дек 2008 17:56

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

webeseit Re: How to slove it?? Any hints? // Задача 1260. Фотограф-зануда 12 ноя 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? // Задача 1260. Фотограф-зануда 14 июл 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? // Задача 1260. Фотограф-зануда 9 апр 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? // Задача 1260. Фотограф-зануда 1 сен 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.

Обсуждение задачи 1260. Фотограф-зануда