ALTARAY - Editorial

Authors: Jaub Safin
Testers: Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Praveen Dhinwa

Simple

PREREQUISITES:

Simple observations, dp

PROBLEM:

An array is called alternating if any two consecutive numbers in it have opposite signs (i.e. one of them should be negative, whereas the other should be positive).

You are given an array A of size N consisting of non-zero elements. For each index i from 1 to N, you have to find the length of longest subarray starting at i.

QUICK EXPLANATION:

We can observe that if an array is alternating, then all of its subarrays are also alternating.

So, we can divide the array into maximal alternating subarrays.
For doing that, we will iterate over array from left to right, if the sign of current number is different than previous number, then this number can be used to extend previous alternating subarray, Otherwise we will have to start constructing a new maximal alternating subarray.

In this way, we can partition the array into various maximal alternating subarrays.

After this, finding length of longest subarray starting at index i is quite easy, as it can be done easily by finding the position of i in the corresponding maximal alternating subarray. If p be position and L be the length of the maximal subarray, then L - p + 1 will be the length of longest subarray starting at index i.

EXPLANATION:

Observation 1:
Values of the number don’t matter, only their signs do.

So, we can change the array A such that it consists of -1 and 1’s only.

Observation 2:
If an array A is alternating, then all of it’s subarrays are alternating.

Let us take an example to understand how we can apply the above observation to solve the problem.
Let A = [1, 1, -1, 1, 1, -1, -1]
So, we start from A_1 and note that A_1 is equal A_2.
So the maximal subarray starting from 1 will be [1] itself.

Now, we go to A_2, we can see that A_2, A_3, A_4 have different signs, and A_4 has same sign as A_5.
So the maximal subarray starting from index 2 will be [1, -1, 1].

So, we break the array into several parts such that each part is maximal alternating subarray. In our example, the parts will be
[1] [1, -1, 1] [1, -1], [-1]

We can formalize the above idea to write a pseudo code to break an array into various parts of maximal alternating subarrays.

vector<vector<int> > parts;
vector<int> curPart;
subpart.push_back(a[0]);
for (int i = 1; i < n; i++) {
// If signs of current and previous number are different,
// then it means that we can extend the current part.
if (a[i] * a[i - 1] == -1) {
curPart.push_back(a[i]);
} else {
// We add the curPart into parts.
parts.push_back(curPart);
}
}
// Check at the end whether the curPart has non-zero length or not.
// If it has, then add curPart into parts.
if (curPart.size() > 0) {
parts.push_back(subpart);
}


Now, let us find the length of longest alternating subarray ending at each index i for our example subarray A.
We get [1] [3, 2, 1], [2, 1], [1]

So, this means that for an maximal alternating subarray of length L, the answers (length of longest alternating subarray start from that index) will be L, L-1, \dots, 1.

We can use this idea to solve our problem.

// i denotes the current index of array at which we currently are.
int i = 1;
for (vector<int> curPart : parts) {
int L = curPart.size();
while (L > 0) {
// increment i
i++;
// decrement L
L--;
}
}
// Note the fact that we didn't use the explicit values of curPart, only its size matter.


Dynamic programming based Solution

You can also solve the problem by a very simple dp.

Let len[i] denote the maximum length of alternating subarray starting at position i.
We can observer that if a[i] and a[i + 1] has opposite signs, then len[i] will be 1 more than len[i + 1].
Otherwise in the case when they have same sign, then len[i] will be just 1.

len[N] = 1;
for (int i = N - 1; i >= 1; i--) {
// a[i] and a[i + 1] have different signs.
// Note that the a[i] can go upto 10^9,
// So if a is stored in int data type, then the a[i] * a[i + 1] might not fit in int.
// So, we cast it to long long
if (a[i] * (long long) a[i + 1]< 0) {
len[i] = len[i + 1] + 1;
} else {
len[i] = 1;
}
}


Time Complexity:

