The Nordic Collegiate Programming Contest (NCPC) 2018 will be held tomorrow. It is the subregional ICPC contest for Denmark, Estonia, 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 6 UTC 9:00, and its duration is five hours.
Welcome! You can also discuss the problems here after the contest.
I did A for most of the contest and never realized that the sum of weights is at most 1e8 :/
I also asked my friends from other teams, and they hadn't noticed it either. Would have been nice if the problem statement didn't hide it like that (usually it's okay to just quickly look at the constraints)
FUCK
This problem (from 2017 Vietnam National Round) put the trick of hiding constrant to increase difficulty to a brand new level. It is as easy as Div2-B once you understand the statement properly, and yet not even a single team solved that problem in the contest.
How to solve F and G?
We had a solution for F which didn't pass: Choose a pair of corners and consider a line passing through them. Then for rectangles intersecting with the line, do some 2 pointers to check maximum number of rectangles within distance l.
G: click
It is possible that the optimal line segment only passes through one corner.
Btw, I also don't know the solution of F.
How to solve K? I thought of a DP on tree solution but it is O(NK^2)
The amount of ways to colour the tree with at most z colours is z * (z - 1)(n - 1). This could also be calculated with a O(N) dp. Then you can just use inclusion-exclusion to calculate the answer, giving time complexity O(Klog(n)) or O(KN) with the dp.
How to solve problem J ?
I have come up with some observations:
(1): We can easily calculate the number of 0s x and the number of 1s y from a and d.
(2): It is possible to construct a string if and only if x*y = b+c.
(3): When we swap 01 to 10, the number of 01 decreases by 1 and the number of 10 increase by 1.
I am not really sure if (2) or (3) is correct.
My algorithm is to start with a string that starts with x 0s and ends with y 1s, and then move the 0 until we get the desired b and c, but it did not pass the third test :(.
UPD: I got Accepted. Some corner cases that you need to consider:
When a=0, the number of 0 can be 0 or 1.
The result need to be non-empty.
The editorial is published.
Now in Gym.
Can somebody give me a hint on D? I have read the editorial.
To check if delay D possible, let $$${L_D(i)}$$$ be latest possible start time for delivering orders $$${i,i+1, . . . ,k}$$$ with max delay $$${D}$$$
Compute $$${L_D(i)}$$$: guess how many orders $$${j}$$$ to bring together with $$${i}$$$, simulate delivering them, then use value of $$${L_D(i+j)}$$$
My question is: how should I guess $$${j}$$$?
Thanks!
Try all possible j?
I just don't understand how should I check all possible j in $$${O(1)}$$$ time
Why O(1)? The constraints are low.
You just iterate over all possible values and take the best one. This will give a time of $$$k^2$$$ for that part, as suggested by the colour coding.