วีดีโอ

Think it as cp become foundation as elementary maths in AI age.

I still think AI is still in its early stages when it comes to competitive programming. I haven't seen AlphaCode solve problems better than humans yet, but AlphaProof & AlphaGeometry managed to "get" Silver on Math Olympiad questions. It's possible for AI to do well in CP but I don't think it will beat the gold medalists in the next decade.

Sério? Eu fiz a OBA, vou ver pra fazer essa aí também, parece legal.

@Wkaelx nunca esperaria um br aqui

Good luck!

I used a TypeScript library called Motion Canvas. I created some custom components (array, tree, graph) that can be found at the github.com/pihedron/motion-canvas-components repo.

@pihedron thanks

Yeah, that is kind of annoying. I guess we could use a 64 bit integer instead of the pair.

It would definitely be slower due to you having to create the triangle in the first place. Pascal's triangle grows at a rate of O(n^2). Plus there's lots of multiplication involved.

Thanks a lot!

Yeah, I recently wrote an algorithm that can generate the nth Fibonacci and Lucas number in O(log n). So, it's possible to do phi^n in O(log n) without loss of precision. It's on GitHub if you're curious.

How does the big o work for example what do O(1) or O(n) represent

@alphazero339 You can probably ask chatGPT for an explanation or lookup in wikipedia. In general, the complexity is determined by the number of iterations you have to do in the main loop. Operations such as addition and exponentiation are done in one CPU cycle so their complexity is O(1). A naive implementation of exponentiation will be to repeatedly multiply the number by itself, n times. It requires n iterations of the multiplication loop so the complexity would be O(n). Fast exponentiation (look it up) needs log_2(n) operations, so it has a complexity of O(log n). There are some floating point multiplication algorithms that can compute the exponential with O(1) complexity but they lose precision. You always take the biggest complexity, so if for example the algorithm has n + n^2 iterations, you say it has a complexity of O(n^2). An algorithm in 3n iterations has a complexity of O(n). log(n) + 4n^3 has a complexity of O(n^3). It just gives an order of magnitude for the computational complexity. That's about it, it's not an exact value, it just gives some sort of reference for the efficiency of an algorithm. Some O(n) algorithms are better than other O(n) algorithms. For example, in my original comment I said that multiplication is the following : (a, b) * (c, d) = (ac + 5bd, ad + bc). While we assume that it's computed with O(1) complexity, multiplication does take more time than addition. Instead of computing the 4 following products : ac, bd, ad, bc we actually only need 3. Here is a little trick : compute ac, bd and (a+b)(c+d). Notice that ad + bc = (a+b)(c+d) - ac - bd. So computing the fast exponential the way I described using only 3 multiplications instead of 4 will be about 25% faster, even though both their complexities are O(lg n). By the way, this is called Karatsuba's multiplication algorithm.

Yes, powers of phi in algebraic form can be computed in O(log n) time due to the identities of the Fibonacci and Lucas sequences. The github.com/pihedron/fib repo contains a function which can compute both the nth Fibonacci and Lucas numbers in O(log n) steps which is O(n log n) time for big integers. Therefore, we can get the nth power of phi as (L + F * sqrt(5))/2.

Don't worry, you will.

or just use the binomial theorem?

I'm glad you understand FPA, but that wasn't the point of the video. I cut that part of the video because it was boring. If the result is not accurate, it's still considered wrong. The point of the video is to devise a method for getting the EXACT answer and bring awareness to the limitations of calculators.

@@pihedron It's not even a limitation of calculators themselves, unless you include *any* method of calculating a numeric result, including pencil & paper. *Any* answer not in the symbolic form of a+b√5 will have to be rounded off it some point. Of course, you can't do anything in the real world with √5. You *have* to turn it into an approximate number for it to be any use. Also, accuracy is not a binary, but a measure of *how* accurate it is. In approximating π, 3 is not very accurate. 22/7 is more accurate, and 3.1415926536 more accurate yet.

"Any answer not in the symbolic form of a+b√5 will have to be rounded off it some point." This is exactly the limitation associated with some calculators. They are approximating. Plus there's no denying that the symbolic answer given in the video is better or more "right" than the answer given by the calculator. When I said "not accurate", I meant "not 100% accurate" or "not accurate enough". It's perfectly reasonable to reject an approximation as an answer no matter how good it is. 4:46 is a warning for people who may blindly use a calculator to verify their answer and get surprised. The explanation as to why this error happens is left as an exercise for the viewer. I hope this clarifies anything you misunderstood.

you're not wrong but you can further simplify this to be 1/(golden ratio)^14

It also applies to numbers besides the powers of phi by the way.

I'm in the process of making a potentially longer video but I also have my SAT exam coming up soon. I'll try my best to release a video next week.

The c can still be 0 because the discriminant will be 9 which is positive. I know you're saying that in the quadratic formula you will divide by 2c but in that case it's not a quadratic anymore and just a line. The lines will intersect at x = 1 if c = 0 due to 3 * x = 3.

I use Manim.

Yes, door A would have a higher probability IF door B was opened. There are 2 conditions that need to be met, so this is conditional probability. If you pick door C, there's a 1 / 3 chance you are right and 2 / 3 chance you are wrong. This doesn't change because door C will never be opened. Monty can only open a door with a goat that also isn't C. If Monty opens B, A has a 2 / 3 chance because there's a 2 / 3 chance you were wrong and the goat is behind the other 2 doors. You are essentially playing for 2 doors when you switch.

The scoreboards are basically public and they contain names, but I'll tell you I got high enough to qualify for camp. Did you get 10th?

@@pihedron yes, do you have discord?

It's not right to left cause 0 <= 0 < 0 would be true and it's -not- left to right cause 0 < 0 <= 0 would be -false- true.

(0 < 0 <= 0) would be true in JavaScript because it's evaluated as ((0 < 0) <= 0). The (0 < 0) is false so implicitly becomes 0. Then, 0 <= 0 becomes true.

right, im just dumb

It's not your fault JavaScript is weird.

I totally didn't make it: github.com/pihedron/edging

Yes.

I'm 0blue4brown.

Yeah, computers work with limited precision, so some values will get rounded during calculations. Adding first and multiplying second may not give exactly the same result as multiplying first and adding second. Imagine if you only had one digit of precision. We know that 1.4 + 1.4 should equal 2.8 and therefore round to 3, but if the inputs are rounded to 1 ahead of time the result becomes 2. Rounding errors are inevitable unless you do completely symbolic calculations.

Even Wolfram didn't get it "precise", just more precise than Google's calculator. It's still has to approximate at some point, because the answer is irrational.

@jursamaj If you paid close attention to the alternate forms, you can see that Wolfram gives a precise answer in symbolic form. Computers aren't limited to just FP approximations. Rational data types do exist. Wolfram has the tools necessary to do algebra.

@@pihedron I was referring to the value it printed with dozens of digits.

HiPER scientific calculator for android gets this right