tag:blogger.com,1999:blog-86988028894253381432024-03-26T23:38:05.756-07:00Algorithms Live!tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.comBlogger41125tag:blogger.com,1999:blog-8698802889425338143.post-50786519385798155862021-11-10T22:13:00.002-08:002021-11-10T22:13:31.735-08:00Episode 39 - String Concatenation<p><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;">This week's episode of </span><em style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;">Algorithms Live!</em><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;"> features David Harmeyer (</span><a class="rated-user user-red" href="https://codeforces.com/profile/SecondThread" style="background: 0px 0px rgb(255, 255, 255); color: #4d87c7; display: inline-block; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px; font-weight: 700; text-decoration-line: none;" title="Grandmaster SecondThread">SecondThread</a>)<span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;">. In this episode, we discuss his problem </span><a href="https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/D" style="background: 0px 0px rgb(255, 255, 255); color: #4d87c7; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px; text-decoration-line: none;">String Concatenation</a><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;"> from Facebook Hacker Cup 2021 Round 2. We recorded the video over the weekend and will be premiering the </span><a href="https://youtu.be/CTJDurf1mU4" style="background: 0px 0px rgb(255, 255, 255); color: #4d87c7; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px; text-decoration-line: none;">video</a><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;"> on YouTube this week. During the premier both David</span><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;"> and I will be available on the chat to answer any questions.</span></p><p><span style="background-color: white; color: #222222; font-family: "helvetica neue", Helvetica, Arial, sans-serif; font-size: 14px;">See you there!</span></p>tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com0tag:blogger.com,1999:blog-8698802889425338143.post-9181878624187090032019-01-21T11:11:00.000-08:002019-01-21T11:11:05.319-08:00Episode 37 - Venture Cup<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
This week's episode of <em>Algorithms Live!</em> features the return of <a class="rated-user user-legendary" href="https://codeforces.com/profile/scott_wu" style="background: transparent; color: #4d87c7; font-weight: bold; text-decoration-line: none;" title="Legendary grandmaster scott_wu"><span class="legendary-user-first-letter" style="color: black !important;">s</span>cott_wu</a>. In the episode we discuss his involvement in Venture Cup, the interest of venture capitalists and tech companies in competitive programming, his work as a commentator for this year's Topcoder Open, the relationship of esports to competitive programming, and the problem <a href="https://codeforces.com/contest/626/problem/F" style="background: transparent; color: #4d87c7; text-decoration-line: none;" title="8VC Venture Cup 2016 - Elimination Round">626F - Group Projects</a> from the first Venture Cup. Most of the episode is podcast style, so I've included time links in advance to make it is easier to navigate to parts of the discussion that interest you. :)</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
The episode is available at this <a href="https://www.youtube.com/watch?v=97ovVAJBbkA" style="background: transparent; color: #4d87c7; text-decoration-line: none;">link</a>. Enjoy!</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com81tag:blogger.com,1999:blog-8698802889425338143.post-36795586716280869952019-01-15T12:50:00.002-08:002019-01-15T12:50:45.391-08:00Episode 36 - El Toll Caves<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
This week's episode features Mikhail Tikhomirov (<a class="rated-user user-red" href="https://codeforces.com/profile/Endagorion" style="background: transparent; color: #4d87c7; font-weight: bold; text-decoration-line: none;" title="International Grandmaster Endagorion">Endagorion</a>). You may know Mikhail from his many problems in Codeforces or other online judges. He has been a finalist of TCO and Google Code Jam and helped host the Barcelona Programming Bootcamp. Mikhail is an ICPC coach for Moscow Institute of Physics & Technology. His teams have earned two gold medals and a silver medal at ACM ICPC World Finals in the past few years. He also has a YouTube <a href="https://www.youtube.com/user/Endagorion" style="background: transparent; color: #4d87c7; text-decoration-line: none;">channel</a> where he regularly post screencasts.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
In this episode we will be discussing his problem <a href="https://codeforces.com/contest/868/problem/G" style="background: transparent; color: #4d87c7; text-decoration-line: none;">El Toll Caves</a> from the Barcelona Bootcamp. This is a math intensive problem with close relationship to the Euclidean algorithm.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
If you have any questions for Mikhail, please leave comments on this post with the question or ask the question live during the stream.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
See you live! (<a href="https://www.youtube.com/watch?v=ndLgzI2TJ3c" style="background: transparent; color: #4d87c7; text-decoration-line: none;">episode</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com96tag:blogger.com,1999:blog-8698802889425338143.post-54372862176154975302019-01-08T19:14:00.003-08:002019-01-09T12:19:11.704-08:00Episode 35 - Looking for a Challenge?This week's episode features Tomasz Idziaszek as a special guest. Tomasz was an ICPC World Finalist from 2005 and a TCO Finalist from 2004-2005. He is an author of over 100 problems, including many hard and interesting problems from Algorithmic Engagements. He was an editor for the polish educational magazine Delta and the famous competitive programming book "Looking for a Challenge?". In 2018 he was a problem setter for the IOI. He also maintains the website <a href="http://www.algonotes.com/">http://www.algonotes.com/</a> that offers interesting educational materials on advanced algorithms.<br />
<br />
In this episode we discuss the history behind "Looking for a Challenge?" and his famous problem Termites, which was included in the book. This problem is truly beautiful and I hope many of you will enjoy the <a href="https://www.youtube.com/watch?v=pOv4LRNt0jo">episode</a>.<br />
<br />
<strong style="color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">Update:</strong><span style="color: #222222; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> Anyone interested in the getting a copy of the </span><em style="color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">Looking for a Challenge</em><span style="color: #222222; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> book can find information in this </span><a href="https://codeforces.com/blog/entry/59876" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; color: #4d87c7; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; text-decoration-line: none;">blog post</a><span style="color: #222222; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">. You can also solve the recommended Woodworms task by seeing the problem statement at this </span><a href="https://www.mimuw.edu.pl/~idziaszek/korzad-en.pdf" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; color: #4d87c7; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; text-decoration-line: none;">link</a><span style="color: #222222; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> and on an online judge in this </span><a href="https://szkopul.edu.pl/problemset/problem/-Y5h4NdpbUjmI2CzEC23hTDb/site/?key=statement" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; color: #4d87c7; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; text-decoration-line: none;">link</a><span style="color: #222222; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">.</span>tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com240tag:blogger.com,1999:blog-8698802889425338143.post-31625490188396550382018-12-14T09:59:00.005-08:002018-12-14T09:59:53.854-08:00Episode 34 - Educational Streaming w/ Errichto<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-bottom: 1em; margin-top: 1em; padding: 0px;">
This week's episode will feature <a class="rated-user user-red" href="https://codeforces.com/profile/Errichto" style="background: transparent; color: #4d87c7; font-weight: bold; text-decoration-line: none;" title="International Grandmaster Errichto">Errichto</a> and will take place on Sunday, December 16th. If you are interested in viewing the live stream, you can find the link <a href="https://www.youtube.com/watch?v=9p-M0JJz_aQ" style="background: transparent; color: #4d87c7; text-decoration-line: none;">here</a> or view the video after the stream following the same link.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
Many of you know <a class="rated-user user-red" href="https://codeforces.com/profile/Errichto" style="background: transparent; color: #4d87c7; font-weight: bold; text-decoration-line: none;" title="International Grandmaster Errichto">Errichto</a> as a prolific problem writer and his recent appearances in TCO, Google Code Jam, Facebook Hacker Cup, and many other programming contest finals. He represented the University of Warsaw in the 2018 ACM ICPC World Finals, where his team placed 14th. This year he started an educational stream for competitive programming that is growing in popularity.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
In this episode, we will discuss the benefits of educational streaming in competitive programming and ideas for making competitive programming more popular. Topics will include: how programming contests relate to e-sports, broadcasts for programming competition finals and how they can be improved, and algorithms videos on YouTube and what we would like to see in the future for popularizing the sport. I think this will be a fun podcast style stream. Please ask questions on this post for ideas that you would like to see discussed.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
As with all <em>Algorithms Live!</em> episodes, we will be discussing an interesting algorithmic programming challenge. In this episode, we will discuss <a class="rated-user user-red" href="https://codeforces.com/profile/Errichto" style="background: transparent; color: #4d87c7; font-weight: bold; text-decoration-line: none;" title="International Grandmaster Errichto">Errichto</a>'s problem <a href="https://codeforces.com/contest/1025/problem/F" style="background: transparent; color: #4d87c7; text-decoration-line: none;">Disjoint Triangles</a>. As build up to this problem, we will also be discussing <a href="https://codeforces.com/contest/1045/problem/D" style="background: transparent; color: #4d87c7; text-decoration-line: none;">Interstellar Battle</a> from Bubble Cup earlier this year. This is sure to be an exciting episode with many interesting topics and ideas.</div>
<div style="background-color: white; color: #222222; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; line-height: 1.4em; margin-top: 1.5em; padding: 0px;">
See you live!</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com121tag:blogger.com,1999:blog-8698802889425338143.post-70933354441239275132018-11-30T19:43:00.000-08:002018-11-30T19:43:22.309-08:00Episode 33 - Maximum Flow IntuitionDuring September I attended the IOI as the USA team's deputy leader. The event was lots of fun and I met many new friends, some of which will be future episode guests. While attending I also presented my <a href="https://ioinformatics.org/journal/v12_2018_25_41.pdf">paper </a>on Tidal Flow, an algorithm I invented while training for ICPC contests. The paper also served as an extensive study on maximum flow algorithms. During testing I implemented many new flow algorithms and decided it would be fun to share some of these algorithms in an extended flow series.<br />
<br />
The first episode of this series is now available <a href="https://www.youtube.com/watch?v=K1i-wP82Zdo">here</a>. I'll be going over terminology, proofs, algorithms, and patterns as the series expands. There is much to talk about. I'll be interspersing the episodes with some guest episodes I've been planning. Hopefully this variety will keep the episodes exciting for all viewers.<br />
<br />
In other news, I've received many requests to start a GitHub repository to store all of the code I write during episodes. Such a repository is now available <a href="https://github.com/tehqin/AlgorithmsLive">here</a>.tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com127tag:blogger.com,1999:blog-8698802889425338143.post-29328295629986762322018-08-19T19:54:00.000-07:002018-08-19T19:54:20.897-07:00Episode 32 - Fracturing SearchIt has been several months since I've created an episode of <i>Algorithms Live!</i> but I'm excited to restart the show. I'll be making some changes to the format of the show that I'm hoping some of you will really like. Before I get into all of that I want to share some personal updates and explain what I've been doing the past few months.<br />
<br />
Sadly, things did not work out with <i>drive.ai.</i> I enjoyed the experience, met many interesting people, and learned a great many things. Not working while in the bay area is terrifying so I had to dedicate most of my time figuring out how to leave the bay area and setting up my next life steps.<br />
<br />
During the last few months, I worked on making videos for <i>Interview Kickstart</i>. This has been interesting because I started to think about how I could change the format of <i>Algorithms Live! </i>so that it is more useful using some of the ideas from making IK videos. One difficulty in running the show is finding a guaranteed quiet place to schedule a live episode. When I originally ran the show, I would run the episodes late at night in my office at UCF. Not having a dedicated quiet office has hurt running the show live. So I've decided to run more polished pre-recorded episodes as an experiment. Let me know what you think of the new format!<br />
<br />
So now on to more exciting and fun news. The first is I'll be attending the IOI this year as USA's deputy leader. So if you are attending IOI, please say hi! I'll also be presenting a paper on Tidal Flow this year at the IOI Conference (<a href="https://ioinformatics.org/page/ioi-journal-index/44">journal</a>, <a href="https://ioinformatics.org/journal/v12_2018_25_41.pdf">paper</a>). Tidal Flow is a maximum flow algorithm I invented while training for the ICPC World Finals in 2012. My team wanted an iterative fast flow algorithm that was also easy to implement and understand. The result was the Tidal Flow algorithm. I taught this technique, along with many other fast flow algorithms, while training teams at UCF for many years and the algorithm enjoyed popular usage among our teams. If you decide to read the paper or use the algorithm, I'd be interested to know what you think of it.<br />
<br />
Earlier this summer, I helped coach at the USACO training camp. One problem I set during the camp was an enumeration problem. The problem is given a weighted graph, print the cost of the kth smallest spanning tree (where <i>n</i> <= 50, <i>m</i> <= (<i>n</i> choose 2), <i>k</i> <= 10,000). Give this problem a try. Can you get something that runs efficiently on random, fully connected graphs? After the contest I presented the concept of <i>fracturing search</i> as a method for solving this type of enumeration problem. The technique is generally applicable, and many of the USACO finalists found it interesting. The idea is based off Murty's assignment ranking algorithm (<a href="https://www.jstor.org/stable/168595">paper</a>, <a href="https://pubsonline.informs.org/doi/pdf/10.1287/opre.16.3.682">altlink</a>). There is even an paper that solve this same problem using the technique (<a href="http://www.scielo.br/pdf/pope/v25n2/25707.pdf">paper</a>). So I've decided to turn this technique and problem into an episode. I hope you enjoy the idea as much as I do.<br />
<br />
So here is episode 32 (<a href="https://www.youtube.com/watch?v=EG_HfFMM0lE">episode</a>). I'd love to hear thoughts of the episode and the new format. Is this format better? What should be changed? I have many more episodes planned and will be releasing them regularly following this year's IOI.tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com58tag:blogger.com,1999:blog-8698802889425338143.post-41931662471492961862018-02-09T20:20:00.002-08:002018-02-09T20:20:15.975-08:00Episode 31 - OrchestraThis week's episode will feature a special guest, Scott Wu. Scott is the top ranked Codeforces member in the US. He helped Harvard earn a gold medal in ICPC World Finals 2016. He also achieved three gold medals at the IOI 2012-2014, achieving a perfect score in 2014.<br />
<br />
We will be discussing his problem, <a href="http://codeforces.com/contest/627/problem/E">Orchestra</a>, from 8VC Venture Cup 2016. We'll be taking a deep dive into this problem and learning several tricks to bringing the runtime down gradually. If you have any questions you would like answered by Scott in the broadcast, please leave them in the comments on this post!<br />
<br />
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+31+-+Orchestra&iso=20180210T12&p1=900">time</a>, <a href="https://www.youtube.com/watch?v=bLxsset706E">stream</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com131tag:blogger.com,1999:blog-8698802889425338143.post-74566857151946979522018-01-20T22:34:00.001-08:002018-01-21T11:14:58.899-08:00Episode 30 - TreapsThis week's episode will cover the treaps. The main advantage of treaps is an easy to implement binary search tree data structure. I'll be discussing why I think they are a useful data structure and a handful of useful tricks that make them more powerful than segment trees.<br />
<br />
Here are some useful notes for learning more about treaps:<br />
<br />
<ul>
<li><a href="http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-treaps.pdf">Jeff Erickson's treap notes</a></li>
<li><a href="http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture16.pdf">Proving depth of a treap</a></li>
<li><a href="https://dl.acm.org/citation.cfm?id=2677251&dl=ACM&coll=DL">Randomized Reduction Lemma</a></li>
</ul>
<br />
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+30+-+Treaps&iso=20180121T10&p1=%3A">time</a>, <a href="https://www.youtube.com/watch?v=erKlLEXLKyY">stream</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com24tag:blogger.com,1999:blog-8698802889425338143.post-71914001586160351032017-12-15T20:57:00.000-08:002017-12-15T20:57:00.456-08:00Episode 29 - Rainbow RoadsI'm happy to announce <i>Algorithms Live! </i>will be returning tomorrow! I'm sorry to have been away for so long. With the amount of travel, reading and preparations for some research ideas, working on ICPC contests, and wanting to focus on my job search, it was difficult to reliably schedule episodes. Plans for the future of this show are exciting. I used some of this time to map out where I wanted these episodes to go. A few of the episodes are based on your requests.<br />
<div>
<br /></div>
<div>
So now for big changes! I recently started a new job at <i>drive.ai</i> working as a simulation engineer. For those that don't know, my research background is in simulation and training in virtual environments. I'm happy to be applying some of this knowledge to self-driving cars and happy that <i>drive.ai </i>is supportive of me continuing to run <i>Algorithms Live!</i></div>
<div>
<i><br /></i></div>
<div>
The other piece of exciting news is I moved to California. I've finally met Lewin in person and hopefully will meet many other competitive programmers in the bay area and have them on the show. :)</div>
<div>
<br /></div>
<div>
Being in California allowed me to finally attend one of Donald Knuth's Christmas lectures in person. Many of you will remember my Christmas tree lecture from last year. This year was a bit different. Donald gave an exploratory lecture where he demonstrated the excitement of diving deep down rabbit holes while doing research and some combinatorial geometry. It was exciting and humorous but oddly enough, the lecture was not about trees!<br />
<br />
I'm going to rectify this dilemma, as it wouldn't be Christmas without talking about one of my favorite classes of graphs. This week's episode will once again feature Lewin Gan. We will discuss his ACM ICPC problem "Rainbow Roads" that was used in several regions in the US. You can try the problem by solving one of the following regionals in Codeforces gym:</div>
<div>
<ul>
<li><a href="http://codeforces.com/gym/101617">South East USA Regional Contest</a></li>
<li><a href="http://codeforces.com/gym/101615">Pacific Northwest Regional Contest</a></li>
</ul>
</div>
<div>
This will be my last episode of 2017 to ease back into things. I'll be going on holiday break this week, but will start running regular weekly episodes at the start of 2018. I've missed running this show and hope that many of you will like the future episodes to come!</div>
<div>
<br /></div>
<div>
See you live! (<a href="https://www.youtube.com/watch?v=8r9bLmn5dgs">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+29+-+Rainbow+Roads&iso=20171216T15&p1=900">time</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com15tag:blogger.com,1999:blog-8698802889425338143.post-91897279215139887402017-07-26T10:48:00.003-07:002017-07-26T10:48:58.543-07:00Episode 28 - Sparse Tables and LCAIn this week's episode, I will be discussing the relationship between the lowest common ancestor problem of a rooted tree and range minimum query. Tree traversals can be saved as a sequence and the idea is the foundation behind Euler tour trees. This idea is also how you relate lowest common ancestor queries to range minimum query.<br />
<br />
Though segment trees are a nice solution to range minimum query, I'll be coding the sparse table solution, which is closely related to the binary lifting technique. This gives another lens to view this problem through. Sparse table has the added benefits of an O(1) query.<br />
<br />
On the personal life side of things, I had some issues where my PhD adviser backed out of moving to the university I was planning to attend this fall. This is what caused the scheduling issue for the episode a few weeks ago. I've decided to go back into industry and am looking for jobs and staying with friends over the next few weeks. What this means for <i>Algorithms Live! </i>is episodes will be at strange times for a bit. I'll try to run at least one episode a week with less notice until my life balances back out. Thank you for being understanding!<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=EKcQt-74bNw">stream</a>, <a href="https://www.youtube.com/AlgorithmsLive">channel</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com27tag:blogger.com,1999:blog-8698802889425338143.post-12959530677697940652017-07-23T10:56:00.002-07:002017-07-23T10:56:53.337-07:00Episode 27 - Topological Sort and Kosaraju's AlgorithmToday is a surprise bonus episode of <i>Algorithms Live!</i> If viewers recall, I missed an episode due to some scheduling problems a few weeks ago. This episode will make up for that.<br />
<br />
In this episode, I will cover two techniques that relate well to each other. In the first half of the episode, I will discuss two methods for finding the topological sort of a graph. In the second half, I will cover Kosaraju's algorithm for finding strongly connected components.<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=9Wbej7Fy5Lw">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+27+-+Topological+Sort+and+Kosaraju%27s+Algorithm&iso=20170723T16&p1=867">time</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com11tag:blogger.com,1999:blog-8698802889425338143.post-47133982203559297262017-07-21T14:35:00.000-07:002017-07-21T14:36:16.246-07:00Episode 26 - Fibonacci MachineThis week's episode will cover the solution to an old segment tree problem I enjoy:<br />
<ul>
<li><a href="http://main.edu.pl/en/archive/pa/2009/fib">Fibonacci Machine</a></li>
</ul>
<div>
<br /></div>
<div>
In episode 4, I covered <a href="https://www.youtube.com/watch?v=Tr-xEGoByFQ">segment trees</a>. This problem requires a segment tree modified for an interesting purpose. I truly love Polish problems and this problem is a nice augmented segment tree problem. I recommend giving it a try before seeing the solution.</div>
<div>
<br /></div>
<div>
See you live! (<a href="https://www.youtube.com/watch?v=k67ueEUBLnI">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+26+-+Fibonacci+Machine&iso=20170721T22&p1=867">time</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com47tag:blogger.com,1999:blog-8698802889425338143.post-61373827064508618322017-07-15T20:41:00.000-07:002017-07-16T17:36:04.356-07:00Episode 25 - Desert WindOne of the viewers, Mikhail Goncharov, has happily contributed time links to an old episode of algorithms live. You can see the links in the description of the <a href="https://www.youtube.com/watch?v=U4O3SwDamA4">knapsack episode</a>. It is now way easier to navigate the episode to find a useful subtopic being discussed. This expanded description also gives a nice outline so you get an overview of an old episode. Thank you so much! If anyone else would like to contribute similar time links, just send me an overview of the episode in this form (either PM through Codeforces or YouTube):<br />
<br />
<span style="background-color: white; font-family: "verdana" , "arial" , sans-serif; font-size: 13px;">00:00 Introduction</span><br />
<span style="background-color: white; font-family: "verdana" , "arial" , sans-serif; font-size: 13px;">03:23 Technique 1</span><br />
<span style="background-color: white; font-family: "verdana" , "arial" , sans-serif; font-size: 13px;">5:31 Problem Name</span><br />
<span style="background-color: white; font-family: "verdana" , "arial" , sans-serif; font-size: 13px;">13:21 Technique 2</span><br />
<span style="background-color: white; font-family: "verdana" , "arial" , sans-serif; font-size: 13px;">14:30 Coding</span><br />
<br />
I really appreciate this type of contribution. If you can contribute to even one episode, please do!<br />
<br />
In this week's episode, I will be discussing an old problem that I find interesting, Desert Wind. You can the problem statement here:<br />
<ul>
<li><a href="https://community.topcoder.com/stat?c=problem_statement&pm=1570">Desert Wind</a></li>
</ul>
<div>
<br />
The episode should be a bit shorter than usual but I hope you will all still enjoy it. I should be done right before the start of this week's Codeforces Educational Round.</div>
<div>
<br /></div>
<div>
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+25+-+Desert+Wind&iso=20170716T10&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=Vv0mn4Qf4rY">stream</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com13tag:blogger.com,1999:blog-8698802889425338143.post-5634450559466791522017-07-07T12:33:00.000-07:002017-07-15T20:43:42.660-07:00Episode 24 - 2SATSadly, due to some personal matters, I had trouble scheduling a time for last week's episode. So I'll be running that episode tonight. I'll make a surprise bonus episode sometime in the future to make up for it.<br />
<br />
This week's episode will cover 2SAT (2-satisfiability). You can attempt these problems:<br />
<ul>
<li><a href="http://codeforces.com/gym/101201">ICPC Pacific Northwest 2016</a> (Illumination)</li>
<li><a href="https://open.kattis.com/problems/pieceittogether">Piece It Together</a></li>
<li><a href="https://open.kattis.com/problems/palindromicdna">Palindromic DNA</a></li>
<li><a href="https://code.google.com/codejam/contest/5314486/dashboard#s=p2">Beaming with Joy</a></li>
</ul>
<div>
<br />
This topic is a bit tricky to explain depending on your background and knowledge base. To make things a bit easier, I'll be using concepts taught in the first chapter of Rosen's Discrete Mathematics. I'll be aligning with the notation and assume some basic familiarity with propositional logic and deductions.</div>
<div>
<br /></div>
<div>
The goals of this episode are to demonstrate how to make 2SAT problems easier to implement, pull the answer out, find the lexicographically first answer, and discuss the problem's relationship to strongly connected components.<br />
<br />
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+24+-+2SAT&year=&month=07&day=07&hour=21&min=00&sec=0&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=0nNYy3rltgA">stream</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com16tag:blogger.com,1999:blog-8698802889425338143.post-22688992155239494952017-06-22T17:04:00.000-07:002017-06-22T17:10:03.393-07:00Episode 23 - Strongly Connected ComponentsThis week's episode will expand upon the technique involving low links to directed graphs. The result is Tarjan's strongly connected components algorithm. I'll be addressing how to extract these components and some additional helpful properties that are implicit to the algorithm.<br />
<br />
Here are a few problems you can try solving involving SCC's:<br />
<ul>
<li><a href="https://open.kattis.com/contests/wjchfk/problems/equivalences">Proving Equivalences</a></li>
<li><a href="http://www.spoj.com/problems/FPLAN/">Field Plan</a></li>
</ul>
<div>
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+23+-+Strongly+Connected+Components&iso=20170623T21&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=z9oOadBgO9I">stream</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com4tag:blogger.com,1999:blog-8698802889425338143.post-76763857372125661272017-06-16T11:14:00.001-07:002017-06-16T11:14:09.843-07:00Episode 22 - Biconnected DecompositionsIn this week's episode I will be discussing the types of meta-graphs that can be formed from 2-edge-connected and 2-vertex-connected components.<br />
<br />
Here are a few problems that are relevant to this technique:<br />
<br />
<ul>
<li><a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3136">Mining Your Own Business</a></li>
<li><a href="https://ser.cs.fit.edu/ser2013/problems/division_1/SER2013%20Problem%20Set%20-%20Division%20I.pdf#page=14">It Takes a Village</a></li>
<li><a href="https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2187">Lucky Cities</a></li>
<li><a href="https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4055">Unique Path</a></li>
</ul>
<div>
I will only be discussing a subset of these problems. You may find the others useful to solve on your own to practice this technique.</div>
<div>
<br /></div>
<div>
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+21+-+Biconnected+Decompositions&iso=20170616T21&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=tRTezLvPZ3k">stream</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com6tag:blogger.com,1999:blog-8698802889425338143.post-75431380400992698652017-06-10T15:07:00.000-07:002017-06-10T15:08:21.632-07:00Episode 21 - DFS Lowlink<i>Algorithms Live!</i> is returns! Both the ICPC World Finals and USACO camp were excellent. Thank you to anyone who reached out and said hello at WF. It was fun meeting some of you and I received many great suggestions for improving the show. Meeting USACO campers was exciting as well. I'm happy to see these videos are relevant and useful for IOI training. It was a blast hanging out and discussing problems/techniques while writing as many challenging cow themed problems as possible.<br />
<br />
Now it is time to resume making episodes. This week, I will be exploring some useful techniques for modifying depth first search on undirected graphs. This will allow us to extract articulation points, bridges, and 2-vertex/edge connected components, efficiently. I'll also be going over some tricks for making theses techniques more resilient to parallel edges and self-loops. Better yet, I'll implement these techniques. :)<br />
<br />
I'll be expanding on different uses for this technique and some neat problems related to them in future weeks.<br />
<br />
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+21+-+DFS+Lowlink&iso=20170611T14&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=iYJqgMKYsdI">stream</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com4tag:blogger.com,1999:blog-8698802889425338143.post-72231869020452564552017-05-17T20:43:00.000-07:002017-05-17T20:46:12.172-07:00A brief hiatusAs I mentioned in Episode 20, I'll be going on a brief hiatus from running weekly episodes of <i>Algorithms Live! </i>from now until mid-June. The reason is I'm attending ICPC World Finals over the next few days and immediately after will be helping with the USACO training camp. I was a bit concerned with the quality of episodes while traveling. I also want to take a much needed break. Once I'm back in Orlando, I'll resume my regular weekly episodes. If you are lucky enough to be attending the world finals, please say hello!<br />
<div>
<br /></div>
<div>
You could even call the first 21 episodes of <i>Algorithms Live! </i>season one. The first run has been exciting! The show has featured three interesting guests: Deon Nicholas, Lewin Gan, and Makoto Soejima. (I hope to bring more guests on during the summer months.) The channel has also reached 1000 subscribers. The show has a global audience with the most popular countries being India, Brazil, and the United States. I hope many of you have found the show useful and interesting.</div>
<div>
<br /></div>
<div>
Thanks for watching and I'll be back soon! :)</div>
<div>
<br /></div>
<div>
<br /></div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com2tag:blogger.com,1999:blog-8698802889425338143.post-13919270941218169792017-05-12T13:25:00.001-07:002017-05-12T13:25:40.646-07:00Episode 20 - Bitmask Dynamic ProgrammingHere are some problems related to this week's episode:<br />
<ul>
<li><a href="https://community.topcoder.com/stat?c=problem_statement&pm=8397">FloorBoards</a></li>
<li><a href="https://community.topcoder.com/stat?c=problem_statement&pm=11955">OrderOfTheHats</a></li>
<li><a href="https://lpc.ucfprogrammingteam.org/localFiles/local2015Problems.pdf">Reach for the Stars</a> </li>
</ul>
The topic this week will be bitmask dynamic programming. In particular I will discuss the so called "rolling bitmask" technique and how it is useful in solving certain types of dynamic programming problems.<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=rlTkd4yOQpE">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+20+-+Bitmask+Dynamic+Programming&iso=20170512T21&p1=867">time</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com4tag:blogger.com,1999:blog-8698802889425338143.post-23523481529601145182017-05-06T12:09:00.002-07:002017-05-06T12:10:08.530-07:00Episode 19 - KnapsackThis week's episode will cover knapsack and subset sum. I'll be going over some of the basics of the pseudo-polynomial time algorithm and some of the variants. Gradually, I'll move into more complex variants and related techniques before ending with the solution to this problem:<br />
<ul>
<li><a href="https://open.kattis.com/problems/thief">https://open.kattis.com/problems/thief</a></li>
</ul>
<div>
<br /></div>
<div>
I recommend attempting the above problem. Even though it is knapsack (which is generally considered simple), the problem is quite tough. I hope this episode has something interesting for everyone!</div>
<div>
<br /></div>
<div>
As I'm the author of this problem, I'll be running through how I came up with the problem and some of the tricks I learned from other problems that became relevant to the solution. I hope you will find this episode a very thorough treatment of knapsack and subset sum in general.</div>
<div>
<br /></div>
<div>
Here is another difficult problem related to subset sum you should be able to solve after this episode:</div>
<div>
<ul>
<li><a href="http://main.edu.pl/en/archive/oi/20/pol">http://main.edu.pl/en/archive/oi/20/pol</a></li>
</ul>
<div>
<br /></div>
<div>
In other news, I participated in the TCO regional event in Austin last weekend. It was great to meet many new friends. Some even watch this show! Overall, it was a fun event and I recommend attending any TCO event in the future. For this contest, I employed a new strategy of listening to a <a href="https://www.youtube.com/watch?v=9LDPExlzQq8">waterfall</a> during the contest to help me focus. Do you have a special technique for focusing during contests?</div>
<div>
<br /></div>
<div>
Tomorrow will be the regional event at ITMO in St. Petersburg. I'm sure many top competitors will be attending. Check it out if you live near there! It seems there will be a mirror of this contest online. :)</div>
</div>
<div>
<br /></div>
<div>
I'm also looking to make <i>Algorithms Live! </i>more useful. Some viewers have requested written versions of each episode. Unfortunately, I don't have enough time to convert each episode into a written version. If any viewers are up for the task, it would be extremely helpful. :) I'd be happy to send my notes and code written during the episode. Please contact me on Codeforces if this sounds interesting to you.</div>
<div>
<br /></div>
<div>
Another suggestion was to include time tags in the video description for specific topics in each episode. As I cover multiple topics, this will help viewers navigate to pieces of interest. I'll be starting on this process (slowly) for each episode. You can help by leaving a comment with time tags for your favorite old episode. Do you have any other suggests for improving this show? Let me know in the comments!</div>
<div>
<br /></div>
<div>
See you live! (<a href="https://www.youtube.com/watch?v=U4O3SwDamA4">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+19+-+Knapsack&iso=20170506T21&p1=867">time</a>)</div>
tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com11tag:blogger.com,1999:blog-8698802889425338143.post-88087461107307415982017-04-26T17:33:00.001-07:002017-04-26T17:33:22.563-07:00Episode 18 - Tree Traversal TrickeryTry these problems:<br />
<ul>
<li><a href="https://ser.cs.fit.edu/ser2011/problems/contest/SER2011%20Problem%20Set.pdf#page=13">Family Fortune</a></li>
<li><a href="http://main.edu.pl/en/archive/pa/2012/ple">Knapsack</a></li>
</ul>
<br />
Last week, I mentioned I would be running this episode on Wednesday due to travelling to the TCO regional event in Austin. It turns out there is an SRM at this time! So this week's episode will take place a day later. <br />
<br />
In this episode, I will cover a handful of tricks involving preorder and postorder numbers on trees and some neat properties involving them. I'll also discuss two different approaches for solving the problems linked above.<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=3nxtY1KStww">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+18+-+Tree+Traversal+Trickery&iso=20170427T21&p1=867">time</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com8tag:blogger.com,1999:blog-8698802889425338143.post-11861325589317205832017-04-21T13:21:00.001-07:002017-04-21T19:06:06.272-07:00Episode 17 - Binary LiftingTry these problems:<br />
<ul>
<li><a href="https://open.kattis.com/problems/tourists">https://open.kattis.com/problems/tourists</a></li>
<li><a href="http://codeforces.com/contest/519/problem/E">http://codeforces.com/contest/519/problem/E</a></li>
<li><a href="https://www.codechef.com/problems/DRAGONST">https://www.codechef.com/problems/DRAGONST</a></li>
</ul>
<br />
I realize the last few weeks have been a bit rough for Div2 viewers. The problems have been near ICPC World Finals level and I want to vary the difficulty of topics to make sure everyone can enjoy the show. This week I'll be covering a technique that is more accessible! This technique is called <b>binary lifting</b>. It is a technique for quickly walking up a rooted tree.<br />
<br />
In last week's episode, I discussed the solution to the problem Ski Resort from NAIPC. The problem required us to compute LCAs (least common ancestors) quickly on rooted trees. I'll be expanding on how to do that in this episode.<br />
<br />
You'll also learn how to quickly know the length of paths in trees, find bottle neck edges quickly in weighted graphs, and other useful tricks.<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=kOfa6t8WnbI">stream</a>, <a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+17+-+Binary+Lifting&iso=20170421T21&p1=867">time</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com6tag:blogger.com,1999:blog-8698802889425338143.post-80862091716867211732017-04-16T21:21:00.000-07:002017-06-27T05:36:35.409-07:00Episode 16 - Ski ResortNAIPC 2017 took place this weekend as well as the Open Cup version (GP of America). I'm hoping many of you enjoyed the problems and found them interesting. The set was challenging for many teams. You can find the official standings to each contest here:<br />
<br />
<ul>
<li><a href="https://naipc17.kattis.com/standings">https://naipc17.kattis.com/standings</a></li>
<li><a href="http://opentrains.snarknews.info/~ejudge/res/res10376">http://opentrains.snarknews.info/~ejudge/res/res10376</a></li>
</ul>
<br />
MIT won NAIPC solving 10 problems. On the Open Cup side, Tsinghua University impressively solved all 11 problems towards their victory! ITMO also had a strong performance. Well done! It should be an exciting ICPC World Finals in a few weeks.<br />
<br />
In this week's episode, I will be covering a solution to the toughest problem from this contest. Only Tsinghua University managed to solve it in both contests. You can find the problem here:<br />
<a href="https://open.kattis.com/problems/skiresort">https://open.kattis.com/problems/skiresort</a><br />
<br />
Dominator trees seem to be trendy in competitive programming at the moment. This problem appears to play the part. Yet there is a solution to this problem that makes no use of dominator trees! Still, this problem is a good excuse to explain dominator trees and how to construct them simply for directed acyclic graphs. There are also a few other tricks and observations needed to solve this problem.<br />
<br />
See you live! (<a href="https://www.youtube.com/watch?v=N2gRzgjJXZw">stream</a>, <a href="https://www.youtube.com/c/AlgorithmsLive">channel</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com8tag:blogger.com,1999:blog-8698802889425338143.post-90931177881502179222017-04-07T13:07:00.000-07:002017-04-07T13:09:55.999-07:00Episode 15 - Split the SequenceAt the start of last week's episode, I mentioned my decision to split the episode in two. The last problem, Split the Sequence, is beautiful and I felt it deserved its own episode.<br />
<br />
I highly recommend you try the problem yourself if you haven't already:<br />
<ul>
<li><a href="http://olympiads.kz/apio2014/apio2014_problemset.pdf">Problem B: Split the Sequence</a></li>
</ul>
<br />
This week's episode we will systematically move through the solution, approaching faster and faster runtimes, as we make observations about the problem structure. See if you can spot the greedy property you need to solve the problem. We'll be discussing the proof of this property using the exchange argument technique from last week's episode.<br />
<br />
See you live! (<a href="https://www.timeanddate.com/worldclock/fixedtime.html?msg=Algorithms+Live%21+Episode+15+-+Split+the+Sequence&iso=20170407T21&p1=867">time</a>, <a href="https://www.youtube.com/watch?v=g2-kTX0GIOg">stream</a>)tehqinhttp://www.blogger.com/profile/17983249486596806434noreply@blogger.com8