c++ - Solving an Algorithmic Challenge involving Differences between Pairs -


the below algorithmic problem came with, motivated harder problem not solve. unfortunately, cannot solve 1 either.

you given n numbers in increasing order (n between 1 , 3*10^5, linear running time necessary). each number range 1 3*10^5 well. each number 1 3*10^5, denote z, want find how many pairs of numbers have pairwise difference of z. read examples below more clarity.

numbers: 1,6,9
answer: 1 pair difference of 5 (1,6), 1 pair difference of 3 (6, 9), , 1 pair difference of 8 (1,9)

numbers: 1,2,3,4
answer: 3 pairs difference of 1 (1,2 2,3 3,4), 2 pairs difference of 2 (1,3 2,4), , 1 pair difference of 3 (1,4).

is there data-structure can used solve problem in linear time?

here's o(n polylog n)-time algorithm compute counts z (assuming have @ n numbers between 1 , n).

prepare 2 polynomials p(x) = sum_{d in list} x^d , q(x) = sum_{d in list} x^(n - d). use fast multiplication algorithm compute coefficients of polynomial product p(x) q(x). answer z, examine coefficient of x^(n + z), is

sum_{d in list} sum_{e in list} [d + n - e = n + z],

where [d + n - e = n + z] = [d - e = z] 1 if d - e = z , 0 otherwise.


Comments

Post a Comment

Popular posts from this blog

javascript - Jquery show_hide, what to add in order to make the page scroll to the bottom of the hidden field once button is clicked -

i have button on website when clicked, reveals map. button can seen when page first loads up, when clicked, section holding map slides open , goes out of screen since page loads @ top (normal). want page scroll down bottom of div select when button pushed, if map out of screen. if page scrolled down, , clicks show map button, don't want page jump bottom of map. i tried figure out myself, no luck. seasoned jquery coders able give me guidance? many thanks! map = mapdiv.gmap3("get"); infobox = new infobox({ pixeloffset: new google.maps.size(-220, -310), closeboxurl: '', enableeventpropagation: true }); mapdiv.delegate('.infobox .close','click',function () { infobox.close(); }); jquery(".slidingdiv").hide(); jquery(".show_hide").show(); jquery('.show_hide').click(function(){ lastcenter=map.getcenter(); jquery(".slidingdiv&quo
Read more

javascript - Highcharts multi-color line -

Image
i looking create highchart multi-colored line. if goes down under value, become red, , when comes on value, become green . here picture example: or maybe highcharts have other charts models differentiate high or low level color? you can achieve coloring using lineargradient coloring: color: { lineargradient: { x1: 0, x2: 0, y1: 0, y2: 1 }, stops: [ [0, 'red'], [0.25, 'yellow'], [0.50, 'green'], [0.75, 'yellow'], [1, 'red'] ] } here 0 in stops relates minimum value of series , 1 maximum value, , in between percentages between values. if find percentages according values prior creating chart use correct stops values make relate specific values in data (at least approximately). see this jsfiddle example .
Read more

javascript - Enter key does not work in search box -

tried search guys sorry. input in search box doesnt work (or search) when hit enter when user clicks search button. doing wrong? here code. thanks. <script type="text/javascript"> $(document).ready(function() { $("#submit").click(function() { var url = "http://asla.org/awardssearch.html"; url += "?s=" + $('#googlecse').val(); window.location = url; }); $('#googlecse').keydown(function(event) { if (event.keycode == '13') { $("#submit").click(); } else { //do nothing :) } }); }); </script> <form class="navbar-form navbar-right" role="search"> <div class="search"> <input id="googlecse" type="text" onblur="if(this.value=='')this.value=this.defaultvalue;" onfocus="if(this.value==this.defaultvalue)t
Read more