Thanks Bro..Nice logic.

nice thinking, but the algorithm will take a long time because the algo will iterate the other array many times

ek no

I used the exact same algo except I didn't reverse the array but created the same fibonacci sequence using reversed indices.

Good thought process! Step II isn't necessary as you could just traverse the arrays from the end instead of the beginning. I like the idea of starting with the smallest array and looking if that value exists, I just had a while loop and decremented one of the 3 counters each time until I reached values that were all the same. This means that I only traverse each array once whereas yours you might traverse the two other arrays for each value that you look at. Here is my for loop:

    //This values reflect what cylinder index we are looking at in each column
    int col1 = 0; 
    int col2 = 0;
    int col3 = 0; 

    //While the heights that we are looking at aren't equal, decrement one
    while( h1[col1] != h2[col2] || h2[col2] != h3[col3] ) 
    {         
        if( h1[col1] > h2[col2] || h1[col1] > h3[col3] )
            col1++;
        else if( h2[col2] > h1[col1] || h2[col2] > h3[col3] )
            col2++;
        else if( h3[col3] > h2[col2] || h3[col3] > h1[col1])
            col3++;
    }

    System.out.println(h1[col1]); //Once they're equal, print this

bool isnumber(int num , vector<int>  arr , int sizeofvec){

    for(int i = sizeofvec ; i > 0  ; i-- ){
        if(arr[i] == num ){
            return true;
        }
    }
return false;
}

int main(){
    int n1;
    int n2;
    int n3;
    int temp;
    cin >> n1 >> n2 >> n3;
    vector<int> h1(n1+1);

    for(int h1_i = 0;h1_i < n1;h1_i++){
       cin >> h1[h1_i];
    }
    vector<int> h2(n2+1);
    for(int h2_i = 0;h2_i < n2;h2_i++){
       cin >> h2[h2_i];
    }
    vector<int> h3(n3+1);
    for(int h3_i = 0;h3_i < n3;h3_i++){
       cin >> h3[h3_i];
    }
h1[n1+1] = 0 ;
h2[n2+1] = 0 ;
h3[n3+1] = 0 ;
//Step - 2 = For revering and adding .. Reverse side adding is performed
    for(int h1_i = (n1 - 1) ; h1_i >=0; h1_i--){
        h1[h1_i] = h1[h1_i] + h1[h1_i + 1];
    }
    for(int h2_i = (n2 - 1) ;h2_i >=0;h2_i--){
        h2[h2_i] = h2[h2_i] + h2[h2_i + 1];
    }
    for(int h3_i = (n3 - 1) ;h3_i >=0;h3_i--){
        h3[h3_i] = h3[h3_i] + h3[h3_i + 1];
    }
    //step - 3 = Checking from last if the same number exists in other two arrays

    for(int h1_i = (n1 - 1) ; h1_i >=0; h1_i--){
        if(isnumber(h1[h1_i] , h2, n2) && isnumber(h1[h1_i] , h3 ,n3) ){
            temp = h1[h1_i] ;
            break;
        }else{
            temp = 0;
        }
    }
    cout<<temp;
    return 0;
}

Good idea, I use your algorithm to solve this.
But i change a little bit after getting the incremental heights.

#!/bin/ruby

def get_sum_of_stacks(*stacks)
  ary = []
  stacks.each do |stack|
    a = []
    b = 0
    stack.reverse.each_with_index{|i, index| a[index] = (b += i)}
    ary << a
  end
  ary
end

def get_answer(*heights)
  a = heights.flatten.group_by(&:itself)
  a = a.select{|k,v| v.size == 3}.max
  print a.nil? ? 0 : a[0]
end

n1,n2,n3 = gets.strip.split(' ')
n1 = n1.to_i
n2 = n2.to_i
n3 = n3.to_i
h1 = gets.strip
h1 = h1.split(' ').map(&:to_i)
h2 = gets.strip
h2 = h2.split(' ').map(&:to_i)
h3 = gets.strip
h3 = h3.split(' ').map(&:to_i)


h1,h2,h3 = get_sum_of_stacks(h1,h2,h3)
get_answer(h1,h2,h3)

not sure if it's faster

Wow!. this is so cool.

I implemented the exact same thing but instead of searching for the elements present in the smallest array, i put them in the stacks in the increasing order and popped the top of whichever stack had the biggest number in a loop. works like a charm and doesn't take too long

