WOUT - Editorial

@admin

but if long long int is required only by 2 or 3 variable why we declare all variable long long int…it slow down solution…because that can not handle at time in 64-bit machine it require double time compare int calculation because long long int 128-bit long variable cpu stored it into two-place and do calculation which simply increase the time required by machine to variable manipulation and calculation…
I think it is not good advice…you should only be aware which variable might get value out of range of int[-2^16 2^16-1]
integer range is quite long no need too worry much just take care of range only some cases…
Happy coding…

why editorialists use too much complex thing which really hard to understand why cann’t they use some images or any other resources to easily visualization of things…

this question was quite easy who knows about BIT/segment tree data structure(I also know…): P
but moment I saw explanation I got stuck and think is this question that much difficult??

is there a way where user also can make editorial too??.1.

Happy coding

13 Likes

Awesome solution! I dunno why the other users are complaining. Even I used a BIT solution to solve this. Thanks for showing me a faster way!

1 Like

Segment Tree solution of WayOut:-
https://www.codechef.com/viewsolution/7856183

1 Like

I used the same algorithm with Big(O) complexity but still I got TLE , I still don’t understand
Can anyone help me ? i am new to coding contests I solved a lot of practice problems although
https://www.codechef.com/viewsolution/7804230
https://www.codechef.com/viewsolution/7806640

I didn’t understand the question during the contest. But reading the problem statement in the editorial made me understand. I solved without reading the editorial any further. Should have paid more attention in the contest. Btw why are you using BIT or segment tree? Simple prefix sum works too.

My solution

3 Likes

What do we mean by this statement

Let C[ϕ(j)] be the number of js such that 0≤j<N and ϕ(j) is true.

what do we mean by this statement

Let C[ϕ(j)] be the number of js such that 0≤j<N and ϕ(j) is true.

Why my segment tree solution has not passed and given TLE please explain

https://www.codechef.com/viewsolution/7686894

@nil96 your solution didn’t passed as you need to optimize it by avoiding use of long long int. Use int instead and at last you can use long long int.

1 Like

sorry can some one explain, how
C[i=hj+1] and C[i=lj] are computed in O(N) ? Aren’t they supposed to be computed for every row ? In which case it would cost around O(N^2)?
I understood the rest of the prefix sum and how it is O(N) though.
I am in learning stage, any explanation would be helpful

Hi ,
I used the following approach for solving the problem without using bit/segment trees.

https://www.codechef.com/viewsolution/7726107

Hope this helps!!

I am getting wrong answer in 2 sections of subtask 2. Could somebody look and point out what me be wrong.
Here is a link to my solution: https://www.codechef.com/submit/complete/11254238

Why is r-1=N? Couldn’t get that.

this is not a dp question too a far and large extent … why wrong tag ??

1 Like

for integer value of constraints answer can be large more than integer limit that’s why you got WA it is advice to keep everything in long long for every question from now on :slight_smile:

3 Likes

thanx for looking into the problem @admin123 but i did try long long as well link and still WA

@admin…but if long long int is required only by 2 or 3 variable why we declare all variable long long int…it slow down solution…because that can not handle at time in 64-bit machine it require double time compare int calculation because long long int 128-bit long variable cpu stored it into two-place and do calculation which simply increase the time required by machine to variable manipulation and calculation…
I think it is not good advice…you should only be aware which variable might get value out of range of int[-2^16 2^16-1]
integer range is quite long no need too worry much

This was demonstrated in the first pseudocode of the editorial. Notice that:

  • This code clearly runs in O(N) time.
  • This code computes all C[i=hj+1] and C[i=lj] (for all j).
  • This only needs to be run once, at the beginning.

@rcsldav2017

Dude please tell me the easy way, this editorial has just crossed my head.