Educational things (part 2)

general
,
1

I really like data structures, so here I’ll present 2 not really well-known tricks:

1. Have you heard about the problem with queries: add X( \leq 10^{18}) to the set and find the sum of all elements between L and R?

It sounds difficult and one may think about the treaps / C++ ordered sets / implicit segment trees and so on…

But there is an amazing and simple solution with… TRIE!!

Yes, observe that sum(L, R) = sum(0, R) - sum(0, L - 1).

Do you see how the Trie can be used?

2. Everyone knows that segment-tree has depth O(log N) and SQRT-decomposition has the depth = 2, but have you ever thought about hybrid data structure, for example 3-level sqrt decomposition, the array divided into N^\frac{1}{3} continuous sub-arrays and each that sub-array is divided into N^\frac{1}{3} continuous sub-arrays. The update will go in O(depth), but the query of sum on sub-segment will processed in O(N^\frac{1}{depth}).

3. Imagine you have the fixed pairing (in scenario of maximal matching). How quickly you can add/remove edges and recalculate the value of the maximal pairing?

P.S. I̶ ̶w̶o̶u̶l̶d̶ ̶l̶i̶k̶e̶ ̶t̶o̶ ̶i̶n̶v̶i̶t̶e̶ ̶t̶h̶e̶ ̶b̶e̶s̶t̶ ̶a̶n̶d̶ ̶t̶h̶e̶ ̶s̶w̶e̶e̶t̶t̶i̶e̶s̶t̶t̶t̶t̶ ̶a̶d̶m̶i̶n̶ ̶o̶f̶ ̶c̶o̶d̶e̶c̶h̶e̶f̶ ̶@̶v̶i̶j̶j̶u̶1̶2̶3̶ ̶t̶o̶ ̶e̶d̶i̶t̶ ̶t̶h̶e̶ ̶b̶l̶o̶g̶ @vijju123 your turn :stuck_out_tongue:

6 Likes
2

http://acm.timus.ru/problem.aspx?space=1&num=1896 -> the link to the problem pushed with the second technique

2 Likes
3

Going to learn a lot by efforts of @mgch :smiley:

1 Like
4

Oh, be careful :stuck_out_tongue:

1 Like
5

Lol. I thought @vijju123 is going write Educational things (part 3).

1 Like
6

Nah, people will say “Its too long, I didnt read it.” :slight_smile: xD

7

Nah, people will say “It’s too long and scary.” :slight_smile: xD

5 Likes
8

Excuse me. Before directly jumping on “Imagine you have the fixed pairing…” Can I get something where I can directly implement “maximal pairing” ??

9

Sorry for the inconvenience caused :slight_smile: It will be resolved asap

10

People != you and taran only.

1 Like
11

@aryanc403 stated public opinion :stuck_out_tongue:

12

For first problem, how are you planning to handle overflow? Maybe add constraints like printing answer modulo 1e9+7 (or some weird modulo of your choice).

Nice practice problem for second idea is SEGPROD. Looking for an explanation? See this answer by owner of this post here:smiley:

PS: Waiting for your educational rounds.

Also, first problem can be extended to handle delete-if-present queries.

13

@taran_1407 , let me clarify -

People = Public != Arayn+Taran

There are others, like @tarini_1407 who believe that the bigger the better :wink:

2 Likes
14

__int128 will works for overflows and deleting can be handled

Yes, I remember, but that idea is a bit different :wink: 1.5 months later gepardo published the good blog about that on codeforces

P.S. Hopefully, the first will be after snackdown

15

Of course, SEGPROD may have weak tests… :frowning:

1 Like