Forum

Post 29.04.2013   # 1
Subject Problem 500

The first part of the problem was to generate the array coins. Than starts the interesting part. If you've never solved a problem where you were asked to find a sum on an interval (where the sum on that interval can change) faster than in linear time than this problem must have looked like hell to you . Lets assume you have some data structure to do this for you in logarithmic time.

-Update  an interval [a,a] by value, meaning array[a] += value 

-Answer( a.k.a. Query ) an interval [a,b] for the total sum on that interval.

Now in our problem you need to iterate over the array coins[], for each value coins[i] add to the final result the sum on interval [0,coins[i]-1] and afterwards update the interval [coins[i],coins[i]] by the value coins[i]. This approach has complexity O(N*logN) where N is the number of elements in coins. 

There are data structures that can do update and query on an interval in logarithmic time, some of which are easier to code than others. Actually, almost any kind of binary tree can do this. Here are some examples:

BIT (binary indexed tree) http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees , the most used approach during the contest

Segment tree http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , the code bellow is a segment tree

AVL tree: http://en.wikipedia.org/wiki/AVL_tree , this one is much harder/longer to code than the previous two. It's not for the faint of heart. Only Igor Kulev chose to go with this heavy-machinery approach. Why ? Because BIT and Segment Tree are too mainstream .

#include <cstring>

#include <ctime>

#include <string>

#include <vector>

#include <cstdlib>

using namespace std;

class LeeroyJenkins {

public:

    

    long long tree[400001];

    int seq[100001];

    

    void generateSequence(long long start,int N,int mod) {

        

        int i = 0;

        seq[i] = (int)start;

        while(i<N) {

            i++;

            seq[i] =  (((long long)seq[i-1]*1103515245 + 12345)/65536)%mod;

            

        }

    }

    int solve(int start,int N,int mod) {

        

        

        memset(tree,0,sizeof(tree));

        long long res=0;

        

        generateSequence((int)start,N,mod);

        for(int i = 0;i < N;i++ ) {

            

            if(seq[i]>0)

                res += query(1,0,100000,0,seq[i]-1);

            update(1,0,100000,seq[i]);

            

            

        }

        return res%1000007;

    }

    

    void update(int node,int i,int j,int val)

    {

        if(j<val || i>val)

            return;

        

        if(i==j && i==val) {

            tree[node]+=val;

            return;

        }

        

        update(2*node,i,(i+j)/2,val);

        update(2*node+1,(i+j)/2+1,j,val);

        

        tree[node]=tree[2*node]+tree[2*node+1];

    }

    

    

    long long query(int node,int i,int j,int l,int r)

    {

        if(j<l || i>r)

            return 0;

        

        if(i>=l && j<=r)

            return tree[node];

        return query(2*node,i,(i+j)/2,l,r) + query(2*node+1,(i+j)/2+1,j,l,r);

        

    }

};

vasja is offline Reply
Post 29.04.2013   # 2

I would like to add that if the values were much bigger than 100,000, BIT and segment trees would fail to solve the problem, but AVL tree can be used to solve it 

igorkulev is offline Reply
Post 29.04.2013   # 3

Not if you first compress the values in a range [0,N] where N is the length of the array which can be done in O(N*logN)

vasja is offline Reply
Post 29.04.2013   # 4

Yes, but you need additional mapping (compression) If you need realtime queries and manipulations with the structure (insertions and deletions) this operation is very expensive

igorkulev is offline Reply
Post 29.04.2013   # 5
Compressing by Min(M,N) is working also
bedjovski is offline Reply

Please login to post reply.