Round 68: Right Triangles

A variant of Fenwick tree

Round 68: Triangular Updates

For the banded updates, one technique is to convert the original array to an delta array. The main benefit is that update can be translated to exactly 2 updates instead of variable sizes => the original items will be recovered by calculating the prefix sum of the delta array.

This problem has similar idea, except that to retrieve the items, prefix sum is diagonal

Round 69: Build Correct Brackets

n^2 DP

Official solution

keep track of cost[i][j], and ways[i][j], i.e., cost/ways to make the first i chars correct out j outstanding (s, for each incoming char, we just see if we can flip or not, and update the answer as we go

Final answer is cost[N][0]

Round 69: Cover the Tree

Official solution

1. need to find a node s.t. no subtree is dominant !!!

2. Obiously, we should try each path to be leave to leave. This means we will have at least ceil(nl/2) pairs = # of pathes, so we can just pick two two leaves for the biggest two subtrees, form a path, and add the remaining leaves back to the pq

3. If there is one remaining at the end, we just connect it to the root

922D: Robot Vacuum Cleaner

Order by the ratio of h/s

proof: Consider the noise function of f(a + b) = f(a) + f(b) + ns(a) * nh(b) Conversely, f(b + a) = f(b) + f(a) + ns(b) * nh(a)

Therefore, f(a+b) > f(b+a) <=> a’s ratio (s/h) is higher

Implementation-wise, watch out for the case where nh = 0 and handling doubles!!!

934C: A Twisty Movement

Considering the point separating 1 and 2, if the band we select does not cover the point => Consider the case of not choosing anything

Therefore, we just dp on the cutting point, and reassemble the two parts 1112222111222

932D: Tree

binary lifting

938C: Constructing Tests

Easy to see the maximamum 1 pattern => x = n^2 - floor(n/m)^2

So we can brute force on all factors and see if possible to form a pair of factors

938D: Buy a Ticket

1. For back and forth, double the edge count

2. To calculate multiple shortest paths, just add all nodes to the initial heap. The final answer is the answer we are looking for!!!

377B:Preparing for the Contest

bsearch on days, and then use a pq on feasible students, but by cost. The key insight is that we can reuse the pq on the next sgement, because the previous capabily ones are still solid!!!

501D:Misha and Permutations Summation

Uses factorial number systems

652D:Nested Segments

A common pattern of solving 2-d problem with the help of a 1-d D.S. Uses fenwick tree!!!

301B: Yaroslav and Time

binary search answer + Bellman-Ford

Suffix Flip

for each number, precalcuate the binary flip of that number

for each number, we have no more that 17 bits to flip, so we can populate a DP table

Overall 10^5 * 17

Official solution

Note that at every move, the last digit keeps changing between 0 and 1, alternatively, until we reach the all 0 cases.

Therefore, all numbers end with 0 => losing case. The other is the winning case.

Falling Balls

Segment tree related

509C: Sums of Digits

need to know minGood[i], suppose we know minGood[i-1], need to find the miniumum number > minGood[i], and sum of digits = b[i], gine b(i), we know the min size of digits.

Then we know the length of string has at most two choices, size of string, size of string + 1, or sum of digits/9

In each case, we just brute force on each digit, and see if it is possible to fit that digit into, i.e., the remaining digit sum range can contain the remaining b[i]

O(n^3) run time, because we have to represent the number as a string

374C:Inna and Dima

Use 4 step BFS to find the edges between D nodes => 4 * 3 * 3 < 40 mil edges max

We can find an edge, we can can use a union find to see if the vs are within the same component, if so, then cycle.

In the end, calculate longest path in each tree

Official solution is confusing to read

264C:Choosing Balls

For each ball, calc the prevvious color index, then we have two choices, either use all values between the two balls,or just use the previous ball + current v * a(i)

353D:Queue

Observations

1. Relatively orders of girls do not change

2. t(i) >=

   final pos - init pos

   , call it D(i).

3. t(i) >= t(i-1) + 1, because at t(i-1), D(i - 1) + 1 = D(i) is occupied by a boy !!!

4. Because each one moves as fast possible, so each t(i) is the max of the two. Note such pattern seems not uncommon, i.e., giving list of reachable lower bounds, the minimal answer is the max of those reachable lower bounds

5. Alternatively, we can use the blocking -> non-blocking + hold trick!!! That is, we don’t swap the F until we are sure that we will not be blocked by previous girl. This means startT(i) = startT(i-1) + 1, if i and i-1 are next to each other. or startT(i) = startT(i-1) - (numM between i and i-1) + 1 !!!

Final answer is max of startT(i) + D(i)

592D:Super M

Find the longest path in the tree, and the answer is len - longest path, just need to tweak the algo a bit the skip subtrees with no nodes to visit

141C: queue

Sort the pair by a(i), and assign n….0 to them. Then for each, just assign them to the existing vector at a[i]. Of course, if a[i] > current size, it is impossible

The insertion can be done by res.insert(res.begin() + a[i], man)!!!

142B:Help General

cases: n or m = 1, n or m = 2, n >=3 and m >= 3. Note that it is a known conclusion that in such case a knight path exists!!! Therefore, we just take every OTHER node of the path to avoid conflict

918C: The Monster

For each i, we start scannning from right to left, and keep track of how many free ?’s we have, and how many (, we have

if size of stack is empty, but we have ( incoming, reduce ?, if nothing to reduce, we know we are bad already if size of stack + free ? % 2 = 0, we add sum[i - j] to sum [i]

The final result is the sum[0] to sum[j]

918D: MADMAX

standard DAG dp, with state[A’v][B’s][last char][A moves now]

Note the first step is special, don’t include them in the DP state

770C:Online Courses In BSU

Standard DP on DAG problem. Also note the standard 3 state cycle check problem

613B:Skills

1. check if possible to fill all skills to max level

2. The final form is that some mininum are raises, and some are increased to max numbers, we know that

a. if incrase all mins by 1, the increased cm < cf

b. if increase a skill to A, then increase cf < increaseing the min cm

1. Therefore, we can calculate the cost to make the min K aligned together

2. After that, we try filling max number one by one, and given the pre-computatin, we know exactly the max min value we can reach, so each fill step can be calcualted in O(logN)

652C: Foe Pairs

keep track of current index at 0, maintain a heap that sorted by end and the start

Keep popling the heap

1. if the curStart >= curIndex, add curEnd - startIndex, and then update curIndex to curStart + 1

2. in the add add n - startIndex

919D: Substring

1. if it has cycle, can be infinitely large

2. otherwise, it becomes longest path on the tree problem, once for each letter

788B: Weird journey

Hard problem for me - uses facts about Euler graph

117C: Cycle

Do a dfs, while maintain an index on the current DFS path, every time we reach an “visiting” node, we can check if that node’s index = current Index - 2

arc089_b: Checker

1. Note that if (x, y) is B, then it is equivalent of asking if (x + K, y), or (x, y + K) is W!!!

2. So for each cell we call categories it into one of the 2k * 2k cells, i.e., the 4 - grids form a cyclic pattern.

3. Then we try all (k^2) possibilies of lower left corner, with the help of 2-D ps to calculate v’s inside the rectangles in O(1) in each try

arc090_b: People on a Line

1. form two direct graph, one forward, and reverse

2. while not all are visited, forward visit form each vs, and then for each node in the graph, reverse visit

3. the moment we have current + edge != next, we know we have an inconsistency

Official solution

But directed graph with pos and neg weights, resepctively. Run DFS for each connected components, update dist (+ or -) as we go

arc090_c: Avoiding Collision

Consider the complement of the problem. Calculate how many ways A and B can collide?

Calculate wayS(v) = # of shortest paths from S to v, waysT(v) = # of shortest paths from T to v

So total possible choices to waysS(T) * waysS(T)

number of ways to meet in a node = for each node, if distS(v) = distT(v), then decrease by waysS(v) * waysT(v)

number of ways to meet in an edge = for each edge (u, v), if distS(u) + distT(v) + len(u, v) = distS(T), and distS(U) < D/2 and distT(v) < D/2 then decrease by waysS(v) * waysT(v)

Round 65: Crossing Tree

Answer = 2 * |E| - |longest path|

So we find the longest path first, and put all its edges on a black list

then we start from the first to the second last on node on the longest path, and print out the traversal minus the blacklist edges

Round 65: Count Arrays

I had many problems during idea and implementation!!!

Consider the final array we get, we will just consider number of good arrays ending with i with a[i] = 0.

Find the left most i, that we can construct a good array even if all betwee i and j are filled with 1,e.g, with a two pointer method, and then calculate the partial sum in [j, i).

Round 66: Counting Quacks

sort n numbers, and start calculating for the min LCM <= T, the first answer = number of index, the second answer the T/LCM(1…i)

Round 66: Flipping Matrix

We can see that if there is a row or col full of 0s, we can not flip it.

Claim: as long as no row or col full of 0s, we can find a way to flip Proof: that means, each row in each col forms a permutation of 1..n, i.e.,we just need to rearrange the perm.

So we can just, for each col, find which rows has it. and we keep track by the set size, and we sort by the set size

For each swap, we will

1. swap first non-visited set.begin() row number with the current col

2. update the doublely linked map of original col <-> after col

3. update visited row to col

Official solution

Modelled it as bipartite graph, and find a perfect matching,e.g., by Hopcroft-Karp

645D:Robot Rapping Results Report

Variant of longest path from root of a DAG

494B: Obsessive String

Hard problem for me!!!

First, use KMP to find all possible mapping points

689D: Friends and Subsequences

Segment tree related

769D:k-Interesting Pairs Of Integers

10^8 brute force

222D:Olympiad

1. Since there is no upper bound, we can always take first

2. To calculate lower bound, we just sort both runs, and run a two pointer with one moving from from L to R, one from R to L

3. if curSum >= x, move both closer, increase the count, else, move the lower bound up. Final answer is the count

622D:Optimal Number Permutation

Easy construction exists for a total zero sum!!!

601B:Lipshitz Sequence

Hard problm for me

916A: Jamie and Alarm Snooze

This is type of question where existance proof leads to solution

Claim: the answer will exist within 24 hours Proof: because each click <= 60 seconds, so we will hit every single minue of the day, i.e., we will hit 07:mm and 17:mm

916B: Jamie and Binary Sequence

This is a relaxation problems

Constraint: we # 1 bits <= N

Note that for each bit we shift to the right, we increase total count by 1, i.e., we can gradually push bits to the right until we hit N

So we can try:

1. Can push all bits?

2. if not, just push 1 to the right by 1, and increase counter by 1

916C: Jamie and Interesting Graph

Build the graph N - 1- 2-…..N - 1, calculate two primes s.t., p2 - p1 > n - 2. Assign p1 to N-1, and 1,…., p2 - n - 2 to (N-2) - (N-1)

For each remaining edege, just add complete graph i -> (i - 1 + deala) % N + 1, with weight p2, until we reach the total count

914C: Travelling Salesman and Special Numbers

The more 1 bits we have, the higher k will be. Therefore, we can dp to find a range of # of 1 bits, s.t., # of steps = k

Then we can answer the following questions, given n, how many #s <= n has < nb 1 bits

so we scan from left to right, keep track of how many 1 bits we have encountered so far, for each one bit we have, we have (remaining pos to the right choose remaining 1bits) to the answer. In the end we need to check if n itself has <= nb 1 bits

914D: Bash and a Tough Math Puzzle

Uses a variant of segment tree

232A: Cycles

Keep caluculating the complete graph, and populate matrix of said complete component

Official solution

29C: Mail Stamps

Build a graph, and dfs with a root with degree 1

346B: Lucky Common Subsequence

lcp[i][j][k] = longset common subseqeucne in s1[1..i] and s2[1…j], with the suffix the first k letters of visit

if(s1[i] != s1[j]){
	lcp[i][j][k] = max(lcp[i -1][j][k], lcp[i][j-1][k]) 
}else{

	if(s1[i]  == 'v'){
		lcp[i][j][1] = max(lcp[i-1][j-1][0..4])
	}else if s1[i] == 'i' {
		lcp[i][j][2] = lcp[i-1][j-1][1]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,,2,3,4])
	}else if s1[i] == 'r' {
		lcp[i][j][3] = lcp[i-1][j-1][2]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 'u' {
		lcp[i][j][4] = lcp[i-1][j-1][3]
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,,3,4])
	}else if s1[i] == 's'{
		lcp[i][j][0] = max(lcp[i-1][j-1][0,1,2,3])
	}else {
		lcp[i][j][0] = max(lcp[i-1][j-1][0,...4])
	}
}

