Round 59: Triangular Matrix

We can do a greedy approach. since for each row, we are interested only in the min char, so we record what candidate indices we have, and only take the indices withe min char as the new candidates, and add the min char to the solution

Round 59: Editor

each line must start with a word, therefore, after max 10^5 lines, we will run into a cycle, and we need to quickly answer this question: if this line start at index i, what the index at which the next line starts, and how many first entries we will see on this line?

This can be calculated by a bsearch. Of course, we need handle the case where total length < W.

Note that official solution uses a two-pointer method by calculating the mod of total length!!! This works because

  1. we reduced to the case where total length >= W, there form the next pointer will never catch up from behind. This is the important gurantee of two-pointer’s performance.

  2. we know EXACTLY many complete cycle exists, so we just reduce the W and delta between start and end pointer, but the length of this many complete cycles

so we need to know, cycle length, plus how many first entries appeared in this cycle, by keeping track of how many first we have seen before we start this line

curstart = 1
ln = 1
while curstart not seen && ln <= H
	seen[curStart] = ln
	next[curStart] = calculateNext(curStart)
	if(nextStart <= curStart){
		numFirst++;
	} 

	numFirst += (W - firstSeg)/TotalLen;
	total[curStart] = numFirst;
	curStart = next[curStart]
	ln++;

if(ln > H){
	return numFirst

}else{
	cycleLen = ln - seen[curStart] 
	numCycle = (H - see[curStart] - 1)/curlcyLen;
	cycleFirst = numFirst - total[curStart - 1]	
	numFirst +=  numCycle * cycleFirst;
	H -= (numCycle - 1) * cycleLen; 
	//repeat the while loop above without bsearch to finish the remaining H
	//alternatively, we can use some formulas
}

Round 18: Squarish Rectangle

brute force search on W, since W <= sqrt(S)

Round 18: Concatenated String

For each char, we maintain a set of its indices, and then we scan b one by one while maintaining the index at i. If we can not find solution via set.lower_bound(), we reset the current A index to 0

However, this implicitly dependes on the size of S, may still be too slow!!! To key insight is that since we keep moving pointer to the right, we can speed up by keeping track of current index, and ignore all index < current index

We will just pre-compute next(i, c) = at index i, what the next index of char c. To calcualte it, we need to keep track of last seen char index, and upgrade everything between the last seen one, but before the current one

Round 17: To Front - To Back

Find the longest consecutive subsequence, anything not on it must be moved. To calculate it, we can just keep track of the seen index of the number, and the length of consecutive subsequence of it.

Round 17: Largest And Subset

Keep a set of candidates, starting from the highest bit. Scan through the candidate to find one with that bit as 1. if there is less than k candidates, we do nothing. Otherwise, we narrow down the scope

Round 16: Marble Weights

Just weight the 2,3,4,…n subrarray. In the end weigh 1 with n

Official solution

3 weights to find w1, w2, and w3, and then we can weigh w1 with w4…w5…w6

Round 16: Fake Coins

  1. The key is to find an arrangement s.t. 10 and 30 are in two different partitions

  2. What is the probability that 10 and 30 will be in the same parititon => 50% !!!

  3. So we just randomly assign coins to two parts, on avg, we expect 2 tried to find them in different paritions

  4. After that, it will be standard ternary search

895B - XK Segments

  1. suppose we have a range (L, R), then the exact number is R/x - (L-1)/x. I had problem coming up with formula during the contest!!! Should be easy to come up with if we view it from the delta band persepctive

  2. Therefore, given x, k, we know the range of R, and we can bsearch on the left and right part of the array, and we take distance as number of js in the form of (j, i)

My (wrong) approach during the contest

  1. calcualte # of coordinates s.t. no more than k number divisible by x in the segment

  2. calculate the segment length, but with k - 1

  3. calcualte the difference

The idea did not work => we didn’t consider the case (i, j) where i > j, and a(i) = a(j). This may happen if we have a band of equvalents, and k happens to be 0 or 1!!!

Implmentaton-wise, normally two-pointer needs two checks, 1 for index, one for predicate. because it is a while on and solution, we need to explicitly check for out of bound/invalid case.

895C - Square Subsets

I got the bitmask idea - need a bit mast to mark the state of products => which primes have odd numbers. However, the answer will be 2^19^n which is still too high.

Instead of iterating on index i, we can just iterating on the value of numbers, since it is < 70!!! We will check how many ways to get a product with odd number of primes in the subsequence of 1…70

i.e., ways(n + 1, oldbm) += ways(n, oldbm) * sum of(choose(num(n), even times)) ways(n + 1, oldbm XOR bitmask of n) += ways(n, oldbm) * choose(num(n), odd times)

893D - Credit Card

How do we calculate the exact amount we need to fill at each step?

If we have to fill a card, we need to fill it s.t. at least one suffix sum of which has to become d. Because otherwise, we will overflow at some point, so we just try the best possbile.

To calcualte to potential maximal to the right, we need to

  1. precompute the sum of all deltas,

  2. scan from right to left, to keep track of max delta so far

  3. also keep track of fills we have done so far, at each point we need to fill, the max we can fill is d - maxDelta - deltaSofar. If deltaSofar + ps[i] < 0, we know it is invalid

Round 19: Cities Robbery

four cases:

  1. go straight to left

  2. go straight to right

  3. left and then right

  4. right and then left.

We can use either set.upper_bound() or a two-pointer approach

Round 19: Smallest Array Permutation

  1. If one # appears > ceil(N/2) times => we have no solution

  2. If one # appears = ceil(N/2) times => we have to use this number ONLY IF IT IS ODD!!!

  3. Otherwise, we use the minimum number. Can use a heap to keep track of current maximum. Note that the official solution does not use a heap!!!