gives the answer but how does this work?

is step 2 necessary?

thank you very much :)

nice algorithm

In step III,is it necessary to take the smallest array, I mean will I pass the timeout error even if I take random array.

in the worst case i think the algorithm complexity will be O(n1*n2*n3) which will give time limit exceeded error...

This code is getting time out for most of the cases. I think it is complexity O(m+n+o)(worst case) m,n,o being length of stack.

Are we supposed to do better than this ?

int main(){
    int n1, n2, n3;
    unsigned long long int sum1 = 0, sum2 = 0, sum3 = 0;
    int i1 = 0,i2 = 0,i3 = 0;
    cin >> n1 >> n2 >> n3;
    vector<int> h1(n1);
    for(int h1_i = 0;h1_i < n1;h1_i++){
       cin >> h1[h1_i];
       sum1 += h1[h1_i]; 
    }
    vector<int> h2(n2);
    for(int h2_i = 0;h2_i < n2;h2_i++){
       cin >> h2[h2_i];
       sum2 += h2[h2_i]; 
    }
    vector<int> h3(n3);
    for(int h3_i = 0;h3_i < n3;h3_i++){
       cin >> h3[h3_i];
       sum3 += h3[h3_i]; 
    }
    while (i1<n1 && i2<n2 && i3<n3) {
        if (sum1 == sum2 && sum2 == sum3) {
            break;       
        } else if (sum1 > sum2 && sum1 > sum3) {
            sum1 = sum1 - h1[i1];
            i1++;
        } else if (sum2 > sum1 && sum2 > sum3) {
            sum2 = sum2 - h2[i2];
            i2++;
        } else if (sum3 > sum1 && sum3 > sum2) {
            sum3 = sum3 - h3[i3];
            i3++;
        }
        
    }
    if (sum1 == sum2 && sum2 == sum3)
        cout<<sum1;
    else 
        cout<<0;
    return 0;
}

Awesome.

You do not even need to store the whole sum while reading the elements from console into array you can calculate the sum of all elements of one stack. Then simply reduce the current element from sum to get total sum at one level lower. This is what I did but my submission is failing for two testcases : 3 and 23. If anyone can then please share these testcases

i used an array to store the frequency of sum if frequency is 3 then it is the answer but need to chk frequency from higg to low

Bad Bad algorithm that one is

impressive :D

That's amazing.

i thought half of your logic first and then i got irritated after so many tries to get the answer but seeing this logic is really good for me

Here's my naive solution in PHP based on OPs logic.

<?php

$handle = fopen ("php://stdin","r");
fscanf($handle,"%d %d %d",$n1,$n2,$n3);

$h1_temp = fgets($handle);      //Fetches line
$h1 = explode(" ",$h1_temp);    //Separates on space
array_walk($h1,'intval');       //Forces each element to be an int
$r1 = array_reverse($h1);       //Reverse to simulate stack
$h1_commulative = 0;            //Variable to keep track of sums in the array
$sumSteps1 = array();           //Array to hold sums
foreach($r1 as $i) {
	$sumSteps1[] = ($h1_commulative += $i);    //Feed in possible stack heights
}
$steps1_rev = array_reverse($sumSteps1);    //Reverse again so heights are stored from highest to lowest



$h2_temp = fgets($handle);      //Repeat for each array
$h2 = explode(" ",$h2_temp);
array_walk($h2,'intval');
$r2 = array_reverse($h2);
$h2_commulative = 0;
$sumSteps2 = array();
foreach($r2 as $i) {
	$sumSteps2[] = ($h2_commulative += $i);
}
$steps2_rev = array_reverse($sumSteps2);



$h3_temp = fgets($handle);
$h3 = explode(" ",$h3_temp);
array_walk($h3,'intval');
$r3 = array_reverse($h3);
$h3_commulative = 0;
$sumSteps3 = array();
foreach($r3 as $i) {
	$sumSteps3[] = ($h3_commulative += $i);
}
$steps3_rev = array_reverse($sumSteps3);



echo getMaxShared($steps1_rev, $steps2_rev, $steps3_rev);

function getMaxShared($a, $b, $c) { //Find the largest number shared between the three arrays
	foreach ($a as $val) {
		if(in_array($val, $b) && in_array($val, $c)){
			return $val;
		}
	}
	return 0;
}
?>

