Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

redgulli's blog

By redgulli, history, 4 weeks ago, In English,

I have been trying out this problem on Hackerearth.

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/help-ashu-1/

This is my code:

#include<bits/stdc++.h>
using namespace std;


int evencount[400004];
bool A[100001];
int num;
void build(int node,int start,int end)
{
    if(start==end)
    {
        evencount[node]=(A[start]%2==0);
        return;
    }
    int mid=start+(end-start)/2;
    build(2*node+1,start,mid);
    build(2*node+2,mid+1,end);
    int left=2*node+1;
    int right=2*node+2;
    evencount[node]=evencount[left]+evencount[right];
}

void update(int node,int start,int end,int idx,int val)
{
    if(start==end)
    {
        A[idx]=val%2;
        evencount[node]=(val%2==0);
        return;
    }
    int mid=start+(end-start)/2;
    if(idx <= mid)
    {
        update(2*node+1,start,mid,idx,val);
    }
    else{
        update(2*node+2,mid+1,end,idx,val);
    }
    int left=2*node+1;
    int right=2*node+2;
    evencount[node]=evencount[left]+evencount[right];
}

int query(int node,int start,int end,int left,int right)
{
    if(end < left || start > right)
    {
        return 0;
    }
    if(left<=start && end>=right)
    return evencount[node];

    int mid=start+(end-start)/2;
    int p1,p2;
    p1=query(2*node+1,start,mid,left,right);
    p2=query(2*node+2,mid+1,end,left,right);
    return p1+p2;
}


int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>num;
        A[i]=num%2;
    }
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++)
    {
        int q,a,b;
        cin>>q>>a>>b;
        if(q==0)
            update(0,0,N,a-1,b);
        else
        {
            int t=query(0,0,N,a-1,b-1);
            if(q==1)
            cout<<t<<endl;
            else
            cout<<(b-a+1)-t<<endl;
        }
    }
}

I have optimized it as much as I can. It is still giving memory limit exceeded. Where and how can I optimize this code further in terms of memory ?

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

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

Hey!

Random observation based on the problem URL: Have you considered to use Fenwick / BIT tree which requires 4 times less memory?

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

    Some facts about memory limit for this problem:

    Time Limit:	1,0 sec(s) for each input file.
    Memory Limit:	256 MB
    Source Limit:	1024 KB
    

    Why he exceeded 256MB with 4MB Segment Tree?

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

    Well, I don't know about Fenwick trees. But I will give it a shot after learning Fenwick trees. Thanks.

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

You can use fenwick tree for optimizing memory.

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

    Yes, but the question can be solved in segment tree as well, according to the question tag. But I will try Fenwick as well. Thanks.

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

      You can decrease memory usage by this trick: Let your current node be x. Let y = (l + r) / 2. (l and r are your node intervals) Now the left child of node x will be x + 1. And the right child will be x + ((y — l + 1) << 1). The memory usage will be 2n (or 2n — 1). If you wanna know why this works, check cp algorithms segtree section. (The ids of nodes that i explained where all 0_based.)

»
4 weeks ago, # |
Rev. 5   Vote: I like it +16 Vote: I do not like it

I added in your code 3 types of assert: assert_re(bool q), assert_tle(bool q) and assert_mle(bool q). If bool q will be false, solution will be finished with verdicts RE, TLE or MLE and you will see which assert was failed. https://pastebin.com/iAXFHf05

assert_mle(depth <= 20); was failed at line 72, it means, that you have a bug and query function never ends and have infinity recursion calls without return. So, you have a bug in your logic, you should debug it and fix it.

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

    Thanks for your help. Really appreciate it.

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

    There are several compilation flags, which can detect problem without code change:

    Flags

    . Then, if you run original code on sample, you will get following exceptions:

    Exceptions

    Obviously, there is an infinite recursion here.

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

      Awesome. Same result can be given by running in Codeforces Custom Invocation with Clang++17 Diagnostics on sample, but without stack trace.

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

        Clang++17 Diagnostics on following code just write 2:

        UB

        Whereas mine compiler warnings me:

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

      Kind of off-topic, but why -fuse-ld=gold? Does default linker (ld in Linux) have some problem?

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

        Yes:

        Compile without -fuse-ld=gold

        I google it and find this. So I just add this flag to my Makefile)

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I use a superset of your compile flags in my makefile. I never had a problem.

          Makefile

          What platform are you on?

          Also, as per the last comment on your linked thread, it was a bug in G++7 and fixed in all distros a year back. It's weird that you still get that error.

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

            Ubuntu 16.04 LTS

            gcc version 5.5.0 20171010

            Your flags on my computer get this eror:

            Error

            If I set -Wshift-overflow= to 0 or 1 or 2, then I get the same error as in the previous comment.

            My Makefile

            Offtop. MikeMirzayanov, why one dollar in editing comment changes to three dollars in comment? How can I write exactly one dollar?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
              Rev. 2   Vote: I like it +8 Vote: I do not like it

              GCC 7 (7.3.0-16ubuntu3) is still broken on Ubuntu 16.04 and earlier. — Stackoverflow

              This is regarding using UBsan with GCC. This leads me to believe that this bug is unfixable for you till you upgrade your Ubuntu version.

              Conclusion: the alternative linker is necessary for you.

»
4 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Read the comments and the corresponding changes I made to your code. Do reply back if you don't understand the reasoning behind the changes, although I suggest you work them out yourself to understand where you went wrong :)

I submitted the commented code and it got accepted. Also, you can look at my code for reference.

Your code modified
My code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man. I am really new to Segment Tree. Thanks for your help.