AtCoder Contest 186

Problems I could not solve -


    Reason : Could not observe pattern => Sort the list then observe.


    Reason : Missing Concepts => Congruence Modulo, Solving Linear Congruences, Extended Euclid’s Algorithm

    Congruence Modulo is basically two integers which give the same answer when taken the mod of by some integer X. For example, if A mod X = 1 and B mod X = 1, then we say A ≡ B mod X

    There are N chairs, we are at S chair from start and can jump K chairs. To reach the first chair in x moves, => S + xK must be equal to 0. => S + xK = 0. => (S +xK) % N = 0 => S + xK ≡ 0 % N (from congruence modulo concept) => Kx ≡ -S % N => Kx ≡ (N-S) % N This is a linear congruence of the form Ax ≡ B % N which can be solved as follows ->

    a. There is a solution iff B % gcd(A,N) = 0. b. There are gcd(A,N) solutions seperated by N / gcd(A,N)

    Let gcd(A,N) be g. Since g must divide A, B and N let, A’ = A/g, B’ = B/g, N’ = N/g. Now the equation becomes => A’x ≡ B’ % N' Since g was the gcd of A and N and we divided A and N by g, hence the gcd of A’ and N’ must be 1. Hence, x = (A’’ * B’) % N’ where A’’ is the inverse modulo of A’ mod N'.

    We can use the extended euclid’s algorithm to find inverse modulo. From extended euclid’s algorithm, we can find integers x and y such that for integers a and b, ax + by = gcd(a,b)

    Let a = A’ and b = N’, and since gcd(A’, N’) = 1, we can write, A’x + N’y = 1

    We can say that, A’x + N’y ≡ 1 % N' => A’x ≡ 1 % N'

    Which basically means that the x co-efficient returned by euclid’s extended algorithm must be multiplied to our ans.

    Hence, final ans = (B % N * x) % N;


    Reason : Missing Concept => Fenwick Trees

    TBF I do understand the logic on how to solve this, but can’t wrap my head around on why and how to use fenwick trees to arrive at the solution. Will try this later.