The Northwestern Europe Regional Contest 2025 will take place on November 30 in Karlsruhe. It is an ICPC regional contest, i.e., the best teams will advance to the ICPC World Finals and the European Championship.
The mirror contest will be held on a DOMJudge instance at https://judge.cpulm.org/public.
- The mirror test session starts: November 29 10:45 CET
- The actual mirror contest starts: November 30 10:30 CET
I invite you to participate in the contest and I hope that you will like the problems.
On the difficulty
The contest features problems with difficulties varying from the easiest problems in Div2 to the hardest in Div1; so anyone can find something at their level.
Many teams with little experience participate in NWERC, so the problem set should be enjoyable also for div2 contestants. On the other hand, solving all the problems should be challenging even for strong teams.
Rules
- The scoring is ICPC-style: teams are first sorted by number of problems solved, then the time-penalty is used as a tie-break. An incorrect submission gives a 20 minutes penalty.
- We encourage participation as a team.
- If you are participating in a team, we encourage you to use only one computer for coding the solutions (as in an ICPC contest). Regarding using templates, googling, and copy-pasting code: feel free to do it.
Streams
You can also watch streams of the onsite contest at these links:
- 2025 ICPC NWERC Awards Ceremony
- 2025 ICPC Northwestern Europe Regional Contest (NWERC)
- 2025 ICPC NWERC Test Session + Team Interviews
- 2025 ICPC NWERC Opening Ceremony
Edit:
Hopefully you liked the problemset! See you next year. The testdata and jury solutions will be uploaded soon™.
Auto comment: topic has been updated by jeroenodb (previous revision, new revision, compare).
Hi, will the contest be added to the gym or uploaded to any online judge?
It is now available on QOJ: https://qoj.ac/contest/2694 And it will be available on Kattis, some time into the future.
All the contest materials you can find at: https://chipcie.wisv.ch/archive/nwerc/, and now also on the official website https://2025.nwerc.eu/
In problem i:
How do you prove that if there are more than $$$2n$$$ intersections, then there exists a rectangle?
Originally I made a proof for a bound of $$$3n$$$ intersections. Later LuCpp came up with a proof for $$$2n$$$. I like this proof better so I will explain it.
The proof is algorithmic, and we will be looking at a sweepline procedure which tries to find all the intersections.
Let's call the number of horizontal segments $$$H$$$ and number of vertical segments $$$V$$$.
In such a sweepline from left to right we have $$$2H$$$ events of adding / removing a horizontal segment. and $$$V$$$ events where we need to find the intersections with a vertical segment and all currently active segments.
One important quantity is the number of pairs of horizontal segments which are ever neighbouring in the set of active segments. We can bound this quantity by $$$2H + H$$$, because each add event makes at most $$$2$$$ new segment pairs neighbouring, and each delete event at most $$$1$$$.
For each vertical segment, if it intersects $$$k$$$ horizontal segments, it "claims" at least $$$k-1$$$ neighbouring horizontal segment pairs. Here claim means: it intersects both segments of this neighbouring pair. If any two vertical segments claim the same horizontal segment pair, this would result in a rectangle. So $$$\text{intersections} \leq V + 3H$$$ if there is no rectangle.
We know $$$V+H = n$$$, and in this argument we can also switch around $$$V$$$ and $$$H$$$ by transposing the coordinate system. So