# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
cool blog better than the previous one
nor speedrunning top of contributions haha :) Great post (like the others)
man just keep bringing these tutorials man you are the best tutorial writer we have plus you always bring something relevant and new to learn.Much love.
I hope someone overtakes you in the top 10 contributors so that we keep getting norz blogs.
many people have created blogs on dp buts your blogs are just so special why don't you make a blog on dp covering all advance aspects of dp with some good problems attached to that blog that will be helpful in learning intermediate and advance dp
DP as a topic is huge, and it's impossible to cover even half of it (or at least half of what I know about it) in a single blog. I might write something on DP in the distant future, but no promises. I'd recommend learning recursion, reading other tutorials on DP, and solving problems from CSES and AtCoder DP contest.
In the next premutation section
"Note that the smallest number in this sequence that is larger than a_i will be the new element at position i."
is it a_i or a_(i-1) ?
In find kth-next functional graphs,
"Each weakly connected component consists of two parts: a directed cycle and directed trees rooted at distinct vertices in the cycle, directed towards the root (also called reverse-oriented arborescences)."
How come directed trees are also present ? Took example from planet queries I
[2,1,1,4]
cycle for each i
1->2->1
2->1->2
3->1->2->1
4->4
I couldn't find any directed tree here.
Hello nor ,
Thank you very much for such a great Blog.
I had problem understanding in the case of counting derangements using recursion...
Our
recurse()
(in original example it is mentioned as methodD()
) method takes 'N' as input where we have 'N' empty places fill. We also make sure that all the 'N' has one-to-one mapping with the places ( such that there exist one 'i' for which a[i] == i ).when
a[n] = k != n
anda[k]=n
, the problem reduces torecurse(n-2)
, this part is clear. After we make place 'n' on 'k's places and 'k' on 'n's place, rest of the n-2 numbers are still having one-to-one mapping with remaining places to fill.But in the case of
a[k] != n
, we have n-1 places to fill and n-1 numbers , but we don't have one-to-one mapping between them. How can we use samerecurse()
method on remainingn-1
places ?Hello nor I am elaborating further on my doubt,
if we have N=6, and for example we are putting value '3' on the index '6' and trying to count number of derangements for remaining values, (we could pick any value other than '6')
Remaining values = { 1 , 2 , 4 , 5 , 6 } Remaining Indices = { 1 , 2 , 3 , 4 , 5 } ( 6'th index is taken by value '3' ) .
Now, when we put value '6' anywhere in remaining indices. There are two cases, 1) We place value 6 on index 3. 2) We don't place value 6 on index 3.
CASE 1 If we place value 6 on index 3 , then... remaining values = { 1 , 2 , 4 , 5 } remaining indices = { 1 , 2 , 4 , 5 } So, our recurrence is still good to go,,, we can continue with our recurrence.
CASE 2 If we place value 6 on any index other than 3, we have (n-2) such a way to do it, but for example I am just taking randomly index 2, remaining values = { 1 , 2 , 4 , 5 } remaining indices = { 1 , 3 , 4 , 5 }
How can we call our recurrence now ??? there is no one-to-one mapping between remaining values and remaining indices... Please someone help me understand this.
Hello nor, There is one solution here : https://math.stackexchange.com/questions/83380/i-have-a-problem-understanding-the-proof-of-rencontres-numbers-derangements/83433#83433
But there is no proof that says that we can swap values of any two indices and the number of derangements will be same after that. !!!!!
Is there a way to find derangements for values { 1 , 2 , 4 , 5 , 6 } on array of size 5 ?
Thank you, very useful.