ak3899's blog

By ak3899, history, 6 months ago, ,

link of the problem is : https://www.spoj.com/problems/TPGA/

i am solving spoj problem in which i have to find the rank of the permutations when the integers lexicographically arranged means eg.

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

rank of 132 is 2. now i want to know how can i solve this using binary index tree ,i found this problem on coding portal in which this problem was queued under the Binary Index Problems someone help. give idea at least.

 » 6 months ago, # |   0 Auto comment: topic has been updated by ak3899 (previous revision, new revision, compare).
 » 6 months ago, # |   +3 I got accepted using SegmentTree. Let n number of items in permutation. Just look on the first item of permutation a1, we can say that before current permutation there are (a1 - 1)·(n - 1)! permutations. Then we need to erase item a1 and continue from next item. SegmentTree or Fenwick can answer on question "how many not erased items before ai?" in O(log(n)): for each item we set 0 when it erased and 1 when it not erased. Examplea = [3 1 2] 0 1 2 3 -------- 0 1 1 1 a[1] = 3. sum(0, 3-1) = 2. Add 2 * (3-1)! = 4. Erase 3. 0 1 2 3 -------- 0 1 1 0 a[2] = 1. sum(0, 1-1) = 0. Add 0 *(2-1)! = 0. Erase 1. 0 1 2 3 -------- 0 0 1 0 a[3] = 2. sum(0, 2-1) = 0. Add 0 * (1-1)! = 0. Erase 2. Total 4 permutations before given permutation, so index of given permutation is 5.