0

I was just solving problems and came upon this one

Given an array A consisting of N integers - A1, A2....AN. You have to find the value of Σ MAX(i,j) * F(i,j) where 1 ≤ i < j ≤ N.

MAX(i,j) is defined as max(Ai,Ai+1...Aj).

F(i,j) is defined as:

F(i,j) will be 1 if (Ai&Aj) = Aj or (Ai&Aj) = Ai F(i,j) will be 0, otherwise. Here & denotes the bitwise AND operator.

reference: GOODPROB

I wrote a fairly simple solution and got 40 points, i.e. it could not handle large inputs in the required 2 seconds time.

This was my code 

#include <iostream>
using namespace std;

int max(int *A, int x,int y){
    int m=A[x];
    while(x<=y){
        if(A[x]>m)
            m=A[x];
        x++;
    }
    return m;
}

int F(int *A,int i,int j){
    return ((A[i]&A[j]) == A[j] or (A[i]&A[j]) == A[i])?1:0;
    }
int main() {
    long N;
    cin>>N;
    int *A = new int[N];
    for(int i=0;i<N; i++)
        cin>>A[i];
    long m=0;
    for(int j=0;j<N;j++)
        for(int i=0;i<j; i++)
            m+= F(A,i,j)?max(A,i,j)*F(A,i,j):0;
    cout<<m<<endl;
    return 0;
}

I checked the successful submitions there but those made me go panic. I couldn't even imagine such large solution for this fairly simple looking problem. Can anyone come up with a solution simple enough to understand.

Hritik
  • 673
  • 1
  • 6
  • 24
  • 2
    I believe using [`std::accumulate`](http://en.cppreference.com/w/cpp/algorithm/accumulate) with a lambda could provide a one liner solution for this. A plea: Please don't waste your time with online code judge engines, rather try to participate in some real world problems/projects. – πάντα ῥεῖ Aug 31 '16 at 12:19
  • Thanks but real world projects are quite long and I'm not completely prepared for them both in experience and time context. – Hritik Aug 31 '16 at 12:22
  • 1
    _"I'm not completely prepared ..."_ You shouldn't believe that online code judges will prepare you in any way for these. You'll just learn bad habits. Working through some good books will make you prepared better a lot. We keep a list of good books [here](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – πάντα ῥεῖ Aug 31 '16 at 12:25
  • I've done a bit of freelancing. Actually online judges provide a good way to sharpen my maths skills (which I assume to be of importance in my future career of programming). They also provide the food for compition hunger. – Hritik Aug 31 '16 at 12:32
  • 1
    @Hritik *Actually online judges provide a good way to sharpen my maths skills* -- `int *A = new int[N];` This isn't math, this is a memory leak. The online judges do nothing to help write quality C++ code. – PaulMcKenzie Aug 31 '16 at 12:56
  • Memory leak ? I wanted array of N elements so I did that. Please enlighten me. – Hritik Sep 04 '16 at 10:50

2 Answers2

0

OK this does not really give you an effective algorithm but the comment section does not give the best formatting options.

I have found some small optimization possibilities. You repeat statements sometimes when not needed.

m+= F(A,i,j)?max(A,i,j)*F(A,i,j):0;

Here you can store the result of F(A,i,j) and only call this function twice (function calls can be expensive). 

return ((A[i]&A[j]) == A[j] or (A[i]&A[j]) == A[i])?1:0;

Same here with A[i]&A[j]. You could store the result beforehand.

So just some small things in your current algorithm. How much they will help / improve you have to measure yourself.

Hayt
  • 5,210
  • 30
  • 37
0

You are finding the maximum value in range of array linearly. Doing this adds up O(n) factor in your overall complexity. And since you are using nested loops and calling max from inside these your overall time complexity will be O(n^3) .

You can reduce this factor significantly by using Segment Tree Data Structure. Using segment tree you can find maximum in a range within O(log(n)) time. Reducing Overall complexity to O( n^2 * log(n) ) For tutorial on Range Max/Min query

Range Minimum Query using Segment Tree

rishabh
  • 96
  • 6