antontrygubO_o's blog

SEERC 2021 and Grand Prix of Southeastern Europe
By antontrygubO_o, 2 years ago, In English

ICPC Logo

Hi everyone!

2021 Southeastern Europe Regional Contest took place on November 21. Here you can view the full standings.

Congratulations to the winners of the contest!

Place Team Name Contestant 1 Contestant 2 Contestant 3 Problems Penalty
1 [Taras Shevchenko National University of Kyiv] KNU_0_GB_RAM KostasKostil VladProg kostia244 13 1788
2 [Kharkiv National University of Radio Electronics] KhNURE_Energy is not over BigBag Barichek Mustang98 12 1274
3 [Lviv National University] LNU Bulldogs mshcherba Vasyl_Protsiv PetroTarnavskyi 11 1429
4 [Faculty of Computer Science, Belgrade] GII Klub milisav Pajaraja MladenP 11 1433
5 [V.N. Karazin Kharkiv National University] KhNU_OtVinta kilt_01 Stroustrup 13022001 11 1444
6 [University of Bucharest] Unibuc Scrambled Eggs Rpd-Strike theodor.moroianu livlivi 11 1527
7 [Taras Shevchenko National University of Kyiv] KNU_Duplee Sonechko danya.smelskiy stanislav.bezkorovainyi 11 1608
8 [University of Bucharest] EchipaDulce Usu Stelutzu alexandra_udristoiu 10 1350
9 [Kharkiv National University of Radio Electronics] KhNURE_Lacrimosa kupriyanov dendi239 viskonsin 9 1068
10 [Babes-Bolyai University] UBB_Zalau00 Bodo georgerapeanu AlexPop28 9 1183

There will be a Grand Prix of Southeastern Europe based on these problems this Sunday, November 28, 08:00 UTC. Here is the link to the OpenCup.

This year, the sets of SEERC and OpenCup are a bit different: OpenCup won't include a few easier problems from SEERC and will additionally include several harder problems. In addition, problems are shuffled, so don't follow the standings of the official contest too much.

The authors of the OpenCup set are eudanip, Um_nik, bicsi, RomaWhite, Andrei1998, and me, antontrygubO_o. After the contest, the editorials to both versions of the contest will be published, and both versions of the contest will be uploaded to the gym.

We hope that you will enjoy the contest!

UPD:

Editorials:

Both contests are uploaded to Gym:

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

»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

kostia244 orz

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +52 Vote: I do not like it

This region became really strong in the last few years (just look at the last WF). What's the chance of them inviting >= 4 teams?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess quotes for a regions will be decided after WF considering performance of all the teams from the region.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess this is the blog for discussing the opencup round.

Is C intended to require fast modular multiplication? We TLEd without and passed with Montgomery multiplication.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    We didn't use any fancy multiplication and passed in 1.6 s.

    Is it possible that you have a slower solution in general? I remember I had to be just slightly clever about the brute force.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    We didn't use any fancy multiplication and passed in 0.6 s.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is pretty different from what we did, but I do see why it's fast.

      We looped $$$r$$$ from $$$1$$$ to $$$18$$$, and maintained a dp array, where $$$DP[v][s]$$$ is the number of ways to have sum $$$s$$$ and product $$$v$$$ with $$$r$$$ numbers greater than $$$1$$$.

      Since not all $$$n^2$$$ states fit in ML we just had $$$DP[v]$$$ be a vector of pairs $$$\{s, c\}$$$ where sum of $$$c_i$$$ over pairs $$$\{s, c_i\}$$$ in $$$DP[v]$$$ is $$$DP[v][s]$$$.

      Changing to Montgomery multiplication gave a speedup from around 2.3s to 1.33s so the overhead from messing around with vectors of pairs shouldn't be that big.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    We also TLEd initially, but passed in about 1.8 seconds by not multiplying by factorials and inverse factorials when they're factorials/inverse factorials of 1.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain in a bit more detail why the DP for specific color in H is O(n*cnt_of_this_color) ?

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I: After reducing to the cycle packing problem (as in the editorial), I guessed that the maximum number of cycles we can take is equal to the minimum size of a feedback arc set (so I just tried $$$k!$$$ permutations). This is clearly an upper bound, and I think this is not exactly correct in general. I wonder if this works for $$$k \le 5$$$.

The supporter of this guess is the answers to https://math.stackexchange.com/questions/1608237/maximum-number-of-edge-disjoint-cycles-vs-minimum-number-of-edges-in-a-cut

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I find it quite amusing that Counting Phenomenal Arrays got only 8 AC during SEERC and the first one was at 2:41 xD

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hello, when will the tests of SEERC be published? The official site http://acm.ro hasn't been updated yet. Thanks!

→ Reply