C21's blog

By C21, history, 3 weeks ago, In English,

Problem: https://www.codechef.com/problems/HLD/

I was only able to come up with the simple O(n^2) DP. I went through the editorial but didn't fully understand it.

Can someone share their ideas/approaches.

Any help would be appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By C21, history, 2 months ago, In English,

Problem: Given an array answer queries(online) of the form [L,R]=number of distinct elements in the array from index L to R.

What different approaches/solutions are there to this problem.

Few approaches I know/heard of:

1.Using Segment/Merge-Sort tree (link:https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n)

2.Modified Sqrt Decomposition (link:https://codeforces.com/blog/entry/44711?#comment-292719)

Are there any other interesting ways.

Also, what if we have update queries as well. (The above approaches will also work for updates but are there any other ways)

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it