Skip to content

Instantly share code, notes, and snippets.

@stevenhao
Last active January 11, 2021 01:23
Show Gist options
  • Save stevenhao/bf2bd013e0948d6f6633dc397bf45e54 to your computer and use it in GitHub Desktop.
Save stevenhao/bf2bd013e0948d6f6633dc397bf45e54 to your computer and use it in GitHub Desktop.
Stevenkplus Stream Notes 1/9/21

Stevenkplus Stream 1/9/21

Education Codeforces Round 101

Goal: Place in top 50

Problem-solving strategy:

  • Plan out implementation ahead of time
  • Try to write all the code in one sitting; any details need to be scoped out ahead of time

A: Regular Bracket Sequence

  • given string with exactly one of '(' and ')', and n - 2 '?'s, can you turn it into a balanced bracket sequence?

  • n must be even or else impossible

  • let k = (n - 2) / 2 (so there are 2k ?s). Exactly k ?'s will turn into (, and k turn into ).

  • greedy simplification if there is a solution, then turning the first k ?s into ( and last k?s into ) will also be solution.

    • proof: basically it's optimal to have ( before ), the condition required for RBS only gets easier to satisfy when you swap a subsequence )( into ().
  • implementation notes: 2 ways, one requires an additional observation option 1) just compute s' = s with ?s replaced optimally, then check if s' is balanced option 2) check if s[0] is not ')' and s[n - 1] is not '(' (and n is even).

Time: ~1:10

B: Red and Blue

two sequences, merge them while preserving relative order of each individual seq's elements maximize the max prefix sum of result

