Традиционно проект SnarkNews проводит голосование "Итоги года".
Цель голосования — отметить лидеров спортивного программирования прошедшего года — как участников, так и тренеров, а также наиболее удачные проекты и наиболее удачные публикации в прессе.
В настоящий момент проходит первый этап — выдвижение номинантов. Первый этап проходит до 23:00 30 декабря. Желающие опубликовать своё предложение по номинантам (и подискутировать по этому поводу) могут сделать это в комментариях к данному сообщению.
В этом году голосование проходит на базе системы Яндекс.Контест. Соответственно, предложить номинантов может любой, кто имеет логин в этой системе. При входе в систему описаны правила; для перехода к конкретным номинациям и выдвижению номинантов перейдите в раздел "Задачи"; справа появится список номинаций. По каждой номинации принимается не более двух вариантов; каждый вариант задаётся в отдельной строке в соответствии с правилами номинации (которые находятся на том же экране, что и форма отправки).
Ссылка на вход в систему для выдвижения номинантов.
Кроме того, Простой Новогодний Контест и Новогодний Блиц-Контест в этом году также пройдут на базе системы Яндекс.Контест; по сравнению с прошлым годом особых изменений в правилах не ожидается.
Открыта регистрация на оба контеста:
Простой Новогодний Контест — начнётся 30 декабря в 0:00, завершится 10 января в 23:50. Состоит из задач, предлагавшихся на различных командных соревнованиях по программированию, но так и не решённых в основное время.
Новогодний Блиц-Контест начнётся 31 декабря в 16:00, завершится 1 января в 8:00. Контест пройдёт по правилам Multiple Language Round (то есть за каждую задачу, успешно сданную на языке программирования, на котором участник ещё не сдал ни одной задачи, начисляется бонус -100 минут от штрафного времени) и по правилам Новогоднего Блиц-контеста (отличие от системы ACM в том, что время отсчитывается не от начала, а от 0:00 1 января по времени сервера, то есть и успешная сдача в 23:55, и успешная сдача в 0:05 дают штрафное время 5 минут).
А уже есть итоговые результаты конкурса прогнозов за 2015? Я их нигде не вижу...
По поводу агитации^W предложения кандидатов в комментариях к посту: на всякий случай упомяну здесь Petr'а (вдруг кто забыл): он выиграл Mailru и TCO, прервав серию побед tourist'а, а также ведёт замечательный блог про спортивное программирование, так что IMHO по совокупности факторов в номинации "Персона года" он должен победить.
Пока нет, они появляются примерно дня за два. Ну и переход на новый движок в середине сезона добавил определённых проблем.
IMHO, персона года и публикация года вне конкуренции.
Петрсона года
А почему нету номинации "Отстой года"?
P.S. Специально для участников NEERC в Барнауле.
А что там было такого?
"Давайте уберём это, сейчас сюда с камерами придут, вы же не хотите начать международный скандал" — по этой причине я не стану оглашать детали)
Зарегистрируйте фейковый аккаунт и расскажите)
Агитирую за некоторых номинантов:
"will start at 16:00 31.12.2015 and ends at 08:00 01.01.2016" — that is cruel...
Yes. I don't understand why to downvote your comment! It's stupid to do a contest in NEW YEAR!
Прогресс года jqdai0815
В прогрессе года предлагаю голосовать за команду ZNTU SetUp. 8-ое место на SEERC-2014 -> чемпионы SEERC-2015.
Чемпионство SEERC — это скорее "Везение года" =) По факту ж мы точно не самая сильная команда региона.
Проблемсет года — Codeforces Round 329 (Div. 2)
Задача года — 593C - Красивая функция
Контест года, серьезно? Баянистые D и E, которые придумываются за 5 минут, но сложны в реализации, и упоротая С, которую решили несколько человек на контесте.
Codeforces Round 329 (Div. 2) — контест года
593C - Красивая функция — задача года(даже tourist похвалил)
У вас с K_Y_M_bl_C в профиле город указан, палитесь.
А на блиц-контесте за бревна обычный штраф 20 минут?
Далеко не все доступные языки указаны в списке компиляторов
А где можно задавать вопросы по условиям задач блица? Я отправил вопрос во вкладке "Cообщения", но ничего в ответ не получил.
Bump?
10 programming languages. I did well.
Can people share their solutions or give hints on how to solve the problems of the MLR blitz?
I am particularly interested in the solutions of problems A, B, D, I, J, K
A: https://en.wikipedia.org/wiki/Eight_queens_puzzle
B: instead of making reflection continue moving in the flipped (horizontally or vertically, depends on contacting border) board. So the movement of the ball is a straight line. We should check if point ( ± xc + 2x1kx, ± yc + 2y1ky) lies on this line for some integers kx and ky.
I: if initial number is odd and removing last digit keeps it odd then Second player wins. Otherwise game continues until string is empty.
N can be up to 200. How is that wiki enough? Am I missing something?
UPD: There is a link to a related paper on that wiki page. I wrote this too early I guess.
There is section with Explicit solutions.
My solution uses the following order of columns in backtracking search and finds solution faster than 10ms:
I noticed the modification for N odd; for N even, I wrote a bruteforce that tries placing (in all possible ways, always placing the first one in the leftmost free column) two sequences of queens with distances (2, 1) + a center-symmetric complement and picks one that works. It's O(N3) or O(N4) with a good constant.
It seems I've understood wrong the problem I, can somebody answer how to solve the following problem?
"We have a string of N ≤ 104 decimal digits (0 — 9). If the number represented by the string is even we must choose one digit and remove it. Two players play and alternate turns. The loser is the one who can't make a move. Who is the winner?"
K: the next integer position to move to from (x, y) is (x ± 1, y + R) or (x, y + 1), so if you use coordinates x' = y - Rx, y' = y + Rx, then you can move from cabbage (a, b) to any cabbage (c ≥ a, d ≥ b) and the borders don't matter — can you solve this standard problem?
B: mirroring trick — imagine that the table is mirrored over its borders an infinite number of times, making a grid of mirrored rooms; if you know the parity of mirroring in x- and y- directions, you reach a condition of the form Ak + Bl = C for
D: just write a condition for touching, extract a quadratic equation for time when it happens, pick the right solution, sort out some cases with negative times etc.
I: write the winning/losing positions for small numbers of digits, think; it's very simple
Your explanation for D is actually the solution for C (the collision of two spheres), can you tell how you solved D (it is something like a modified cost edit distance)?
Oh ok. We know the cost of any common subsequence. since we know what should be added and removed; it's best to add/remove as many letters at once as possible. My algorithm is just a modification of LCS.
Я вот уже который раз к концу года забываю про всех номинантов. А в течение года никуда не записываю. Раз уж появилась такая система выдвижения с учётом последней посылки, то может пусть она целый год идёт как контест на следующий раз?
Firstly, I would like to bring this post into recent actions. Prime New Year contest is one of not many great opportunities to challenge oneself against really hard and entertaining problems. Judging from number of submissions, I think that it gets much lower attention than it deserves.
And on a second note, I have to admit that I was very amazed when I saw problem "Solar lamps" which I have authored :). Originally it was posed as problem on POI, but concluding from its presence here — it was passed to Russia and used on some ACM contest. I think that it's too easy for that contest, fact that I am the only one who has solved it so far surprises me even more :P (of course I had prewritten solution).
It was used at Spring Training camp in Urozero (something like "mini Petrozavodsk" in March for finalists from Northern Subregional of NEERC; last year it had mirror in MIPT), problemset was called "Warsaw U Selection". It was supposed to be used in Petrozavodsk Winter Camp 2015, but unluckly, teams from other Polish universities were familiar with some problems.
Btw, there is another problem in Prime Contest from this problemset. And for OpenCup not so much luck for Prime Contest in this year: at current season teams show great performance and we have no unsolved problems for all 8 contests.
EDIT: Here was something which is not currently valid
OK, it looks like something is wrong with my program, out of the blue exactly the same code which was successfully executing both on ejudge and on my computer started to spit out some errors and nans. Let me investigate it, it's not a typical situation for me to search for bugs in programs which got AC :).
EDIT2: OK, ACed -_-..... This task will definitely haunt me for ages. What I was dealing with when making it pass both on ejudge and yandex was without a doubt the most treacherous and one of most nerves-destroying things which I have encountered in my long competitive programming experience :P.
How did you solve it?
Assume that we know cdf of Taja's results. Then using some pretty easy dp in O(n2n) we can find out best strategy against that fixed cdf. However we do not know Taja's permutation of dices, so I tried to estimate that cdf using information form so far retrieved results (for every score, how many times I lost and won). That cdf can be guessed using many different approaches and really slight changes can change getting OK into getting WA on 1st test. So proceed using that algo:
Here's my code for reference: http://ideone.com/SsFW3X (it's not typical to me, but some names of variables express my frustration during all diferent troubles I had when I was solving it :P, I will better not describe those :P)
Were you the one to solve all problems in your team? What is the solution to 23. problem? (Marcin_smu got it ACed but that doesn't mean that we know how to solve it :P) Have you solved 31. without reading any papers? As far as I know it has a very hard and long solution (I mean description of algo, not code) which can be found here: http://www.sciencedirect.com/science/article/pii/0001870874900310
What about 23 problem :)? I know that if all dp's are different then all guys are comparable, so comparability graph is a tournament and there exists a hamiltonian cycle in every strongly connected tournament, so answer are exactly guys which create last SCC, but if there are guys with equal dp and close hp we get some draws and we lose that structure and I don't know how we can proceed.
After my another nerve-destroying struggle that problemset fulfills all conditions of an ideal problemset:
1) Every problem is solved
2) Nobody has solved all problems
3) Everybody has solved at least one problem
:)
Good job!
Just curious, did you see the problem 2 before, or did you solve it from scratch?
Thanks :). I haven't seen problem 2 before, however I really like all kinds of math/combinatorial counting problems, so after reading it I fell in love at first sight with this problem and I had to solve it :P.
Since I have already described that before, here's a description of solar lamps solution without any heavy data structures if anyone is interested:
Firstly, using some cross and dot products, let's reduce our problem to one where those angles are determined by (0, 1) and (1, 0) (it may be troublesome when angle given in description has zero degrees, but it can be handled well without any if for that case).
Let's start with determining output for just one fixed lamp. We can simply binary search an answer and for a fixed moment in time by using sweeping line we can determine all lamps which are lit at that moment, so we have solved that easier version in O(n log^2 n). In fact, we get information which lamps are lit at moment t and if a lamp is not lit at this moment, we also know exact number of lit lamps which illuminte it and that is powerful info, because that let's us call recursively to two time intervals [1, n/2] and [n/2 + 1, n]. To first half we put all lamps that were lit at moment n/2 and to second half we put all lamps which were non lit at n/2, but we update their k_i numbers by subtracting number of lamps illuminating them at moment n/2. That division may be far from "half of lamps there, half there", but since we are dividing time by two, that recursion still has logarithmic depth and on a fixed level, fixed lamp is present in exactly one call, so on a fixed level we need O(n log n) work, so overall complexity is O(n log^2 n).