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 -

Tags

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).

Soln

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.

5 Likes

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

F -

Tags

Meet in the middle.

Hint 1

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

Soln

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.

6 Likes

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

1 Like

https://codeforces.com/profile/ritik_patel05
Yours?

Please check my code because I cannot understand what I am missing and why? (help will be appreciated)…
https://codeforces.com/contest/1257/submission/64901593

yay spoonfeeding.

3 Likes