aya_cool's blog

Playrix Codescapes Cup Problem D
By aya_cool, history, 8 years ago, In English

Can someone explain me how to solve problem D of playrix cup using meet in the middle algorithm. Link to problem http://mirror.codeforces.com/contest/799/problem/D

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

Do a binary search on answer.

Now, how do we check, whether it is possible to take X extensions in order to satisfy the problems condition?

Obviously, we'll consider only taking the greatest X extensions. Use Meet-In-The-Middle. Divide the greatest X extensions into two same-sized multisets A and B (the way you divide doesn't matter).

For each multiset count the following value — maxa[val] is the maximum product of all extentions you spend on extending the first side, while all other extensions are spend on the second side (we are only considering extensions in set A). We can brute forcing all the masks in A. Calculate maxb[] in the same way. Use map <  >  to store this data.

Now let's iterate over maxa[]. Consider having maxa[p] = q. Now we have to check, whether it is possible to take r extensions for the first side and s extensions for the second size (from the multiset B), so that a·p·r ≥ x and b·q·s ≥ y. We check this by doing a binary search over a maxb[].

So the overall complexity is — (which is actually faster than it sounds, because we don't consider MAX_ANS elements on every binary search step).

I guess, that this solution is not intented...

→ Reply