Algo Talk with SecondThread: Parade
Vložit
- čas přidán 3. 06. 2024
- I'm joined by David (SecondThread) to discuss my problem Parade, where you can choose a subset of input to make your task easier. Check out a beautiful IOI problem Joining Points on his channel • Algo Talk with Erricht...
Full English statement of Parade: github.com/Errichto/youtube/b...
Submit in Polish judge: szkopul.edu.pl/problemset/pro...
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Watch my live streams on Twitch or my 2nd YT channel / errichto & / errichto2
- Frequently Asked Questions: github.com/Errichto/youtube/w...
Interesting fact: as organizers, we were afraid of some people squeezing good TSP heuristics and completely missing the point of the problem. So our checker was a complicated state-of-the-art solution for TSP. There were tens of tests and you would get WA if for any test the checker found a cycle shorter than yours (for your K chosen points). This already makes it hard enough to pass the problem with any heuristics. What if I tell you that the checker also had bigger ML and TL than participants' submissions. And the checker used multi-threading! We used threads (numbered from 1 to 8) and the first one was the master thread just to distribute the work. Any mistake was most often caught by the first of the remaining threads. Long story short, Second Thread made sure that every submission was indeed optimal. So please subscribe to him czcams.com/channels/XbCohpE9IoVQUD2Ifg1d1g.html
I see what u did there :"D
nice episode btw, really enjoyed the problem and the awesome solution!!
Awesome problem I can hear you think. Question? Why not find the 4 points that are furthest away from each other, then use a line to segment them, and then find the variance of the distance from that line and using that result, while retaining the distance between each point on the line, resulting in an the area leading us to the most optimal path? Would that work? If it does then the complexity of the algorithm would most likely be from n points O( m ) where m is the distance from the line and the distance between the points on that line. I'm probably totally off.
The summary was very helpful!
Errichto + SecondThred = Main Thread( Coding )
Errichto + SecondThread = Errichto2
?
@@Errichto There is no limit to Creativity!!! You're so creative.
Now we've an equation Errichto + SecondThread = Errichto2
hence LHS == RHS Proved! Math Wins!
@@Errichto You smart for a reason.
Thanks for posting this. I learned a lot. Keep up the good work.
I didn't know I needed this and now I need more.
The podcast I didn't know I was searching for
Collab for which I've been waiting since forever.
Finally SecondThread is here.
21:45 wow really nice use of erdos-szekeres there to get sqrt(N) increasing or sqrt(N) decreasing subsequence
Was waiting for this!!!!🔥
This is amazing.
Last time I came this early, my GF broke up with me.
When do you talk about the proof that the bitonic TSP is optimal in 2D LIS(LDS) points?
The proof for a path is around 19:00. Then for a cycle we just say that cycle consists of two parts, each going from bottom-left to top-right point. Or maybe I misunderstood your question?
Which K points you choose from the set of LIS points (size of set is greater than K)?
From that dp you end when i or j is equal to K, but we assume that we start from the first point of the set of LIS points, why we can’t start from another one?
Any K of those points, can be first K of them. It's only important that chosen points form a monotonic chain. I don't know what dp you want to do after starting not from the first point.
@@Errichto what if we have 4 points, K=3 and first point is far away from the second point and points 2,3,4 are close to each other? Then you better pick points 2,3,4.
@@MrDalgerokChannel You don't need to choose K points in optimal way. The task says: choose any K points, forget about the other N-K points, then do TSP optimally.
What type of drawing software do you use?
I am also curious of the editor they use
Im at 11:00 so idk the solution. Could it be using angles between points like the convex hull? and if you already visited the point then you go for the next. Lets see!
not really :/(
Make more AlgoTalks @Errichto
@Errichto What is dp[m | 1
It's ok if you aren't familiar with bitmask DP, just skip those few minutes. The actual solution doesn't use that.
@@Errichto Sure Thanks Errichto. I am your constant follower of all your videos and codeforces blog. You' re the best! Always inspired by the way you code!
I'm curious, how does the judge know if the output is not the solution to TSP? Won't the judge be able to solve TSP if it can always find a shorter path for incorrect answers?
Read the pinned comment. In short, the checker tries to find a better solution with good heuristics.
@@Errichto yup
@21:40 How can we say that LIS or LDS will have k > √N?
we get back to this fact at 32:45
u can use erdos skizeres theorem. given n^2 + 1 points u can always find either an increasing sequence of length n or a decresing sequence of atleast length n
@@techwithwhiteboard3483 Thanks for sharing!
Errichto + second thread=red thread
Where do i learn the basics of the math for algorithm programming
good question
How did the organizers check that some other solution was not correct?
If judge can find minimum than the sol it means sol is incorrect
See the pinned comment
Hi Errichto, Could u please make a video on counter examples for Greedy algos or sort of a mental models for Greedy counter egs... it will help differentiate between DP and Greedy.....PLEASE UPVOTE THIS COMMENT IF U GUYS AGREE!!!!!
There is so much of red color in one video, CZcams hq will have a server meltdown
Jestem polakiem i już myślałem, że znajdę coś ciekawego po polsku, a tutaj cały kanał po angielsku xd
so the cold war is over.
Can u please provide solution and explanation for the below :
Write a program to find Largest 4 digits Prime Number whose Sum of Digits is also Prime.
1.Prime Number is any number that is divisible only by 1 and itself. Examples are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,........
2.Sum of Digits means sum of all the digits in that number. Example is number is 1234 then the sum of digits is 1+2+3+4=10
Print("3+2=5")
SecondThread looks like radewoosh
Being second threads brother, no he does not
@@sasmitvaidya3594 no, not even close
second
I challenge you to make mini metro solver
what is metro?
@@Errichto"mini metro" is an android game
simple but quite interesting.I was eager to make an algo to solve that but i have no idea on ml so i left if.
David looks like a character from subway surfers
please help me my fb account was hacked, can you help restore my fb account
this was made for high schoolers to solve.