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

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

Комментарии (6)

Написать комментарий?

Sachit_Jaggi

5 лет назад, # |

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

→ Ответить

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 лет назад, # ^ |

Nice explanation!

Блог пользователя Sachit_Jaggi