In search of an editorial of Poo Poo

editorial
, ,
1

Hello guys!
I am in search of a detailed editorial on the problem Poo Poo from the recent LoC Aug contest. It would be of great help to me and many others if any one can step up for this!!

I personally would request @likecs to at least explain his solution because I saw his submission took very less execution time and I am learning Segment Tree too. Also the editorials he posted for LunchTime were just amazing!!

Thanks for the help :slight_smile:

2

Hey! Did you solve ALATE? I got only 20 points for it. Can you please explain it so that I can pass Sub task 2 without TLE? Please provide an improvement.

Here is my code.

#include bits/stdc++.h
#define ll long long
#define MOD 1000000007
#define N 1000005
using namespace std;
ll a[N],n;
ll func(ll x)
{
    ll k,sum=0;
    for(ll i=x;i<=n;i+=x)
    {
        k=(a[i]*a[i])%MOD;
        sum=(sum+(a[i]*a[i]))%MOD;
        sum%=MOD;
    }
    return sum;
}
int main()
{
    ll t,q,i,j,qno,x,y;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&q);
        for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
        for(j=1;j<=q;j++)
        {
            scanf("%lld",&qno);
            if(qno==1)
            {
                scanf("%lld",&x);
                printf("%lld\n",func(x));               
            }
            else
            {
                scanf("%lld%lld",&x,&y);
                a[x]=y;
            }       
        }
    }
    return 0;
}

```
3

Let us take an example, A = [a,\ b,\ c]

The subsequences of A with their PooPoo sum are:

[a] : (a)^2 = a^2
[b] : (b)^2 = b^2
[c] : (c)^2 = c^2
[a, b] : (a - b)^2 = a^2 + b^2 - 2ab
[a, c] : (a - c)^2 = a^2 + c^2 - 2ac
[b, c] : (b - c)^2 = b^2 + c^2 - 2bc
[a, b, c] : (a - b + c)^2 = a^2 + b^2 + c^2 + 2(-ab - bc + ac)

If we add them, we get :- 4[(a^2 + b^2 + c^2)\ -\ (ab + bc)]

For 4 elements, we get :- 8[(a^2 + b^2 + c^2 + d^2)\ -\ (ab + bc + cd)]

As you would have guessed from the pattern, the answer for array A of n elements is:

2^{n-1}\ \Big(\ \sum_{i\ =\ 1}^{n}\ A_i^2\ - \sum_{i\ =\ 1}^{n-1}\ A_i * A_{i+1}\ \Big)

Now the question reduces to the following:

For a given range [L,\ R], find the sum of squares of the elements and the sum of the product of adjacent elements, along with point updates.

The above operations deal with range sums and point updates and hence can be solved by using Segment Trees or Binary Indexed Trees (BIT) / Fenwick Tree.

Here are my codes:

Using Segment Tree: https://www.codechef.com/viewsolution/15108856

Using Fenwick Tree: https://www.codechef.com/viewsolution/15112212

To keep things separate, I’ve used one tree to store the sum of squares of elements and the other to store the sum of the product of adjacent elements.

5 Likes
4

Thank u so much :slight_smile:

1 Like
5

@ramini If you are searching for a solution to Always Late, just look at @rns_kjch 's solution. It is very intuitive and easy to understand.

P.S.: Sorry, I didn’t know how to comment on an answer :).

6

Can we solve this problem with square root decomposition?