Please help me with this not able to find anything after days of thought

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

question Educational Codeforces Round 76 (Rated for Div. 2) D-Yet Another Monster Killing Problem

I am not able to understand which test case is failing any testcase would be highly helpful ..

I have put the following conditions *if maximum power of hero is less than maximum power of monsters then directly print -1 and exit

*else answer exists we iterate throughout and we create the bst array which is as described in the editorial.Using which we check the 2 conditions :-

--->if maximum in a our range is greater than our hero's power then we break and add a count to our days

--->if we have reached the hero with highest endurance and have exhausted him too then we again break and add a count to our days

I believe this covers all the possibilities ..

please help me .

Thanks in Advance

EDIT -- Now it is working

GUYS IT IS NOW WORKING THE ERROR WAS THAT I HAD INCREMENTED THE INDEX OF HEROES ONLY BY 1 EACH TIME WHICH DID NOT COVER ALL THE CASES. I HAD TO INCREMENT THE INDEX OF HEROES TILL I FOUND ONE WITH HIGHER ENDURANCE.

THANKS A LOT EVERYONE FOR YOUR REPLIES.

NEW SUBMISSION -- WORKING

OLD SUBMISSION

I HAVE UPLOADED THE CHANGES YOU CAN SEE

Comments (6)

Write comment?

Sachit_Jaggi

5 years ago, # |

Auto comment: topic has been updated by Sachit_Jaggi (previous revision, new revision, compare).

→ Reply

masaow

I have implemented the same approach and got it accepted. The basic idea being start with minimum endurance(1) and try to increase it until the power of the hero is sufficient enough to kill the target monster and if u are not able to find any such endurance of positive length simply print -1 and terminate the program. U can find my solution here. 67199296 https://mirror.codeforces.com/contest/1257/submission/67199296

lafifi

This is the same approach I used,maybe hearing my idea can help you somehow :) What I did was I had the heroes as pairs (Strenght, Endurance) and I sorted this, also I had an array of the maximum endurance for every range [i, m — 1]. What I did was the same as you for going trought the monsters and updating the maximum (Most Powerful Monster). But the way I looked for a heroe that had Stength >= Most Powerful Monster and Endurance >= The number of monsters I was killing with this Heroe was:

I got the first pair of my heroes that had Stenght >= Most Powerful Monster, I did this using lower bound wich gave me the position of the first heroe with <= Most Powerful Monster. But since I only wanted greater or equal I had to move one position forward in case the Stenght in that postion was lesser.
After that, I knew that I had to look for the endurance of heroes between [pos, m -1] and in case there exist at least one with Endurance >= The number of monsters I was killing with this Heroe, there was an answer. And you could do this by looking at your precalculated array that gives you the maximum endurace for a range [pos, m — 1]
In case I found a heroe I can use, I can try to kill more monsters, for that you just update the maximum power of a monster in the range I have being working on (Maximum = max(Previous Monsters I've killed, New monster I want to kil) ) and just repeat the process. When you cannot keep doing that then you will have to add a move.

This is my submission: https://mirror.codeforces.com/contest/1257/submission/69544960 , hope it can help you! :)

snest21

5 years ago, # ^ |

Nice explanation!

Sachit_Jaggi's blog