321B: Ciel and Duel

1. either we destroy all defense card and attack card or we just pick a few attack cards only

2. if we try destroying all D’s cards, we will try to match as close to the defense card as possible, and then match as close as possible the attach card. If feasible, the answer is total of remaining attacks cards after step1 - total of D’s attach cards

3. the decide how many attack cards we destroy, we have to brute force on how many 1..i, sorted by strength, of D’s attack card.

Official solution

770D: Draw Brackets!

During the bracket matching process

1. Keep track of which level the bracket is at

2. Keep track of max level all together

3. We add a space only for the, i.e., the matching [ is next to ]

223A: Bracket Sequence

maintain a balance of strings, on each closing ones, we can calculate

1. the current length of the string, by peeking at the top of stack’s pos

2. how many [ we have in this substring => by pre-calcuing a prefix sum

In the end we just find the best solution

343D:Water Tree

Uses segment tree

372B: Counting Rectangles is Fun

Note that q will dup # of possible cells, so we just brute force calculate if (i, j, k, l) is a properrectangle in O(n^4)

After this, we can use a 4D consecutive sums!!!

792D: Paths in a Complete Binary Tree

1. Up: find the right most 1 bit, change this bit to 0, check the bit to its left, mark it 1

2. Left: find the rightmost 1 bit, change the bit to the right to 1, mark cur bit to 0

3. Right: similar to left, except we leave curbit alone

915C - Permute Digits

This follows the patterns of relaxation under constraint!!!

The key insight is that it doesn’t matter how you do brute force search, you have to try the minimal suffix, and see if it can be smaller,i.e., the first digit < b’s digit may not be d[i] - 1.

One counter example is 31, 30, the answer should be 13.

915D - Almost Acyclic Graph

The removed edge must be on a cycle, so we just find a cycle, and try edges on them one by one, to see if the removed graph is acyclic.

Note that to detect cycle in directed graph, we need a “visiting” state on top of the visited state.

I got the idea during the contest, but i was hesitant to calculate n^3 solution, because I didn’t notice that # of edges is no more than 10^5, which makes the overall performance right into the bound!!!

906A - Shockers

Maintain a set of impossibles

1. for each ., add letter to impossible

2. for each !, add all letters not in the word to impossible, and check if all but one letter in the word is invalid

3. for ?, check and update if we are in guessed mode

Official solution

From the last entry we know the answer, and then for each letter, we calculate the latest entry that deny’s its existance. The final answer is the latest of all other 25 letters

912C - Perun, Ult!

This problem has a lot of corner cases!!!

Three types of events

1. health is set to less than the kill threshold

2. health is set to higher than the kill threshold

3. health has been regened more than the threshold

Note that max value must exist in the second right before the second and third event. So for each event, we add a type 2 and or 3 events, and then we do linear scan

agc020_a: Move and Win

A naive DP-ish approach will not work, because you can move back and forth => creates cycles, thus should not use DP approach and think about an insight based approach

agc020_b: Ice Rink Game

I used a band-based approach to reverse and calc min-max values.

But note that at each step, f(x) = x - x mod a[i], i.e., f(x) is monotonic, and the whole sequence of actions can be though as a composition of monotonic functions. Thus, we can just bsearch min/max to see if the final answer >= 2 for lower bound, and <= 2 for upperbound!!!

The uppoerbound for k is 2 + K * max(A(i))

agc020_c: Median Sum

Consider any subsequence and its complements, we know that one must be =< total/2, one must be >= total 2, i.e., for any subsequence <= total/2, we can mirror its complemnet to the other side => total/2 IS the cut off value for median!!!

Therefore, we can DP to find the min value >= total/2. We can compress the DP state by keeping only a list of values, and scan from max value to min value

Official implementaion uses a bitset which I don’t quite understand!!!

Round 63: Find Remainder

1. K > max(b(i))

2. a(i) - b(i) >= 0

3. (a(i) - b(i)) % K = 0

4. Consider the GCD of all deltas > 0, and filter buy the constraint that K > max(b(i)).

5. Note that K should be smallest, i.e., GCD % K = 0 !!!

6. So we just bruteforce from 2 to sqrt(GCD), update K by either divisor or GCD/ divisor, as long as they > max(b(i))

Round 63: Graph Game

The key insight is that # of even deg vs has the same oddity as total # of vs!!!

Therefore, suppose N is even, A will always pick the scenario with even # of even degs, B will always pick the scenario with odd # of even degs, i.e., B can not lose => A always loses.

Conversely it is true for the odd case

Round 64: Create Tree

Just check them one by one, because unique path among all = unique path from single node to all!!!

Round 64: Limited Moves

Claim: A will win all cases if N is not a power of 2!!! Proof: we keep removing the least signficant bit 1 in current N, we know that the next move will introduce 1s to the right of the bits B removed, i.e., we can keep goinging, this means as long as B can move, A can move, i.e., A can not lose

How to verify that consul is in a normal state

1. the nodes request shows expected number of nodes

2. insert a value on the first node, check its value on the second node

Drill 1: single node failure

1. Stop an EC2 instance, verify autoscaling group kicks and spawns a new instance.

2. Verify that the new instance joins the existing cluster and reaches a stable state

3. Go inside the container, verify that the new consul instance is at the correct version (to test the rolling upgrade case)

4. Restart the stopped instance at 1), force remove it after it joins the new stable cluster. Otherwise, force remove it.

