You are not logged in. Please login at www.codechef.com to post your questions!

×

ALTARAY - Editorial

2
1

PROBLEM LINK:

Contest
Practice

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

DIFFICULTY:

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) {
        answer[i] = L;
        // 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:

setter
tester

This question is marked "community wiki".

asked 20 Mar '16, 17:34

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52124164
accept rate: 21%

edited 21 Mar '16, 00:08


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

link

answered 21 Mar '16, 00:18

dibya1rb12_3's gravatar image

3★dibya1rb12_3
111
accept rate: 0%

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

link

answered 21 Mar '16, 00:12

vineet1003's gravatar image

3★vineet1003
1
accept rate: 0%

#include <iostream>
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;
}
link

answered 21 Mar '16, 00:14

shalini0512's gravatar image

2★shalini0512
1
accept rate: 0%

edited 21 Mar '16, 00:18

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52124164

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

link

answered 21 Mar '16, 00:16

shalini0512's gravatar image

2★shalini0512
1
accept rate: 0%

can tester tell me ur test cases and corresponding answers pls

link

answered 21 Mar '16, 00:21

vineet1003's gravatar image

3★vineet1003
1
accept rate: 0%

If your solution is wrong, then try generating subarrays of length <= 10 (with +1, -1) only and run against a correct solution.

Also if you have some overflow bug due to not using long long at desired places, then for the same test cases, change $+1$ to $10^9$ and $-1$ to $-10^9$

