- 2
- 15 825
averagedice
Приєднався 4 вер 2022
How Can Competitive Programming Geometry (sometimes) be Beautiful #SoME3
my submission to #SoME3
prerequisites: mostly high-school math and coding knowledge, also if you are familiar with norms and metrics you can skip introduction to them
bgm: debussy reverie, debussy ballade, debussy clair de lune
there are some audio issues but can't re-record due to sickness
also this is my first non-introductory level manim usage, hence I couldn’t translate animations in my head into perfect manimations, yet the tool is incredibly powerful!
00:00 Introduction
00:30 Naive approach
01:00 Asymptotic analysis
01:57 Statistical approach
04:35 Brief explanation of norms on the plane
08:46 Core idea of the solution
10:15 Solution
prerequisites: mostly high-school math and coding knowledge, also if you are familiar with norms and metrics you can skip introduction to them
bgm: debussy reverie, debussy ballade, debussy clair de lune
there are some audio issues but can't re-record due to sickness
also this is my first non-introductory level manim usage, hence I couldn’t translate animations in my head into perfect manimations, yet the tool is incredibly powerful!
00:00 Introduction
00:30 Naive approach
01:00 Asymptotic analysis
01:57 Statistical approach
04:35 Brief explanation of norms on the plane
08:46 Core idea of the solution
10:15 Solution
Переглядів: 5 292
(x+1)(y+1)=5 .....(I) (x+1)(z+1)=10 .....(II) (y+1)(z+1)=37 .....(III) Divide (I) by (II):- (z+1)=2(y+1) Putting in (III):- 2(y+1)²=37 y = ±√(37/2)
Absolutely did not expect Murasa's theme. Truly a convegence of two things I love
If we remove the 4th restriction and instead allow x, y, and z to be any complex number, there are 4 solutions: x=(√(721+493√(889))±√(-721+493√(889))i)/√(5334) y=(-x-√(16-3x²))/2 z=(-x-√(36-3x²))/2 and x=(-√(721+493√(889))±√(-721+493√(889))i)/√(5334) y=(-x+√(16-3x²))/2 z=(-x+√(36-3x²))/2
beautiful😮
Indian: "I solved it mentally without catching a pen"
Reminds me of the Steinhaus Longimeter
This was from CMI BSc entrance, cannot recall the year.
Wow, beatiful and simple! How maths should be
Here's a very quick algebra solution using the fact that x,y,z>0: 1) x²+xy+y²=4 => y²<4 => y<2 2) similarly z<3 3) y²yz+z² < 2²+2*3+3² < 36.
Beautiful proof.
Another solution: 36=y^2+yz+z^2<=2(y^2+z^2)<4x^2+2xy+2xz+2y^2+2z^2=2*(4+9)=26, which is a contradiction.
To clarify: is your first inequality just Cauchy Swartz?
In complex plane |x-y e^(2pi/3)|^2=(x+y/2)^2+(sqrt(3)y/2)^2=x^2+xy+y^2=4, |x - y e^(2pi/3)|=2 |y e^(2pi/3) - z e^(4pi/3)|^2 = |y - z e^(2pi/3)| = y^2+yz+z^2=9 |y e^(2pi/3) - z e^(4pi/3)|=3 |z e^(4pi/3) - x| = 6 But 6=|x - z e^(4pi/3)| <= |x - y e^(2pi/3)| + |y e^(2pi/3) - z e^(4pi/3)| = 2+3 = 5 So there aren't real solutions of the system
What initially confused me were the 3 lines labelled x, y, z looking like a 3D coordinate system. It's only when I wondered how the angles could be 120° that I realized it was meant to be a 2D plane figure. ^_^
That threw me too
😅 me
I only got it when I read your comment. Thank you very much.
You could also use symmetric polynomials. The elementary ones can reduce the degree of this equation which is really helpful.
Can you tell where to search for this solution?
Could anyone explain this properly. As in here, x,y and z doesn't satisfy the triangle.(x,y,z are angled in 120°to each other) Does it mean that it can't satisfy any other triangle.(x,y,z are at random angles with each other)
I'm not sure whether I correctly understood what you mean but I'll try to answer: Triangle is a way to show that there are no such (x, y, z) satisfying system of equations, it wouldn't really matter whether there are "other" triangles or something like that, since we get contradiction from our triangle. Then it's kind of hard to say about "satisfying any other triangle", since there are just no such (x, y, z) We could construct other triangles with other angles which may (or may not) prove the initial problem, angles between line segments is a thing we determine, other angles could be helpful for other systems, e.g. { x+y=6, x^2+z^2=9, y^2+z^2=4 (x, y, z > 0) } could be solved in the same way but with other angles
This youtuber has 2 videos? 2 videos??? Please! Are you going to make more?
Yeah, I want to be making ~1 "fullsize" video a month in 2024 upd: i could not fullfill my promises
If everything is correct, and I think it is, man, that's brilliant.
美しい！ Beautiful!
i don get it
If there was a solution (x, y, z) we could construct three line segments from a single point with pi/3 angle between them with length (x, y, z) respectively. Then we could construct a triangle like in video and we can find length of any of its edges (using law of cosines and initial question parameters), but there can't be such triangle due to triangle inequality hence there can't be solution (x, y, z).
Why would you call a problem given by system of algebraic equations purely analytic? I would say quite the opposite, that it’s purely algebraic XD (maybe only except the inequality x,y,z>0 not being quite algebraic)
yeah you might be right, I didn't put enough thought into naming this video ig, fixed
Clean
Is this touhou music? Overall, very based indeed
yes, 東方 supremacy ua-cam.com/video/zJ_2NTthBnU/v-deo.html&ab_channel=Louchan2
I knew it haha@@animeanimeanimeanimeiminsane
very cool!
4:32 optical illusion
Very interesting ! Thanks
noice solution
Very pretty video, did not expect such math to be applied directly to such problem. Overall, calculating efficient approximations of values are beautiful in how they may be counterintuitive at first, yet absolutely logical when you think about them
Really good video. Can you share the source code for the video?
Thanks! Since it was my first project with manim all source code is such an atrocity that i deleted it once I uploaded video so I couldn't translate mistakes from that code to future projects.
Great video!
What a beautiful problem! And a very well-made video
brings me back to my codeforces days man, super fun
Too strong russian accent, the rest is great
This reminds me of a technique used in machine learning for dimensional reduction. If you have data with a very high dimensionality, you can reduce the dimensionality by projecting the data onto a random set of basis vectors. It tends to be pretty good at preserving the norms between the data points. One example would be if you have a discrete graph/network with a million points. The adjacency vector representatuon for each point would have a dimensionality of 1 million. You could then use the technique to reduce the dimensionality to only a few hundred pretty easily and generate an embedding of the graph.
УРА УРА ДАВАЙ ДАВАЙ
Really liked the video! Could you give a link to the problem? on icpc website or some online judge
Thanks! I couldn’t find problem anywhere except the main contest (Moscow Regional Qualifiers 2021), where you have to be pre-registered to upsolve, sorry, can’t help you here…
Damn! that is pretty!
Omg based