dingshu's blog

By dingshu, 7 years ago, In English,

Let's divide this queue into to 2 parts: 1... k and k + 1... n.

It's obvious that pi ≤ k while i ≤ k, pi > k while i > k.

So the answer to the part of pk + 1... n is (n - k)n - k.

Image a tree with k vertexes. The number of those trees is kk - 2. (Cayley trees)

Choose a vertex to be root, there are k ways.

Set pi = fatheri in the tree. And for the root, set proot = 1.

It's easy to find p1... k satisfied the problem.

So answer is kk - 1(n - k)n - k.

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
7 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Maybe kk - 1(n - k)n - k?

ADD: It's OK now.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thx, I made a mistake just now. :)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Because k <= 8, it could be solved by backtrack too.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i cann't understand the k^(k-1) ?? if input is 3 3 so all of the number are e.g:(p1,p2,p3),(2,1,1),(2,3,1),(3,2,1),(3,3,1),(3,1,1). can you tell me some else?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Actually, first number in a triple can be equal to one. Therefore, we have got (1,1,1), (1,3,1), (1,1,2), (2,1,1), (2,3,1), (2,1,2), (3,1,1), (3,3,1), (3,1,2). That is, answer=9.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      thank you very much~ ^-^

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm confused about whether (1,1,1),(1,3,1),(1,1,2) satisfy the restriction 3: "When the penguin starts walking from house number 1, he can get back to house number 1 after some non-zero number of walks from a house to a house."?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ohh...from house 1 to house 1, though we have no move, that's also 1 step.