The Nordic Collegiate Programming Contest (NCPC) 2017 will be held tomorrow. It is the subregional ICPC contest for Denmark, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 7 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

How to solve problem D ?

Graph of masks and bfs from each mask from input. Graph contains the edge if two masks are different only on one bit. The answer is a vertex with the biggest distance.

We solve 7 problems and didn't solve this problem , omg..!!!

Ty!

What is the name of your team?

LeXaHam

How to solve C?

zscoder your team is "Soromonogatari" ?

Yes

Do you solve problem F?))

Yes (actually my 8th submission is already AC and I submitted the cleaned version after that because I thought it won't count though apparently the scoreboard says 0+9 instead of 0+8)

Can you explain solution ?

Let

f(u,v,k) denote the distance of node u and v inF_{ k}. From now on, we assumeu≤vfor convenience.Let

Ldenote the number of leaves ofF_{0}.If

L= 1, the answer is justv-usince the tree is a path. Thus, we assumeL> 1.Note that the size of

F_{ k}is .Note that the tree

F_{ k}can be constructed by replacing each leaf ofF_{0}with a copy ofF_{ k - 1}. (note that this is slightly different from the original defintion but you can prove that they're equivalent)Thus, each node in the original tree corresponds to a range of nodes in

F_{ k}. Specifically, each non-leaf node in the original tree will correspond to one node in the final tree and each leaf node will correspond toS(F_{ k - 1}) nodes in the final tree, whereS(F_{ k - 1}) is the size ofF_{ k - 1}, which can be computed with the formula above.The main idea to calculate

f(u,v,k) is to first check which node inF_{0}containsuandvthen try to recurse downwards.Now, if

k= 0 we can compute the answer directly from the original tree (note that you need to precompute heights and LCA to answer this in ).Let's first consider the naive solution.

Iterate through the nodes of

F_{0}one by one in depth-first manner to determine which nodeuandvcorresponds to. Letu' andv' be these nodes. Then, there are a few cases :If

uandvcorresponds to non-leaf nodes, returndist(u,v) and we're done.If

ucorresponds to a leaf node andvdoesn't, then returndist(u',v') +f(0,u-S,k- 1), whereSdenotes the number of nodes inF_{ k}encountered before we reach the node containingu. Similarly, we can do a similar recursion ifvcorresponds to a leaf andudoesn't.If

uandvboth corresponds to leaf node, then ifu' =v', returnf(u-S_{ u},v-S_{ v},k- 1) (S_{ u}is number of nodes inF_{ k}encountered before reachinguandS_{ v}is similar) and ifu' ≠v', returndist(u',v') +f(0,u-S_{ u},k- 1) +f(0,v-S_{ v},k- 1).This solution should work in

O(kn) time (we omit the time required to calculate size ofF_{ k}for simplicity), which is clearly too slow.The first optimization that can be made is to speed up the process of finding

u',v' andS_{ u},S_{ v}. Let's do a dfs on the tree and for each nodeu, store a pair (x,c), wherexis the number of nodes encountered till now andcis the number of leaves encountered till now. Then, the total number of nodes inF_{ k}encountered up touisx+c·(S(F_{ k - 1}) - 1).With this, we can do a binary search and determine which nodes

uandvcorrespond to inF_{0}in time. However, the complexity is still , which is unacceptable.The next optimization is to note that if

kis large, for example whenk> 32, the value ofS(F_{ k}) will definitely exceed 2^{30}. Thus, a lot of calculations can be omitted. Indeed, when we reach the case whereu' =v', and letSdenote the number of nodes inF_{0}encountered beforeu', then we'll keep calling the functionsf(u,v,k),f(u-S,v-S,k- 1),f(u- 2S,v- 2S,k- 2), ... untilk≤ 32 or one of the arguments become less thanS. We can calculate exactly when this happen with some math and from there we can switch to the casef(0,v,k).For

f(0,v,k), the process is similar, except the answer will be increased byH, the height ofv' inF_{0}each time you recurse down, so you need to add a multiple of height ofv' to the answer.Thus, each query can be answered in time, and the total complexity is .

Thank you!!

Keep track of the cards' uniqueness for each colour individually.

For any one colour, first sort the cards by their angles and then put them in a linked list. You can quickly work out the card's score contribution for this colour as either

`uq(x) = dist(x.prev,x) + dist(x,x.next)`

, or just 0 if it has a neighbour with the same angle.Every time you remove a card, the only scores that might change are the scores of its neighbours in the linked list, so recalculate both of them every time you delete something.

To get the overall least-unique card, keep a global set<pair<Value, ID>> and make sure to update it every time you change the score for a particular colour. You can repeatedly pop the smallest element off that set, update the small number of affected nodes, and repeat until there's nothing left.

Right, for some reason I somehow thought this wouldn't work but now I feel dumb. :P Thanks.

I use the

`priority_queue`

instead of`set`

, because I worry that`set.find()`

can't find the exact element.when will the scoreboard be unfreeze?

anybody knows how to fix WA 12 (Problem H)?

Our solution: for each citizen find left & right train by sorting citizens & trains as events by polar angle, then for each citizen we are determine closest train (if it only one, we connect them immediately, otherwise we assign citizen to the sector between two trains). After that step only citizens between two trains left and we are find sector with smallest amount of citizens (it needs to achieve O(N) and fits to TL) and just try every possible assignment to the left train in this sector — at the other sectors we can make greedy assignment. I can't break this solution.

The idea of your solution is correct, so most likely you have a bug in the implementation. The test data used in the contest will be published.

Thanks, please let me know, when test data will be published

When and where will be the test data of contest will be published?

It is now available here.

Most likely you failed in determining "closest train". I used eps = 1e-9 and failed, while eps = 1e-13 plus long double gave AC.

Hmm, I thought about it, but I can't imagine test since coordinates only up to 1000 (I supposed that worst case for this is two rays (minX, maxY) and (maxX, minY) and test point (maxX, maxY — 1)).

I don't know the tests, but my line of thinking was :

After contest EndTime told me that 1e-12 gives WA, so probably there is a test about that

Thank you! I got AC with 1e-13 eps, very surprising!

How to solve problem K? I don't know how to check feasibility after binary searching over the answer.

The official solutions can be found here.

Thanks! But I still can't understand the way in the solution and I tried many times but always WA.

just do a greedy? basically for each kayak, find the smallest pair that fulfill the required speed?

Thank U!!! I got it