niyaznigmatul's blog

ACM ICPC 2016−2017, Northeastern European Regional Contest
By niyaznigmatul, 8 years ago, translation, In English

Hello, Codeforces.

This weekend ITMO University in St. Petersburg with Barnaul, Almaty and Tbilisi will host ACM ICPC Northeastern European Regional Contest. text

We have 266 teams (thanks to MikeMirzayanov and snarknews for the link) competing for the chance to go to the ACM ICPC World Finals 2017 which is going to take place in South Dakota, USA.

In ITMO University site 106 teams will compete, including ACM ICPC 2016 World Champions and the team that is leading Opencup ranklist.

We have an Instagram account, we will post there some pictures from contest halls and other weekend activities.

If you are not competing in NEERC, you can try to solve the same problems in mirror. It will take place at 8 AM UTC, December, 4.

Contest scoreboard.

Some NEERC teams with their Codeforces ratings
Team name Team member 1 Team member 2 Team member 3 Total rating
SPbSU Base aid (2765) ershov.stanislav (2739) -XraY- (2551) 8055
MIPT Jinotega zemen (2741) ifsmirnov (2721) Arterm (2506) 7968
ITMO University 1 izban (2762) enot110 (2550) Belonogov (2545) 7857
Perm SU Indigenous I_love_Tanya_Romanova (2650) mmaxio (2576) KuchumovIlya (2411) 7637
Saratov SU 1 HellKitsune (2537) danilka.pro (2485) IlyaLos (2349) 7371
ITMO University 2 budalnik (2450) YakutovDmitriy (2422) SpyCheese (2413) 7285
Belarusian SUIR netman (2571) andrew.volchek (2318) teleport (2247) 7136
SPbSU 3 Kaban-5 (2474) pavel.savchenkov (2431) tunyash (2226) 7131
Ural FU Charmander Tinsane (2438) kb. (2363) KungA (2262) 7063

Good luck to all participants
NEERCNews

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

Comments Comments (39)
| Write comment?
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

http://codeforces.me/blog/entry/16986 looks more accurate than simple sum.

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

    HSE #1 will benefit from such scheme — they have Um_nik :)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    1. HSE#1 2999.5121561847
    2. SpbSU Base 2937.9237191871
    3. Jinotega 2913.1504943568
    4. Latvia U 1 2909.5113778587
    5. ITMO 1 2877.7099709162
    6. PermSU 2800.9196640221
    7. Saratov SU 2704.5859363758
    8. ITMO 2 2662.9688777241
    9. B SUIR 2658.7313493079
    10. SpbSU 3 2635.0951672458
    11. UralFU Ch. 2599.9579123698

    Link (IDEOne)

    P.S. it's not a generated code,so there may be errors

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

First place in standings (Eurasian National University named L.N. Gumilev 3 (Abdilmanov, Zhaksylyk, Zhussupov)) did 3 problems in just 38 seconds? OMG I can't believe that

UDP: Standings of ACM ICPC 2016-2017, Northeastern European Regional Contest, Practice Session

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

    Many teams voluntarily do weird things during Practice Sessions. ;)

    Update : oh, wait, it's 38 seconds since the beginning. That's really weird, then. :P

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

      Access to the problems and computers were given 10-15mins before starting practice session. So, they had all the problems solved before starting practice session and they just sended all problems in 38 seconds.

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

can the problems be got in English version? https://contest.yandex.ru/neerc2016/contest/

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

This is a twitch channel where you can observe how two violets write mirror contest.

So poor result but so close...

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

Where is Moscow SU: Chihuahua? I cant find them

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

    Teams displayed under

    "Могли бы выиграть NEERC, но не приехали"

    are not contestants.

    "Могли бы выиграть NEERC, но не приехали" == "were able to win contest, but not arrive"

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

      there is no such information in english version of the site

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

        But I try to describe "able to win contest" means "able if participate", because their CF ratings shows their skill level. But there are no these teams in the contest.

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

And how many of them will get in next tour ???

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

Will there be mirror contest later in the gym?

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

I want to participate at mirror version, but Yandex keeps redirecting me to login page... can anyone share the problem statement?

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

when will the standings be melt?

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

How to solve B and I?

I knew Problem D because it was first proposed by tourist for a SRM, but we decided not to use it because it fits better in longer contests. It is surprising that jcvb and jqdai0815 solved it in the mirror contest — congratulations!

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

    I solved it using simplex directly.

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

      1000 variables and 1000 equations? Maybe you have something that works fast for sparse matrix?

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

        https://en.wikipedia.org/wiki/Revised_simplex_method

        The Revised simplex method is easy to implement (as a template) and works fast for a sparse matrix. A large number of "flow" problems and other linear optimization problems can be solved this way, without complex reductions, or clever thinking.

        Using LU decomposition on sparse matrix, my code is 260 lines, but probably can be trimmed down to <200. Might be a pain to type this in during a contest though.

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

      Is it obvious that it will return an integer solution? It seems easy to prove, but I haven't found one-line argument.

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

    Insert every string (2 possibilities) into a trie. Then do 2-sat. Use an extra node for each node to indicate the OR of its subtree.

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

    How to solve D? I think the optimal value can be computed by duality (into famous min-cost flow model). But this does not lead to the construction of the solution explicitly.

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

      First ignore the constraints for me. The key observation in this case is that the set of sleeps can be divided into ms chains, and each adjacent pair in a chain has the difference of k or more. It will lead to a mincostflow solution.

      Then, if we change the capacity of some edges, it magically corresponds to the constraints of me.

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

        Can you elaborate the statement "The key observation in this case is that the set of sleeps can be divided into ms chains" ?

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

    Here is my solution of pI.

    We implement DFS on the graph (like Tarjan algorithm). If one vertex is in the stack, we mark "R" on it (place the stone on the right of passage). If this one is unvisited, we mark "C" on it. Otherwise, we mark "L" on it.

    For every "L" vertex, we link it to the vertex with the smallest lowlink it can directly reached. So if we visits an "L" vertex, we can always jump back to the vertex in stack through these edges.

    The part remained is not hard.

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

How can we enter the mirror?

Tried to use Facebook, Twitter and G+ login but it doesn't work. Tried to register on Yandex but always fail the captcha (maybe due to Russian letters?)

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

How to solve problem J?

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

Final result: http://neerc.snarknews.info/index.cgi?data=2016/neerc/running&menu=index&head=index&qf=neerc&class=neerc2016&year=2016

So, 17 qualified, in GTF I guessed 15 and the intersection was 14, I think my guess was quite good.

By the way, is there any simple solution for E? My solution was: when a person p arrives at time t1 and waits for a unicycle u that arrives at time t2 (t1 < t2), let's say p contributes to the sum by  - t1 and u contributes to the sum by t2. Then, the contribution by a group of people or unicycles will be a function of b, and this function is a polyline with at most two "bends". Now we can compute the sum of these polylines. But the implementation becomes messy and I feel I did something overcomplicated.

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

    Consider every segment of time. If there are x unicycles required without initial unicycles, and there are q unicycles at the start of the day, it contributes max(x - q, 0) * t to answer.

    So we can sort all the segments by their x value.

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

    Online Mirror Results!

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

Yerevan SU1: first and only to solve D. Go ahead guys!

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

I think this is an inspirational story about passion and determination:

I went to the same high school with aid. He started coding only four years ago. It is particularly admirable since I have been doing this for many more years (about 7 years) and was in fact at one point better than aid. But his passion and determination proved to be fruitful: aid is a terrific coder and has joined the arguably strongest team in the world right now.

I wish him and his team all the best.

→ Reply