observation:

  • take the max prfeix sum of each individual seq (mx1, mx2)
  • ans is mx1 + mx2 intuition for proof:
  • any prefix pref_{a+b}(merged) of merged sequence is merge(pref_a(seq1), pref_b(seq2)).
  • in other words, a prefix of the merged sequence is merged prefixes of the original sequences
  • so, maximizing that is equivalent to maximizing the two prefixes independently
    • by separating out these two problems, it becomes much simpler (fewer options to consider; there are O(2^n) possible ways to merge, but now there's only O(n) prefixes to iterate through)

implementation plan:

  • helper function getMaxPrefix(ar)
  • dont need long long here.
  • initialize mx to 0 (because empty prefix is allowed)

Total Time: 1:10 retrospective: would've been nice if n, m were same line, saves some typing.

C: Building a Fence

Given n, k, and an array h[0]...h[n-1], Produce an array v[0]...v[n-1] such that the following conditions hold:

h[i] <= v[i] < h[i] + k |v[i] - v[i + 1]| < k

solution idea: iterate over i from left to right (i.e. starting from 0) maintain a range [lo, hi) <-- half-open interval such that lo <= v[i] < hi fully describes constraints on i.

as long as there is always at least one choice, we're good.

implementation notes:

  • Init: lo = 0, hi = inf
  • Enter i: lo = max(lo, h[i]), hi = min(hi, h[i] + k)
    • Special case; enter 0 & enter n - 1 --> hi = h[i] + 1
  • Exit i: lo -= k - 1, - hi += k - 1,
  • Test non-empty --> if (lo >= hi) ans = "NO"

Final Time: 10:25 (w/ 2 WAs) Reason:

  • bug --> hi = h[i] + 1 should be hi = min(hi, h[i] + 1)
    • messed this up in planning. should've thought more clearheadedly
    • should've stuck out as a problem because all other updates to lo/hi were relative
    • whereas this was absolute

D: Ceil divisions

  • update op: v[x] = ceil(v[x] / v[y]) for any x,y
  • n + 5 ops to make everything 1s except for one 2
  • n <= 2E5

Observation: log n is up to 17, which is much larger than 5. so n + logn not feasible

What happens to a_n? your first op on it turns it into something >= 2 eventually... 5 is log log(n). Because what you do is:

To reduce problem from n to ceil(sqrt(n)), do op (x = i, y = n) for all i = ceil(sqrt(n)) + 1 ... n - 1

do this op twice: (x = n, y = ceil(sqrt(n))) --> a_x becomes <= y, then 1

continue until n = 2 (at which point there will be exactly n - 1 = 1 ones, and 1 two) Key idea: we formulated the algorithm as recursive -- reducing the problem to a smaller subproblem

200000 448 22 5 3 2 (2 ops to spare in the worst case)

Implementation:

  • vector ans;
  • hardcode seq = { 448, 22, 5, 3, 2 }
  • read n;
  • for i in seq, if i >= n continue, else do all ops for i + 1...n - 1, do op for twice, set n = i
  • print ans

Total Time: 1:18

E A bit Similar

2 strings are "a bit similar" if they are equal at least one position (s ~ t iff s[i] = t[i]) for some i

  • Observation 1 simplification --> two strings are a bit similar if they are not complements of each other (s != ~t)

  • Observation 2: consider the set of all substrings of s of length k. if some string x is not in s, then ~x is possible answer.

  • Solution:

  • Hash all substrings of length k. store in some kind of set

  • try all substrings in lexicographically increasing order, until you find one whose complement is not in the set. (then you're done! that's the answer!)

    • guaranteed to take O(n) iterations to terminate, b.c. that's the size of the set.
  • Implementation notes:

  • n = 1E6, TL is 2s, no need to mess around with unordered set.

    • hashing use this person's code: https://ekzlib.netlify.app/external/indy256%252Fcodelibrary,cpp%252Fstrings%252Fhashing.cpp -- dacin (rated 2600+)

    • this code allows arbitrary number of bases & generates bases randomly 😍

    • allows querying hash of substring in O(1) time!!

    • need to add new method to the hashing struct to support concatenation, basically.

    • concat(hsh, str): vector

    • hash('00000000000000' + some string of length up to 20) --> do this 1E6 times -> need to do O(20) ops here -> hash('00000000000000') * p[d][20] + hash(str)

    • have a fn toPii: vector -> pii

    • have a fn toStr: int -> string

    • have a set seen, and a way to go from int -> complement -> str

    • set goal_len = min(20, k). pref_len = k - goal_len. pref_hash = hash('0' * pref_len)

    • iterate i from 0 to 1 << goal_len, set compl = to_str((1 << goal_len) - 1 - i) set compl_hash = concat(pref_hash, compl)

    • if compl not in seen we are done, ans is '0' * pref_len + to_str(i)

Total Time: ~17:00 (1 WA test 43, 1 TL test 135)

  • retrospective:
    1. wa because i took hash of '0' * prefLen instead of hash of '1' * prefLen, didn't think clearly about this part, should've slowed down shouldn't have rushed [mistake happened in planning]
    2. tle because i used book code that relied heavily on vectors
    • vectors are very non-performant in this case because of their initialization overhead. vector of size 2 = very slow code
    • even after removing this, my runtime was 1591. so not amazing!!
      • could've done less string stuff, but then code gets uglier
      • could've done more intelligent hashing of binary numbers (via bit-by-bit updates, makes it O(n) instead of O(nlogn) to iterate over n = 2^goalLen hashes)
  1. also overcomplicated; could've used the observation that first prefLen chars must be 1 for a substring to matter

F:

  • find min "value of tree"
  • bin search?
  • no reason to ever not use middle of chain as connection point
  • no reason to use longer chain after (i.e. descendant of) shorter chain
  • binsearch on ans
  • maintain counts of how many white nodes at each level of tree (only count first ans levels)
  • always split @ the top-most level L, dec[L, L + 1); inc[L + 2, L + 2 + a); inc[L + 2, L + 2 + b), where a and b depend on length of chain
  • return true if there are ever at least K white nodes

Implementation notes:

  • data structure: could use segtree, but suffices to track difference array & sum
    • inc[l, r) by val --> first clamp r = min(r, ans + 1), l = min(l, r) diff[l] += val, diff[r - 1] -= val, totsum += (r - l) * val;
  • initializing v[0] = 1, i did this incorrectly. i forgot to track d[0] = -1, instead had it as d[0] = 0
  • track cur = 0, while (cur < ans && curval > 0) curval += diff[cur], ++cur;
  • if sum >= k return true
  • a & b are floor and ceil (v[i] - 1)/2

Total Time 30 mins (WA test 5, peeked at test data) retrospective

  • cur, curval state management in tandem with inc/d stuff is sketchy. need to be very careful here, and plan it out ahead of time!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment