SPOJ problem, DOTAA

general
1

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?

2

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 )

2 Likes
3

@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 :wink:

2 Likes
4

You play dota too???!!! Niceeeee!!! XD

5

http://ideone.com/LyzzJk link to my very naive solution, you’re approach is good, didn’t thnk it that way!

6

Thank you, I’m implement this!

7

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 :slight_smile:

1 Like