SEACO - Editorial

editorial
, , , ,
26

Can anyone give similar problem like this?

27

Sqrt decomposition technique works fine…AC in 0.33s

28

Solution using BIT. CodeChef: Practical coding for everyone

29

Finally was able to solve this after learning from the editorial about difference array. Here is my solution: [Yay! AC <3][1]
[1]: CodeChef: Practical coding for everyone

30

Please, someone tells how to solve this problem using fenwick tree(Binary Index Tree).
Share methods, not code. :slight_smile:

1 Like
31

For each command, we need to count how many times it’s executed during the whole process, denoted by cnt[i]. We can iterate the commands backwards, and every time we meet a command 2 l r which is executed k times, we add k to cnt[l∼r]. When we know cnt[i] for every command i of type 1, we can easily figure out the answer by maintaining the difference array of a.
Can anyone explain this.I am completely unable to understand.

32

lazy propagation is an overkill here actually. Normal segtree would work. I used a segtree but now am realising that there was an even easier way using a difference array.

2 Likes
33

yes, i realised that while solving it. There was no way 2k people would be able to solve it using segtrees.

1 Like
34

it usually happens they will just rectify it soon you must wait for sometime

35

Honestly I didnt expect it to cross 2k when I got AC for my sqrt decomposition method.

36

The editorial solution is O(n+m).

1 Like
37

You need to use modulo arithmetic when implementing BIT.

38

Oh right. I misread the alternative solution.

39

I used that but may not be correctly

40

@harsh24
I have used the same approach and got 100 points. I have added explanation just above, alongwith a link to my code.

Ask me anything if required…

Hers’s the link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please upvote if u find that helpful…

41

Because the alternative is to update the actual array, which will result in O (N) complexity per command, thus O (N^2) comolexity for whole task, giving TLE.

using difference array, u apply update in constant time.

I have used difference arrays only and got 100 points. I have added explanation just above, alongwith a link to my code.

Ask me anything if required…

Hers’s the link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please upvote if u find that helpful…

42

The contest has ended.

Now submission is not allowed for contest. U may solve the question in practice section using following link

This is the contest problem link.

Just remove the contest name and ull be able to submit solution…

Following link

43

I saw your code . The last part of your approach is the same as mine.But I haven’t yet found out the mistake in my code.Please tell me if you find any bug in my code.
Thank you

44

Hii! Can u please elaborate why did u do the following steps for type 2:


if(command[i][0] == 2){
                    range[command[i][2]]+=t+1;
                    range[command[i][1]-1] -= t+1;
                }

I mean I am not able to get why you add t+1 to range[command[i][2]] and subtract it from range[command[i][1]-1] and why not like you did in query of type 1!

Thanks :slight_smile:

45

Well, the essential point is given in the question itself,

“It’s guaranteed that r is strictly less than the enumeration/number of the current command.”

So, we run a loop in backward order, keeping track which command is to be executed how many times…

Well, a restore to actual sum sequence is required because after that, we are to provide for command type 1 also.

I have discussed my implementation in detail in the following link

https://discuss.codechef.com/questions/108189/seaco-editorial/110993

Please UPVOTE if you find this helpful…