| Show all threads Hide all threads Show all messages Hide all messages |
| Don't waste your time if you can't solve this problem | mksdbk | 1260. Nudnik Photographer | 16 Dec 2021 21:09 | 1 |
The DP version actually harder than you think. The solution with magic formula is disappointing. Go solve other problems and come back later.
The score of problems are calculated by number of accepted solutions, and some problems are very popular and people find out answers and send ready solutions. |
| How to slove it?? Any hints? | tbtbtb91 | 1260. Nudnik Photographer | 12 Nov 2018 11:39 | 25 |
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] I use the same methon...But I got Wa???? 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; 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] I konw why I was WA...... Very thanks!!!! 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 But Timgreen had almost proved it. 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... Can somebody give tests? for exmaple for 6,10,55... Thanks. for 6 , ans = 9
for 10, ans = 46
for 55, ans = 1388937263 I don't understand your formula .
Could you explain ? 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! 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) I don't know if we can call this a proof. This is an observation I guess. 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! 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 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! 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] Can you explain your formul?how should I use it!) cool, note that we can unite 3rd and 4th cases as one case when n >= 4. 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 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]) 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. |
| Explanation | naik | 1260. Nudnik Photographer | 11 Oct 2014 23:40 | 1 |
This problem solved with the left edge.
We look for position of "2".
We have three cases:
1) 12***** - "2" in the second position
2) 1*2**** - "2" in the third position
1**2*** - "2" in the fourth position is impossible
1***2** - "2" in the fifth position is impossible
3) 1******2 - "2" in the last position is possible (the one special case).
For example: 1357642
For each case find sub-task:
1) a[i-1]
2) is NOT a[i-2]
For 1*2**** there can only be one 132****, more accurate 1324***.
Therefore is a[i-3].
3) is 1
Recurrent expression: a[i] = a[i-1] + a[i-3] + 1.
And a precalculation:
a[1] = 1
a[2] = 1
a[3] = 2
A some answers to compare:
a[4] = 4
a[5] = 6
a[6] = 9
a[7] = 14 |
| Precalc? | Arseniy | 1260. Nudnik Photographer | 12 Oct 2013 00:28 | 1 |
|
| my idea | yuanyuan | 1260. Nudnik Photographer | 21 May 2013 12:58 | 4 |
You can search some small test data, then the solution is here:
For f[n], there're three ways to construct it.
Put 2 onto 2nd position, then it's f[n-1];
Put 3 onto 2nd position, put 2 onto 3rd position. This is
f[n-3]! (You must put 4 onto 4th position)
The last condition contains only one possible way like that (first odd, then even)
13578642
So f[n]=f[n-1]+f[n-3]+1. Good Job!You're quite clever! Pal, you must have pains in eggs..... Really nice! How you get that, really smart! |
| A little typo (: | Ivan Nikulin | 1260. Nudnik Photographer | 26 Dec 2012 21:34 | 1 |
Dear administrators, could you please fix one little typo?
"of his big family", not "if his big family" |
| It's nice problem | Qodirov Nodir [ Tashkent U of IT ] | 1260. Nudnik Photographer | 12 Jan 2012 21:07 | 2 |
1
1
2
4
6
9
14
21
31
46
68
100
147
216
317
465
682
1000
1466
2149
3150
4617
6767
9918
14536
21304
31223
45760
67065
98289
144050
211116
309406
453457
664574
973981
1427439
2092014
3065996
4493436
6585451
9651448
14144885
20730337
30381786
44526672
65257010
95638797
140165470
205422481
301061279
441226750
646649232
947710512 |
| Test Cases Here :-) | Varun Sharma | 1260. Nudnik Photographer | 26 Apr 2009 05:38 | 1 |
50 205422481
51 301061279
52 441226750
53 646649232
54 947710512
55 1388937263
Edited by author 03.11.2010 09:06 |
| No subject | saba | 1260. Nudnik Photographer | 29 Nov 2007 01:27 | 3 |
4321_ is it the answer, too? for (i=6; i<=60; ++i) M[i]=M[i-1]+M[i-2]-M[i-5];
Good luck
Edited by author 13.06.2007 12:47 No. first symbol must be 1! |
| I got AC | Тёма и Серёжа | 1260. Nudnik Photographer | 28 May 2004 19:39 | 1 |
I got AC Тёма и Серёжа 28 May 2004 19:39 If you want to know how to solve it, write me on shteynerserg@mail.ru |
