Proof Consider overshooting \(t\) by \(2^{n}-1\), where \(n\) is the smallest integer that overshoots the target. We would like to prove considering a jump \(2^{n+1}-1\) is not going to yield a shorter set of actions. Note that \(t\) is in \([2^{n-1},2^n-2]\), so from point A we have a remaining distance in \([2^n+1, 3(2^n)-1]\). Again if we consider the possible jumps from A, either we jump to \(2^{n}-1\) or \(2^{n+1}-1\). Of course we will not take \(2^{n+1}-1\) because that would mean we arrive back at the beginning.

extent of region We begin with the segment tree version. Note that Ershov uses a version of the segment tree where the right side of the range of responsibility is open, i.e. \([3,4)\) is equivalent to \([3,3]\) The function get below will find the size of the largest range whose prefix sum is \(k\). int get(int v, int vl, int vr, int &k) { if (k >= st[v]) { k -= st[v]; return vr - vl; } if (vl == vr - 1) { return 0; } int mid = (vl + vr) / 2; int res = get(v * 2, vl, mid, k); if (res == mid - vl) { res += get(v * 2 + 1, mid, vr, k); } return res; } It does so by allowing the \(k\) to go down to \(0\), while there are empty ranges the recursion goes to the right child, until it reaches a single element range containing an element (\(>0\)) at which point it returns \(0\).

credits It is interesting that MiFaFAOvO’s solution has the same pieces are ershov.stanislav’s solution. In fact they both use the worm method (my own naming for subsequence like states). What is interesting from MiFaFAOvO’s solution is that he uses a BIT to solve the problem. what kind of tree is a BIT While the update part of a BIT is pretty straightforward one may wonder at the reverse query part which was done in ershov’s solution \(O(\log n)\).

credit This is ershov.stanislav’s solution to the problem. summary of problem Given an array of integers (colors), find the mininum nunber of consecutive grouping containing at most \(k\) colors (number of unique integers in a subarray). greedy For a single \(k\) one can take \(O(n)\) time to greedily scan through the array and accumulate \(k\) unique integers at a time. problem size However, given the size of the problem (\(10^5\)) and the fact that we must do this for \(k \in {1,\cdots,n}\) implies that we must look for a better solution.

E. Ciel and Gondolas Fox Ciel went into an amusement park. She is in line for the Ferris wheel. There are \(n\) foxes in the queue. We will assume that the first fox is at the beginning of the queue, and the \(n\) th fox is at the tail of the queue. In total there are \(k\) gondolas. We distribute foxes into gondolas as follows: When the first gondola swims up, \(q_1\) foxes enter from the front of the line into the gondola.

Description From Bryant and O’Hallaron’s book Computer Systems: A Programmer’s Perspective. http://www.cs.cmu.edu/~bryant/ http://www.cs.cmu.edu/~droh/ http://csapp.cs.cmu.edu/ One of the first labs. The Bomb Lab, contains a binary bomb that must be diffused, by disassembling the executable. sample bomb A sample bomb can be obtained here. http://csapp.cs.cmu.edu/3e/labs.html problem set and blog Here are a couple of helpful resources: https://web.stanford.edu/class/archive/cs/cs107/cs107.1174/assign5/advice.html http://zpalexander.com/binary-bomb-lab-phase-1/ name list (nm), strings, objdump These are kind of unnecessary, all can be done within gdb.

Bloom Probability of false positive Probability that BF reports positive set membership for an element that is not in the set \[ {\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.} \] \(k\) is the number of hash functions, \(m\) is the number of bits in the array, and \(n\) is the number of entries inserted into the table. Obviously increasing \(m\) and decreasing \(n\) would decrease the \(\varepsilon\) however \(k\) has a optimal point.

5.1 High Availability Chunk Replication RF of 3 master clones existing replicas when chunkservers go offline or detect corrupted replicas Master Replication operation log and checkpoints replicas “shadow” masters provide read-only access file metadata like directory contest could be stale reads replica information from logs pools from chunkservers to locate chunk replicas depends on primary for decisions to create and delete replicas 5.2 Data Integrity impractical to very replica data between replicas use 32bit checksum on 64KB blocks stored persistently with logging and separate from user data in reads: chunkserver verifies the checksum before returning data client reads from another replica master creates a different replica and delete the corrupted one in appends: incrementally update the checksum for last partial checksum blocks even if last partial checksum is corrupted, new checksum value will not match stored data and corruption will be detected in writes: if write overwrites an existing range on the chunk, need to verify the first and last blocks of the range being overwritten calculate new checksums based from previous checksum so that corruption of unchanged areas will be detected 6 Measurements 1 master, two master replicas, 16 chunkservers, and 16 clients 6.

Asciio Modifications clone P5-App-Asciio change the zoom in and zoom out keys ./setup/actions/unsorted.pl: ‘Zoom in’ => [‘000-plus’, \&zoom, 1] Building prep perl Build.PL Dependencies In Ubuntu most dependencies can be resolved by sudo aptitude install lib<Module>-<Submodule>-perl For example if the dependencies require `Foo::Bar`, install it with `sudo aptitude install libfoo-bar-perl` Hash::Slice unfortunately is not part of Ubuntu distribution so you will have to install it via CPAN cpan Hash::Slice Building .

Upstream and origin