Edu 6 Editorial

Bosu Baiko

Brute force solution

Notice that the form of the string is either DD...DDDKDKDK... or KK...KKKDKDKD…

​

We can just brute force both cases as well as all the possible change points, and check how many to change

DP solution

Honestly overkill but might be easier to code

​

dp[position][last letter][second last letter] = min cost to achieve

Four Buckets

Greedy (60 points)

Always add to the smallest bucket and see if you die or reach the target

Full solution

We can figure out how many times we need to do the operation.

​

Let n = (a+b+c+d-1)/2 (of course if a+b+c+d is even it’s not possible)

​

We need to perform the operation n times

Full solution

Replace a with a-n, b with b-n …

Now, in 1 operation, we can add 2 to a single number.

​

Guess:

It is possible if there is exactly 1 odd number, and none of them are >1?

Full solution

Almost AC

Consider 4 1 1 1 → 1 -2 -2 -2

This case is actually not possible

​

Full solution

Almost AC

Consider 4 1 1 1 → 1 -2 -2 -2

This case is actually not possible

​

​

​

​

The last turn can only have at least -1, but d is -2

*the limit exists because the number of balls in each bucket cannot be negative

Full solution

Let’s focus on the last turn:

​

The smallest number that can exist is -1. Hence the configuration of 1 0 0 -2 is not allowed

​

​

​

​

Full solution

Let’s focus on the last turn:

​

The smallest number that can exist is -1. Hence the configuration of 1 0 0 -2 is not allowed. It needs to be -1 0 0 0

​

​

​

hence, the initial odd number must be less than 0.

Full solution

Replace a with a-n, b with b-n …

Now, in 1 operation, we can add 2 to a single number.

​

AC Solution:

It is possible if there is exactly 1 odd number, and none of them are >0

Robobear

Idea

We can construct a graph.

Each node can be represented as (x, y, dir), representing which the position we are at and which direction we are facing.

We can draw an edge to the next node in the direction we are facing with weight 0 (e.g. (0, 0, right) -> (0, 1, right) or (1, 0, up) -> (0, 0, up))

We can draw an edge to each other direction we are facing with weight 1 or 2 (e.g. (0, 0, up) -> (0, 0, right) with weight 1 and (0, 0, up) -> (0, 0, down) with weight 2)

We then perform dijkstra on the graph. Time complexity: O(4*n*m*log2(n*m))

Speedup

Instead of drawing an edge to each other direction, we can draw edges only to the 2 adjacent directions (e.g. (0, 0, up) -> (0, 0, right) and (0, 0, up) -> (0, 0, left) with weight 1).

Then, instead of dijkstra we can use 0-1 BFS. Time complexity: O(4*n*m)

Find and Prevent

N <= 1000

For a given component the number of pairs of people is size * (size - 1) / 2

Suppose we root the tree at node x. Then the cost of blocking node x is:

a[x] * (a[x]-1) / 2 (people within the city)

+ sum of sz[y] * (sz[y]-1) / 2 for all y such that there exists an edge x-y

where sz[y] is the size of the subtree rooted at y

If we root the tree at each node and calculate the cost the time complexity is O(N^2)

N <= 1000000

Instead of rooting the tree at each node, we can root the tree at any node.

We then calculate the cost as

a[x] * (a[x]-1) / 2 (people within the city)

+ sum of sz[y] * (sz[y]-1) / 2 for all y such that y is a child of x

+ (sz[root] - sz[x]) * (sz[root] - sz[x] - 1) / 2 (“subtree” of parent)

Time complexity: O(N)

​

Judge anti-breaker

N <= 2000

You can try all N^2 combinations and memo for each cost, what is the best result.

Then each query can be answered in O(logN) which binary search

Full solution

The 1 2 3 4 5 is very fishy, hint: square root

Full solution

Consider the solution where we maximize the number of core speed upgrades first

Then, slowly decrease the number of core speed upgrades one by one, channelling them to core number upgrades.

We stop early once we max have fully upgraded core number (or until we have no more core speed upgrades to downgrade)

​

What is the time complexity?

Full solution

O(sqrtN)!!

​

Consider even 1+2+3+4…. it takes only about 2sqrtN terms to make the sum N

​

When we downgrade, we are downgrading k, k+1, k+2, k+3, … You can only add up at most O(sqrtN) of these terms before reaching N, and hence maxing out the core number upgrade

Full solution

Hence, the final solution runs in O(QsqrtN)

Persistent Lists

Hints

1. As the great shiwei once said, a persistent list is a tree

Hints

• As the great shiwei once said, a persistent list is a tree
• Solve the line subtask

Hints

• As the great shiwei once said, a persistent list is a tree
• Solve the line subtask
• Consider a fenwick tree

Note

I’ll just discuss the online solution from here onwards

The line subtask

Firstly, we need to change the way of thinking. Instead of many lists, we just have a tree (and a line for subtask 3).

Each node of the tree contains a single value.

Then each query is some query about the path from the node a to the root.

The line subtask

This is a fenwick tree, red is the “tail” of the node.

The line subtask

When you do a range query on a fenwick tree, you jump by the black arrows

The line subtask

The main idea is that in a node of size X, we can store O(X) information, and only take O(NlogN) space in across the whole tree

Then when querying, we jump up the fenwick tree in order.

The line subtask

Suppose the node [9,12] has elements [1, 7, 3, 5]

We only need to consider 5 different ranges of b. For each range of b, we need to know the sum of elements, and the value of f(node, b)

​

​

​

​

A node of size X, tabulating this table can be done in O(XlogX) with another standard fenwick tree. In total, it’ll take O(Qlog^2Q)

The line subtask

Using the table, we jump up node by node, and add its contribution to the answer.

It takes O(logQ) time per node, as we need to upper_bound the value of b to consider

​

Hence, it takes O(log^2Q) time per query

f(node, b)

prevcnt * sum

previous nodes

The tree subtask

We can use a similar idea when the tree is not a line

​

The red arrows represent the next node to jump to. Everything in between would be the values that node is responsible for

​

Notice that the red arrows point to the first node with height greater than itself

The tree subtask

We define a value called height for each node.

Height is the number of trailing zeros in the node’s depth.

​

Since the tree is randomly generated, this ensures O(Qlog^2Q) in total

The final subtask

However, this does not work in general as the testcase may be malicious.

For example, this case would have you making new nodes that are responsible for 2^16 values many times, which would TLE or MLE

​

​

The final subtask

Instead of deterministically generating heights based on depth, we can randomly generate them instead��Set height as = 0

Flip a fair coin, if it’s tail break

If it’s heads, increment height, and repeat

​

This means about half are height 0, quarter are height 1, eighth are height 2...

The final subtask

For a node with height h, the node to jump to is NOT the (2^h)th parent

Doing so will probably TLE

​

It is the first parent whose height is at least h

The final subtask

This ensures O(Qlog^2Q) time on average (and randomization means it cannot be maliciously killed)

​

Rough proof:

�About half the time, your height will increase when you jump.

Distance jumped is approximately 2^height.

Hence you jump only O(logQ) times

Bonus tmi

We’re assuming that the coin is fair (i.e. 50% chance of heads)��But apparently the optimal ratio is not always 50% and can be optimized further by playing with the ratio.

​

Another very interesting thing is that even if the coin is very biased like 1.5% or 98.5%, it somehow can AC? I don’t have an intuitive explanation why this is the case, but it does somehow