p250, given clock hands for hh and mm, after rotating some degree, find out the earliest possible time that the measure is taken.
A natural solution is to enumerate all possible rotations. One catch is that the problem mentioned that measure is taken on a 30deg mark. So rotation is from 0 to 360 with increment of 30. One more observation is that the smallest (hourDeg,minuteDeg) pair is the desired answer. Got this problem correct, after struggle with a test case that require a rotation of 6 deg. Luckily there is an announcement just in time to clarify this.
Lesson: work out formula and multipliers on paper before typing. Spent too much time running testcase to get correct multiplier.
p550, a problem with subtle statement. A shop owner has some number of swords for sale. Each customer has several (hour,price,probability) triples. The owner wants to maximize the total price of sale. The restriction is that each hour at most one customer may have the hour in its list, and there are 24 hours.
A DP solution is almost obvious:
use mask 1<
=recurse(sword, time+1, mask) if the customer has time in its list already appear in mask
=(1-p)*recurse(sword,time+1,newmask) + p*recurse(sword-1,time+1,newmask)
that is, customer show up with probability p, and with (1-p) it no show. The trick, however, is to keep newmask=mask if there is no further event with the current customer. Actually, this is what differentiates a bmerry's solution and my offline solution.
Notice that dp[sword][time][mask] may have up to 24*24*2^24 size and this is too much. However, if we keep mask unchanged if no more event for the same customer, then mask has at most 2^12 instead of 2^24.
p1000: opened the problem but didn't think too much about it yet.
Not too hard either, actually this is the first time I think I can do a 1000 problem.
Three animals, L, F and R each have some possible start positions in a maze. F<=20, R<=20. maze cells are marked as 'L','F','R','#' for wall, '.' for empty. maze size is at most 50x50. L,F,R each choose start position uniformly and randomly. Find a maze cell as meet point so as to minimize the total expected move distance.
For each pair of F pos, R pos, 20x20x2500(cells)x2500(bfs)=2x10^9, try every cell as a meeting point, do bfs to find distance to all 'L' marks.
No, actually 2x10^9 is too slow. looked at rng_58's code and the solution runs in 20x20x2500xlog(2500)=2x10^7 roughly.
The idea is to loop each F and R pair as before. Then in each iteration, we can compute shortest path via bfs from current F and current R. Now each cell can be reached at dist=d(cell,currF)+d(cell,currR). We also know that a neighboring cell can be reached at d+1 provided that it is not '#'. Now use a priority_queue to compute min dist for each cell, and update dist(F,R,L) if that cell is an 'L'. Accumulate dist(F,R,L) to num. And deno is size(F) x size(R) x size(L).
A potential catch is that num might be larger than MAX_INT, as the path may wind several times because of '#'. So use long long.
This time p500 and p1000 both look doable, although it is much harder to actually get it.
No comments:
Post a Comment