c++ - Calculation of Expected number of inversions in a changing array -


problem: have array of size n , allowed perform @ k operations each operation can

  1. decrease number of inversions 1.
  2. make random shuffle of whole array.

my problem perform k operations in such way expected number of inversions in final array minimized.

constraints:
100s of testcases
1 < n < 100
1 < k < n(n-1)/2

my approach: thinking dynamic programming solution. can calculate probabilities of having e inversions in array of size n using mahonian numbers. fill array dp[k+1][1+n(n-1)/2] row wise such dp[i][j] denotes minimal expected inversions in array having j inversions after i operations have been performed , using can generate minimal expected value (i+1)<sup>th</sup> operation possible inversions in array.

the problem approach probabilities not accurate due limitation of doubles in c++ , algorithm o(kn<sup>2</sup>) each test case slow.

for example:
probability of having no inversion in array of size 100 = 1.0/factorial(100) ~ 10<sup>-160</sup> (i think there lack of precision here).

i think there accurate , more efficient approach. please suggest ideas.

thank you

in order answer question going need able compute expected #inversions assuming have k moves left , assuming @ kth move shuffle , decide stop shuffling (and subtract 1) or continue shuffling depending on how many inversions after shuffle. easy if have 2 moves left , current #inversions greater n(n-1)/4. shuffle first, , stop shuffling , subtract 1 second move if number of inversions n(n-1)/4 or lower after first shuffle, , shuffle again if number of inversions greater n(n-1)/4 after first shuffle. more 2 moves though, things more complicated because @ kth move if shuffle can choose upper bound nk on number of inversions nk stop , subtract 1 thereafter, , need optimize nk expected number of inversions minimal overall. if k larger, nk should chosen smaller, question how much. if can compute nk (for each k), have solved problem.

my intuition can solve nk k=1,2,...,k in o(nk) time, using sort of recursive formulation. i'll update if work out details. if true, mean can solve expected number of inversions in o(nk) time well.


Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque...
Read more

jsf - How to ajax update an item in the footer of a PrimeFaces dataTable? -

this visual of table have: +---------+------------+-------------------+ | header1 | header2 | header3 | +---------+------------+-------------------+ | row | input | calc'ed output | | row b | input b | calc'ed output b | | etc.. | etc.. | etc.. | +---------+------------+-------------------+ | total: total calc'ed output | +------------------------------------------+ and stripped-down code: <p:datatable id="mytable" value="#{mybean.somelist}" var="currentitem"> <p:column headertext="header1"> <h:outputtext value="#{currentitem.name}" /> </p:column> <p:column headertext="header2"> <pe:inputnumber value="#{currentitem.inputval}"> <p:ajax event="change" listener="#{mybean.changelistener}" update="outputval outputtotal...
Read more

jquery - Keeping Kendo Datepicker in min/max range -

when user types type in date outside of range, we're trying ensure date gets changed closest min/max. text displayed in date picker not change though thought script changing value() @(html.kendo() .datepickerfor(x => x.dob) .max(new datetime(datetime.now.addyears(-18).year, datetime.now.addyears(-18).month, datetime.now.addyears(-18).day)) .min(new datetime(datetime.now.addyears(-70).year, datetime.now.addyears(-70).month, datetime.now.addyears(-70).day)) .events(e=>e.change("ondobchange")) .htmlattributes(new { required = "required", ng_model = "model.dob" })) <p ng-show="validatestate.submitted && frmmain.dob.$invalid" class="help-block">please select</p> <script> function ondobchange(e) { var d...
Read more