I use your logic but i changed a little bit. Instead of storing in arrays, i store data in stacks and i compare top elements(i mean each of peek()) and popped the maximum element recursively until the top elements are equal.it works for me but only for 3 cases i get runtime error because of too much recursion. Good logic!

it's working fine. Awesome man! Thanks!

vector<int> reverse_sum(vector<int> stack)
{
    reverse(stack.begin(),stack.end());
    for(int i=1; i<stack.size(); i++)
        stack[i]=stack[i]+stack[i-1];
    reverse(stack.begin(),stack.end());
    return stack;
}

int max_height ( vector <int> s1, vector <int> s2, vector <int> s3)
{
    int h=0;
    for(int i=0; i<s1.size(); i++)
        if(find(s2.begin(),s2.end(),s1[i]) != s2.end())
            if(find(s3.begin(),s3.end(),s1[i]) != s3.end())
            {
                h=s1[i];
                break;
            }
    return h;
}

int main()
{
    ifstream infile("i.txt");
    int n1,n2,n3;
    cin>>n1>>n2>>n3;
    vector<int> stack1(n1),stack2(n2),stack3(n3);
    for(int i=0; i<n1; i++)
        cin>>stack1[i];
    for(int i=0; i<n2; i++)
        cin>>stack2[i];
    for(int i=0; i<n3; i++)
        cin>>stack3[i];

    stack1=reverse_sum(stack1);
    stack2=reverse_sum(stack2);
    stack3=reverse_sum(stack3);

    if(stack1.size()<=stack2.size() && stack1.size()<=stack3.size())
        cout<<max_height(stack1,stack2,stack3);
    else if(stack2.size()<=stack1.size() && stack2.size()<=stack3.size())
        cout<<max_height(stack2,stack1,stack3);
    else
        cout<<max_height(stack3,stack1,stack2);
    return 0;
}

This seems a bit overcomplicated.

There is a simple rule to solve this problem: always remove the block from stack i such that the height of i, minus the top block, is maximized.

This always works since the resulting stack is as tall as possible, such that it may admit a solution.

Be careful not to make your algorithm O(n^2), which can happen if you compute the height at each iteration by walking the entire (remainder of) the height arrays.

Smart!

basic logic behind this algorithm is we want a common cummulative sum of length of stacks from the ground.

its showing time out..any help!!

include

using namespace std; int main() { long int a,b,c; cin>>a>>b>>c; long int arr1[a],arr2[b],arr3[c]; long int arr4[a],arr5[b],arr6[c]; for(int i=0;i>arr1[i]; } for(int i=0;i>arr2[i]; } for(int i=0;i>arr3[i]; } long int sum=0; for(long int i=a-1;i>=0;i--) { sum=sum+arr1[i]; arr4[i]=sum; } sum=0; for(long int i=b-1;i>=0;i--) { sum=sum+arr2[i]; arr5[i]=sum;

}
 sum=0;
for(long int i=c-1;i>=0;i--)
{
    sum=sum+arr3[i];
    arr6[i]=sum;
}
for(long int i=0;i<a;i++)
{
    for(long int j=0;j<b;j++)
    {
        if(arr4[i]==arr5[j])
           {
            for(long int k=0;k<c;k++)
            {
                if(arr4[i]==arr6[k])
                {
                    cout<<arr5[j]<<endl;
                    return 0;
                }
            }
        }
    }
}
cout<<"0"<<endl;

return 0; }

How this solution came to your mind?? pretty good algorithm

Yes! This is more or less the approach I followed. Would you call this functional programming?

I essentially calculated the cummulative list for each list, appended them together, then checked for items with a count of 3.

The try except is a bit of a hack, but did the job.

Python

#!/bin/python3

import sys
from itertools import accumulate
from collections import Counter

n1,n2,n3 = input().strip().split(' ')
n1,n2,n3 = [int(n1),int(n2),int(n3)]
h1 = [int(h1_temp) for h1_temp in input().strip().split(' ')]
h2 = [int(h2_temp) for h2_temp in input().strip().split(' ')]
h3 = [int(h3_temp) for h3_temp in input().strip().split(' ')]

