MikeMirzayanov's blog

Reply Code Challenge 2020
By MikeMirzayanov, 5 years ago, In English

Hello Codeforces!

You may know that the crowdfunding campaign on the occasion of the 10th anniversary of Codeforces is in full swing! I am pleased to inform you that the Reply Code Challenge not only prepare a great competition but also supported Codeforces, which means all of us! Thanks!

Please pay attention to the information below. I am sure that this is a great chance to compete.

And here is the message from the Reply Code Challenge:

Hello Codeforces!

We're glad to invite you to the upcoming Reply Code Challenge, on 12 March. It's a free online team-based challenge and you can choose between:

  • Standard Edition: designed for university students and professionals.
  • Teen Edition: designed for students aged 14 to 19.

Great prizes are waiting for the winning teams:

  • Standard Edition: each member of the winning team will win a Mac Book Pro™ 16’’. Each member of the second and third place team will receive Apple Watch Series 5™ and Apple Air-pods Pro™
  • Teen Edition: 5.000€ for the first team in the leader board, 2.000€ for the second and 1.000€ for the third place team.

When&Where?

Online at challenges.reply.com on March 12th from 4.30pm to 8.30pm CET. To play you must form a team by March 11th.

Follow us on our Telegram Channel, WIP but ready soon for the Challenge: https://t.me/replychallenges

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

Comments Comments (80)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did they control my Age?(my birth date is 31/08/2006 is it OK to participate contest?)

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

    Hi! It's an online Challenge so we trust in a fair and honest participation :) Anyhow, we'll check winning team rules compliance after the competition in order to reward them.

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

Yay, team contest on my birthday!

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

There's nothing mentioning what kind of problems there are, but when you register and look at previous problems, it seems very similar to Hashcode.

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

I am 13 :(

Can I join it with three friends aged 14~19?

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

    You can't, but that's about the same "can't" as for making a FB account or visiting pornsites.

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

How can I be sure that I have registered for the contest successfully? There is no notification to ensure it. Please check it.

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

Just to mention this, Code Challenge 2019 has been won by a Codeforces community team :)

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it -9 Vote: I do not like it

.

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

Can college students with age 19 years and N months participate in Teen Edition? Where N <=4. Another post about Teen edition just mentioned High School students so asking for confirmation.

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

Whooh. Apple Watch as a prize does not sound cool at all as it is almost impossible to use it with an Android phone which i believe is more popular than iPhone. I wonder why both you and Technocup offer it as a prize...

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

is the problems test your problem solving skills like online judges(eg codeforces)?

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

    The Standard Edition follows the Google HashCode format, while in the Teen Edition there are classic algorithm problems.

    In both challenges you are required to download the input files, run the solution on your machines and submit a valid output to the platform.

    You can test yourself the platform using the sandboxes with the previous challenges at Reply Challenges

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

Are teams allowed to use multiple computers?

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

All is smiles until you realize that Benq can still participate in Teen's edition

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

    Benq is strong, and we can learn from him :).

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

    No he can't. Benq isn't a teen anymore.
    IOI 2019 was his last attempt at IOI. He is in MIT now. :)

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

      Then you realise there's plenty of OP Chinese each year, not just him.

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

Where can we see the past scoreboard?

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

