Hello, Codeforces.

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

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.

Some NEERC teams with their Codeforces ratingsTeam 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 | Nebuchadnezzar (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

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

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

Link (IDEOne)

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

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

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

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.

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

Problems from NEERC always are only in English.

http://neerc.ifmo.ru/information/problems.pdf

thanks! I joined the contest! hard but very interesting to me.

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

So poor result but so close...

Where is Moscow SU: Chihuahua? I cant find them

Teams displayed under

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

are not contestants.

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

there is no such information in english version of the site

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.

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

Will there be mirror contest later in the gym?

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

http://neerc.ifmo.ru/information/problems.pdf

when will the standings be melt?

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 Retired_MiFaFaOvO solved it in the mirror contest — congratulations!

I solved it using simplex directly.

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

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.

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

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.

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.

First ignore the constraints for

m_{e}. The key observation in this case is that the set of sleeps can be divided intom_{s}chains, and each adjacent pair in a chain has the difference ofkor more. It will lead to a mincostflow solution.Then, if we change the capacity of some edges, it magically corresponds to the constraints of

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

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.

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?)

did you try https://contest.yandex.com/neerc2016/contest/3529/enter/ ?

Yes, I was talking about that page. The login is working today, but yesterday it didn't — after login it would request login again.

How to solve problem J?

Isn't it pure implementation?

rng_58 ala gijdillax, ushax bilse sorushmazdida.

Duz deyirsan qardawim!!! Bunlarin gotu qalxir bir iki masala iwlayandan sonra

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

parrives at timet_{1}and waits for a unicycleuthat arrives at timet_{2}(t_{1}<t_{2}), let's saypcontributes to the sum by -t_{1}anducontributes to the sum byt_{2}. Then, the contribution by a group of people or unicycles will be a function ofb, 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.Consider every segment of time. If there are

xunicycles required without initial unicycles, and there arequnicycles at the start of the day, it contributesmax(x-q, 0) *tto answer.So we can sort all the segments by their

xvalue.Online Mirror Results!

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

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.