Mitko Nikov
Mitko Nikov
  • 154
  • 504 964
Retroactive Data Structures and Time Traveling
Disclaimer: We are talking about data structures, not physics. This specific type of data structure allows for retroactively updating and querying the past. We walk through an example of a retroactive queue and its incredible ability to view and change the past in O(log(N)) time.
Timestamps:
0:00 Intro
1:08 Analogy at the bar
8:48 Example and Explanation
19:00 Order-Statistic Trees
22:33 The Consistency Problem
Thanks to Ivan Mastev for filming the video!
Animations created using Manim Community.
Filmed using Sony A7III in 4K.
Lens used: Samyang 14mm f/2.8.
Edited in Davinci Resolve 18.
References:
Retroactive Data Structures, Erik Demaine:
erikdemaine.org/papers/Retroactive_TALG/paper.pdf
Frequently Asked Questions:
github.com/mitkonikov/competitive#frequently-asked-questions
Collection of Algorithms and Data Structures:
github.com/mitkonikov/atlas
Code for the animations:
github.com/mitkonikov/animations
Переглядів: 549

Відео

AtCoder Beginner Contest #331 - ABCEF (Fenwick Tree on Hashes!)
Переглядів 4499 місяців тому
We had some fun training competitive programming while solving today's AtCoder problems! Make sure you have the data structure "Fenwick Tree on Hashes" with you! Timestamps: 0:00 Intro 0:40 Problem A 2:37 Problem B 5:07 Problem C 15:20 Problem D (unsolved) 49:22 Problem F 56:29 Problem E 1:18:37 Problem D and G (discussion) 1:46:31 Explanations Frequently Asked Questions: github.com/mitkonikov/...
AtCoder Beginner Contest #328 - ABCDEF solutions with explanations!
Переглядів 41710 місяців тому
We practice on AtCoder again and use Gosper's Hack and the Augmented DSU data structure to solve problems E and F! Link to the Augmented DSU data structure: github.com/ShahjalalShohag/code-library/blob/main/Data Structures/Augmented DSU.cpp Timestamps: 0:00 Intro 1:00 Problem A 2:07 Problem B 5:02 Problem C 8:00 Problem D 12:38 Problem E 23:37 Problem F 36:46 Problem G 1:28:23 Explanations Freq...
Amortized Complexity and The Skyscrapers Problem
Переглядів 37010 місяців тому
Amortized complexity is incredibly powerful, especially in invariant-based data structures. So, in this video, I present a simple, intuitive problem that is filled with gems! Link to the gym (you need a CodeForces account to see it and submit): codeforces.com/contestInvitation/47ae8382a534ff7e8bf220bd0122f4bfcbf9dabd Timestamps ⏱️: 0:00 Intro 0:22 The Backstory 2:20 The Problem 5:47 An Example ...
AtCoder Beginner Contest #323 - ABCDEF solutions with explanations!
Переглядів 42411 місяців тому
As usual, we practiced on AtCoder Beginner Contest and solved all problems until and including F on the first try. I also had an idea for G but didn't even try to optimize it due to the lack of time. Timestamps: 0:00 Intro 2:00 Problem A 3:07 Problem B 5:48 Problem C 12:26 Problem D 17:04 Problem E 37:01 Problem F 1:16:06 Problem G 1:31:25 Explanations Frequently Asked Questions: github.com/mit...
AtCoder Beginner Contest #322 - ABCDE solutions with live commentary!
Переглядів 45011 місяців тому
Back for practice on AtCoder! Timestamps: 0:00 Intro 0:49 Problem A (AC) 2:26 Problem B (AC) 4:37 Problem C (AC) 8:29 Problem D (calculating) 12:57 Problem E (AC) 35:56 Problem F (coding) 54:21 Problem D (AC) 1:23:09 Problem F (again)
CodeForces Round #899 (Div. 2) - Solved ABCD with live commentary!
Переглядів 50011 місяців тому
The problems were very fun and interesting in this CodeForces round! If you haven't tried solving them, I recommend first checking them out! Timestamps: 0:00 Intro 0:43 Problem A 2:30 Problem B 20:04 Problem C 51:59 Problem D 1:49:21 Problem E
CodeForces Round #898 (Div. 4) - Full solve with explanations!
Переглядів 1,4 тис.11 місяців тому
Notice, I publish the videos AFTER the contest has ended, even though, we solved the contest way before it ended. This is to avoid cheating! Since I was out of the competition, I didn't really care if I got wrong answers. If I were to compete for rating points, I would be much more careful in testing the problems for edge cases. Also, check out the other videos on my channel including CodeForce...
AtCoder Beginner Contest #320 - ABCDE solutions with explanations!
Переглядів 40511 місяців тому
AtCoder Beginner Contest #320 - ABCDE solutions with explanations!
CodeForces Round #897 (Div. 2) - Solutions to ABCD with explanations!
Переглядів 75011 місяців тому
CodeForces Round #897 (Div. 2) - Solutions to ABCD with explanations!
AtCoder Beginner Contest #318 - ABCDE solutions with explanations!
Переглядів 547Рік тому
AtCoder Beginner Contest #318 - ABCDE solutions with explanations!
CodeForces Round #889 (Div. 2) - ABC1C2 +100 rating
Переглядів 951Рік тому
CodeForces Round #889 (Div. 2) - ABC1C2 100 rating
AtCoder Beginner Contest #312 - ABCDF with explanations of E and G.
Переглядів 496Рік тому
AtCoder Beginner Contest #312 - ABCDF with explanations of E and G.
CodeForces Round #888 (Div. 3) - ABCDEF Solved with Explanations!
Переглядів 1 тис.Рік тому
CodeForces Round #888 (Div. 3) - ABCDEF Solved with Explanations!
CodeForces Round #886 (Div. 4) - Full Solve, Easy Solutions and Explanations!
Переглядів 2,7 тис.Рік тому
CodeForces Round #886 (Div. 4) - Full Solve, Easy Solutions and Explanations!
Binary Milestone and Open-Sourced an Atlas of Algorithms!
Переглядів 153Рік тому
Binary Milestone and Open-Sourced an Atlas of Algorithms!
AtCoder Beginner Contest 309 - A...F solutions with explanations!
Переглядів 747Рік тому
AtCoder Beginner Contest 309 - A...F solutions with explanations!
CodeForces Round #883 (Div. 3) - Solutions to all problems!
Переглядів 766Рік тому
CodeForces Round #883 (Div. 3) - Solutions to all problems!
AtCoder Beginner Contest 308 - ABCDEF in 50 minutes
Переглядів 766Рік тому
AtCoder Beginner Contest 308 - ABCDEF in 50 minutes
CodeForces #881 (Div. 3) - Solutions
Переглядів 514Рік тому
CodeForces #881 (Div. 3) - Solutions
AtCoder Beginner Contest 306 - ABCDEF - Explained
Переглядів 315Рік тому
AtCoder Beginner Contest 306 - ABCDEF - Explained
CodeForces Round #874 (Div. 3) - Easy Solutions Live Explained
Переглядів 1,5 тис.Рік тому
CodeForces Round #874 (Div. 3) - Easy Solutions Live Explained
The Clique In A Room Problem | Erdős-Rényi Theorem
Переглядів 216Рік тому
The Clique In A Room Problem | Erdős-Rényi Theorem
CodeForces Round #871 (Div. 4) - Solutions to all problems explained (ABCDEFGH)
Переглядів 2,4 тис.Рік тому
CodeForces Round #871 (Div. 4) - Solutions to all problems explained (ABCDEFGH)
AtCoder Beginner Contest 299 - Solutions to ABCDE (in 34min)
Переглядів 442Рік тому
AtCoder Beginner Contest 299 - Solutions to ABCDE (in 34min)
Manim Basics in 100 Seconds
Переглядів 51 тис.Рік тому
Manim Basics in 100 Seconds
AtCoder Beginner Contest 298 - Solutions to ABCDEF
Переглядів 382Рік тому
AtCoder Beginner Contest 298 - Solutions to ABCDEF
SQRT Decomposition on Trees
Переглядів 966Рік тому
SQRT Decomposition on Trees
AtCoder Beginner Contest 296 - Solutions to ABCDEG
Переглядів 491Рік тому
AtCoder Beginner Contest 296 - Solutions to ABCDEG
DSU with log(n) Evaluation Function - One of the coolest DSU techniques
Переглядів 391Рік тому
DSU with log(n) Evaluation Function - One of the coolest DSU techniques

