Блог пользователя Riyuzak251097

Question Asked in Hackerearth October easy challenge : Mojtaba and Construction camp I
Автор Riyuzak251097, история, 6 лет назад, По-английски

Hi everyone. I am facing difficulty in understanding the editorial for the third question asked in Hackerearth October easy challenge 2018. It would be very helpful if someone tells me how to approach this problem and suggest where problems similar to this can be found

Link for the Question

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Riyuzak251097 (previous revision, new revision, compare).

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Let's fix a single number (say i) and count how many times it occurs in the same position across two distinct permutations. Let's say we consider two permutations P1 and P2 (of size n).

P1 and P2 both contain our number i in the same position.

There are n places where i can occur. Remaining places are (n — 1) where we are free to arrange the remaining (n — 1) numbers.

Number of ways we can arrange (n — 1) numbers in P1 and P2 = (n — 1)! * (n — 1)!.

This however also counts arrangements in which P1 = P2. So we need to subtract all such arrangements. P1 can be formed in (n — 1)! ways. In each one of these ways, we can have P1 = P2. Therefore, duplicate arrangements = (n — 1)!.

Total arrangement where number i is fixed in one place = (n — 1)! * ( (n — 1)! — 1)

Number i can occur in n places

Total arrangement where number i occurs in the same place = n * (n — 1)! * ( (n — 1)! — 1)

We have n choices for our number i (1 ,, n)

Total = n * n * (n — 1)! * ( (n — 1)! — 1)

We need to find unordered pairs, so we simply need to return Total / 2. This last part I will leave it for you to figure out.

→ Ответить