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

×

What is the logic behind this problem "Number of ways" ?

How do I solve this problem ? Number of ways . I read the editorial here but didnt quite understand why cnt[i+2] is being added when ss==s . The editorialist's solution can be found here.

asked 25 May '17, 21:38

chari407's gravatar image

2★chari407
44827
accept rate: 0%


I think it will become clear with an example.

Let's assume the given array is a = [0 0 0 0 0].

"Let’s create an array cnt[], where cnt[i] equals 1, if the sum of elements from i-th to n-th equals S/3 and 0 — otherwise." -where S is the sum of all the elements of the array a. Constructing the cnts array, we get
a = [0 0 0 0 0]
cnts = [1 1 1 1 1]

"Now, to calculate the answer we have to find the sum cnt[j] + cnt[j+1] + ... + cnt[n] faster then O(n). There are a lot of required ways to do this, but the easiest one is to create a new additional array sums[] where in j-th element will be cnt[j] + cnt[j+1] + ... + cnt[n]"
a = [0 0 0 0 0]
cnts = [1 1 1 1 1]
sums = [5 4 3 2 1]

"Thus, we receive very simple solution: for each prefix of initial array 1..i with the sum that equals we need to add to the answer sums[i+2]."

We are required to break the given array into 3 pieces. If we are at the i-th element and the sum of elements from 0 to i is equal to S/3 then the segment from 0 to i is a valid first piece of the array. And for all the position j where cnts[j] is 1, the segment from j to the end is a valid third piece of the array. Since we require a second piece of the array, there must be a segment of non-zero length between these 2 segments, which is why the "i+2" comes in. It ensures that the second segment is of length ≥ 1. Hence if you choose the given prefix 0 to i with sum S/3 as the first piece, then the number of ways to choose the third piece is equal to the number of positions ≥ i+2 where the cnts[] value is 1. This is nothing but sums[i+2].

Getting back to the example, only 3 prefixes within acceptable range have sum S/3 marked with | and their +2 positions marked with ^.
a = [0 0 0 0 0]
cnts = [1 1 1 1 1]
sums = [5 4 3 2 1]
. |---^
. |---^
. |---^

The answer is hence 3+2+1=6, and the actual 6 ways are
[0 | 0 | 0 0 0]
[0 | 0 0 | 0 0]
[0 | 0 0 0 | 0]
[0 0 | 0 | 0 0]
[0 0 | 0 0 | 0]
[0 0 0 | 0 | 0]

link

answered 26 May '17, 05:06

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

edited 26 May '17, 05:19

Thanks a lot mate.

(26 May '17, 07:11) chari4072★

No problem :)

(27 May '17, 02:17) meooow ♦6★
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:

×682

question asked: 25 May '17, 21:38

question was seen: 846 times

last updated: 27 May '17, 02:17