A bad time for Chinese users :(

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

It happens to coincide with #627 Div 3.

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

I can not create an account :(((

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

It's my first team-based contest , I'm excited!

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

I heard that this contest(Teen Edition) is only for Italians. True?

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

    Absolutely not! In previous editions we have had members from more than 100 countries around the world!

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

Past Problems, please...

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

I'm between the age constraints for the teen edition, but I've just finished high school past year (I'm not even in college yet). Is it ok to participate?

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

The Chalange is on Div. 3 codeforces Contest I Want to compete in div. 3 and chalange But I cant Please change The chalange Time or Div. 3 Contest Time Thanks for very good chalange

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

Hi, I want some clarifications on the rule of the teen edition:

Quote: If there’s a tie-break, we’ll consider the total resolution time for each input. In other words, the sum of completion times of all the solved input files. If two or more teams have the same score, the team with the shortest time wins.

What is the 'total resolution time' or 'completion time'? I could think of (a) timer starts from the beginning of contest (b) timer starts once you open that problem (c) timer starts once you start downloading the test.

Also if I'm not wrong, the teams can download as many inputs on all problems and submit outputs as they want? And no penalty will be given for doing so? (And you'll know the submission results for all submissions except for the last testcases?)

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

    From the platform you can download an input file with the testcases and you can submit an output file with the solutions within minutes.

    If the output file is correct you will gain the related points, the completion time it's the time between the starting of the challenge and the time of your submission.

    The total resolution time it's the sum of all the completion time for you correct input.

    (more or less icpc-style)

    If you want you can test the platform using the available sandbox https://challenges.reply.com/tamtamy/challenge/teen-edition-code-challenge/detail

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

      Sounds good.

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

      TLE: "Also if I'm not wrong, the teams can download as many inputs on all problems and submit outputs as they want? And no penalty will be given for doing so?"

      Is that true?

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

      If output file is wrong, will i be able to submit another one after 4 minutes?

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

"Codeforces Round #627 (Div. 3)" Overlaps with the reply challenge.

Is it possible to shift Div.3 to another day ? MikeMirzayanov

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

Why do we need to upload source code? Is it taken into account in something?

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

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

Hey guys, I don't know if this is a good place to do this, but I am searching for a team on teen edition. If anyone is interested, please send a message on my codeforces profile...

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

How to solve fifth problem in Teen Edition?

Statement can be found by the link(I hope): https://challenges.reply.com/tamtamy/challenge/code-teen2020/detail

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

    We managed to pass 4/5 of the inputs with max flow.

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

    Run maxflow in the original graph. We can change vertex capacity to edge capacity with standard technique of splitting each vertex into two. Then we can do two bfs, one from the source and one from the sink as if we are trying to find a additional augmenting path. Then for each edge it is easy to check if it's capacity increase then additional augmenting path occurs.

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

Our scores (team Errecto with JohnPaulII, mnbvmar, Radewoosh):

A — 96
B — 3'036'699
C — 710'371
D — 8'042'896
E — 4'923'352
F — 9'624'293
total: 26'337'707

EDIT yay, we won with a huge margin :)

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

    What was your base approach?

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

      As always, there are two parts: greedy, improving.

      Greedy

      Version 1: In some order (row-wise or random), go through cells and put a person who will maximize the total score (let's call it SIMPLE-MAX-GREEDY for a single cell). The complexity is quadratic so it runs a few seconds for small tests and a few minutes for F.

      Version 2: After putting a person in some cell, do BFS and cover 50 cells nearby, doing each cell in SIMPLE-MAX-GREEDY style. This way we do clusters in nice order.

      Version 3: 100 times repeat this: get random cell and person, put him there, do BFS and cover 50 cells nearby with SIMPLE-MAX-GREEDY. Rollback operations after each of 100 possibilities. Among 100 possibilities, go with one that maximizes the total score and do it for real (or alternatively for some tests: maximize improved score divided by the number of cells taken).

      To make version 3 fast, when choosing a person for a cell with some neighbor already filled, consider only people from the same company as that neighbor.

      Improving after greedy

      Some climbing up the hill: try to swap two random cells and check if it improves the score. Maybe sometimes try things close to each other. I don't know details, Radewoosh did this part. I think this worked best for F where it improved score from 9.1kk to 9.6kk.

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

        Interesting. We had a similar idea, but (if I'm not mistaken) we started by placing managers and then extend with BFS to place employees (maybe that's the bad idea). This yielded us, sadly, quite significantly less than 20M.

        For optimization, we unassigned some (400-1000) desks at random (sometimes all from the same company, sometimes not) and reassigned them by applying maximum weighted matching.

        It's easy to see that if there are no two adjacent desks in this random sampling, maximum matching would yield the best possible re-assignment, so we made our best to pick such subsets. This got us to something over 25M, so it was a big improvement for a local search technique (although it's hard to say, given that the initial solution seemed to be unsaturated to begin with).

        I wonder how that would work for your initial outputs.

        Congrats!

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

          Yes, I think we would improve significantly from something with max matching.

          btw. we analyzed tests a lot but in the end we didn't distinguish developers from managers.

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

    Our (relatively humble) score:

    A — 71
    B — 2.737.127
    C — 633.942
    D — 6.890.182
    E — 4.325.734
    F — yet to be evaluated (around 8.500.000)

    with zeyunow and tusg25

    What algorithm did you use? We noticed that you rose to 23 million really quickly.

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

MikeMirzayanov Don't you think if there is a platform hosting these contests, it should be on Codeforces. Please make it happen.

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

Hi! Do we get any certificate for participating in this competition?

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

Dear coders, get the chance to meet the winners of the last Reply Code Challenge and discover all their secrets!

The Usaco team members, Teen Edition’s winners, and the Errecto team, Standard Edition’s winners, together with the Reply Code Masters will be waiting for you to comment the problems they faced and the solutions that made them win.

Get online on our YouTube Channel at 5PM CEST for the Meet the winners live webinar!

replychallenges.com/YouTube

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

Live in a few minutes at https://www.youtube.com/watch?v=lL119xZ-C4Q!

→ Reply