×

# In search of an editorial of Poo Poo

 0 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 :) asked 29 Aug '17, 00:54 614●1●9 accept rate: 12%

 5 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. answered 29 Aug '17, 01:46 1.1k●5 accept rate: 17% 1 Thank u so much :) (29 Aug '17, 10:01)
 0 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; }  answered 29 Aug '17, 01:31 2★ramini 61●5 accept rate: 8%
 0 @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 :). answered 29 Aug '17, 16:42 1★pixel0x8 1●1 accept rate: 0%
 0 Can we solve this problem with square root decomposition? answered 29 Aug '17, 22:20 94●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,494
×2,700
×135

question asked: 29 Aug '17, 00:54

question was seen: 460 times

last updated: 29 Aug '17, 22:20