715B: Complete The Graph

Consider only edges with weight > 0, if possible to have path < L, bad

Then make each erased edge weight 1, see if it is possible to have a path < L

find edges in the path, increase one erased edge to delta -1 , and other free edges outside path by the same amount

360B: Levko and Array

bsearch on the target c(a), then dp(i) = min steps to keep i constant, and yet satifies c(a) constraint!!!

145B:Lucky Number 2

we can see that the different betwen cnt(47) and cnt(74) is at most 1

if cnt(47) = cnt(74), we can easily constructa 474747, and append attach remainng 4 and 7s

if cnt(47) = cnt(74) + 1, and the base form is 47474, we will attach the remaining 4 and 7s to first 4 and 7

118C:Fancy Number

First, brute force to decide the target digit, sorted by (cost, improvement = (index * improvement or not))

653C:Bear and Up-Down

linear scan to find the first violating pair, we know we will have to switch one of then

each swap we can fix at most 4 bad indices, so we keep track of the first 4 bad inices. brute froce and see if all for are fixed afterwards. This also means answer -1 if we have > 4 bad indices

691C:Exponential notation

string implementation,find the decimal point index , and first non-0 digit index, we can calculate Eb

need to handle the case without the decimal point

665D:Simple Subset

Consider a(i)s > 1, we know that the max subset size is 2 => one even # and one odd number

After that, we consider all a(i) = 1, and find 2 numbers, s.t., a + 1 is prime, b+1 is prime and a + b is prime

we can pre-compute the prime # with sieve

843B:Interactive LowerBound

randomed sample 1000 entries, pick the highest number <= target, and try finding the next.

The probabily that the 1000 entries don’t hit the band = (1 - bandLength/n)^number of pokes => minimal!!!