algorithm - DP with Segment Tree and Lazy Propagation -


i read simple problem, , tried complex further , further , included other concepts along that. got stuck @ 1 point , cannot resolve further now.

problem 1: given array, there q queries have find out next greater element of element in array.

ex: array: 1,2,4,3,5 next greater element of 2 4, next greater element of 4 5 5 not have next greater element.

solution: can use stack , can solved in o(max(n,q)). can find out here.

problem 2: have find out next ith greater element, when saying next ith greater element, mean, make strictly increasing array greedily, starting given element , tell me ith element in that. (if see closely it's related problem 1).

ex: next 2nd greater element of 2 in 1,2,4,3,5 5 , not 3. because increasing array 2,4,5 starting 2 , made greedily.

solution: can solved using dp, make array of n x log(n) , i,j element of table store next 2^j th greater element index of ith element. table can filled column wise this:

dp[i][j] = dp[dp[i][j-1]][j-1];

where 0th column filled using stack solved in problem 1. hence query complexity o(nlog(i)) , space complexity o(nlog(n)).

problem 3: let's make problem 1 dynamic. let's can update range of array increasing or decreasing number. , query next greater element of ith element.

ex: array: 1,2,4,3,5. here next greater element of 4 5. let's updated range[4,5] 3 new array be, 1,2,4,6,8. next greater element of 4 6.

solution: not solve problem in reasonable complexity, point observed here is, if updating range elements effected(whose next greater change) lie in range next greater lie outside range , on left side of range next greater element lie inside or on right side of range.

so, tweaked little bit, , said have see next greater element in small next range, if greater element exist ok otherwise -1. ex: if small range 2 next greater element 6 in 4,3,2,6,5,7 7 4 none or -1. because 6 lie @ distance of 3.

now problem can solved involving segment tree picture. whenever there range[lower,upper] update have update solution left part(lower-smallrange,lower+smallrange) , right part(upper-smallrange,upper+smallrange) in solution (lower-smallrange,lower) , (upper-smallrange,upper) update only(it can seen above logic). , while applying stack method used in problem 1, have current value @ index after multiple range update using segment tree in o(log(n)). can solved in o(q * smallrange * log(n)) q number of queries.

problem 4(main problem): let's combine problem 2 , problem 3, there 2 types of queries now, in first query have find ith greater element of given element. , in second query can update range number. not solve after including smallrange concept used in problem 3.

ex: array: 1,2,4,3,5. here 2nd next greater element of 2 5. let's updated range[4,5] 3 new array be, 1,2,4,6,8. 2nd next greater element of 2 6.

solution: thinking mix both solutions used in problem 2 , 3 main problem is, in dp table elements other smallrange(as mentioned in problem 3) affected because of 2^j concept used in table. , affect complexity badly. in other way, not take smallrange here used in problem 3. tried think use lazy propagation inside dp table did not either.

i know long problem, tried explain stepwise. hope read , me here.


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj
Read more

performance - Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures? -

i'm doing micro-optimization on performance critical part of code , came across sequence of instructions (in at&t syntax): add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx i thought had use case xchg allow me shave instruction , write: add %rbx, %rax xchg %rax, %rdx however, dimay found agner fog's instruction tables , xchg 3 micro-op instruction 2 cycle latency on sandy bridge, ivy bridge, broadwell, haswell , skylake. 3 whole micro-ops , 2 cycles of latency! 3 micro-ops throws off 4-1-1-1 cadence , 2 cycle latency makes worse original in best case since last 2 instructions in original might execute in parallel. now... cpu might breaking instruction micro-ops equivalent to: mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx where tmp anonymous internal register , suppose last 2 micro-ops run in parallel latency 2 cycles. given register renaming occurs on these micro-architectures, though, doesn't make sense me done way. why wouldn't register renamer
Read more

jquery - Responsive Navbar with Sub Navbar -

good day, forgive me nav vocabulary not best. if question confusing apologize. i'm working on navigation bar needs centered on page @ 768px , above. items in nav open (or perhaps toggle) subnav lives directly below. these nav should appear centered on page. i have been able work through responsive portion of nav bar, having main items align vertically , sub nav menu of each item roll out below, , gave them indent separation. working well. however, issue not responsive side, behavior @ width greater 768px. happens toggling menu's sub navigation pushes other main items down page below sub nav. here's code: $(document).ready(function () { //stick in fixed 100% height behind navbar don't wrap $('#slide-nav.navbar-inverse').after($('<div class="inverse" id="navbar-height-col"></div>')); $('#slide-nav.navbar-default').after($('<div id="navbar-height-col"></d
Read more