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

mathusalen's blog

By mathusalen, history, 8 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mathusalen (previous revision, new revision, compare).

»
8 months ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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/icpclive
Twitch — https://www.twitch.tv/icpclive

»
8 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

I've heard that Errichto will be one of the commentators :P

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Where to submit solutions after the contest ??

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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   Vote: I like it +43 Vote: I do not like it

    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, # |
  Vote: I like it +16 Vote: I do not like it

Will you upload it to the gym?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mathusalen (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve K?