Drill 2: loss of quorum - multiple instances down

1. Reboot all servers

2. The ECS should kick in and all servers restart and rejoin the same cluster successfully

Drill 3: loss of quorum - complete outage

1. Stop all but one server. ASG will kick in and spawn new instances, but the cluster is at a corrupted state, so any rejoin will fail.

2. Stop all newly spawned instanced expect the original alive one

??4. Change the -bootstrap-expect, note for the init bootstrap you need -boottrap-expect flag for sure -need to take out ASG desired capacity

1. go to the -data-dir of each server, inside ratf/ dir add a raft/peers.json file. Find the server id in node-id file of data directory. This file should include ONLY the alive node

2. reboot the only alive server now. Make sure the log shows that peers.json is read correctly

3. Go into the new instances, and manually join the node to the cluster

Why migration

1. Spring Cloud Config does not provide good secret management solutions, compared to vault + consul

2. Using Eureka implicitly infers that all our services will be using spring cloud. This assumption is too strong

3. The self-preservation node makes our DR drills trickier.

4. Modifying the main DNS entries with EIP is annoying for our DR drills. If we use hosted zones instead, the from time to time the service will report unable to resolve the main eureka DNS entries.

5. EIP is public ip, but most likely you want your Eurkea instances to be on private subnet

6. Need to explicitly override EurekaIp if you want to run your services in ECS, otherwise, it will register as the docker container ID

