Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I like sequences, but in this case, they are probably the wrong tool for the job. This problem is a chance to try out a non-trivial recursive solution. Using mutation, it would be easy to do an algorithm like this (in Python, my pseudo-code of choice..)</p> <pre><code>def f(n): i = 0 j = int(1 + sqrt(n)) count = 0 # 'i' will always be increased, and j will always be decreased. We # will stop if i &gt; j, so we can avoid duplicate pairs. while i &lt;= j: s = i * i + j * j if s &lt; n: # if any answers exist for this i, they were with higher # j values. So, increment i. i += 1 elif s &gt; n: # likewise, if there was an answer with this j, it was # found with a smaller i. so, decrement it. j -= 1 else: # found a solution. Count it, and then move both i and # j, because they will be found in at most one solution pair. count += 1 i += 1 j -= 1 return count </code></pre> <p>Now, this seems to work. Maybe its not right, or not the best, but I like how the recursive code looks in F#. (warning.. I don't have F# on this computer... but I hope I got this right.)</p> <pre><code>let f n = let rec go i j count = if i &gt; j then count else let s = i * i + j * j if s &lt; n then go (i + 1) j count else if s &gt; n then go i (j - 1) count else go (i + 1) (j - 1) (count + 1) go 0 (1 + (n |&gt; float |&gt; sqrt |&gt; int)) 0 </code></pre> <p>This solution runs in O(sqrt(N)) time for each call, and requires constant memory. The memoizing solution takes O(N) time to setup the dictionary and the dictionary size is at least O(sqrt(N)). For large N, these are quite different. </p>
    singulars
    1. This table or related slice is empty.
    1. POF# - Facebook Hacker Cup - Double Squares
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdave jones
    1. USdave jones
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POF# - Facebook Hacker Cup - Double Squares
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COFrom an initial glance at this, it looks like it's still brute forcing, but without a memoize to speed the subsequent test case lookups. I would probably incorporate a dictionary of "n"'s and check for and increment any relevant other test cases along the way. That way, the most you have to go through is one time for the largest test case.
      singulars
      1. PO
      1. USJacob
    2. COThat is true, it brute forces the solution every time. The python solution takes a quarter of a second to solve all of the inputs from the example, so I am not too worried about memoizing here, because it is not needed. This was more of an example of a way recursion can be used besides fib or factorial functions.
      singulars
      1. PO
      1. USdave jones
    3. COI've updated the question with the actual competition numbers given, it does seem like your algorithm is blazing fast for even large n so brute forcing even the maximum 100 cases shouldn't be a problem. If you wan't to try snippets of F#, http://tryfs.net/ is great for messing around in the browser. Thanks for your answer.
      singulars
      1. PO
      1. USJacob
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload