language agnostic - Algorithm to calculate number of intersecting discs -

-

given array a of n integers draw n discs in 2d plane, such i-th disc has center in (0,i) , radius a[i]. k-th disc , j-th disc intersect, if k-th , j-th discs have @ least 1 common point.

write function 

int number_of_disc_intersections(int[] a);

which given array a describing n discs explained above, returns number of pairs of intersecting discs. example, given n=6 , 

a[0] = 1 a[1] = 5 a[2] = 2 a[3] = 1 a[4] = 4 a[5] = 0

there 11 pairs of intersecting discs: 

0th , 1st 0th , 2nd 0th , 4th 1st , 2nd 1st , 3rd 1st , 4th 1st , 5th 2nd , 3rd 2nd , 4th 3rd , 4th 4th , 5th

so function should return 11. function should return -1 if number of intersecting pairs exceeds 10,000,000. function may assume n not exceed 10,000,000.

so want find number of intersections of intervals [i-a[i], i+a[i]].

maintain sorted array (call x) containing i-a[i] (also have space has value i+a[i] in there).

now walk array x, starting @ leftmost interval (i.e smallest i-a[i]).

for current interval, binary search see right end point of interval (i.e. i+a[i]) go (called rank). know intersects elements left.

increment counter rank , subtract current position (assuming 1 indexed) don't want double count intervals , self intersections.

o(nlogn) time, o(n) space.


Comments

Post a Comment

Popular posts from this blog

sql server - python to mssql encoding problem -

-
Image
greetings by using pymssql library, want write data mssql database encounter encoding issues. here sample code write db: # -*- coding: utf-8 -*- import _mssql .... connection info data here .... def mssql_connect(): return _mssql.connect(server=host, user=username, password=pass, database=db, charset="utf-8") con = mssql_connect() insert_ex_sql = "insert mydatabsae (id, programname, programdetail) values (1, 'test characters ÜŞiçÇÖö', 'löşüiiğĞü');" con.execute_non_query(insert_ex_sql) con.close() sadly data written db corrupted: the collacation of mssql db is: turkish_ci_as how can solved? here possible solution : the key insert_ex_sq.encode('your language encoder') . try instead: con.execute_non_query(insert_ex_sq.encode('your language encoder'))
Read more

java - SNMP4J General Variable Binding Error -

-
i trying use snmp4j snmp bulkget. when ever use snmp4j make call returned responseevent error says "general variable binding error" , data returned equal null. to debug: print out, console, exact oid , version number using in snmp4j. use printed out data snmpwalk on command line. valid results. know sending snmp4j correct pdu correct oid, version number, max repititions, etc. i have used snmp4j , code wrote succesffuly monitor other devices years. don't know different time. leaving me stumped. why "general variable binding error?" causes error? ideas debug? can reproduced? if so, first action should using wireshark or microsoft network monitor capture network packets. my guess agent gives generr response, not surprising, http://www.ietf.org/rfc/rfc1157.txt
Read more

c# - BasicHttpBinding equivalent CustomBinding using WCF Client and PHP WebService -

-
i running visual studio 2008 unit test c# webservice php using wcf , received following error: system.servicemodel.security.messagesecurityexception: http request unauthorized client authentication scheme 'anonymous'. authentication header received server 'ntlm,basic realm="(null)"'. ---> system.net.webexception: remote server returned error: (401) unauthorized.. i using windows xp sp3 machine, unit test vs 2008 , wcf connect php webservice. i have no control php webservice. cannot modify (neither configuration security). here config file client use webservice php: <system.servicemodel> <extensions> <bindingelementextensions> <add name="customtextmessageencoding" type="company.integracioneasyvista.customtextencoder.customtextmessageencodingelement,company.integracioneasyvista.customtextencoder, version=1.0.0.0, culture=neutral, publickeytoken=9744987c0853...
Read more