Migration Plan

1. For each service to migrate, start a new branch with dependency and config changes. This branch keeps rebasing from dev

2. Migrate Cloud Config as the first service, so that other services can reuse it.

3. Update all services build jobs, and create a new ECS cluster that mirrors the existing ones

4. On production, change the DNS record to point to the new ECS cluster’s LB

5. During the process, keeps rebasing from the master

6. Run DR drills before completely replaces Eureka

Setting up consul

1. For the deployment, we use an autoscaling group (ASG) of fixed size, i.e., min size = max size = 3 or 5, and set -bootstrap-expectto the cluster size. Desired size for ECS and ASG are equal to the min size

2. Use -retry-join "provider=aws tag_key=$TAG_KEY-ecs tag_value=$TAG_VALUE" to mark the consul EC2 instances. Other flags don’t seem to work in my experiments.

However, this retry-join by tag actually gave me a lot of trouble in DR drills, namely the handle the case where majority of instances are replaced by autoscaling group. In the end I took it out and manually join the cluster. Consul is smart enough to rejoin previously know cluster

1. Need -client 0.0.0.0 so that the consul inside docker can receive traffic from outside the docker,i.e., consul will listen to all network interfaces

2. The image we use is based on the offical consul image, but we have to modify docker-entrypoint.sh to include EC2 API call. So that we can fix the node id to the EC2 instance ID, and address to the EC2 private IP. I also tried invoking the curl call from terraform or supply the command from docker command, but my efforts are not successful

