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.
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.
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
#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;
}
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--;
}
}
}
This problem can be easily solved using stacks. Here is my solution Online Compiler and IDE >> C/C++, Java, PHP, Python, Perl and 70+ other compilers and interpreters - Ideone.com .
If you find anything incorrect please let me know.
#include
#include <stdio.h>
#include
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 !
#include
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<n;i++)
{
if(s[i]!=s[i-1])
a[0]++;
else
break;
}
cout<<a[0]<<" β;
for(int i=1;i<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;
}
I am wondering if you could solve that problem using a segment tree ? Anyone used that approach ? Would it be more efficient ?
Thanks
One question we can ask in an interview will be to how to treat 0βs .
#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β¦
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?
- Change every positive element to 1 and every negative element to -1
- Then calculate to product of every two consective terms of the new array
- Check the maximum number of continuous -1 's in the product array
- The answer is max number of -1 's (-1)
There is something wrong in your claims. Can you give links of both the solutions?
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)
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
Tried inputting many cases and getting every tym correct answer.Still i am getting WA in ur compiler