codeworrior's blog

spoj subseq
By codeworrior, 14 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);
    }
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
14 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);
}
}

→ Reply
  • 14 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.
    → Reply
14 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...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    map is very slow..you can write a hash table..
    → Reply
    • 7 years 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)

      → Reply
      • 7 years 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

        → Reply