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

×

# Yahoo Hackathon DP Problem

 4 1 There is a sequence of N random integers, which can contain any integer between -10 and 10 (both of which are inclusive). The task is to find the number of continuous sequences of integers such that their sum is -1 or +1 1 <= n <= 10^6 asked 22 Jun '13, 18:18 156●2●5●8 accept rate: 14%

 10 Well since you didn't give any memory limit, i'm just going to assume it's 256MB. Let dp[i] be the sum from 0..i for example : dp[2] = array[0] + array[1] + array[2]. Calculate the dp array : dp[i] = dp[i - 1] + array[i]. Let cnt[dp[i]] be the number of times dp[i] appears.Array cnt ranges from -10.000.000 to 10.000.000. Iterate through every dp[i], i = 0..n-1 and to the answer add cnt[dp[i]+1] and cnt[dp[i]-1]. Reason is you are trying to find a number of pairs of indices (i, j) such that j < i and dp[i] - dp[j] = -1 or 1. Don't forget to use a 64bit integer as an answer. Also don't forget to count every dp[i] that's 1 or -1. Here is a simple pascal code. var cnt:array[-10000000..10000000] of integer; dp:array[0..1000000] of integer; currNum, N, i:integer; ans:int64; begin read(N); for i := 0 to N - 1 do begin read(currNum); if (i <> 0) then dp[i] := dp[i - 1]; dp[i] := dp[i] + currNum; ans := ans + cnt[dp[i] + 1]; ans := ans + cnt[dp[i] - 1]; if (dp[i] = -1) or (dp[i] = 1) then ans := ans + 1; cnt[dp[i]] := cnt[dp[i]] + 1; end; writeln(ans); end.  Complexity : O(N). Memory used : 41248 kB. http://ideone.com/T9v3Kc - ideone link where you can test the code. answered 23 Jun '13, 12:28 575●1●5●11 accept rate: 13% Brilliant answer. Cleverly avoiding the double-counting and took care of the corner case. (23 Jun '13, 15:36)
 1 I think the following code can solve the problem. If any explanation is wanted, please ask I shall explain. #include #include #define OFFSET 1000000 #define LIMIT 1000000 main() { int sumupto[LIMIT+2]; int countsum[20*LIMIT+2];//mapping is as 0->-10000000 and 20000000-> +10000000 int n,num; unsigned long long int ans=0; int sum=0; scanf("%d",&n); for(int i=0;i<20*LIMIT+2;i++)countsum[i]=0; for(int i=0;i
 0 Hello, As the use of DP is needed, I say that I also don't know how to solve this problem, but, usually, a recurrence relationship needs to be derived, especially one that can exploit the property of optimal substructure... For instance, let's try to denote: S(i,j) -> sum of the elements of the array that start at element i with length j; Also let our array be denoted as Arr. As we want a contiguous subsequence, we can have three cases to consider now: Case 1 S(i,j) = -1 or S(i,j) = 1, case where we add this sequence to our total sequence counter. Case 2 S(i,j) + Arr[i+j+1] > 1 or S(i,j) + Arr[i+j+1] < -1; This case means that, as the next element on our array, (remember we start on element i and have a sequence of length j) A[i+j+1] is not a suitable candidate to form an admissable sequence, so we can possibly restart our sequence counter as S(i+j+1, vl), where vl denotes the variable length that our new subsequence can take. Case 3 A case where S(i,j) + Arr[i+j+1] = -1 or S(i,j) + Arr[i+j+1] = 1, case where we should count this sequence and where we have S(i,j+1) being similar to case 1. Possibly there might be more cases or this formulation might be incorrect, and maybe someone more skilled than me can help you better... I just wrote the formulation that came to my head. This seems like a mix between Kadane's algorithm and the subset sum problem, but I am yet too newbie in DP to help in a more specific way... Best regards, Bruno answered 22 Jun '13, 21:39 3★kuruma 17.7k●72●143●209 accept rate: 8%
 0 #include #include int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); int arr[n],i,j,count=0,c,sum; for(i=0;i
 toggle preview community wiki:
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:

×2,172

question asked: 22 Jun '13, 18:18

question was seen: 3,787 times

last updated: 14 Aug '13, 00:45