A working example, inside the docker-entrypoint.sh

set -- "$@" agent -server -ui \
        -data-dir="$CONSUL_DATA_DIR" \
        -config-dir="$CONSUL_CONFIG_DIR" \
        $CONSUL_BIND \
	-bootstrap-expect=$BOOTSTRAP_EXPECT \
	-node $(curl -s http://169.254.169.254/latest/meta-data/instance-id) \
	-retry-join "provider=aws tag_key=$TAG_KEY tag_value=$TAG_VALUE" -client 0.0.0.0 \
	-advertise $(curl -s http://169.254.169.254/latest/meta-data/local-ipv4)

Setting up consul client

1. EACH instance in your service cluster needs consul agent and registrator running. This can be done by using ECS api call in user data AND adding that to systemd, or just force ECS task capacity same as cluster size.

2. By default, i.e., without -dev or -server, agent runs in client mode. It can reuse our custom consul server docker image above.

3. Registrator and consul client should not be in the same task, because during start, registrator should wait for the consul client to get ready. Otherwise, the registrator ECS task would fail.

4. The registrator automatically discovers the service name by its BASE docker image name. This means all our deployments should use a single ECR with different tags

5. However, most likely you don’t need the registrator, because most consul client package will include the registration

6. Consul client agent container should run in the host mode, so does all its client programs, i.e., we should manage ports to avoid conflicts here. Note if the network is host mode we don’t need to set -client

7. Unlike server agent, client agent can and should rejoin by tag, since its stateless

Gotchas

1. For spring cloud consul, MAKE SURE you set spring.cloud.consul.discovery.queryPassing = true. Otherwise, spring’s consul library will grab unhealthy instance as well. This caught us off guard during our DR drills.

2. To deregister a service instance, use the agent API instead of catalog API on the same host the service instance is running. The service ID is the “ServiceID” field returned by the GET request

3. ECS has no auto restart API. So as part of deployment, we need to register a new service definition and then update the service, as shown by many other people. However, pay attention to the minium health threasold you set. If it is too high (> 0 if you have only 1 instance), the auto restart upon service update will not kick in, because otherwise, the # of health services will drop below your min thresold

612D: The Union of k-Segments

Do a standard event based approach. Note need to handle the tail.

877D: Olya and Energy Drinks

How to improve the naive BFS runtime?!!!

To root cause is there are too many wasted edges => therefore, we try not to store or traverse them.

For each row and col, we keep set of unvisited cells, at each step of BFS, we just keep using lower_bound() and upper_bound() to find and later remove the next cell to visit

442A: Borya and Hanabi

1. Try all 2^10 guesses, maintain a colorCount for each card, and cardCount for each color, current know cards.

2. for each hint, populate corresponding color/card. every time we fix a point, reduce the unknown count for each color-card, by 1. Note we need to skip the already populated case.

3. Do a recurisve reduction, stops if current know cards = n, or this reduction finds none that can reduce, if only card is known, check if the card has only 1 type of unkown color, if so, mark it as known. if only color is known - similar. If both are unkown, we can try only if only 1 color has 1 unknown cards.

14D:Two Paths

Official solution

The two paths don’t intersect, so we can try each edge that cuts the tree into two, and calc the product the longest path in each subtree

891B: Gluttony

find the inverted index of all values, and shift them to the left by one, i.e., new inverted index for 1 is the old inverted index for 2.

Proof: such shift works because, consider the subset doesn’t include the old 1 index,i.e., the new n index, the subset sum of the new one is already greater than the old one

Otherwise, the subset sum is the total sum, which is a constant, mius the subset doesn’t include the old 1, which is already different

778B: Bitwise Formula

iterate them bit by bit, use dp to solve the value

514D: R2D2 and Droid Army

since its continous, just use a two pointer to calc shift, use a heap on each col to maintain the max value. not we will allow start = end + 1, to mark invalid ones

627B: Factory Repairs

looks like fenwicks tree problem

263D: Cycle in Graph

Consier the case where we can not expand the path in DFS ANY LONGER, then all its neighbors must be on the path generated by DFS already!!! so the first vertex on the path marks the start of the cycle, and the cycle has K+1 vertices, i.e., len k + 1

I got stuck here because

571B: Minimization

This follows the patterns of decoupling (1D -> 2D) into independent parts and then recoupling (2D -> 1D)

First, notice that we can decouple the whole array in a list of silo, the indicies from the same silo have the same value mod k. The best value for each silo is to sort inside it, i.e., the different between max and min.

Moreover, to achieve the optimal value, we should avoid overlaps between the max and min values. Therefore, the problem reduced to, given a sorted array, how do we partition them into S segments (no rotation either, otherwise we will introduce overlaps)!!!

Claim: we have k - (n mod k) groups of size n/k!!!

Proof: because we organize the groups by mod value, so we have k groups in total. Because each index is evenly distributed, group sizes are either n/k or n/k + 1. We can see that we have n mod k groups that has size n/k + 1, and thus the remaining ones are the smaller groups

Now, how do we do the partitioning? Note the placement order matters even with the same group count, because the gap between silos are ignored, so we need to place our small and large groups carefully. Therefore, we do a O(k^2) bottom up DP on the optimal placement, and keep update the dp[l+1][s] or dp[l][s+1] value

387C: George and Number

1. Suppose the numbers have no 0, then answer is either N or N -1, depending on the first two digits

2. If the nubmers have 0 suffix, then it must be part of the number, if the prefix < the number, so we look for the right most occurance of prefix < the 0-suffix, then we know it must be a single number. To the right of it, all prefix > 0-suffix, so we can just add the numbers one by one!!!

570D: Tree Requests

Do a DFS, keep track of the following things

1. upon visiting each node, add it to the end of the list which is for all nodes at that level - this is where I got stuck!!! The effect is that each list is a left-to-right scan of the tree, i.e., for each node, there exists [l, r] s.t., all nodes in that band are children of that root node.

2. keep track of in/out time of each node, make sure add time by 1 at each in AND out

By 1) and 2), we can see that l >= in time of the root node, and r <= out time of the root node => so just bsearch twice. Use lower_bound!!!

