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

×

In search of an editorial of Poo Poo

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

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

edited 29 Aug '17, 00:56


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.

link

answered 29 Aug '17, 01:46

c_utkarsh's gravatar image

5★c_utkarsh
1.1k5
accept rate: 17%

1

Thank u so much :)

(29 Aug '17, 10:01) dishant_185★

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; }

link

answered 29 Aug '17, 01:31

ramini's gravatar image

2★ramini
615
accept rate: 8%

@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 :).

link

answered 29 Aug '17, 16:42

pixel0x8's gravatar image

1★pixel0x8
11
accept rate: 0%

edited 29 Aug '17, 16:43

Can we solve this problem with square root decomposition?

link

answered 29 Aug '17, 22:20

phantomhive's gravatar image

4★phantomhive
944
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,494
×2,700
×135

question asked: 29 Aug '17, 00:54

question was seen: 460 times

last updated: 29 Aug '17, 22:20