| |
| |
| |
|
Page: 1 2 3 4 5 6 7 8 9
<Cale> but that isn't terribly useful, I don't think
<Geren> Cale, if i is left out and j is a duplicate, shouldn't it be n(n+1)/2 - j + i?
<Cale> um, no
<Geren> oh i ic
<Geren> ok
<Geren> so if i sum all members of my array, then subtract n(n+1)
<Geren> then i get the difference
<Geren> then what
<Cale> I don't see how that's terribly useful :)
<Geren> hmm
<Cale> You might be able to collect some other piece of information though
<Geren> so what is the most optimal solution?
<Cale> However, summing is already going to take O(n) time.
<Cale> There's an obvious O(n) time and space solution, ***uming that you have arrays with an O(1) update and read
<Geren> how ?
<Cale> like I said
<Cale> Have an array of n cells
<Geren> and?>
<Cale> and fold over your input array, updating the ith cell in your working array with the number of times that you've seen the number i.
<Geren> what do u mean fold over?
<Cale> loop, if you want :)
<Geren> thats like a hash table
<Cale> well, sort of, yes, without any hashing
<Geren> do i initialize all members of my array to 0?
<Cale> yes
<Geren> hmm ok
<Geren> i guess that'll do :)
<Cale> It's cheesy, but it works
<Geren> so at the end, the element with the value 2 is the i want
<Geren> i'll just extract the index of it
<Cale> you can test whether the cell you just updated is a '2' each time
<Geren> oh right
<Cale> which is guaranteed not to do any more tests than doing them all afterwards would
<Cale> (on average, you'll do half as many tests)
<Geren> ok another harder question :)
<Geren> Returns the largest sum of contiguous integers in the array
<Geren> Example: if the input is (-10, 2, 3, -2, 0, 5, -15), the largest sum is 8
<Geren> this one is hard
<godling> mathe ist gut
<Cale> that's a standard problem, though I don't remember the best solution to it
<RyuKojiro> How can I implicitly differentiate sin x + cos y = sin x cos y ?
<GRedner> here's a math question
<GRedner> if my cookies were supposed to bake for 11 minutes, and I baked them for 25 by accident, just how burnt will they be?
<GRedner> :(
<Cale> :(
<kernel_dan> GRedner: its a vertical asymptote at 25
<GRedner> damn!
<SourceCode> Geren, i think the best solution is done recursively
<GRedner> I want to see a rigorous proof of the existenct of this asymptote before I give up home
<GRedner> hope*
<SourceCode> Geren, i have an old program I wrote that checks all the sums in an array recursively, if you want it, could probably build off that
<SourceCode> its like 5 lines
<Geren> SourceCode, can u explain to me how that works
<Geren> in pseudocode?
<Cale> @eval maximumBy (\x y -> compare (sum x) (sum y)) (tails [-10, 2, 3, -2, 0, 5, -15] >>= inits)
<mbot> Cale: [2,3,-2,0,5]
<Cale> there's a rather inefficient Haskell version :)
<Cale> (just brute force)
<SourceCode> to be honest the psuedocode is longer than the code, and I couldn't explain it because I forgot how it works
<SourceCode> it took me like 5 days to write it
<SourceCode> and it was like 4-5 lines after i figured it out
<Cale> maximumBy takes a comparison operation and finds the maximum element in a list under that comparison:
<Cale> @eval maximumBy compare [1,2,3,4,5]
<mbot> Cale: 5
<Cale> @eval maximumBy (\x y -> compare y x) [1,2,3,4,5]
<mbot> Cale: 1
<Cale> tails produces the list of tails of a list and inits produces the list of initial sublists
<Cale> @eval tails [1,2,3,4,5]
<mbot> Cale: [[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[]]
<Geren> hmm?
<Cale> just explaining the parts of my one-liner solution
<Geren> Cale, is this about my problem?
<Cale> yes
<Cale> @eval maximumBy (\x y -> compare (sum x) (sum y)) (tails [-10, 2, 3, -2, 0, 5, -15] >>= inits)
<Geren> ok can u explain it in english please
<mbot> Cale: [2,3,-2,0,5]
<Cale> see?
<Geren> what did u do?
<SourceCode> Geren, this is essentially the problemy ou are working on i think, http://mathworld.wolfram.com/SubsetSumProblem.html i remember cale gave a lecture the same week I was working on it, he suggested usign generating functions
<SourceCode> Geren, i'll message you the function
<Geren> ok well i'm not looking for some very sophisticated algorithm, or the most optium solution
<Cale> It's not quite the subset sum problem
<Geren> but a solution, any solution
<Geren> as long as it's reasonable
<Cale> Geren: produce all sublists of the list and compute their sums
<Cale> (all contiguous sublists)
<Geren> so i start with 1, and do 1+2, 1+2+3, 1+2+3+4.....
<Geren> and then start with 2, and do 2+3, 2+3+4, 2+3+4+5.....
<Geren> by 1 and 2 i mean the index of hte array
<Geren> then store all those sum into another array
<Geren> and find the max of that array??
<Cale> yeah, that'll certainly work
<Cale> it's not at all efficient
<Cale> and much better solutions are certainly possible
<SourceCode> hey that works
<Cale> but that's essentially what my Haskell solution is doing
<Cale> and it's only one line :)
<Geren> thats quite bull****
<Geren> anyway
<palomer> gah! BuDDy is broken!
<RyuKojiro> kernel_dan: if it is a vertical asymptote at 25 then he needs to cook them longer to unburn them ;)
<kernel_dan> RyuKojiro: its a vertical asymptote from the left (i.e. at time is infinitessimally less than 25)
<kernel_dan> for time greater than 25, it is undefined
<RyuKojiro> Oh, okay ;)
<kernel_dan> by now, his cookies would be really burnt
<RyuKojiro> I wish I could unburn burnt food by cooking it longer though *sigh*
<RyuKojiro> kernel_dan: indefinitely burnt ;)
<kernel_dan> quick! the freezer
<RyuKojiro> Wait, then it would be a 3 dimentional plot of this asymptote
<RyuKojiro> temp, cook time, and burnt-ness :P
<RyuKojiro> kernel_dan: then it would decrease on the z making it just a cold, yet indefinitely burnt cookie
<kernel_dan> and what if burnt-ness where a complex number?
<RyuKojiro> kernel_dan: Then he could risk having imaginarily burnt cookies!
<kernel_dan> but they would still really be burnt
<RyuKojiro> Yeah
<kernel_dan> emphasis on 'really'
<palomer> what's a multiplier called in circuit theory?
<eigenlambda> piep piep kleiner sattelit
<eigenlambda> sag ihm da es mich noch gibt
<Tirlas> rawr, why isn't 30031 a prime
<eigenlambda> piep piep kleiner sattelit
<eigenlambda> frag ihn ob er mich noch liebt
<eigenlambda> @math 30031/59
<mbot> eigenlambda: 509
<eigenlambda> piep piep kliener sattelit
<eigenlambda> sag ihm da mein herz vergiht
<eigenlambda> piep piep
<Tirlas> kleiner sattelit
<eigenlambda> wenn es nicht bald zu ihm fleigt
<Tirlas> I guess I'm applying this theorum wrong.
<Tirlas> didn't euclid say that if p_n was the last prime, 2*3*5*...*p_(n-1)*p_n + 1 was also prime, therefore there are an infinite # of primes
<nerdy2> no
<nerdy2> if p_1, ..., p_n are primes, then p_1 * .... * p_n + 1 is a number larger than 1 which is not divisible by any of the p_i
<nerdy2> it's not necessarily prime
<nerdy2> but it must (by factorization) be divisible by a prime aside from p_1, ..., p_n
<nerdy2> proving an infinitude of primes
<Tirlas> Hmm, thanks nerdy2
<teferi> back with more topology problems...anyone want to help me prove that if XxY has the product topology and A \subset X, B \subset Y, closure(AxB)=closure(A)xclosure(B)? I seem to be stuck on proving that the limit points of AxB are the limit points of A x the limit points of B.
<RyuKojiro> in differentiating Sqrt[x^2 + 1] I wouldn't use the chain rule, right?]
<t35t0r> d((x^2 + 1)^1/2
<t35t0r> d((x^2 + 1)^1/2)/ dx
<t35t0r> @math Diff[(x^2 + 1)^1/2,x]
<mbot> t35t0r: Diff[(1 + x^2)/2, x]
<t35t0r> @math Diff[(x^2 + 1)^(1/2),x]
<mbot> t35t0r: Diff[Sqrt[1 + x^2], x]
<t35t0r> @math D[(x^2 + 1)^(1/2),x]
<mbot> t35t0r: x/Sqrt[1 + x^2]
<t35t0r> @math Int[(x^2 + 1)^(1/2),x]
<mbot> t35t0r: Int[Sqrt[1 + x^2], x]
<t35t0r> @math I[(x^2 + 1)^(1/2),x]
<mbot> t35t0r: I[Sqrt[1 + x^2], x]
Return to math
or
Go to some related
logs:
3dsmax
|
|