As we have seen in both the solutions we have to iterate over the array A only once or constant number of times. So, time complexity of the algorithm will be \mathcal{O}(N) which will easily fit in time with N = 10^5 and T = 10.

AUTHOR’S AND TESTER’S SOLUTIONS:

7 Likes

CAn u provide us with ur test cases and corresponding answers pls…
since I am getting wrong answer .

3 Likes

#include
using namespace std;

int main()
{
int t,i,j,x,k;
int a[100][100];
int n[10];
x=0;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n[i];
for(j=0;j<n[i];j++)
{
cin>>a[i][j];
}
}
for(k=0;k<t;k++)
{
for(i=0;i<n[k]-1;i++)
{
x=0;
for(j=i;j<n[k];j++)
{
if(((a[k][j]<0)&&(a[k][j+1]>0))||((a[k][j]>0)&&(a[k][j+1]<0)))
{
x=x+1;
}
else
{
break;
}
}
if(x==0)
{
cout<<"1";
}
else
{
cout<<x+1;
}
}
cout<<"1";
cout<<"\n";
}
return 0;
}

3
4
1 2 3 4
4
-1 2 -3 4
6
-2 -2 -3 5 -2 -1

My Approach:

Everytime you find a subarray whose longest alternating count is greater than one, all you have to do is print it, and decrement and print it till it becomes one. Then skip the next count-1 elements.

My Solution

1 Like

can tester tell me ur test cases and corresponding answers pls

In the dp solution why do you write a[i]*1ll*[i+1] instead of simple a[i]*a[i+1],
I wrote the latter during contest and got wrong answer and when I changed it to former it was accepted later. I thought maybe it is to prevent int overflow but I tried making array as array of long long ints but still I got wrong answer.

https://www.codechef.com/viewsolution/9712232
This is link of my solution… getting wrong answer continuously…Still i cant found any bugg… Pls help me out

Did exactly the same way which is mentioned in Quick Explanation.

My Solution : https://www.codechef.com/viewsolution/9708007

is my program correct?
someone pl tell
https://www.codechef.com/viewsolution/9714935

#include<stdio.h>
int main ()
{
int T=0,i=0,n=0,flag=0,c=0;
long long int j=0,count=0,A[100001];
scanf("%d",&T);
for(i=0;i<T;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
{
scanf("%lld",&A[j]);
}
for(j=1;j<=n;j++)
{
count=1;
flag=0;
c=j;
if(j==n)
{
printf("%d",1);
}
if(j!=n)
{
if(A[j]*A[j+1]>0&&j!=n)
{
printf("%d",1);
printf(" “);
}
else
{
while(A[j]*A[j+1]<0)
{
count++;
j++;
flag=1;
}
if(flag==1)
{
printf(”%lld",count);
printf(" ");
}
}
j=c;

        }
}
printf("\n");
}
return(0);


}

can you please check where i got wrong?

Why u people dont tell ur testing test cases so that every one check why they are getting wrong answers…

1 Like

Why u people dont tell ur testing test cases so that every one check why they are getting wrong answers…

@vineet1003

Your solution fails for the following case:

1

2

1 1

The correct output is “1 1” whereas your program prints “2 1”.

1 Like

Can someone help me with my program. I am getting Time Limit Exceeded error
https://www.codechef.com/viewsolution/9739516

My program shows exactly the same output as shown in the problem but it still says “wrong answer”
here’s the link to my code
https://www.codechef.com/viewsolution/9755162

nice editorial

Can’t spot mistake…getting WA :’(

https://www.codechef.com/viewsolution/9757999

public static void main(String arg[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
int n;
while(t>0)
{
n=sc.nextInt();
long[] a=new long[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextLong();
}
int[] b=new int[n];
b[n-1]=1;
for(int i=n-2;i>=0;i–)
{

if(a[i]*a[i+1]<0)
b[i]=b[i+1]+1;
else
b[i]=1;
}
for(int x : b)
System.out.printf("%d ",x);
System.out.println();
t–;
}
}
}

time limit is exceeding

plz help