Skip to content
This repository was archived by the owner on Jul 29, 2021. It is now read-only.

Latest commit

 

History

History
94 lines (92 loc) · 3.23 KB

action.md

File metadata and controls

94 lines (92 loc) · 3.23 KB

Action Items

  • Stay alert during contests! Don't make silly mistakes!
    • Check understanding with the test case!
    • Memoization broken?
      • Make sure memoization array is large enough, or it could wrap
      • Make sure the arguments to the function aren't being modified
    • DJS broken?
      • Init djs!
    • Tree input broken?
      • Worst case, use an adjacency list, traverse with DFS and pre
    • DFS infinite loop?
      • Base cases for all arguments, both high and low end
      • Make sure you have a pre if the graph is bidirectional
      • Check for if (nxt != pre) not if (cur != pre)
    • Djikstra Pointers
      • No vis array, just check if dist is already less after popping from pq
      • Remember to set dist when pushing into pq so you don't need to do it when popping
    • Treap
      • Spot check variable names
        • stp vs cur vs dir
        • < or > ?
        • dir or 1-dir?
      • Update treap base to have ins in the insert fxn not be a reference
        • Because otherwise it may break due to rotations
  • Paper work
    • Do more of it...?
    • PSUDOCODE!!
    • Consider MLE too (not just TLE)!
  • Don't over think problems! Think transformations, not more advanced stuff!
  • Redo missed USACO Gold Problems
    • 2020open
      • 1. haircut
      • 2. fcolor
      • 3. exercise
    • 2019open
      • 1. snakes (TLE 4/12)
      • 2. walk (TLE 9/15)
      • 3. balance (not started)
    • 2018open
      • 1. sort
      • 2. milkorder
      • 3. talent
    • 2018dec
      • 1. dining (not started)
      • 2. cowpatibility (TLE 1/11)
      • 3. teamwork (TLE 8/10)
    • 2016open
      • 2. closing
      • 3. 248
    • 2015dec
      • 1. cardgame (not started)
      • 2. feast
      • 3. dream
  • Redo other problems
    • s20o
    • contests/dated/2020_04_07 2..4, 5 someday
    • contests/dated/2020_04_27
    • contests/dated/2020_04_29
  • Redo problems as bottom up
    • #1 dp13 oj12186
    • #2 dp14 oj1220
    • #3 dp15 (redo as both top down and bottom up)
    • #4 dp37 tm1039
    • dp36 (do as both)
  • Summer 2020 401 homeworks
  • Transformations
    • What if it was backwards?
    • What if it was rotated? (2+ dimensional arrays)
    • What if it was rotated conditionally? (even/odd?)
  • Advanced time complexity analysis
    • contests/dated/2020_04_07/ 2 and 3 and 4
    • s20o2
  • Practice algebra with inequalities, max and min, abs, floor.
  • Familiarity with data structures
    • Stack, c-dated 2020_04_20/7
  • Familiarity with classic algorithms (code them a bunch)
    • KMP
    • Trees (struct, see contests/dated/2020_04_29 #3)
    • Trie
    • Graph shortest paths
      • Djikstra
      • Bellman Ford
      • Floyd
    • MST
      • Kruskal
      • Prim
  • "If there is some way to remember to step back and avoid my mistake in gold2019open problem 2, that would be helpful as well but I don't know how to systematically avoid that."
  • Questions
    • Sparse Table
      • What's the complexity to update the table if we update an entry in the base array?