Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

mathusalen's blog

By mathusalen, history, 8 months ago,

The 2019/20 SWERC (Southwestern European ICPC regional contest) takes place tomorrow January 26 at 9:15am CET in Paris. You should see the scoreboard here once the contest starts.

There will be an online mirror here and life streaming here

UPD: I have prepared a GYM based on the contest and it is available here. Many thanks to ko_osaga and the team Ruber Duck Forces (Infoshoc, nagibator and EvgeniyZh) for providing solutions to the problems.

• +150

 » 8 months ago, # |   0 Auto comment: topic has been updated by mathusalen (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 2 →   +40 Oh, I made a blog without seeing this one. I'm removing mine then.I'm in Paris as a commentator today. Tune in for ICPC Live broadcast:Youtube — https://www.youtube.com/icpcliveTwitch — https://www.twitch.tv/icpclive
 » 8 months ago, # | ← Rev. 2 →   +21 I've heard that Errichto will be one of the commentators :P
 » 8 months ago, # |   +3 Where to submit solutions after the contest ??
 » 8 months ago, # |   +8 In problem E, I still don't understand how to do the Gaussian Elimination in $O(\min(L, K)KL)$. Can anyone explain this in more detail?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +43 That's what I would do:Assume $H \geq W$ (the board is taller than wider). The input consists of bits $a_{i, j}$ ($1 \le i\le H$, $1 \le j \le W$) putting constraints on the final values in each cell.Let $x_{i,j}$ be the boolean variable describing whether you tapped on the cell in $i$-th row and $j$-th column ($1 \le i \le H$, $1 \le j \le W$). We can now describe all $x_{\star, \star}$ as a linear combination of all $x_{1, \star}$ and a constant $1$. When describing $x_{i, j}$, we want to ensure that the final value $a_{i-1, j}$ is correct; that is, $x_{i, j} = a_{i-1,j} + x_{i-1,j} + x_{i-1,j-1} + x_{i-1,j+1} + x_{i-2,j}$. This allows us to describe all $x_{i,j}$'s in $O(HW^2)$ or $O\left(\frac{HW^2}{64}\right)$ time.For instance, $x_{2,1} = x_{1,1} + x_{1,2} + a_{1,1}$, $x_{2,2} = x_{1,1} + x_{1,2} + x_{1,3} + a_{1,2}$, and then $x_{3,1} = x_{2,1} + x_{2,2} + x_{1,1} + a_{2,1} = \\ (x_{1,1} + x_{1,2} + a_{1,1}) + (x_{1,1} + x_{1,2} + x_{1,3} + a_{1,2}) + x_{1,1} + a_{2,1} = \\ x_{1,1} + x_{1,3} + (a_{1,1} + a_{1,2} + a_{2,1}).$Now notice that we only need to ensure the correctness of the bits in the final row (all previous rows were taken care of when assigning $x_{\star, \star}$). This is equivalent to solving a system of $W$ linear equations (each describing a cell in the final row) with $W$ variables (each describing a cell in the first row), which takes $O(W^3)$ or $O\left(\frac{W^3}{64}\right)$ time. After solving the system, it's straightforward to restore the correct values of all remaining variables $x_{i, j}$, $i \ge 2$.
 » 8 months ago, # |   +16 Will you upload it to the gym?
•  » » 8 months ago, # ^ |   +20 I am working on it, but I need to solve all the problems first to have a model solution. I am not involved in the organization at all, but they have provided on their web page the tests so it should be feasible.
•  » » » 8 months ago, # ^ |   +43
•  » » » » 8 months ago, # ^ |   +10 Many thanks
•  » » » » 7 months ago, # ^ |   +5 404 not find，Can you post it again？
 » 8 months ago, # |   0 Auto comment: topic has been updated by mathusalen (previous revision, new revision, compare).
 » 8 months ago, # |   0 How to solve K?