h1c, h2c, h3c = [list(accumulate(reversed(l))) for l in (h1, h2, h3)]
total_stack = h1c + h2c + h3c
counter_stack = Counter(total_stack)
try:
    print(max(i[0] for i in counter_stack.items() if i[1] == 3))
except:
    print(0)

Could you please explain why this works?

pritty awesome .. thanks

Good logic, here is my implementaion in C++

int max_height(vector<int> h1, vector<int> h2, vector<int> h3) {
	int n1, n2, n3;

	n1 = h1.size();
	n2 = h2.size();
	n3 = h3.size();

	reverse(h1.begin(), h1.end());
	reverse(h2.begin(), h2.end());
	reverse(h3.begin(), h3.end());

	vector<int> h1_cumulative(n1 + 1);
	
	for (int h1_i = 1; h1_i < n1+1; h1_i++) {
		h1_cumulative[h1_i] += h1[h1_i-1] + h1_cumulative[h1_i-1];
	}

	vector<int> h2_cumulative(n2 + 1);
	for (int h2_i = 1; h2_i < n2 + 1; h2_i++) {
		h2_cumulative[h2_i] += h2[h2_i - 1] + h2_cumulative[h2_i - 1];
	}
	vector<int> h3_cumulative(n3 + 1);
	for (int h3_i = 1; h3_i < n3 + 1; h3_i++) {
		h3_cumulative[h3_i] += h3[h3_i - 1] + h3_cumulative[h3_i - 1];
	}

	reverse(h1_cumulative.begin(), h1_cumulative.end());
	reverse(h2_cumulative.begin(), h2_cumulative.end());
	reverse(h3_cumulative.begin(), h3_cumulative.end());

	vector<int>::iterator it1 = h1_cumulative.begin();
	vector<int>::iterator it2 = h2_cumulative.begin();
	vector<int>::iterator it3 = h3_cumulative.begin();


	while (true) {
		if (*it1 == *it2 && *it2 == *it3) {
			return *it1;
		}
		
		if (*it1 >= *it2 && *it1 >= *it3) {
			++it1;
		}
		else if (*it2 >= *it1 && *it2 >= *it3) {
			++it2;
		}
		else if (*it3 >= *it1 && *it3 >= *it2){
			++it3;
		}
	}
}

beatiful aalgorithm

Nice work! However, I don't think you need to reverse the arrays when you can just iterate backwards. Below is my java version, but I gotta say ... this is another problem that is not categorized or explained clearly. Symbolically these are stacks but the solution doesn't require stack data structures. In fact utilizing one would make the solution more complicated (and may still require an auxiliary DS). Second, Nabila expects the input stack values in reverse order (at least from a LIFO perspective). Not sure if this was on purpose to try and trick people, or just a weird way of thinking about stacks.

static int equalStacks(int[] h1, int[] h2, int[] h3) {

int maxHeight = 0;

if(h1 == null || h1.length < 1 
|| h2 == null || h2.length < 1 
|| h3 == null || h3.length < 1)
    return maxHeight; 

int[] s1 = calculateSums(h1);
int[] s2 = calculateSums(h2);
int[] s3 = calculateSums(h3);

// handle simple case where stacks are already equal in height
if(s1[s1.length -1] == s2[s2.length - 1] && s2[s2.length - 1] == s3[s3.length - 1])
    return s1[s1.length -1];

int[] shortest = s1.length < s2.length ? s1 : s2;
shortest = shortest.length < s3.length ? shortest : s3;

// walk array of sums backwards to simulate reading stack from top to bottom
for(int i = shortest.length - 1; i >= 0; i--) {

    int sum = shortest[i];          
    int matchCount = 0;                     
    matchCount += s1 != shortest && Arrays.binarySearch(s1, sum) >= 0 ? 1 : 0;
    matchCount += s2 != shortest && Arrays.binarySearch(s2, sum) >= 0 ? 1 : 0;
    matchCount += s3 != shortest && Arrays.binarySearch(s3, sum) >= 0 ? 1 : 0;

    if(matchCount < 2) continue;

    maxHeight = sum;
    break;          
}

return maxHeight;

}

