ALTARAY - Editorial

One question we can ask in an interview will be to how to treat 0’s .

check out a very simple solution here
https://github.com/anjn98/codechef/blob/master/ALTARAY.cpp

#include<stdio.h>
#define MAX 1000007
typedef long long int ll;

int stk[MAX];
int top = -1;
 
int empty(){
 
    return top == -1;
}
 
void push(int x){
 
    stk[++top] = x;
}
 
int pop(){
 
    if(!empty())
        return stk[top--];
}
 
int peek(){
 
    if(!empty())
        return stk[top];
}
 
 
int main(int argc, char const *argv[])
{
    /* code */
    int t;
    scanf("%d",&t);
    
    while(t--){
 
        int n;
        scanf("%d",&n);
 
        int res[n],s[n];
        ll a[n];
        for(int i=0;i<n;i++){
 
            scanf("%lld",a+i);
            res[i] = 1;
            s[i] = (a[i]>0)? 1 : -1;
        }
 
        
        top=-1;
        int cnt=0;
        for(int i=0;i<n;i++){
 
            if(!empty() && (s[peek()] == s[i]) ){
 
                cnt=0;
                while(!empty()){
 
                    res[peek()] += cnt++;
                    pop();
                }
            }
            else
                push(i);
        }
 
        cnt=0;
        while(!empty()){
 
            res[peek()] += cnt++;
            pop();
        }
 
        for(int i=0;i<n;i++)
            printf("%d ",res[i]);
        
        printf("\n");
    }
    return 0;
}

I want to know on which test case this stack implementation fails…help…

could someone help why i am getting RTE here

def getAlt(arr):
n = len(arr)
ans = [1]*n
for i in range(n-2, -1, -1):
# print(ans[i], ans[i+1])
if (arr[i] < 0 and arr[i+1] > 0) or (arr[i] > 0 and arr[i+1] < 0):
ans[i] += ans[i+1]
# print(ans)
print(’ '.join(str(x) for x in ans))

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    getAlt(arr)

A simple pytonh DP approach utilising the fact that minimum length will be taken as 1 per index

Why can’t we do this?

  1. Change every positive element to 1 and every negative element to -1
  2. Then calculate to product of every two consective terms of the new array
  3. Check the maximum number of continuous -1 's in the product array
  4. The answer is max number of -1 's (-1)
1 Like

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

@dpraveen

CodeChef: Practical coding for everyone ← this is solution where a is long long int(WA)
CodeChef: Practical coding for everyone ← this is the other one(AC)

The Above solutions are similar to solution in editorial

CodeChef: Practical coding for everyone ← This is the one I submitted during contest.(WA)

CodeChef: Practical coding for everyone ← This is with a is long long int (WA)

CodeChef: Practical coding for everyone ← This is the same submission with only one change as mentioned above in previous comment(i.e. including 1ll). (AC)

1 Like

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

1 Like

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

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.