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 kzitem.info/rock/XbCohpE9IoVQUD2Ifg1d1g
@so7am96
4 жыл бұрын
I see what u did there :"D nice episode btw, really enjoyed the problem and the awesome solution!!
@softwaredeveloper4304
4 жыл бұрын
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.
@AlgosWithKartik
4 жыл бұрын
The summary was very helpful!
@naklecha
4 жыл бұрын
I didn't know I needed this and now I need more.
@darshpatel8385
4 жыл бұрын
Collab for which I've been waiting since forever.
@pratyushmisra2516
4 жыл бұрын
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!!!!!
@MrDalgerokChannel
4 жыл бұрын
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?
@Errichto
4 жыл бұрын
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.
@MrDalgerokChannel
4 жыл бұрын
@@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.
@Errichto
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.
@ChandraShekhar-by3cd
4 жыл бұрын
@Errichto What is dp[m | 1
@Errichto
4 жыл бұрын
It's ok if you aren't familiar with bitmask DP, just skip those few minutes. The actual solution doesn't use that.
@ChandraShekhar-by3cd
4 жыл бұрын
@@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!
@dhananjaysonawane1996
4 жыл бұрын
@21:40 How can we say that LIS or LDS will have k > √N?
@Errichto
4 жыл бұрын
we get back to this fact at 32:45
@techwithwhiteboard3483
3 жыл бұрын
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
@dhananjaysonawane1996
3 жыл бұрын
@@techwithwhiteboard3483 Thanks for sharing!
@kathilroyal3554
4 жыл бұрын
Jestem polakiem i już myślałem, że znajdę coś ciekawego po polsku, a tutaj cały kanał po angielsku xd
@kubakakauko
4 жыл бұрын
Where do i learn the basics of the math for algorithm programming
@mateuszlukaszczyk5359
4 жыл бұрын
good question
@nomnom1378
4 жыл бұрын
please help me my fb account was hacked, can you help restore my fb account
@ChandraShekhar-by3cd
4 жыл бұрын
Errichto + SecondThred = Main Thread( Coding )
@Errichto
4 жыл бұрын
Errichto + SecondThread = Errichto2 ?
@ChandraShekhar-by3cd
4 жыл бұрын
@@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!
@OptimisticForce
3 жыл бұрын
@@Errichto You smart for a reason.
@jan1495
4 жыл бұрын
Last time I came this early, my GF broke up with me.
@OzdyTube
4 жыл бұрын
When do you talk about the proof that the bitonic TSP is optimal in 2D LIS(LDS) points?
@Errichto
4 жыл бұрын
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?
@dhiresh5980
3 жыл бұрын
The podcast I didn't know I was searching for
@x0cx102
2 жыл бұрын
21:45 wow really nice use of erdos-szekeres there to get sqrt(N) increasing or sqrt(N) decreasing subsequence
@dovyraj1272
4 жыл бұрын
so the cold war is over.
@anuraggupta3557
4 жыл бұрын
Thanks for posting this. I learned a lot. Keep up the good work.
@manas_singh
4 жыл бұрын
There is so much of red color in one video, KZitem hq will have a server meltdown
@shivamjalotra7919
4 жыл бұрын
Finally SecondThread is here.
@welldone3806
4 жыл бұрын
Errichto + second thread=red thread
@arjanbal3972
4 жыл бұрын
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?
@Errichto
4 жыл бұрын
Read the pinned comment. In short, the checker tries to find a better solution with good heuristics.
@welldone3806
4 жыл бұрын
@@Errichto yup
@subhadipadhikary270
4 жыл бұрын
I challenge you to make mini metro solver
@Errichto
4 жыл бұрын
what is metro?
@subhadipadhikary270
4 жыл бұрын
@@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.
@Nunocesarsa
3 жыл бұрын
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!
@Nunocesarsa
3 жыл бұрын
not really :/(
@raghavbansal4403
4 жыл бұрын
SecondThread looks like radewoosh
@spicyginger4289
4 жыл бұрын
Being second threads brother, no he does not
@spicyginger4289
3 жыл бұрын
@@bulletprooftrading no, not even close
@janix4000
4 жыл бұрын
What type of drawing software do you use?
@tiktoktrending9
3 жыл бұрын
I am also curious of the editor they use
@nachiketkanore
4 жыл бұрын
Make more AlgoTalks @Errichto
@aladeenaladeen6274
4 жыл бұрын
second
@genuineprofile6400
4 жыл бұрын
This is amazing.
@shubh_chaudhri
4 жыл бұрын
Was waiting for this!!!!🔥
@AlexSav
4 жыл бұрын
How did the organizers check that some other solution was not correct?
@welldone3806
4 жыл бұрын
If judge can find minimum than the sol it means sol is incorrect
@Errichto
4 жыл бұрын
See the pinned comment
@baxi9227
4 жыл бұрын
this was made for high schoolers to solve.
@raghugore3990
4 жыл бұрын
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
Пікірлер: 60