private static int[] calculateSums(int[] data) {

if(data == null || data.length < 1) return new int[0];

int[] sums = new int[data.length];        
int last = data.length - 1;
int sum = 0;

// walk input array backwards (since it's supposed to be a "stack", but
// generate sum array in normal order to facilitate binary search 
for(int i = last, j = 0; i >= 0 && j < sums.length; i--, j++) {
    sum += data[i];
    sums[j] = sum;
}

return sums;        

}

If this works, that is disgustingly clever, would've never come up with that. Major props!

Used the same logic except i took differences from top instead of sums from bottom. Which is the same thing essentially.

I had the same way of thinking as you :) ! But, instead of re-reversing arrays, I just did append all sums to a list ([1,2,3,5,8,2,5,9,1,5,6,7]) and I found the value with maximum occurences in it. The maximum value is the only one that occurs in those 3 arrays.

max(list, key = list.count) , returns 5 !

azhagu azhagu

is It take O(n^2) time complexity in worst case ?

private static final Scanner scan = new Scanner(System.in);

public static void main(String[] args) throws IOException {
    int n1=scan.nextInt();
    int n2=scan.nextInt();
    int n3=scan.nextInt();
    int a[]=new int[n1];
    int b[]=new int[n2];
    int c[]=new int[n3];
    int temp[]=new int[n1+n2+n3];


    for(int i=0;i<n1;i++)
    {
        a[i]=scan.nextInt();
    }

    for(int i=0;i<n1;i++)
    {
        temp[i]=a[n1-1-i];
    }
     for(int i=0;i<n1;i++)
    {
        a[i]=temp[i];
    }
     for(int i=0;i<n1;i++)
    {
        if(i==0)
        {
            a[i]=a[i];
        }
        else
        {
        a[i]=a[i]+a[i-1];
        }
    }

    for(int i=0;i<n2;i++)
    {
        b[i]=scan.nextInt();
    }
     for(int i=0;i<n2;i++)
    {
        temp[i]=b[n2-1-i];
    }
     for(int i=0;i<n2;i++)
    {
        b[i]=temp[i];
    }
       for(int i=0;i<n2;i++)
    {
        if(i==0)
        {
            b[i]=b[i];
        }
        else
        {
        b[i]=b[i]+b[i-1];
        }
    }
    for(int i=0;i<n3;i++)
    {
        c[i]=scan.nextInt();
    }
     for(int i=0;i<n3;i++)
    {
        temp[i]=c[n3-1-i];
    }
     for(int i=0;i<n3;i++)
    {
        c[i]=temp[i];
    }
       for(int i=0;i<n3;i++)
    {
        if(i==0)
        {
            c[i]=c[i];
        }
        else
        {
        c[i]=c[i]+c[i-1];
        }
    }



    int max=Math.min(n1,n2);
    int min=Math.min(max,n3);
    if(min==n1)
    {
        for(int i=n1-1;i>=0;i--)
        {
           int value=a[i];
            for(int z=0;z<n2;z++)
            {
                if(value==b[z])
                {
                    for(int k=0;k<n3;k++)
                    {
                        if(value==c[k])
                        {
                            System.out.println(value);
                            System.exit(0);
                        }
                    }
                }
            }
        }
    }
     if(min==n2)
    {
        for(int i=n2-1;i>=0;i--)
        {
           int value=b[i];
            for(int z=0;z<n3;z++)
            {
                if(value==c[z])
                {
                    for(int k=0;k<n1;k++)
                    {
                        if(value==a[k])
                        {
                            System.out.println(value);
                            System.exit(0);
                        }
                    }
                }
            }
        }
    }
     if(min==n3)
    {
        for(int i=n3-1;i>=0;i--)
        {
           int value=c[i];
            for(int z=0;z<n1;z++)
            {
                if(value==a[z])
                {
                    for(int k=0;k<n2;k++)
                    {
                        if(value==b[k])
                        {
                            System.out.println(value);
                            System.exit(0);
                        }

                    }
                }
            }
        }
    }
   System.out.println("0");


}

It is not working for all the test cases.It was showing me error for some of the test cases

Great thinking!

your complexity will be of O(n1*n2+n1*n3), where n1 is the length of the smallest array so after making the prefix array merge them end to end and then apply sorting thus your complexity will reduce to O(nlogn).

what do you think the time complexity of this is ?

def makeEqual(s,a):

                    ans = sum(s)
                    while a < ans:
                            top = s[0]
                            s.pop(0)
                            ans -= top
                return ans