КОМЕНТАРІ

  • @heyNepti
    @heyNepti 12 днів тому

    Could you make a video for testing rest apis with this stack? Typescript, TypeORM, MySQL, Express with dedicated test database

  • @Phuey
    @Phuey Місяць тому

    appreciate the hard work , hopefully this stays free i know it takes a lot of hard work but this one is a need for the whole community dont get greedy

    • @MitkoNikov
      @MitkoNikov Місяць тому

      @Phuey Thank you so much! Everything I've done and everything I wish to do on UA-cam has to be accessible for everyone! I know how it feels to be in a position where you couldn't afford things that you need. Everything will remain free forever ❤️ Thanks for reminding me of humanity! Have a wonderful day!

  • @Langorithmic
    @Langorithmic Місяць тому

    you're funny, i'd love to be your friend

  • @Langorithmic
    @Langorithmic Місяць тому

    loved the numberphile references, the humor and the top tier explanations! subbed instantly

  • @Hamster_Tool
    @Hamster_Tool Місяць тому

    Source code ??

  • @stardreamix786
    @stardreamix786 2 місяці тому

    amazing! - i need to get back up to scratch with python this is odd to me 🤣 thank youuu

  • @armandine2
    @armandine2 2 місяці тому

    show more and talk less, a lot less

  • @user-uj6uf3qd6y
    @user-uj6uf3qd6y 2 місяці тому

    This is awesome! I found this is the most well explained video about the data structure. Thanks a lot :)

    • @MitkoNikov
      @MitkoNikov 2 місяці тому

      @@user-uj6uf3qd6y Thank you so much! Every positive comment means a lot!

  • @KushLemon
    @KushLemon 3 місяці тому

    Useless video.

    • @onirique.r
      @onirique.r 6 днів тому

      it helped me and many others, please speak for yourself

  • @angelogalimba133
    @angelogalimba133 3 місяці тому

    God, this is so helpful! Thank you so much, sir!

  • @Ahryno781
    @Ahryno781 4 місяці тому

    How to be good as you

  • @kushmazumdar2800
    @kushmazumdar2800 4 місяці тому

    Can u make a video on link cut tree and treaps?

  • @rubberduck2078
    @rubberduck2078 4 місяці тому

    if you watch on double speed, this becomes Manim Basics in 50 Seconds

  • @silversun4196
    @silversun4196 4 місяці тому

    What are the differences when making in After Effects?

    • @MitkoNikov
      @MitkoNikov 4 місяці тому

      After Effects is amazing for small Motion Graphics, but the problem arises when you have to animate hundreds of objects in some mathematically defined way. Let's say that you want to draw exactly 10000 small circles in a grid. This simple operation is just 3 lines of code in the Manim, but in After Effects, you will have to be a lot more creative to pull it off, or use proprietary plugins. Just handling this many objects in AE becomes cumbersome.

  • @keithTRADING
    @keithTRADING 4 місяці тому

    You can make 2 videos, 1 short one 1 longer one and get paid more adsense for longer 60 mins tutorial and make it shitty whatever

  • @keithTRADING
    @keithTRADING 4 місяці тому

    Great video but I need more advice and more examples!

  • @devchoudhary8892
    @devchoudhary8892 4 місяці тому

    Incredible Video

  • @draido-dev
    @draido-dev 5 місяців тому

    may i request you cover dancing links? it's a pretty interesting way to solve exact cover problems and a general way to 'speed up' backtracking, that is just clever, knuth covered it in extent in his TAOCP vol 4B, either ways just look it up :) pretty interesting stuff! (hail knuth!)

  • @jitendradubey2006
    @jitendradubey2006 6 місяців тому

    💀

    • @jacobb8832
      @jacobb8832 6 місяців тому

      What's that skull for?........Hmm?🤨

    • @jitendradubey2006
      @jitendradubey2006 6 місяців тому

      i accidentally commented my bad@@jacobb8832

  • @foxypiratecove37350
    @foxypiratecove37350 6 місяців тому

    It was too fast! This is great.

  • @jitendradubey2006
    @jitendradubey2006 6 місяців тому

    bro i learned so much from you thank you for educating students who are not able to buy paid courses

  • @jitendradubey2006
    @jitendradubey2006 7 місяців тому

    bro i learned so much from this video thankyou so much for uploading it

  • @pyrobadger
    @pyrobadger 7 місяців тому

    ImportError: cannot import name 'Self' from 'typing_extensions"

  • @1732ashish
    @1732ashish 7 місяців тому

    a `lazy propagation` video is referred to many times, was that uploaded?

  • @stoic_sheep
    @stoic_sheep 7 місяців тому

    How to work with this on termux Android, how to export animation as mp4 format?

  • @karankasraei8025
    @karankasraei8025 8 місяців тому

    How did you use the reset pin on the pcb to initiate a reset? Did you ground it?

    • @SamiJumppanen
      @SamiJumppanen 5 місяців тому

      If the reset pin is "high" (having pull up resistor to Vcc, either internal or external, doesn't matter), it must be grounded for reset. If it's normally low (zero or close to it), then connect to Vcc for reset. Not a big deal to measure, but would be nice to know.

  • @astromessier
    @astromessier 8 місяців тому

    it doesn't work, "No module named manim"

  • @AnuvabSpeaks
    @AnuvabSpeaks 8 місяців тому

    please make a video for installation in 2023, it is not working for my windows laptop pls

  • @Pur5str
    @Pur5str 8 місяців тому

    Is that like a practice site or something for improving your problem solving skills for coding? If so. Could tell me where? I need to improve

    • @faizalrahman6027
      @faizalrahman6027 8 місяців тому

      its atcoder bro

    • @MitkoNikov
      @MitkoNikov 8 місяців тому

      Yes! It's atcoder.jp - a japanese site that hosts fun weekly contests :)

  • @saravananjeeva5258
    @saravananjeeva5258 8 місяців тому

    looks complicated

  • @edbertkwesi4931
    @edbertkwesi4931 8 місяців тому

    powerful

  • @anshumankalra5877
    @anshumankalra5877 8 місяців тому

    Greatt, thanks a ton ❤

  • @mdisrafil2491
    @mdisrafil2491 9 місяців тому

    I need 332 E and G solutions

  • @mdisrafil2491
    @mdisrafil2491 9 місяців тому

    ABC 332 (E) a similar bit mask problem can you make a tutorial on it?

  • @ryanmcgowan3061
    @ryanmcgowan3061 9 місяців тому

    Works in 4.0. Great addon!!!

    • @jaybryan5808
      @jaybryan5808 2 місяці тому

      Lmao just wanted to ask. Cheers mate

  • @-CornDawg
    @-CornDawg 9 місяців тому

    Does this work with Blender 4.0?

  • @arghadeepdey7796
    @arghadeepdey7796 9 місяців тому

    Really liked the solution for E, got to learn something new !

  • @bilolbakhrillayev
    @bilolbakhrillayev 9 місяців тому

    keep it up

  • @martinmendez695
    @martinmendez695 9 місяців тому

    I will try to create a volume per version of the app, so lest say you have the first 50 containers running on version 1.0., later other 25 containers or so using volume node_module_v2...

  • @ziedbrahmi4812
    @ziedbrahmi4812 10 місяців тому

    thank you! keep them comming :)

  • @ziedbrahmi4812
    @ziedbrahmi4812 10 місяців тому

    Thank you, please any other problems with sqrt decomp on trees?

  • @sseu123
    @sseu123 10 місяців тому

    great channel

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      Thank you very much! There is more interesting content coming up!

  • @HarshitGupta-iq9bh
    @HarshitGupta-iq9bh 10 місяців тому

    Can you make tutorial for 326 E

  • @abdelrahmanemad1122
    @abdelrahmanemad1122 10 місяців тому

    Amazing Amazing Amazing ❤ Love your content a lot

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      Thank you!!! 😊

  • @justfree9860
    @justfree9860 10 місяців тому

    nice video

  • @charanteja1160
    @charanteja1160 10 місяців тому

    suggest some resources to learn Dynamic programming

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      Solve the AtCoder DP Educational Contest, I think it's the best way for a beginner to try out dp problems: atcoder.jp/contests/dp

    • @charanteja1160
      @charanteja1160 10 місяців тому

      @@MitkoNikov any tutorials??

  • @1braincellremaining165
    @1braincellremaining165 10 місяців тому

    Need more videos like this. Absolutely loved this one.

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      That means a lot to me! Thank you so much!

  • @rafaelsuazo5993
    @rafaelsuazo5993 10 місяців тому

    Great explanation!

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      Thank you, hope you enjoyed it!

  • @martinsuperfind7779
    @martinsuperfind7779 10 місяців тому

    Love the black & white animations!

  • @AnuarPhysics
    @AnuarPhysics 10 місяців тому

    Great! How do you save the videos so they will have vertical format for smartphones?

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      You can render it in any resolution with the flag --resolution RESOLUTION (passed as “WxH”, e.g. “1920x1080”).

    • @AnuarPhysics
      @AnuarPhysics 10 місяців тому

      @@MitkoNikov Oh OK. Thanks! And what about rising video quality? I tested 1080x1920 and 1440x2560 but both videos look the same in quality. I'd like to render a full HD or more quality video.

    • @MitkoNikov
      @MitkoNikov 10 місяців тому

      @@AnuarPhysics I think by default it's the best quality. Try rendereing it in 4K if you think it's not sharp enough. But, I believe that even 1080p is increadibly good. This is why you don't see much difference from 1080p to 1440p.