arc070_b: No Need

Note that the orignal problem means that, a number is necessary if and only if there exists a subset without a(i), s.t. subset sum in [K - a(i), K) !!!

Also, since all a(i)s are positive, we can ignore ALL a(i) > K, as it will never appear in the subset we need anyway !!!

Idea 1

Claim: a(i) < a(j), and a(j) is not necessary, a(i), will not be necessary

Proof:

  1. consider all subsets without a(i) and a(j), either it is >= K or < K - a(j), consider the second case, adding a(i) will not bring its value to >= K

  2. Suppose we have a subset with a(j), s.t., subsetSum + a(j) is in [K-a(i), K), then we swap a(j) and a(i), we have subsetSum + a(k) >= K - a(j) and < K - a[j] + a(i) => contradiction!

Therefore, we need to find the smallest i, s.t., a(i) is necessary. log(n) checks, with O(K) at each check

Idea 2

No binary search, just DP on prefix and suffix sum, at each step, we do a two pointer approach, one at 0 from LHS, and K at rhs

rv = K
LPE(lv, 0, K) {

	while(rv + lv >= K && rv > 0)
		rv--;

	while(!suf[i+1][rv] && rv > 0){
		rv--;
	}

	if(rv + lv < K && rv + lv >= k - a[i])
		return true;
}

arc081_b: Coloring Dominoes

Just do a linear scan from left to right. The number of ways is deterministic at each step, 3 cases, ||, |=, ==, and =| !!!

agc019_b: Reverse and Compare

Consider the contribution from individual approach!!!

If a[i] = a[j], doing a swap will not contribute to the final count, because it will be same as swapping i + 1, j - 1.

Conversely, if a[i] != a[j], it will definitely contribute to the final count.

Proof: if swapping i and j does not contribute to the unique count, then there must exist i1, j1, s.t., i1 =< i, and j1 >= j, s.t., swaping gives the same answer. But this implies i, j is on the same side of a palindrome, i.e., a[i1] = a[j1], this contradicts with fact that a[i1] = a[j1] does not contribute to the final count

Therefore, we can count char count for each letter, and the answer is N^2 - sum of ( count ) * (count -1)/2

arc082_b: Derangement

Consider the first i = p[i], if p[i - 1] < i - 1, swap i and i - 1, otherwise, swap i and i + 1.

Offcial solution just swaps i with i+1 all the time if i = p[i], and n with 1 if p[n] = n !!!

arc083_b: Restoring Road Network

Order shortest paths by length, and we try adding them as edge one by one. Every time we see a new shortest path, we try finding the current shortest path between the two end points, if it is longer than the current path, we know that this must be a new edge. add it to the network

Official solution

Consider if there exists a third vertice w (w != u or v) s.t., a(u, v) >= a(u, w) + a(w, u), we know (u, v) is not necessary - idea similar to F-W. So we just sum over all necessary a(u,v)

agc010_c: Cleaning

Official solution

Assign an alternate function to edge instead of nodes, for each appeareance in our paths, we can add 1 to the edge. So we know that for leaves, ev = weight, internal nodes, sum of evs = 2 * weights. So we can uniquely determine the path bottom up.

The check i missed is that for an internal node, we have to make sure no edge is more than HALF of the total evs, otherwise, tehre will not be enough endpoints to assign to the incoming edges!!!

arc084_b: Small Multiple

try all 1s from 1 to K 1s, by pigeon hole principle

  1. At least 1 will have mod K = 0

  2. very likely to have two numbers with same mod.

Whichever one comes first will give the answer

Official solution

Construct a graph by assigning 1 to an inc operation, and 0 to * 10 operation, do a 01-bfs, until we have more than K #s,