NWERC 2020 was finally held this last weekend after a few month delay due to the pandemic. The format was a little different this time around, with each contestant participating from home (i.e. three computers per team) and having full read access to the internet during the contest.
We wanted to let you know that this Saturday at 12:00 GMT we will be hosting an open version of the contest on Kattis: https://open.kattis.com/contests/nwerc2020open
The problemset, solution slides, testdata and judges' solutions are already available on our website, but we ask that you please refrain from looking at them until the open contest is over. Good luck, and we hope you enjoy the problems!
This coincides with the div 1 codeforces round :(
That's unfortunate :( I don't think we can change the time now, sadly.
We had a solution to B that is very different from the jury's solution.
We define the function $$$f(i, d)$$$, which is given by
The answer is given by $$$f(0, \infty)$$$, and $$$f(n, d) = 0$$$ for all $$$d$$$.
Now, if $$$a[i] = 0$$$, then $$$f(i, d) = f(i+1, d+1)$$$.
Otherwise,
Then, $$$f(i, d) = f(i+1, d - (a[i] - 1)) + (a[i] - 1)$$$ + $$$a(i, d)$$$, where $$$a(i, d) = 0$$$ if $$$d \in [j_2 + (a[i] - 1), j_1 + (a[i] - 1) - 1]$$$, and $$$1$$$ otherwise.
These updates can be made in $$$\mathcal{O}(\log n)$$$, though our implementation was $$$\mathcal{O}(\log^2 n)$$$. Thus, total complexity is $$$\mathcal{O}(n \log n)$$$.
The problems are available for upsolving on Kattis, but by popular demand we have also uploaded the contest to the Codeforces gym.
In problem I, my teammate AsunderSquall used a weird algorithm and magically got accepted.
There is a simple $$$O(n^4)$$$ brute force method and it's too slow. But we add this line :
It means if we can't find a vaild solution in TL, the program just gives up. Then we passed the test.
After the (VP)contest we guessed that if the solution exists, we can just make the first person start at $$$1$$$.
Can anyone proof this, or figure out it is fake and passed just because of weak test?