Jugo's blog

By Jugo, 5 days ago, translation, In English

Summer programming olympiad #1

Editorial in PDF:

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

329695A - Strange message

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695B - Bunker code

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695C - Loss of the number

Task author: Jugo

Translate author: MatesV13

Solution author: Gareton

tutorial
code

329695D - Mysterious pen

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695E - Under fire again

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695F - Preparation for the hit

Task author: Jugo

Translate author: MatesV13

Solution author: Gareton

tutorial
code

329695G - Sudden shotdown

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695H - Implementation of the plan

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695I - Final battle

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo

tutorial
code

329695J - Afterword

Task author: Jugo

Translate author: MatesV13

Solution author: Jugo, xyz.

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 days 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.

  • »
    »
    2 days 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.