Skip to content

Instantly share code, notes, and snippets.

@stevenhao

stevenhao/stream_1_7_21.md

Created January 8, 2021 05:34
Show Gist options
  • Save stevenhao/f9ebb94b6c21ef8c70091680153e26d7 to your computer and use it in GitHub Desktop.
Save stevenhao/f9ebb94b6c21ef8c70091680153e26d7 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
stream_1_7_21.md

Plan for the stream

  • Do a division 2 virtual contest

  • Monitor Chat & respond to any messages

  • For Each Problem:

    • Solve it
    • Write solution notes
    • Write implementation notes
    • Set a timer & see how fast I can write the code after having planned out the implementation

  • Goal: Develop habit of preplanning implementation

Solve problems & explain solution in writing (in note form)

Warmup: 684 Div 2 A & B

Notes

A: - all chars independent of each other - simple formula for each char: 0 --> min(c_0, c_1 + h) 1 --> min(c_1, c_0 + h) - implementation planning - count #0s and #1s (num0s, num1s) - compute cost of 0 & 1 (cost0, cost1) - return num0 * cost0 + num1 * cost1 - because limits are small, answer fits in int32 (n * h ~ 10^6) Final Time: 1m 07s B: - Let n = a + b, where a <= b <= a + 1 - the k * a smallest numbers will form the "left half" (smallest a numbers of each of the k arrays) - V = the k * b largest numbers will form the "right half" - which k of the k * b will be the medians? can't do better than just taking - ANS = (V[0], V[b], V[2b], V[(k-1)b] - can't do better, because you can compare any other list of medians (sorted) - ANS' = (ANS'_0, ANS'_1, ...) - the largest element of ANS' must be less than at least b - 1 elements <= largest element of ANS - the second largest element of ANS' must be less than at least 2b - 1 elements - the i-th largest element of ANS' must be less than at least i * b - 1 elements - implementation notes: read in the nk elements, sort, and then take off = k * a, - where a = n / 2, b = n - a - and then select v[off + i * b] for i = 0...k Final Time: 3m + 1 WA (test 2) - retrospective: forgot to think about int vs ll - off by 1 when computing a, should've thought about it more when writing down the formula - where it went wrong: PLANNING PHASE

Main round: 670 Div 2

Goal: Top 5 (with commentary, excluding other unofficial participants) Suggestions in chat!

  • A: Subset Mex

    • Solution: Greedily maximize the mex of the first array A by taking 1 of each of 0, 1, ..., i, until you can't take i + 1
    • B is whatever remains
    • ans is mex(A) + mex(B)
    • Implementation strategy: write a function mex, and use it to find the answer.
    • mex(A) is just i + 1, but since we need to write mex anyway, might as well call it twice.
    • use multiset.erase to yield B after constructing A
    • A will also be a multiset (to match the function signature of your mex function -- it expects a multiset), even though all elements should be distinct
    • constructing A will look like a while loop; iterate i starting from 0, and keep erase/inserting i from B to A as long as B contains i

    Final Time: 1m 12s

  • B: Maximum Product

    • if n = 5, there's one possibility -- trivial.
    • if n is at least 6, optimal solution takes 0, 2, 4, or 5 negative numbers
      • why not 1 or 3? because there's one number you haven't taken.
      • if it's negative, swap w/ positive and now you have a positive product. likewise, if it's positive, swap w/ negative to obtain positive product
    • let vPos & vNeg be arrays, sorted by magnitude (inc)
    • for 0, 2, 4 -- always take the suffix of vPos and vNeg
    • for 5 -- always take the prefix of vNeg
    • don't have to special 0, just treat it as pos (or neg, doesn't matter)
    • implementation notes
      • need long long. (3E3)^5 = 27E15.
      • gonna write a lot of things like ans = max(ans, cand)
    • do the 5 case first, and initialize ans to the 5 case (neg) First Submit Time: 3:14 (WA test 2) Final Submit Time: 7:28

  • lesson learned: if you're gonna deviate from impl plan, make sure you're not leaving something out!

  • maybe just don't deviate at all because it's risky

  • C:

    • constructive problem statement
    • n is 10^5
    • recall standard centroid finding algorithm. start at a node. if a child's subtree has at least n/2 nodes, walk to it.
    • else you're done. works because of the following true statement:
      • after removing the centroid of a tree, the largest remaining CC size is < n / 2 (assume not true, let largest CC be Y and deleted "centroid" be X. move along path X-->Y to X'; X' will be weakly better of a candidate than X because new largest CC is upper bounded by max(n - old CC size, old CC size - 1)

  • resource: https://usaco.guide/plat/centroid?lang=cpp (plug for usaco.guide!! amazing resource for all levels)

  • What does the 2 centroid tree look like?

    • Exists an edge connecting X and Y s.t. exactly half of the nodes are on each side of this edge

  • How do you break a 2 centroid tree?

    • Take an arbitrary leaf in X's subtree, move it to be a child of Y.
      • leaf exists because n >= 4
      • This breaks because Y now has n + 1 nodes in its side
      • moving from Y to any child will reduce size of cc by at least 2 because deg(Y) is at least 2 (not incl. x).
- Implementation
  - root tree arbitrarily, compute subtree sizes, check for subtree of size n/2.
    - store par array
    - 0-indexing; 0 is root.
  - if exists, (call it centroid) then move a leaf to its parent
    - find leaf by doing an array leaf[], and setting leaf[par[x]] = leaf[x] when processing a node
    (post-order op; do it AFTER visiting all your children). initialize leaf[x] = x
    - cut leaf[centroid] -- par[leaf[centroid]]
    - join leaf[centroid] -- par[centroid]
  - if not exists then no-op (cut some edge & restore edge -- 1--par[1] is a good edge to no-op on)

Final Time: 6:31

  • D
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment