765D:Artsem and Saunders

If h and g exist, what properties can we infer?!!!

f(f(x)) = h(g(h(g(x)))) = f(x)

i.e., for all values of f(x), it must be a stable point, i.e., f(vfx) = vfx

Now we just need to construct a solution to prove that as long as f(vfx) = vfx for all vfx presented, we can find g, and h

m >= number of distinct f(x), otherwise, we will have 1 m mapped to 2 f(x)

m <= number of distinct f(x), because for each stable point we discovered, we can assign an m value

Therefore, m = distinct values of vfx. So we define g1(vfx) = index(vfx), and h(index(vfx)) = vfx at that index, i.e. g1 is the inverse of h, and then g = g1 * f

h(g(x)) = h * g1 * f(x) = f(x) 

g(h(mx)) = g1 * f(h(mx)) = g1 * f(vmfx)  = g1(vmfx) = index of(vmfx) = mx

When implementing, we can just interation all vfx values from 1 to n, if f[vfx] = vfx, we know it is a stable point, and thus we can safely include that in the final answer, because our condition requires only vfx are stable points of f.

768C: Jon Snow and his Favourite Number

I realize that XOR itself is reversible operation, so I spent too much time finding a sequence of actions than can save some sorting work!!!

Instead, if you pay attention to the input constraint, the values are only 10^3, therefore, instead of sort the input array directly, we can just keep track of distinct values and their numbers, and brute force simulate the process. Overall run time is O(k * 10^3 * 2), which is enough is for its 4 sec run time bound

768D: Jon and Orbs

Consider p=1000, q =1000, this is the max number of days we possible need to calculate

Pr(day, collected) = Pr(on day -1, pick within collection) * Pr(day - 1, collected) + Pr(outside collection) * Pr(On day -1, pick outside collected - 1, collected - 1)

When p, q = 1000, we can calucate to know day <= 1000 for sure!!!

Therefore, we just calculate all probablilites with DP (standard coupon collector problem), for each queries, we can just do a linear search on Pr(day, k)