Once we get bound, we can do a prefix sum on each letter, to decide if there is too much odd numbers.

487B: Strip

Just go greedy to expand band from left to right

Official solution

f(i) = min(f(j)) + 1, i - g(i) < j < i - l

260C: Balls and Boxes

The last index must have one of the lowest values.

For each candidate,

1. if i = x, we are good

2. if i > x, then there is no value = min value in the range of [1, i], [x + 1, n]

3. if i < x, then there is min value in the range of [i+1, x]

so we need to keep track of

1. left most min value

2. right most min value

3. rightmost min value to the left of x

Official solution

Consider the reverse of the operation, we remove balls one by one from right to the left, at one point, we will reach a 0, and that will be one feasible choice for the init index.

To speed up implementation, we can just reduce all values by minV - 1, and then finish the last incomplete loop

432C: Prime Swaps

Calculate all primes <= 10^5, and inverted index for each number. For each number, use bubble sort idea, except that pick the larget prime < distance, and repeats. The prime number is about 10% of all numbers, i.e., we can reduce the distance to 1/10 in each swap => good for 5N requirments

691D: Swaps in Permutation

get all chars and indices in a components, sort the chars and components

825D: Suitable Replacement

Do a bsearch on the final number, find the larget one s.t. number of ?s > missing chars we need to fill

