codeworrior's blog

By codeworrior, 7 years ago, In English,
i  m doing this (spoj SUBSEQ) problem on spoj...my algo is n*logn bt its giving me TLE ...hw this problem is to b solved ..i m using map...
here is the code...

int main()
{
     map<int,int>list;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        list.clear();
        int n;
        scanf("%d",&n);
        int tmp;
        VI a,sum(n+1);
        a.pb(0);
        FOR(i,1,n)
        {
            scanf("%d",&tmp);
            a.pb(tmp);
            sum[i]=tmp+sum[i-1];
            list[sum[i]]++;
        }
        list[0]++;
        int64 ans=0;
        int val;
        for(int i=n;i>=0;i--)
        {
            list[sum[i]]--;
            val=list[sum[i]-47];
            if(val>0)
                ans+=val;
        }
        printf("%lld\n",ans);
    }
}
 
 
 
 

7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
here is my code tht i chnged a bit still getting TLE
int main()
{
  map<int,int>list;
int t;
scanf("%d",&t);
while(t--)
{
list.clear();
int n;
scanf("%d",&n);
int tmp;
VI sum(n+1);
a.pb(0);
list[0]++;
int64 ans=0,val;
FOR(i,1,n)
{
scanf("%d",&tmp);
sum[i]=tmp+sum[i-1];
            val=list[sum[i]-47];
ans+=val;
list[sum[i]]++;
}
printf("%lld\n",ans);
}
}



7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
here is the code ..previous one was incorrect..
int main()
{
  map<int,int>list;
int t;
scanf("%d",&t);
while(t--)
{
list.clear();
int n;
scanf("%d",&n);
int tmp;
VI sum(n+1);
list[0]++;
int64 ans=0,val;
FOR(i,1,n)
{
scanf("%d",&tmp);
sum[i]=tmp+sum[i-1];
            val=list[sum[i]-47];
ans+=val;
list[sum[i]]++;
}
printf("%lld\n",ans);
}
}

  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
     val=list[sum[i]-47];

    If the map doesn't contain (sum[i]-47), then it is added in this line, so the size of the map increases and it affects the constant in the complexity of your solution.
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i got AC in 7.44 sec.. jst took the declaration of map inside the while loop and removed list.clear() statement..

bt the bst solution in this prob is 0.66 sec..hw to achieve time of under 2 sec...
thnx in advance...
  • 7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    map is very slow..you can write a hash table..
    • 4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please suggest a good implementation of a hash table?(I am not aware of it if it's in the STL; even if it is, I would like to have a custom hash)

      • 4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Good day to you,

        Sure, there is hash table in STL [C++], called "unordered_map" (which works fine without custom hash for types like int/long long/string/...).

        Their hash works pretty well, yet it is true that anti-hash tests can be so some precautions could be made.

        First: (Easier & yet not what you desired) is playing with max_load_factor().

        Second is making your own custom hash (as you sugested) which can be done by — for example — structure with "operator ()".

        Here you can refer to accepted code using what I suggested:

        24> The structure

        25> The stl-map itself

        28> First method

        Hope it was at least a little-bit helpful

        Good Luck & Have nice day!

        ~/Morass

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please explain me your logic ? I am getting WA bcoz my code works good only for positive integers :')