D: Yet Another Monster Killing Problem Codeforces how to solve it?

Problem - https://codeforces.com/contest/1257/problem/D
My solution - https://codeforces.com/contest/1257/submission/64891555 (Got tle, obviously)

My approach-

  1. Sort the power array of heroes.
  2. Iterate from first to last on the monsters
  3. While calculating which monster to choose, I am applying a binary search to find index of heropower>= powerofMonster.
  4. Then I iterate all the vertices after that in linear time and choose the one which will kill maximum monsters.

Any help how can I optimize my approach further or would like to know how did you solve it?
I checked the submissions mostly I found out the segment tree approach but I don’t know it.

Would like to know your creative approach.
Thank you :slight_smile:

1 Like

I am also waiting for the tutorials. whats ur cf handle btw???

1 Like

Does anyone know how to add inline spoilers?

D -


Two pointers with greedy.

Hint 1

Precompute what can be the maximum power monster you can get if you want to use it for X days. Can be done in O(n).


Instead of binary search, find how far you can go from the present vertex with a single monster. Can be done by maintain segment max and using the above array. Greedy - Go as far as you can.
Use two pointers for segments.
Answer is no of segments found.

No soln

Only if maximum of power of mosters > maximum power of all heros.


Can You explain the solution of problem F, same contest…

F -


Meet in the middle.

Hint 1

Brute force for first 15 bits.
Separately Brute force for last 15 bits.
Then combine results.


Let’s assume that no of on bits finally be x.
Then for each bitmask of first 15 bits, we know how much bits of each element we need for the last 15 bits. Use a map of vectors to find.


Loved it bro… had watched tags only, will try it again now.

1 Like


Please check my code because I cannot understand what I am missing and why? (help will be appreciated)…

yay spoonfeeding.