Stevenkplus Stream Notes 1/9/21

stevenkplus_stream_1_9_21.md

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)

3. 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!