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

×

CSUBSQ Editorial

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi

PREREQUISITES:

divide and conquer, dynamic programming

PROBLEM:

Let's call an integer sequence nice if the sum of its elements is divisible by a given integer $K$. You are given an integer sequence $A_1, A_2, \ldots, A_N$.

For an arbitrary non-empty sequence of indices $i_1 \lt i_2 \lt \ldots \lt i_M$, let's call a subsequence $A_{i_1}, A_{i_2}, \ldots, A_{i_M}$ very nice if it is nice and $i_M-i_1 \ge W$. Find the number of very nice subsequences modulo $10^9+7$.

EXPLANATION:

If approaching the array as a complete piece is kind of hard. Try to use divide and conquer. In our problem, it works pretty fine. (There were some solutions without divide and conquer but probably harder to come up with).

Let's suppose we are processing a part of the array $A[L\,...\,R]$.

Break it into 2 pieces, $A[L\,...\,mid]$ and $A[mid+1\,...R]$. where $(mid = \frac{L+R}{2})$

Subsequences completely residing in the left part can be calculated by passing the left part to our divide and conquer function. We should do the same for the right part also.

Now we should calculate the very nice subsequences that have at least one element in the left part and one element in the right part.

Let's introduce 2 functions:

$F_{left}(pos, m)$ denotes the number of subsequences considering numbers in the subarray $A[pos,mid]$ and have their sum modulo $K$ equal to exactly $m$.

$F_{right}(pos, m)$ denotes the number of subsequences considering numbers in the subarray $A[mid+1,pos]$ and have their sum modulo $K$ equal to exactly $m$.

calculating both of tables is a simple DP exercise that's left to you. Calculating both tables take $O((R-L+1)*K)$ in total.

Now let's find our nice subsequences.

Fix the rightmost element (which has index $i_M$ in problem description). For each $x$ in range $[0,K-1]$ let's find the number of subsequences in the right part such that the last element is our fixed element and their sum modulo $K$ is equal to $x$. Their number is $F_{right}(i_M,x)-F_{right}(i_M-1,x)$

(consider processing one possible value of $x$ as the process will be the same for the rest).

Now we want to combine these subsequences with some subsequences from the left part (they must have their sum modulo $K$ equal to $y=K-x$). The first element must be at least $W$ elements away from the last one. Since we fixed the last one, our life is much easier now. The first element has index $i_1 <= i_M-W$.

By the same logic, what is the number of subsequences in the left part such that the first element has the index $i_1$ which is at most $i_M-W$ and have sum modulo $K$ equal to $y$. Well it's equal to $F_{left}(L,y)-F_{left}(i_M-W+1,y)$

So for a fixed last element $i_M$ and a fixed modulo sum $x$ if the right part's subsequence

$Result \, += \, (F_{right}(i_M,x)-F_{right}(i_M-1,x)) \, * \, (F_{left}(L,y)-F_{left}(i_M-W+1,y))$

Complexity: $O(N*K*log\,N)$

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution

TESTER's solution

This question is marked "community wiki".

asked 24 Dec '18, 16:58

deadwing97's gravatar image

3★deadwing97
108830
accept rate: 0%

edited 25 Dec '18, 04:25

admin's gravatar image

0★admin ♦♦
19.8k350498541


We can do it in O(N*K).Make blocks of size W and do dp on prefix and suffix! link to submission : https://www.codechef.com/viewsolution/22073432

link
This answer is marked "community wiki".

answered 25 Dec '18, 22:01

zetapi's gravatar image

6★zetapi
12
accept rate: 0%

edited 25 Dec '18, 22:01

https://www.codechef.com/viewsolution/22085609. I have tested my solution with my own test generator and in the worst case (i.e all variables at their extremes) it takes 6.2 sec on my computer. Since the time limit is 5 sec, I am getting TLE. I was wondering what I should do to make my solution run within 5 sec.

link

answered 25 Dec '18, 21:38

vijay1999's gravatar image

4★vijay1999
1
accept rate: 0%

Aah, yes that's right! Very nice solution. Thank you @zetapi

link

answered 25 Dec '18, 22:51

vijay1999's gravatar image

4★vijay1999
1
accept rate: 0%

toggle preview
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:

×15,639
×2,167
×136
×74
×4

question asked: 24 Dec '18, 16:58

question was seen: 427 times

last updated: 25 Dec '18, 22:51