Do you use AdGuard? I disabled it and the same problem was fixed.

What is exact contest duration? 15 days (like in contests system) or 2 weeks (like in blog)?
One year ago contest duration was increased for 1 day in the last day. It was unexpected and a little bit unfair.

Update: D is 1805 points now.
Nothing interesting. A lot of random swaps in 10 threads for ~30 minutes

A: 2
B: 5
C: 5
D: 1804
E: 2083
Total: 3899

The contest duration has been extended to 5 days. The actual finish time is October 14, 2021, 00:00 UTC**

What?! I planned my time with a duration of 4 days. It's not fair!

Is it true that 3 hours contest and 4 days contest are same task and some contestants can cheating?

Has anyone received prizes?

Main points:
1) Use brute-force for small regions (I did it for <= 18 elements).
2) Otherwise use greedy-algorithm for regions with less than 150 vertices (very important for final score):
- Firstly add all possible vertices in region.
- Remove or add vertex which change balance (shortest/longest) better than other variants. Do it while balance < 0.9 (including decreasing of balance too).
- Add vertex which change balance better than other. Do it while balance stayed >= 0.9. For that greedy-algorithm we must check possible balance for changing all vertices on each iteration.
- After that algorithm we can add some vertices by random swapping.
3) Use another more simple greedy-algorithm based on weights for regions more than 150 vertices. I have some problems with rational description for that part. When I tried to improve algorithm I got worst result (about 100-150 points). May be solution with local maximum for big regions degrade final solution.
4) We must make regions in the some order. On each step try to make region from maximum possible vertices (without looking to weights/balance).
5) Don't see on first x elements from step 4. I chose x=7 and jumped from ~9550 to ~9050 points after that improvement. I think that very big regions can degrade answer for a lot of small regions. Firstly I tried exclude only first biggest candidate and it gave me ~250 points. It was surprising.

Important hints:
- We must calculate shortest/longest paths very effective. I did it with O(N + M) with small constant , when N and M is number of vertices and edges in subgraph. Subgraph is vertices only in possible region (marked vertices with candidates).
- We can get some points with random and other magic constants. I think that value about 100-200 points.

Standings and list of finalists

Yes. 31st place.

Don't use std::rand :)

It isn't magic. It's small period of std::rand

Northern Eurasia — Northern (Arctic) Federal University: Svenny ijnhtrgdew Artichoke

Разве это запрещено правилами контеста?

>>>>.>.V
^.<.<<<<

Может быть

UPD: именно то, что написано ниже