Asia Pacific, Taiwan, National Taiwan University

https://codeforces.me/team/47344

In Taiwan, we get roughly about $6000 / $3000 / $1500 USD for gold / silver / bronze from our Ministry of Education.

I solved it in contest using the exact same way. I didn't prove the correctness, though.

As what I saw, they just installed a few needed extensions.

Text below is quoted from IOI 2017 Website.

Visual Studio Code 1.11 (+ cpptools and vscode-javac extension)

The host hasn't published "Contest Environment" page on the website. So I think we should wait until the page be published for the details.

Moreover, I think they'll just install extensions they think are needed, and won't let us install arbitrary packages, as it may results in cheating.

Btw, Visual Studio Code was listed as "Things under consideration" on the "Contest Environment" page in last year's website. I didn't participate last year, can someone tell me whether they provided VS Code in contest?

No.

As stated in Code Jam Rule:

4.3 Judging and Scoring.
...
"Visible Test Sets" are test sets for which the outcome of judging will be reported during a Round.

Visible test set can contain testcases other than sample.

It's enough to qualify after solving visible test sets for problem A and B.

Bell numbers count the possible partitions of a set. But in this problem, not every partition method is valid.

For example, when $$$k=4$$$, it won't happen that the first and the third cell are in one component, and the other two cells are in another component. (You can try drawing it on a paper.)

So when $$$k=6$$$, only around 130 connectivity states are valid, as stated by jasony123123.

I solved it with Euler's formula, which stated that number of faces in a connected planar graph is equal to (# of edges) - (# of vertices) + 2.

I add cells into the graph one by one from the lowest to the hightest. For each connected component, it can be considered as a planner graph, with neighboring cells forming an edge, and each cell as a vertex.

I maintained # of edges and # of vertices in each connected component. These are easy to maintain.

I also maintained # of 2 by 2 squares in each component, because each of them forms a face when turning into graph, but that's not what we considered a "hole". When adding new cells, this could be updated by directly checking whether this cells forms a 2 by 2 square.

After updating each counter, I checked whether (# of edges) - (# of vertices) + 2 - (# of 2 by 2 squares) is equal to one (region outside the component is also considered a face). If not, then there must be a hole in it.

We can see that when we got more trees, each individual tree are smaller, and their "distance => (count, sum)" array have many empty cells.

So I decided to "compress" them, that is to remove every empty cell. I put those non-empty cells into vector, so I can enumerate through each non-empty cells without taking time walking thorough empty cells.

Surprisingly, this approach indeed reduced time complexity down to .

Let T be a positive number, using as a "threshold" size, we'll decide it's actual value later. Then we split those threes into two groups, one group with tree size less than T, and the other one with tree size grater than or equal to T.

Total complexity for the first group (smaller size) is O(T^2NY), as each tree has at most O(T²) non-empty cell; Total complexity for the second group (larger size) is , as there could be at most trees with size not smaller than T.

So the Total complexity is . Solving give us , which leads to total time complexity of

I'll first explain my O(NY²) solution, as it may be different from yours.

First, for each tree, I calculated number of paths in this tree that has distance d, for 0 ≤ d ≤ Y. for those paths with distance grater than Y are counted as d = Y. I also sum up distance for all paths with distance not less than Y.

This problem is asking for both picking routes in each tree and the order of them, but we need only the former part, as the later part can be done with a little bit math.

Let dp_i, j = (count, sum) as number of ways to get total distance j (or Y, if the sum is grater than Y) from the first i trees, and the sum of distances.

To update the answer, I just enumerate each distance for the next tree, and update the appropriate values.

The dp array has complexity O(NY), and each update takes O(Y) time. So this approach took O(NY²) time in total.

I'll explain the optimization and the proves in the next comment, as I'm typing too slow...

I proved it earlier, and got the same complexity.

Edit: Oh, I think my complexity is a little bit worse than yours.

Do you mean p2 of Platinum division? I also got a NY^2 solution, but with some optimization, the complexity can be reduced a little bit, so it can fit into the time limit.

If you want, I can try to elaborate my solution.

Not completely sure, but I remember seeing the author saying that they turn all RE into WA.

You should do MultiX(x) again, cause you shouldn't change the state of given input.

I think not. He's not re-declaring the variable, but re-using it.

Or even something like this:

for(int i = 0;i < n;i++){
    for(int j = 0;i < n;i++){
        // do something
    }
}

I actually implement a 8-bit Toffoli, with only CNOT gate and CCNOT gate, and using 4 extra qubits. It passed the test.

The official solution is definitely much easier, though.

Actually it's a little too late for Asian. It's hard to meet everyone's need. So it's better to enjoy those you can participate in and stop complaining about everything.

\10000 Registration!/

It seems the problem have been fixed. Thanks for your help and the wonderful platform.

If you can do it off-line, then you can first re-assign 1 — 10⁵ to all x while preserving their relative order (e.g. {3, 2, 5, 2} => {2, 1, 3, 2}). After that you can use data structure like Binary Index Tree to maintain the prefix sum of count of each number, then each insert query can be done in O(logN). Queries are equivalent to finding the first prefix sum of count greater than or equal to k, this can also be done in O(logN) on the Binary Index Tree. (I think this blog by someone else may help you.)

If you must do it on-line, then you need to use something like Treap to dynamically maintain both the order and prefix-sum of count.

Sorry for my poor english :)

0123 is clearly not a valid answer. As in the problem description No number in input and/or output can start with the digit 0. And also the problem promises that It is guaranteed that answer exists., so 1230 123 is definitely not a valid input.

Chung-Yao Cheng from Taiwan has codeforces handle mark31408a , thanks.