arc076_b: Built?

Sort by deltas in x or y coordinate, and then add edge iff it will the new edge will expand existing components => similar to MST

arc076_c: Connected?

Hard problem to me

Official solution

  1. Given two numbers, it is impossible to construct if all 4 occurance appear in the order of 1,2 ,1, 2 clockwise, i.e., we form a line that cuts the plane into halves. Note if only one number is on the boundary, we can force all lines to go along the sides

  2. So we connect all non-boundary numbers first, and then all boundary numbers

  3. We can use a stack and go clockwise to make sure no intersecting boundary numbers

arc077_b: 11

Classfication: with both same numbers with 0 same numbers with 1 number, and nothing in between with something in between, and one number either to the left or right

Note the official solution calculates the complements

agc017_b: Moderate Differences

Rearrange all the operations to do increase first, and then decrease second, do a brute force search on all possible turning points

arc078_b: Fennec VS. Snuke

Find the path between two starting cells, and find the edge where the two colors. Calculate subtree size rooted at either end of the cell - the one > N/2 wins

agc018_b: Sports Festival

Assume all sports are selected, and we calculate how many people are on each sports. Then we start taking out sports one by one, and update all affected users in the process in O(n)

arc079_b:Decrease (Contestant ver.)

Official solution

Consider the inverse of the problem on an array [0,1,……n-1] !!! Apply them one by one. Speed up by only simulating the last K%N ops, because applying inverse to all = increase all by N

arc079_c: Decrease (Judge ver.)

Official solution

  1. One key insight is that the difference between entries will never be more than N, i.e., one operation will move a number from max to min !!!

  2. bsearch to find Y, s.t., we have a solution for the high watermark value Y, given that we will run operation X times

  3. Apparantly some people just do bruteforce simulate, by try decreasing all values to below N???

arc080_a: 4-adjacent

  1. each odd number must be followed by a product of 4

  2. each product of 2, must be followed by a product of 2 or 4

So we use all 4s to try to satifiy the first condition, and then see if product of only 2 is odd, if so, it is impossible only if we have no 4 remaining

arc080_b: Grid Coloring

Use the zig zag line construction for each square. Use a event-based two-pointer model when coding

arc071_c: TrBBnsformBBtion

Upon inspection, we can see that AA <-> B, and BB <-> A, so we can just covert all B to A, and see the diff in length % 3 = 0

agc013_b: Hamiltonish Path

Use the “growth” approach!!!

We just start with an edge and changing the endpoint if one endpoint has a neighbor that is not in the path yet. Keep doing this, and we will exhaust all unchecked vetirces in N - 1 steps, or we reach an dead end.

arc074_b: 3N Numbers

maintain a minheap and a max heap, and move separator i from N to 2N - 1

agc015_b: Evilator

same direction one, opposite twice

agc015_c: Nuske vs Phantom Thnook

For a forest, we know # of components = total # of nodes - total # of edges. Cutting the region will preserve the forest properties. Therefore, we just need to calculate how many nodes, and edges in that subregion, e.g., by 2-D prefix sum!!!

arc075_b: Widespread

bsearch on the number of expositions, calculate # of As we need for each monster and see if the total sum is good

agc016_b: Colorful Hats

Official solution goes by classfication!!!

  1. max = min, then all unique or all the same

  2. max = min + 1, we know that A = max(a(i)). So number of unique cats = cats with A - 1. A >= unique + 1 and A <= unique + freecat/2

agc016_c: +/- Rectangle

As long as H * W % h * w != 0. It is always possible. Set corner to 10^9, every other to the min v, s.t. v * (h * w - 1) > 10^9

Official construction

  1. if the row number % h = 0, then write positve number. Otherwise, write negative number.

  2. The ratio will be fixed at h/1, so one construction is to have 1000(h-1) - 1 as postive, and -1000 as negative!!!