def equalStacks(h1, h2, h3):
            minn = min(sum(h1),sum(h2),sum(h3))
            summ = sum((sum(h1),sum(h2),sum(h3)))
            if minn in (0,1):
                    return minn

        while minn != summ/3:
                ans1 = makeEqual(h1,minn)
                ans2 = makeEqual(h2,minn)
                ans3 = makeEqual(h3,minn)
                minn = min(ans1,ans2,ans3)
                summ = ans1+ans2+ans3
        return summ//3

' ' '

A crude implementation of this approach:

int equalStacks(vector h1, vector h2, vector h3) {

    //reverse each vector and find the cumulative sum
reverse(h1.begin(),h1.end());
for(int i = 1; i < h1.size(); i++){
    h1[i] = h1[i] + h1[i-1];
}
reverse(h2.begin(),h2.end());
for(int i = 1; i < h2.size(); i++){
    h2[i] = h2[i] + h2[i-1];
}
reverse(h3.begin(),h3.end());
for(int i = 1; i < h3.size(); i++){
    h3[i] = h3[i] + h3[i-1];
}

/*create copies and copy the vectors such that 'search' will be the vector with shortest length and 'cp1' & 'cp2' being the other two */
    vector<int> search, cp1,cp2;
if(h1.size()<h2.size()) {
    if(h1.size() < h3.size()) {
        search = h1;
        cp1 = h2;
        cp2 = h3;
    } else {
        search = h3;
        cp1 = h1;
        cp2 = h2;
    }
} else if(h2.size() < h3.size()){
    search = h2;
    cp1 = h1;
    cp2 = h3;
} else {
    search = h3;
    cp1 = h1;
    cp2 = h2;
}

//create a reverse iterator to start comparing values
    vector<int>::reverse_iterator rit;
rit = search.rbegin();
int ans = 0;

     /*for each value of starting from the end of 'search' vector, find if any of it exists in both 'cp1' and 'cp2'*/
while(rit != search.rend()) {
    vector<int>::iterator it1,it2;
    it1 = find (cp1.begin(), cp1.end(), *rit);
    it2 = find (cp2.begin(), cp2.end(), *rit);

    if(it1 != cp1.end() && it2 != cp2.end()){
            ans = *rit;
            break;
    }
    rit++;
}
return ans;

}

what if arrays are: [3,2,1,1,1] [4,3,2] [4]

i tried this algorithm, but it is not working for all the test cases, can you please post the code so that I can see where my code is wrong.

but its running out of time

That is confusing for me too.

Yeah I was confused by this as well. I ended up using a queue instead.

What's the reason for doing this:

height[i] -= stack[i][index[i]++];

Why are you doing index[i]++, instead of just index[i]?

just check it

int main() {

int a,b,c,i;

cin>>a>>b>>c;
int d[a],e[b],f[c];
long long int x=0,y=0,z=0;
for(i=0;i<a;i++)
    {       cin>>d[i];
    x=x+d[i];   }

for(i=0;i<b;i++)
   { cin>>e[i];
    y=y+e[i]; }
for(i=0;i<c;i++)
    { cin>>f[i];
    z=z+f[i]; }
int p=0,q=0,r=0; 
     while(x!=y ||y!=z ||x!=z) 
    {if(x>y && x>z|| x==y && x>z || x==z &&x>y)
            x=x-d[p++];
          if(y>x && y>z|| y==x && y>z || y==z &&y>x)
            y=y-e[q++];
          if(z>x &&z>y || z==y && z>x || z==x &&z>y)
            z=z-f[r++]; } 
cout<<x;
   return 0;

}

No need to use recursion. Simple push and pop will do.

LOL the code's too complicated. It's a simple problem so the code should be simple too. Elegance is important in programming. There's also a lot of repetition in your code. Repeated blocks of code should be made into a function. This is the "do not repeat yourself" principle. Have a look at how small my python code is:

from collections import deque

def read_queue():
    return deque(map(int, input().strip().split()))

nstacks = len(input().split())
stacks = [read_queue() for i in range(nstacks)]
heights = list(map(sum, stacks))

while len(set(heights)) > 1:
    ihighest = heights.index(max(heights))
    heights[ihighest] -= stacks[ihighest].popleft()

print(heights[0])

Edit: made the code a bit more elegant.