Posts

May 2024

  CodeForces Fenwick Tree Find the structure and pattern of taking the Fenwick tree to powers It involves stars and bars method and combinatorics, counting method. Also helpful to have understanding about how binary indexed tree or fenwick trees work. Equal XOR Segment Related to range xor queries Can precompute the xor sums just like prefix sums algorithm. Greedy you split into either 2 or 3 segments. Division + LCP (Hard Version) z-algorithm memoization binary search Trails (medium) dynamic programming matrix exponentiation Trails (hard) Associativity in matrix multiplication. BCBCBC = B(CBCB)C matrix multiplication is not commutative. Get into format where it is a 2 x 2 matrix Exact Neighbors (hard) constructive, pattern If ai = 0, then you can place rest in zig zag They are all distinct can place (1, 2, …, n) in zig zag There is no ai ≠ 0 and they are all distinct, place zig zag, but skip at first repeat Min-Fund Prison (medium) graph theory c
Post a Comment
Read more

Codeforces Round 920 div3

Image
  Codeforces Round 920 (div 3)     Problem F Square root trick, You can use the square root trick to calculate prefix sums in n * sqrt(n).  Where you compute the prefix sums for each step size from 1 to sqrt(n).  Now anytime you have a query where d <= sqrt(n) it can be solved in O(1) with the precomputed prefix sum.  Else it will have sqrt(n) iterations in brute force looping through to get the value.   You do need two prefix sums because you have to create the ones that will give the answer for this specific problem.  Which is a little bit tricky to derive.  Problem G   My approach was very bad for this problem.   You want to use a diagonal prefix sum and column-wise prefix sum.   But the thing is that implementation is very important.   If you try to pad by K to avoid where the diagonal is out of bounds you will end up with 10^5 by 10^5 matrix which is too large.   And if you pad by 1 for the diagonal prefix sum it is a difficult to deal with off by 1 situations.   The
Post a Comment
Read more