# Consecutive Subsequences

# Consecutive Subsequences

Dark_Knight99 + 1 comment can anyone plz explain me the logic of choosing two 0's and two 1's to get the consecutive subsequence as given in editorial ?

mohammadhb25 + 0 comments There are for example {0110011} mods of accumulated numbers right? then you wanna choose i and j so you have to select some elements that their difference %k is 0 then you can assure that their sum is divisible.

bh2smith + 1 comment I would like to point out that, the notion of

*consecutive*here is misleading. Espesially considering all of the examples suggest something that was not intended.This could easily be avoided by including even a single example that would where the subarrays that fit the description are not always of each other.

rofi93 + 1 comment How the notion of of

*consecutive*is misleading here? The only thing I find misleading is your comment.GeoMatt22 + 0 comments I also found it confusing at first. I think many people interpret subsequence to be analogous to substring. Perhaps "contiguous subsequence" would be more clear?

umeshkumarmahato + 1 comment Scanner sc = new Scanner(System.in); int size = sc.nextInt();

`for(int l = 0; l < size; l++) { int n = sc.nextInt(); int k = sc.nextInt(); long[] numbers = new long[n]; for(int i = 0; i < n; i++) { numbers[i] = sc.nextLong(); } long[] prefixModCount = new long[k]; for(int i = 0; i < k; i++) { prefixModCount[i] = 0; } prefixModCount[0] = 1; int prefixSum = 0; for(int i = 0; i < numbers.length; i++) { prefixSum += numbers[i]; prefixSum %= k; prefixModCount[prefixSum] += 1; } long result = 0; for(int mod = 0; mod < k; mod++) { result += prefixModCount[mod] * (prefixModCount[mod] - 1) / 2; } System.out.println(result); }`

killmachine3000 + 0 comments for(int i = 0; i < k; i++) { prefixModCount[i] = 0; }

They are already 0.

laishaovan + 0 comments Anyone passed with Python? I passed with C++ but TLE with Python3 with the exact same algorithm.

vivek4434 + 1 comment #include<iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int n,k; cin>>n>>k; long pre[n],F[n],i; for(i=0;i<n;i++) cin>>F[i]; pre[0] = F[0]; for(i=1;i<n;i+=1) pre[i] = F[i] + pre[i-1]; int count[111]= {0}; count[0] = 1; for(i=0;i<n;i++) count[pre[i]%k]++; long sum=0; for(i=0;i<=110;i++) sum += count[i]*(count[i] -1)/2; cout<<sum<<endl; } return 0; }

Don't Know why it is showing WA in CASE #3 ... Any help will be appreciated.

m_gagik + 0 comments change "int count[111]= {0};" to "long count[111]= {0};" when k==1 ( test #3)then max count of result is encountered hence count[0] == n*(n+1)/2, which is bound to 10^12. also count[100] should probably do fine in your code since k <= 100. note also that when k==1 answer is known right away - n*(n+1), so some more runtime gain ))))

regards

Pwochnowski + 1 comment I'm passing all the other tests, but getting an abort on the last one. I've checked the input/output and I'm getting the correct answer running it on my own computer. Could it be a time out issue, even though the error I'm getting is abort called?

m_gagik + 0 comments it happened to me several times(with other problems). I managed to verify that program throws exception by inserting try-catch in different lines, particularly for lines of code doing memory allocation (with "new"), thus verified that it was a memory limitation issue. when I decreases O(n^2) memory usage - it passes. However it can be other reasons as well like overflow(you computer may have other arch of course) and as a consequence - division by zero etc. this happened to me too )). regards.

kiner_shah + 1 comment In first sample input..the possible sub sequence cud be..1 3 4 1..right? It's not given there!

bpmoehringAsked to answer + 1 comment **Endorsed by kiner_shah**No. While 1 3 4 1

*is*a subsequence of 1 2 3 4 1, it's not formed by using*consecutive*terms, because you removed the 2 from between the 1 and the 3. Therefore, we wouldn't consider 1 3 4 1 in this challenge. If it helps at all, you can replace "consecutive" with "contiguous" (which I would argue is a more appropriate descriptor for the subsequences themselves).kiner_shah + 0 comments Okk..means we have to take only consecutive subsequence! Thnxx!!

No more comments

Sort 7 Discussions, By:

Please Login in order to post a comment