harniver's blog

Reply Code Challenge — Teen Edition
By harniver, history, 6 years ago, In English

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.

Gaspare Ferraro and Giorgio Audrito, Italian Olympiads in Informatics staff

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To 19 inclusively?

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

How to solve last problem? Please, don't say that in $$$O(M^3 * logN)$$$

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

    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

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

    Calculate answer up to N = O(M), then use lagrange interpolation.

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

      But how is the answer a polynomial in terms of $$$N?$$$ Can't it be exponential?

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

        I think it can be exponential. But it solved a few inputs. Oh, maybe it is only correct then s=1111...11 :D

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

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

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

      (... and where are they?)

      I was told that this could be done with FFT. Anyone willing to post more details?

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

    $$$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.

    → Reply