Alternating subarray prefix | CodeChef (DP SOLUTION)

general
,
1

Problem statement:: CodeChef: Practical coding for everyone
My solution:: CodeChef: Practical coding for everyone

Getting Runtime Error :: SIGCONT
Please Help !!!

2

Use the following recursive equation for longest alternating prefix for every a[i].
I am using dp[i] for representing the longest alternating prefix from i^{th} index in a[i].

dp[i] = \begin{cases} 1, & \text{i = n - 1}\\ 1, & \text{if $a[i]$ and $a[i + 1]$ have same-signs.} \\ dp[i + 1] + 1, & \text{if $a[i]$ and $a[i + 1]$ are of opposite signs.} \end{cases}

Start filing the dp[i] array from n - 2 index as we know the answer for dp[n - 1].
Then just print the dp[i] from 0 to n - 1.

NOTE: I am using zero-based indexing for filling the data and traversing the dp[i] array.

Solution Source-Code Link: CodeChef: Practical coding for everyone

Thanks for reading.
Peace :v:

3

Can you explain what is wrong in my solution ???

4

In short, SIGSTOP tells a process to “hold on” and SIGCONT tells a process to “pick up where you left off”. This can work really well for rsync jobs since you can pause the job, clear up some space on the destination device, and then resume the job. The source rsync process just thinks that the destination rsync process is taking a long time to respond.

You can read about the above runtime-error code SIGCONT here: SIGSTOP and SIGCONT

EDIT: Your code is not giving SIGCONT signal i.e. runtime-error rather its a wrong answer, that means you are missing something.
Your code is giving incorrect output for the following test-case:

2
4
-1000000000 -1000000000 -1000000000 -1000000000
4
-1000000000 1000000000 -1000000000 1000000000

Your code has a lot of bugs, I am listing them down:

  • If you look at the constraints, the value of a[i] can go as large as 10^{9} and as small as 10^{-9}. Moreover you are using multiplication to check whether the number is -ve or not, which leads to an integer overflow as you have defined the data-types of res and memo[n] as int. I will leave the math to yourself to figure it out, why integer-overflow .

  • Why are you checking for x == n?

  • Why are you using recursion when there is a simple iterative solution to the problem using DP. Think about what if the constraints for N is of the order of 10^{18}, then there would be a lot of recursive calls which will lead to runtime-error.

Some Suggestions on your code:

  • If there exist a recursive and iterative solution for the problem, always go for the iterative approach unless iterative approach is complex than recursive approach, like merge-sort recursive approach is much simpler than iterative one.
  • Format your code properly, when I read your code, there are a lot of confusion about if-else block, also the indentation of your code is messy.
    Always use the {} even if there is only one statement associated with if-else or loops, it makes code easier to read.

At last you can refer to the edited version of your accepted solution. I wouldn’t suggest you to implement it again, rather find out another way of thinking to solve the problem, I already gave you the idea here.

Thanks for reading.
Peace :v:

1 Like
5

Thanks @striker22 for debubgging my code and giving a fruitful review .

6

No problem :+1:

1 Like