Riyuzak251097's blog

Question Asked in Hackerearth October easy challenge : Mojtaba and Construction camp I
By Riyuzak251097, history, 6 years ago, In English

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

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

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

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

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

    Thanks xyloto, this was really helpful in understanding the approach

    → Reply