Hi everyone!
A week ago, the 2nd edition of the Western European Olympiad in Informatics was held in London, UK, and now we've brought the problems for everyone to solve on Codeforces! The mirror contest will be held on the Codeforces Gym on Sunday $$$14^{\text{th}}$$$ July 2024 at 10am UTC+1 (check your timezone here!).
Please don't participate in the mirror contest if you have participated or seen the problems!
The Western European Olympiad in Informatics is an individual contest for top secondary school students from Belgium, France, Ireland, Italy, Luxembourg, Netherlands, Portugal, Spain, Switzerland and United Kingdom.
The contest consists of a single day; contestants are given 5 hours to solve 4 problems of various difficulty. Each problem is worth 100 points, distributed into multiple subtasks with different constraints that allow the participant to earn partial scores. For testing, the IOI grading format is used, where the participant receives full feedback about the execution of the solution on all tests during the contest. C++ is the only allowed language in this contest.
We hope you enjoy the contest!
- WEOI 2024 Committee & Contributors
FelixMP hugopm I_love_MikhailRubinchik ScarletS veluca93, Ahmadsm2005 Bakry erekle
So there is only one day of WEOI?
Yes. The competition lasted only 3 days.
Is it Rated contests or Not ??
Probably not
When I try to submit a code, it says you need to be registered for the contest? Where do I register? I cannot see any registration link. Thank you.
Go the Gym. It is the first contest in the list. Click register and then enter the contest.
how to unskill-issue
Thanks for a fun contest!
When will the editorial be released?
Thanks for the contest! I really enjoyed solving all the problems, especially A.
Some hints for solving the problems -
Try solving the 3rd subtask
iterate on each bit from the highest bit to the lowest bit and increase the lower number by that bit. Then compare the two numbers in the end, if they are equal we are done. If they are not, then increase the smaller number by 1 and we are done. The proof of why this works is left to the reader.
Code: 270446214
Try doing what we did above by using something similar to divide and conquer.
Let solve(l, r) make everything from [l, r] equal, then we can do something like -
Since everything from [l, mid] and [mid + 1, r] are the same, we can apply the subtask3 algorithm and make everything from l to r equal as well.
Note that this doesn't solve the problem. We need to optimise the number of add operations we use. This is left to the reader. Try grouping similar looking queries somehow.
Code: 270463943
Try solving subtask 4
..
..
..#
...
#..
..##
...#
#...
##..
Express the given number K as sum of powers of 2. Construct a solution for powers of 2 (previous subtask) and somehow find a way to add the number of ways up. This should solve the full problem.
Code: 270441721
The problem somehow seems to ask us to break the path between nodes
X
andY
into $$$O(log_{2}(N))$$$ segments, and somehow combine the answers using that.We need to first figure out how to break the given path into $$$O(log_2(N))$$$ segments. One way is to use binary lifting! We can break the path from
X
tolca(X, Y)
and the path fromY
tolca(X, Y)
into $$$O(log_2(N))$$$ segments each. We can pre-calculate some information for all such paths and somehow combine them to answer the query.What information do we store for the paths? Let the path we store information for be $$$X \rightarrow Y$$$ (yes, its going to be directed. The answer from $$$X \rightarrow Y$$$ is not necessarily the same as the answer from $$$Y \rightarrow X$$$)
Let us store a 2x2 matrix. Lets call it Mat.
Combining two Mat's together is left to the reader, and so is the basecase.
However we use these precalculated Mat's to answer the queries using binary lifting.
Code:270456248
Note that the problem statement basically asks us not to have $$$3$$$ or more chosen nodes on any path. For this we can arbitrarily root the tree at any node, and do dp.
Let $$$dp[x][i]$$$ be the number of possible sets such that the maximum number of chosen nodes on a path from $$$x$$$ to a node in its subtree is $$$i$$$, for $$$0 \leq i \leq 2$$$
The transitions are left to the reader. The final answer will be $$$dp[root][1] + dp[root][2]$$$
Code: 270445208
I wrote a quick unofficial editorial to the contest on my blog (https://blog.suneetmahajan.com/posts/weoi-2024-editorial/) with my solutions, there will be a more detailed editorial published later.
Could you make the codes public? I think it'd be helpful to view others' codes.
Unfortunately, in the Codeforces Gym for a public contest, it is only possible to view submissions for a problem once you have solved the problem :(
Hi! When will the official rankings be announced?
They have been announced already, and can be found here: https://weoi.org/results/2024/