On the 15th of March 2019, the Italian company Reply will hold the second edition of the Reply Code Challenge, a team-based coding competition open to students and professional coders. In its first edition, this competition involved more than 7,700 contestants from 67 countries.
This year, a new contest will also be launched: the Reply Code Challenge Teen Edition, open to and designed for teenagers from the ages of 14 to 19. This contest, created in collaboration with the Italian Olympiads in Informatics staff, will challenge teams of up to four young students to solve algorithmic problems. The winning team will receive €5,000 to be divided among the members, the second ranked team will receive €2,000 and the third ranked team will receive €1,000.
To take part, sign up at https://challenges.reply.com/ before March 14th, create a team, and participate on March 15th: both the Standard Challenge and the Teen Edition will be held online from 4.30pm CET to 8.30pm CET. Participants can use any programming language and send as many solutions for each problem as they like.
- Registration: https://challenges.reply.com/
- Rules & FAQ: https://challenges.reply.com/tamtamy/page/teenfaq.action
- Official news: https://www.reply.com/en/newsroom/events/code-challenge-15-03-2019
Gaspare Ferraro and Giorgio Audrito, Italian Olympiads in Informatics staff
To 19 inclusively?
Yes
How to solve last problem? Please, don't say that in $$$O(M^3 * logN)$$$
I tried Berkelamp-Massey; compute the answers for length up to $$$50000$$$ manually and then find a linear recurrence. Not sure if it's right though ...
https://github.com/bqi343/USACO/blob/master/Implementations/11%20-%20Math%20(4)/Polynomials%20(6)/Linear%20Recurrence.cpp
Calculate answer up to N = O(M), then use lagrange interpolation.
But how is the answer a polynomial in terms of $$$N?$$$ Can't it be exponential?
I think it can be exponential. But it solved a few inputs. Oh, maybe it is only correct then s=1111...11 :D
A O(M²*log(N)) solution was required to solve the last input during the challenge. We have also a O(M*log(M)*log(N)) solution (but it was too difficult for the challenge).
In the next few days we will publish the problems on our platform with higher limits, stay tuned ;)
(... and where are they?)
I was told that this could be done with FFT. Anyone willing to post more details?
$$$O(M^3*\log N)$$$ passes each test case in around a minute on my computer, so you could just run each case from the last input on each core, and pass with that complexity rather easily.