305C: Ivan and Powers of Two

First, preprocess the inputs to remove all duplicates of powers, i.e., for each power, get the count, and then add each binary index to the count of binary + current power

Then we scan from v = 1 to maxV => answer is just ?!!!

524C: The Art of Dealing with ATM

For each request, for each bill, try k1 from 1 to 20, the k2 from 0 to 20 - K1, see if K2 is a possible solution

Official solution

Create < 5000 * 20 possible values, with least # of bills to get the value. For each of the 20 query, we iterate over the first part, and look up on the second part

873C: Strange Game On Matrix

for each column, the band size is fixed, so we can just two pointer to find the highest starting band with max value. The cost is the band sum in [0, optimalStart]

360A: Levko and Array Recovery

make an upper bound for each entry. For op type 1, update the delta array, for op type 2, update the upper bound for the band.

In the end, run the array through the sequence of action again to verify all op2s are still good.

615C: Running Track

Just brute force, try both forward and backwards for the longest substring that matches the current head. Note that by the greedy approach, it doesn’t matter if we matched more in the first then the second => O(n^2)

Official solution use a DP LCP(i, j), to calculate the longest common prefix of the suffixes, i to m, j to n, and longest comon prefx i to m, j to 1

Round 61: Paint the Fence

Even-based approach, looking for the fence with layer 0.

