notred's blog

By notred, history, 2 months ago, ,

I used API to fetch my first contest's details, and this came The initial rating is shown to be 1200, is this some bug or has the change happened?

• +98

By notred, history, 11 months ago, ,

You are given a permutation of the n numbers 0, 1, 2, ...., n-1. It is required to sort the permutation in increasing order. The only operation allowed on the permutation is to swap the ith element with the jth element, for any 0 <= i < j < n. Each number i has an associated weight w_i, which is a positive integer. You are also given n-1 positive integers d_0, d_1, .., d_{n-2}, where d_i is the "distance" between the ith and (i+1)th element in the sequence. The distance between the ith and jth element, d_{ij} for i < j, is defined to be d_i + d_{i+1} + ... + d_{j-1}.

The cost of swapping the ith element with the jth element is d_{ij} multiplied by the sum of weights of the two numbers that are swapped. Basically, it is the distance by which the objects are moved multiplied by their weights. In such a swap both the ith and jth element are moved by a distance d_{ij}, other elements remain where they were.

You have to find the minimum total cost of swaps required to arrange the permutation in increasing order. Any help would be appreciated..

• -29

By notred, history, 13 months ago, ,

How to efficiently calculate the value of $\frac{3^{n}-1}{2}$ modulo an even number $p$, when the bound on $n$ is up to $10^{18}$ and $p$ is up to $10^9$?