436A: Feed with Candy

Consider the final solution: we should never eat 2 in a row. Therefore, we just try 2 cases, the first we eat is type 1 or type 2, and pick the best answer.

407A: Triangle

we can fix one point at (0,0), and then brute force to search for the second point coordinate with the a conditon, and then use the b condition to locate the 3rd point, or use the fact that (x, y) and (-y, x) form a right angle.

The part I failed is that I forget to check if the 3rd edge is parallel to any axis!.

460C: Present

Idea 1

Bsearch the answer, for each answer, we linear scan the array from left to right, also, we need to maintaind a d matrix to record the stop watering event

Idea 2

Greedy works on O(nm), but need additonal DS to speed it up

407B: Long Path

Claim: when we arrive at i + 1, all j < i has been visited even times already

Proof: By induction,

  1.  when we reach the i for the first time, by inductive hypothesis, prevous i-1 has beenn visted even times 

  2. if i points to itself, it will loop until it reaches even time, then move onto i+1

  3. if move to previous entry, then following sequence of action is same as p visited for the first time. By the difference of the
induction on case p and case i, we know the number of ops introduced by the subseqenct actions at each cell is even. Now we have visited i
even time, and move onto i+1

Therefore, when we later on move back to previous entries, the # of actions is same as we visit it for the first time, because even times case = 0 times case

visit(i,j) : number of steps to visit j, from i for the first time, with all cells visted even times already, with the exception of i

visit(i, j) = visit(i, j -1) + visit(p(j-1), j -1) + 2 //1 for moving from j-1 to p(j-1), one for moving from j - 1 to j

base case visit(i, i) = 0

246D: Colorful Graph

For each edge, consider C(u) and C(v), we just update Q(c(u)) and Q(c(v)), and in the end select the set with max cardinality

similarly, it is as if we create a graph based on colors, and add edge between colors

459C: Pashmak and Buses

This one uses the trick of focusing on individual in collective actions

Consider the unknown: if the two students have the same assignment each day, what would that suggest?

Consider the sequece of assignment for each student, there are k^d possible choices, this means the two students will be friends if and only if they share exactly a sequence of assignments. Therefore, if n > k^d, we know it is bad. Otherwise, we can assign a unique sequence id to each student

My wrong approach focused solely on collective actions, which gives a maximum of k * d

C. Bear and Prime Numbers

My (Failed) Idea

  1. generate all primes <= 10^7

  2. factor all n numbers, for each factor, increase the match[factor] by 1

  3. sweept through the array generated by 2, to compute the prefix sum

  4. the range becomes difference of prefix sums

The basic idea is sound, however, the main problem is that factoring in step 2) is too slow. Instead, we can use the sieve to reverse the factoring process, and calculate answers for all numbers in a single runr, i.e., instead of increasing match[factor] by 1, we can increase it by f(p)

429B: Working out

Consider the cell they meet at (mi, mj), one has to enter horizontally, and the other has to enter vertically, otherwise, they will have more than 1 same cells, we just need to iterate all possible meeting points, each with 2 possiblites

also, note that the path is effective cut in 2, and each half must exist, i.e., meeting point can not touch border!

so 2 * 10^6 to calculate the cost in 4 directions + 10^6 brute force on meeting points

311A: The Closest Pair

the total number of ops <= n (n-1) / 2, therefore, if k >= that max # of ops, no answer

Notice that we only require delta(x) < d, then we can force all points to have to same x coordinate, and then put them on the same y-axis, the distance between them does not even matter