Partial-sum approach

we mark delta[L] = 1, delta[R +1] = -1, then the number of layers at i = sum of delta[0] + delta[1]….+delta[i]

Can do a second ps on if layer[i] = 1 or 0, so we can calculate # of solutions between [L, R] efficiently

Round 61: Strictly Increasing Array

If we are looking for a non-decreasing array, we just need to find LCS. However, we can not use it directly, as we know A(j) - A(i) >= j - i, in the LCS we found!!!

So we just do a reduction, i.e., A(j) -j >= A(i) - i, this reduces to our LCS problem.

Round 62: Simple Paths

Find the first path from A to B, mark all discovered edges as bad. Then run again, while ignoring the blacklist.

Official solution

For each edge, calculate if it is a bridge or not => i.e., if without this edge, the graph is still connected

Then for each query, try to find a path without containing any bridge!!!

Round 62: Partial Maximums

Do a rolling start, keep track of top 2 numbers. For each number, track if it is already max, only 1 greater, or 2 greater than that. If only 1 greater than the current number, that greater number count++.

In the end, we just looking the number with max count, plus all number that is already max.

Official solution

Claim: We can introduce new partial maximums only if we removed an existing one!!!

Proof: Suppose suppose a new partial maximum got introduced as a result. then the one removed must be > all before i, i.e, the removed on itself j (j < i), must be a partial maximum

so for each 3 consecutive local maximua, we can just remove the middle one and do a brute force search

Note that for the last partial maixumum, removing it will introduce at most 1 new one, so we can ignore that case

arc081_c: Don’t Be a Subsequence

Start from empty string, try finding the first index where all a-z are included. If unable to find it before the end of the string, we have an answer. Otherwise, reset indices, and repeat the process

Official solution

1. Use dp to caluate the length of target subsequence len[i] = min(len(next(i, c))) + 1

2. start from 0, find the smallest char c, s.t., len[i] = len(next(i,c)) + 1, and then update i

arc083_c: Bichrome Tree

Official solution

Consider minV(v) = min total of the values of different color, then for each child node, we can mark either the child node same as the root color or not!!! i.e., we add sum to either v(c) or minV(c) to the current node value. We want to find min other value while to current node value <= v(parent), we can use a minOther(child, current value total) dp at each node. Again, because the value is positive, we can just ignore out of boudn case

arc085_b: ABS

Claim: A can not get better result than taking all but last or last in the first step!!! Proof: If A takes less than second last in the first move, and can achieve better result, then B can take the last or second last instead, which blocks A’s moves

arc086_b: Non-decreasing

If |minV| > |maxV|, add minV to all, and do a rolling add from n to 1. Otherwise, add maxV to all, and do a rolling add from 1 to n.

arc087_b: FT Robot

Standard coding problem. Note that for the each of coding, we can handle x and y separately!!!

arc088_b: Wide Flip

bsearch on K, at each K guess, do a greey conversion, start at the leftmost 1, and issue a flip, to improve the speed, use an even-based approach.

Official solution

For each different a[i] and a[i+1], we know we have to flip it, and the min length <= min(i + 1, L - i + 1).

It becomes obvious that we can find a solution given these upperbounds, i.e., the tighest upper bound is the solution, because it is no problem for us to filp longer segments. We can fix them one by one from left to right