try_kuhn's blog

By try_kuhn, 3 years ago, translation, In English

[contest:329695]

Editorial in PDF:

https://drive.google.com/file/d/1KL723lzYE8tVlgIUveMt2lSWDbd4nccv/view?usp=sharing

[problem:329695A]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695B]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695C]

Task author: try_kuhn

Translate author: MatesV13

Solution author: Gareton

tutorial
code

[problem:329695D]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695E]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695F]

Task author: try_kuhn

Translate author: MatesV13

Solution author: Gareton

tutorial
code

[problem:329695G]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695H]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695I]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn

tutorial
code

[problem:329695J]

Task author: try_kuhn

Translate author: MatesV13

Solution author: try_kuhn, xyz.

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

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

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

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

Can someone please explain to me Problem C solution.I was trying to relate it to a Standard P&C problem of finding the rank of a word in a dictionary like if $$$a_i$$$ is $$$!= i$$$ then the total possible ways of arranging $$$n-i$$$ numbers is $$$(n-i)!*i$$$ and for the whole array it will be the summation of this.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Okay, I'll try. Imagine that we have counted the number of permutations that are lexicographically smaller than the given one. Then the answer will be cnt + 1. We will process the permutation from left to right. From the definition of a lexicographically smaller permutation, a permutation a is less than a permutation b if the first m numbers of these permutations are the same, and the (m + 1) th number of a permutation a is less than the (m + 1) th number of b permutation. Let's say we are now at position i. Consider all the numbers of this permutation that are to the right of the current position i. Then it follows from the definition above that if we put a number Pj at position i such that Pj < Pi and j > i, this permutation will be lexicographically smaller. Then if we know the number of such Pj's, call it k, this will add k * (n — i)! to the answer, since if Pj < Pi, the arrangement of the remaining (n — i) elements is not important to us. To find k, you can use, for example, a data structure such as the Fenwick tree.

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

      Ok now i understood what was the use of fenwick tree in this question.Thanks for help.