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

×

CHEFARRP - Editorial

1
1

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an array, we have to report the number of subarrays such that the product of all numbers in that subarray is equal to the sum of all numbers in that subarray.

EXPLANATION:

The problem is very direct given the size of the input array. Since $n \leq$ 50, we can directly iterate over the subarrays and calculate product and sum. The editorialist's solution is very clear in describing the approach. Below is the pseudo-code of the same:

function get_ans(input_array[n])
{
    int count = 0;
    for(i = 1 to n)
    {
        int sum = 0, product = 1;

        for(j = i down_to 1)
        {
            //considering all subarrays ending at i.

            sum = sum + input_array[j];
            product = product*input_array[j];

            if(sum == product)
                count = count+1;
        }
    }

    return count;
}

COMPLEXITY:

$\mathcal{O}(n^2)$ per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 16 Dec '15, 14:51

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 09 Feb '16, 13:54

admin's gravatar image

0★admin ♦♦
19.8k350498541


@mgch

Actually.

Since there can't be too many numbers greater than 1 in any such subarray (since the product grows exponentially, $O(\log{sum})$ at most), you can store just the numbers greater than 1 in another array and try all their subarrays - there are $O(N\log{sum})$ of them. For each such subarray, you know the product, which the ignored 1-s don't change; this subarray corresponds to subarrays $[a,b]$ in the original array, where $a$ and $b$ must be in some, disjoint, ranges (only up to the first integer $> 1$ to the left/right); the sum is a linear function of $b-a$ and since it has to be equal to the product, any $a$ for which we have a valid $b$ gives one of the counted subarrays; we just need to find the range of such $a$-s.

For a given subarray of integers $> 1$, everything can be implemented in $O(1)$, so we have $O(N\log{sum})$ time complexity.

link

answered 21 Dec '15, 02:17

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

edited 21 Dec '15, 02:18

nice explanation....

(21 Dec '15, 16:01) likecs6★

I did the same way and got correct answer. But what if n would have been a large number? What is a faster(in terms of time complexity) way to do it ?

link

answered 21 Dec '15, 00:28

infinitparadox's gravatar image

3★infinitparadox
111
accept rate: 0%

@infinitparadox

Good question, I think in this problem nothing faster than O(n^2). If someone has something better, I will glad to hear it.

link

answered 21 Dec '15, 01:14

mgch's gravatar image

6★mgch
4051435
accept rate: 20%

How to solve the same problem for larger numbers and strict time limit!!!

link

answered 27 Dec '15, 00:00

sierra101's gravatar image

2★sierra101
11
accept rate: 0%

I have submitted the sol. but m getting a nzec. I am using string.split("\s+"). Any suggestions ?

link

answered 18 Feb '16, 20:19

krittam's gravatar image

0★krittam
1
accept rate: 0%

Pardon me if i am missing something elementary, but wouldn't this fail with an inputs such as [2,3,2]?

This algo will not be able to generate 2,2 as a possible option and will return the result as 3. The result should be 4. [2], [3],[2],[2,2]

link

answered 20 Mar '16, 16:52

sampod's gravatar image

0★sampod
1
accept rate: 0%

Pasting a reply from Stackoverflow about what is a subarray

"I think the subarray means the array in which the contiguousness is based on the index . for example lets take an example 2 3 1 3 1 (index are 0,1,2,3,4 respectively ) so subarray is 2,3,1 3 (index 0,1,2,3) But (1,2 1) (index 2,0,4) cannot be a subarray coz the indexes are non-contiguous .."

Your example [2, 3 ,2] The [2, 2] array has indexes 0, 2 which are non-contiguous. Therefore, it can't be an option for subarray

link

answered 25 Mar '16, 20:10

povi's gravatar image

0★povi
1
accept rate: 0%

this editorial isn't completely correct,what if some random number position elements yield such type of sub-array for ex like a[o],a[3],a[9].this case i not incuded in the editorial

link

answered 22 Nov '16, 23:58

ajaman13's gravatar image

3★ajaman13
1
accept rate: 0%

@ajaman13 see the explanation by @povi

link

answered 01 Jun '17, 20:41

alphasingh's gravatar image

3★alphasingh
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,683
×1,173
×951
×105
×3

question asked: 16 Dec '15, 14:51

question was seen: 6,822 times

last updated: 01 Jun '17, 20:41