I’ve solved DOTAA with time complexity of O(n*m)
Is there a better method?
Comment says, we can solve using some STL container, which one is it?
I’ve solved DOTAA with time complexity of O(n*m)
Is there a better method?
Comment says, we can solve using some STL container, which one is it?
O(n *m)?
pre<
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int nh, twr,dmg;
cin>>nh>>twr>>dmg;
int i,arr[nh],ans=0;
for(i=0;i<nh;i++)
{
cin>>arr[i];
ans+= (arr[i]/dmg );
if(arr[i]%dmg==0)
ans-=1;
}
if (ans>=twr)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}>
I don’t know the complexity of my code (lolmenub XD). I think O(T*n)? It ran in 0.04 sec.
What did you do? Did you also do something similar? Or something else?
(BTW : Dota is lyfff. Dotaa is louvvvvv <3333333 )
@vijju123’s approach is correct in \mathcal{O}(n) and there cannot be any better/faster way. If I had to guess, I would say the comment on the SPOJ problem page refers to using a priority queue to always bring forward the hero with the highest health to tank the tower damage for each tower, but that would be \mathcal{O}(n+m\;log\;n). Anyway, always good to see another DOTA player
You play dota too???!!! Niceeeee!!! XD
LyzzJk - Online C++0x Compiler & Debugging Tool - Ideone.com link to my very naive solution, you’re approach is good, didn’t thnk it that way!
Thank you, I’m implement this!
I see, so you ran a full check. That’s nice, had the Q asked something else which needed the current health of heroes after every step, your approach would score way higher than mine