(21 Mar '16, 07:56) dpraveen ♦♦4★

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

(21 Mar '16, 08:26) vineet10033★

Getting right answer for every sample input

(21 Mar '16, 08:28) vineet10033★

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.

link

answered 21 Mar '16, 00:52

yougaindra's gravatar image

4★yougaindra
913
accept rate: 0%

edited 21 Mar '16, 00:52

There is something wrong in your claims. Can you give links of both the solutions?

(21 Mar '16, 01:10) dpraveen ♦♦4★

@dpraveen

https://www.codechef.com/viewsolution/9713110 <-- this is solution where a is long long int(WA) https://www.codechef.com/viewsolution/9713154 <-- this is the other one(AC)

The Above solutions are similar to solution in editorial

https://www.codechef.com/viewsolution/9711723 <-- This is the one I submitted during contest.(WA)

https://www.codechef.com/viewsolution/9713715 <-- This is with a is long long int (WA)

https://www.codechef.com/viewsolution/9713162 <-- This is the same submission with only one change as mentioned above in previous comment(i.e. including 1ll). (AC)

(21 Mar '16, 03:08) yougaindra4★

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

(21 Mar '16, 14:16) yougaindra4★

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

link

answered 21 Mar '16, 08:06

vineet1003's gravatar image

3★vineet1003
1
accept rate: 0%

Tried inputting many cases and getting every tym correct answer.Still i am getting WA in ur compiler

(21 Mar '16, 08:09) vineet10033★

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

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

link

answered 21 Mar '16, 08:46

code_hard123's gravatar image

6★code_hard123
7717
accept rate: 7%

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

link

answered 21 Mar '16, 14:24

adisk_dtu1996's gravatar image

0★adisk_dtu1996
1
accept rate: 0%

edited 21 Mar '16, 14:25

someone plzzzz help!!

(21 Mar '16, 14:56) adisk_dtu19960★

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

(21 Mar '16, 17:29) yougaindra4★

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

(21 Mar '16, 19:05) adisk_dtu19960★

and thanks for helping

(21 Mar '16, 19:06) adisk_dtu19960★

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&lt;=n;j++)" {="" scanf("%lld",&a[j]);="" }="" for(j="1;j&lt;=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?

link

answered 21 Mar '16, 17:41

baniya_01coder's gravatar image

1★baniya_01coder
1
accept rate: 0%

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

(21 Mar '16, 20:10) abcdexter242★

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

link

answered 21 Mar '16, 18:20

vineet1003's gravatar image

3★vineet1003
1
accept rate: 0%

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

link

answered 21 Mar '16, 18:21

vineet1003's gravatar image

3★vineet1003
1
accept rate: 0%

@vineet1003
Your solution fails for the following case:
1
2
1 1
The correct output is "1 1" whereas your program prints "2 1".

link

answered 22 Mar '16, 00:50

samarth_1996's gravatar image

5★samarth_1996
9
accept rate: 0%

link

answered 23 Mar '16, 13:37

pragyan_123's gravatar image

2★pragyan_123
11
accept rate: 0%

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

link

answered 26 Mar '16, 12:01

sid6's gravatar image

0★sid6
1
accept rate: 0%

My program shows exactly the same output as shown in the problem but it still says "wrong answer" please help me where i am going wrong? here's the link to my code https://www.codechef.com/viewsolution/9755162

link

answered 27 Mar '16, 13:10

yeshu_123's gravatar image

2★yeshu_123
1
accept rate: 0%

nice editorial

link

answered 27 Mar '16, 17:23

vinu010398's gravatar image

0★vinu010398
1
accept rate: 0%

Can't spot mistake..getting WA :'(

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

link

answered 27 Mar '16, 22:59

pirateboy's gravatar image

2★pirateboy
1
accept rate: 0%

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

link

answered 22 Apr '16, 15:35

a_0000_prerna's gravatar image

3★a_0000_prerna
1
accept rate: 0%

edited 22 Apr '16, 15:36

https://www.codechef.com/viewsolution/9972627 this is my solution.it works fine with the test cases but its not getting accepted. pls help thanks in advance.

link

answered 27 Apr '16, 15:50

ankitkataria's gravatar image

1★ankitkataria
1
accept rate: 0%

I would like to thank you for the time you invest in making such nice post cause as I think it can be very helpful for many people who just wish to get as much information about this topic as possible.

link

answered 29 Apr '16, 15:37

raleighsimon's gravatar image

0★raleighsimon
1
accept rate: 0%

when i am running this code it is showing correct output, but when i am submitting it, it is showing wrong answer. Here is the link to my solution: https://www.codechef.com/viewsolution/10155565

link

answered 24 May '16, 20:36

ankur2006's gravatar image

0★ankur2006
11
accept rate: 0%

edited 25 May '16, 13:08

include <stdio.h>

int a[100002];

int sign(int);

int dp(long long int, long long int,long long int);

int main(void) { long long int n,t,i,x; scanf("%lld",&t); while(t--) { scanf("%lld",&n); for(i=0;i<n;i++) scanf("%lld",&a[i]);

      for(i=0;i<n;i++)
          {
            x=dp(i,sign(a[i]),n);
            printf("%lld ",x);
          }
       printf("\n");

    }
// your code goes here
return 0;

}

int dp(long long int y,long long int s,long long int n) { if(y==n-1) return 1;

    else if(sign(a[y+1])!=s)
     return  1+dp(y+1,sign(a[y+1]),n);

    else
     return 1;

}

int sign(int n) { if(n>0) return 1;

  else
   return 0;

}

link

answered 01 Jun '16, 16:17

ujjwal451's gravatar image

3★ujjwal451
92
accept rate: 0%

edited 01 Jun '16, 16:21

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

(01 Jun '16, 16:18) ujjwal4513★

I am getting time limit exceeding but cant see my mistake , plz help

import java.io.*;

import java.math.*;

import java.util.*;

class subarrayprefix
{

public static Long[] a=new Long[1000000];

public static Long[] ans=new Long[1000000];
public static void main(String arg[])
{
    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    int n;
    long x=1;
    while(t>0)
    {
        n=sc.nextInt();
        for(int i=0;i<n;i++)
            a[i]=sc.nextLong();
        ans[n-1]=x;
        for(int i=n-2;i>=0;i--)
        {
            if((a[i+1]*a[i])<0)
                ans[i]=ans[i+1]+1;
            else
                ans[i]=x;
        }
        for(int i=0;i<n;i++)
            System.out.printf("%d ",ans[i]);
        System.out.println();
        t--;
    }
}

}

link

answered 10 Jun '16, 22:28

a_0000_prerna's gravatar image

3★a_0000_prerna
1
accept rate: 0%

https://www.codechef.com/viewsolution/10533083 Can you check why am I getting a WA ?

link

answered 19 Jun '16, 04:53

debanjan_97's gravatar image

2★debanjan_97
1
accept rate: 0%

This problem can be easily solved using stacks. Here is my solution http://ideone.com/fork/WaJVs5 . If you find anything incorrect please let me know.

link

answered 24 Jun '16, 10:24

d4dev's gravatar image

3★d4dev
114
accept rate: 0%

Get videoder for HD videos download videoder

link

answered 24 Jun '16, 11:46

videoder's gravatar image

0★videoder
1
accept rate: 0%

include <iostream>

include <stdio.h>

include <algorithm>

int main() {

int cases, i;
scanf("%d", &cases);
for (i=0; i<cases; i++) {
    int n,j,k;
    long int a[100000];
    scanf("%d", &n);
    for (j=0; j<n; j++)
        std::cin>>a[j];
    for (j=0; j<n; j++) {
        int count=1;
        for (k=j; k<n; k++) {
            //printf("%d and %d\n", a[k], a[k+1]);
            if (a[k]*a[k+1] < 0)
                count++;
            else
                break;
        }
        printf("%d ", count);       
    }
    printf("\n");
}

return 0;

}

What is wrong in this code, Why is it showing Wrong Answer !

link

answered 20 Jul '16, 13:47

anantsharma18's gravatar image

4★anantsharma18
1
accept rate: 0%

All the test cases turn out fine.

(20 Jul '16, 13:48) anantsharma184★

include <iostream>

using namespace std;

int main() { int t; cin>>t; while(t--) { int n; cin>>n; string s; long long int x; int a[n]; for(int i=0;i<n;i++) {="" cin="">>x; if(x>0) s+='+'; else s+='-'; a[i]=1; } //cout<<s<<endl; for(int="" i="1;i&lt;n;i++)" {="" if(s[i]!="s[i-1])" a[0]++;="" else="" break;="" }="" cout<<a[0]<<"="" ";="" for(int="" i="1;i&lt;n;i++)" {="" if(a[i-1]="">1) { a[i]=a[i-1]-1; } else for(int j=i+1;j<n;j++) { if(s[j]!=s[j-1]) a[i]++; else break; } cout<<a[i]<<" "; } cout<<endl; } return 0; }

link

answered 03 Aug '16, 15:33

hsagarthegr8's gravatar image

2★hsagarthegr8
161
accept rate: 0%

wikified 03 Aug '16, 15:34

I am wondering if you could solve that problem using a segment tree ? Anyone used that approach ? Would it be more efficient ?

Thanks

link

answered 20 Jun, 18:33

sysm's gravatar image

2★sysm
111
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×1,259
×780
×39

question asked: 20 Mar '16, 17:34

question was seen: 5,707 times

last updated: 20 Jun, 18:33