ALTARAY - Editorial

https://www.codechef.com/viewsolution/9712232
This is solution… And not able to get any bugg

Getting right answer for every sample input

@dpraveen did you see the solutions above? What do you think?

someone plzzzz help!!

You should not print anything other than output, So remove printf("enter no of cases ");

1 Like

ok.i will take care of this now.
Apart frm that d program is ok na?

and thanks for helping

Please edit your answer to make it readable or provide the link to your solution.

1 Like

why i am gtting tle while submitting .
running well for given test cases

All the test cases turn out fine.

Here is my simple C++ solution based on DP.
https://www.codechef.com/viewsolution/25977294

The range of array value is too big to handle for an integer.
You need to use long int in place of int for array values.

My DP solution
What I did was traverse the array from right to left. The rightmost element will always have 1 subarray that is the element itself.
So I call a function to n-1 to 1 to check for every element in the array. If the elements have same sign the subarray at that position will be 1, the number itself. If they are different in sign the number of subarrays at that position will be (1+ no. of subarrays at next position).
Hope it helps. :smile:

That’s exactly I also did. This is a good approach :grinning:

Python coded simple DP solution and very easy to understand as well.
LInk to solution

Just traverse from right to left … and if sign of current ele is diff than previous then increment 1 on prev count and store this as count of longest alternating subarray for current element …else just put count as 1 for this element.

AC in one go… try this DP approach.

** check recursion + memoizise version**

O(n) code

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

int main() {

int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int arr[n],size[n];
memset(size,0,sizeof(size));
for(int i=0;i<n;i++)
cin>>arr[i];

        size[0]=1;int posi=0;
        int tot=1;
    for(int i=1;i<n;i++)
    {
        if(arr[i]>0 && arr[i-1]<0 || arr[i]<0 && arr[i-1]>0)
        {
          tot++;
          posi=i-tot+1;
        }
        else
        {
        posi=i;
        tot=1;
        size[i]=tot;
        }
        size[posi]=tot;
    }
    
        for(int i=0;i<n;i++)
        {
            if(size[i]==0)
            {
                size[i]=size[i-1]-1;
                cout<<size[i]<<" ";
            }
            else
            cout<<size[i]<<" ";
        }
        cout<<endl;
}

}

1 Like

Wow such simpler

We can solve this without using dp
keep a variable cnt = 1;
keep a stack or an array to store the values of cnt
Traverse the given array from backwards
cnt variable is updated in every iteration : if a[i] and a[i+1] are alternating then increment cnt , otherwise make cnt = 1 and store the cnt in the stack/array
Now print the stored cnt values…
My solution here
:innocent: