HackerEarth Magic Sum problem solution

In this HackerEarth Magic Sum problem solution We have a FULL binary tree i.e. each node except leaves has two children.

The magic sum between any two leaf nodes (both possibly same) is the number obtained after adding values of all the nodes (including starting and ending nodes) in a unique path from first leaf to the later one.

Your task is to find the maximum magic sum in the binary tree.

HackerEarth Magic Sum problem solution.

#include<vector>
#include<stdio.h>
#include<assert.h>
#include<limits.h>
#include<string.h>
#include<algorithm>
#define read(x) scanf("%d",&x)
using namespace std;

vector<int> list[515];
int sum, visited[515], ans;

int dfs(int i, int a[], int st=0)
{
    visited[i]=1;
    if(list[i].size()==1) ans=max(ans,a[i]);
    if(list[i].size()==1 && !st)  return a[i];
    int sum=INT_MIN;
    for(int j=0; j<list[i].size(); j++)
    {
        int v = list[i][j];
        if(!visited[v]) sum=max(sum, dfs(v, a));
    }
    return a[i]+sum;
}

int main()
{
  //clock_t startTime = clock();
  //freopen("in_2.txt","r",stdin);
  //freopen("out_2.txt","w",stdout);
    int T, N;
    read(T);
    while(T--)
    {
        read(N);
        int a[N];
    assert(N>=1 && N<=511);
    if(N==1) { scanf("%d",&a[0]); printf("%dn",a[0]); continue; }
        for(int i=0; i<N; i++) list[i].clear();
        for(int i=0; i<N; i++) read(a[i]);
        for(int i=0; i<N/2; i++)
        {
            list[i].push_back(2*i+1);
            list[2*i+1].push_back(i);
            list[i].push_back(2*i+2);
            list[2*i+2].push_back(i);
        }
        ans=INT_MIN;
        for(int i=N/2; i<N; i++)
        {
            memset(visited, 0, sizeof(visited));
            ans=max(ans, dfs(i,a,1));
        }
        printf("%dn",ans);
    }
    //clock_t endTime = clock();
    //fprintf(stderr, "nTime: %.5f secondsn", double(endTime - startTime) / CLOCKS_PER_SEC);
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define assn(n,a,b) assert(n>=a && n<=b)
int arr[100009][3]={};
void foo(int cur, int n)
{
    if(cur>n/2){arr[cur][1]=arr[cur][2]=0;return;}
    foo(cur*2,n);
    foo(cur*2 +1,n);
    arr[cur][1]=max(arr[cur*2][1],arr[cur*2][2])+arr[cur*2][0];
    arr[cur][2]=max(arr[cur*2+1][1],arr[cur*2+1][2])+arr[cur*2+1][0];
}
int main()
{
    int t;
    cin >> t;
    assn(t,1,500);
    while(t--)
    {
  int n,i,ans=-INT_MAX;
  cin >> n;
  assn(n,0,511);
  assert((n&(n+1))==0);
  for(i=1; i<=n; i++)
      cin >> arr[i][0];
  foo(1,n);
  for(i=1; i<=n; i++)
      ans=max(ans,arr[i][0]+arr[i][1]+arr[i][2]);
  cout << ans << endl;
    }
    return 0;
}

coding problems solutions