Entries from 2016-02-08 to 1 day
3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…
I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…
Many people are familiar with hash algorithms on string because they are easy to write. However, not many are really aware of the probability of collision. Like me, I had always thought the probability of collision is ( 1 / MOD ), and I ha…
Fast fourier transform can be applied on multiplication of polynomial functions, giving O( N lgN ) time complexity. One of the most common usage is for fast multiplication on big numbers. It exploits the property of the complex roots of un…