MikeMirzayanov's blog

Psyho Challenge: Where are your likes?
By MikeMirzayanov, 23 months ago, In English

Hello Psyho, this is Mike. We are happy to help with likes. So, Codeforces?

He waits for your likes here: https://twitter.com/FakePsyho/status/1605570944537280512?t=MV0OksdeUb8FXKApncDZcw&s=19

I believe that 40 facts are too few for us. We need more!

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

Comments Comments (56)
| Write comment?
»
23 months ago, # |
  Vote: I like it +18 Vote: I do not like it

EPICO

→ Reply
»
23 months ago, # |
  Vote: I like it +355 Vote: I do not like it

Thanks, it seems I'm not going to sleep tonight!

→ Reply
»
23 months ago, # |
  Vote: I like it +56 Vote: I do not like it

It's time to create twitter account?

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

Alright.. It's time to use all 3 of my Twitter accounts! :)

→ Reply
»
23 months ago, # |
  Vote: I like it +52 Vote: I do not like it

Press F

→ Reply
»
23 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Glad I could be of service.

→ Reply
»
23 months ago, # |
  Vote: I like it +40 Vote: I do not like it

At this moment, I feel afraid of asking what is heuristic/bot programming.

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

MikeMirzayanov When will magic and handle changing start? On the 25th ?

→ Reply
»
23 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Nitter link.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Read all of those tweets and couldn't get a piece.

I'm having trouble understanding what exactly all of these tweets from @Psyho are about.

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    He's giving advice for optimization and bot programming contests.

    That's a different type of contest than your normal codeforces round. On codeforces you have about 2.5h for several problems. There are also contests where you have only one problem and a week or even more time to solve it. There is no known best solution, yet you can say that one solution scores higher than another. A classic (and well studied) example is "travelling salesman". You have a salesman who wants to visit a lot of different cities while minimizing travelling time/distance. Of course he could just visit the cities in alphabetical order and it would still be a valid solution. But there are faster routes.

    We had an optimization problem on codeforces last month.

    For bot programming go to CodinGame and click "view last battles" to get an idea of what it's about. The contest will run for another 2 weeks.

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

It was at this moment that he knew... He f*** up

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

And this is how you create a heuristic contest roadmap without intending to do so XD

PS: Thanks Psycho for the tips, and thank you Mike for sharing!

→ Reply
»
23 months ago, # |
  Vote: I like it +93 Vote: I do not like it

Thank you Psyho for sharing your experience. I read all the tips — it's incredibly interesting.

I think everyone will understand if you limit the number of tips to a nice number (128? 256?). The Internet is too big and your experience is too interesting to keep up with likes.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +144 Vote: I do not like it

    Thanks for increasing visibility! 128 looks like a reasonable number, I'll keep this as my target. I definitely don't want to spend Christmas writing programming tips on twitter.

    Small announcement for everyone: I'm going to sleep (I know, I lied before), but I'll continue tomorrow (I have few hours to burn). If you have any specific topic or question that you'd like to learn more about, let me know.

    → Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

After reading the entire twitter thread, I got very interested in Heuristic programming.
Will attempt a Heuristic contest soon! (Most probably on Atcoder)
Thanks Mike and Psyho.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    You are not the only one. I was also more interested in this topic. Psyho, do you think it's difficult to prepare regular (say, one per month) heuristic contests by Codeforces community? You took part in marathons here. What needs to be improved in the system so that we can run the perfect competition like this?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +42 Vote: I do not like it

      I think the codeforces platform is already capable of handling a heuristic contest.

      For final standing I highly recommend system testing (running the solutions on a different set of testcases after the end of the contest). Unfortunately we saw how not to do it in the Huawei contest in September, where the final testcases were too different from the initial ones and some solutions failed with TLE or MLE.

      That leads me to the second point: provide is a local tester (with testcase generator) so participants can test offline. Topcoder gives you a Java application with a visualizer, atCoder has a webpage from where you can download testcases and upload your solution to analyze step by step.

      The alternative (no system testing) will result in a lot of submits with almost identical code and some testcase detection to decide which features or random seed to use to make the submission score higher without actually having a better solution.

      Another point is relative scoring (relative to other contestants or to some upper bound). If the possible score per testcase differs too much, some testcases would just become irrelevant. Topcoder does relative scoring to the highest scoring submission on a testcase. While I think that's the best way to handle it in order to evaluate the strength of different solutions, it might confuse newcomers (your own score can drop, when someone else submits a better solution). AtCoder uses some upper bound and normalizes to it (every testcase could give 100k points in theory, although not always possible in reality — just a rough estimation).

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I'd like to have Deadline format because I show good results in it:

      • you calculate all results locally
      • relatively small number of tests (usually 10), each test must be represented as a problem in terms of Codeforces
      • you submit only one archive with answers for all tests, and it's counted as you sent solutions for all problems
      • all tests are random so we don't have to find their structure as is HashCode
      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      It's not that difficult and as eulerscheZahl mentioned, most of the infrastructure is already here. Honestly, I agree with everything that he said and I have no clue why he's being downvoted. Most of the things I'm going to say are more or less the same, just using different words.

      In general, I'd say there are only two good ways of designing heuristic contests:

      1) Same as Topcoder & AtCoder does: every problem needs an official test generator that is available for download (with source code included). You need a "system phase" as well, where you run all of the final solutions against a large hidden test set. This solves the overfitting problem and makes the contest fair at the same time.

      2) Alternative is to give away all of the testcases for download and contestants only submit the answers. There's a version of submitting code instead of output only, but this usually devolves into a contest of compressing your output into the solution. It's fun to do that every once in a while, but it gets boring very quickly.

      I would generally discourage from (2) as I don't think such design is good for building community and it's generally not very educational as there's no mandatory code sharing. There's also no incentive for submitting your solutions, which makes the contest way less exciting. It also gives major advantage to people with access to a lot of computing power. The main upside is that, it's easier to setup such contests and that you don't need to care about support different language etc. Since CF already has all of the important components, I really don't see any reason to do such contests.

      As for (1), you already had a contest meeting all of those criteria: https://codeforces.net/contest/636

      I remember that after the contest I gave feedback to Gassa (who coordinated the contest) about things that could be improved. I can check them later and give a tl;dr. But based on what I remember, most of them were small issues.

      That being said, in order to have good quality heuristic contests you need:

      • Good problem editor & problem testers. Designing good heuristic (and bot) contests is very similar to designing games. The goal is to create something that has very simple rules, but it has a lot of depth. Recent Huawei matches were complete opposite of this. Bonus if it looks cool and you can make a nice visualizer. Topcoder has dimkadimon, AtCoder has wata and both of them are doing great job. Note that I'd be mostly concerned with the editor/coordinator role. From my experience, a lot of people have great ideas for contests, but it takes experience to turn great idea into a great problem.

      • Problem visualizer. Not a strict requirement, but this is what makes those contest fun. Not every contest needs a visualizer though. In theory, community can build visualizers as well and share them. The downside (other than having an official visualizer) is that in such situations it's tricky to design exact rules for competitors. Topcoder (and I think Atcoder as well) have very strict rules about no possible cooperation, code sharing or even talking about results on specific testcases while the contest is active.

      I'm happy to talk more about this if you're interested. After I'm done with tips that is.

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

        Another suggestion: Have two system tests : one that is randomly generated and one with lots of features.

        Release them all and ask the users to submit only the solution in, say, 1 hour duration. (like meta competitions)

        → Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Are Bot programming contests possible on codeforces?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    yes bots are allowed on codeforces. most entries in contests are bots, you can see this since there never are as many comments on posts as there are entries in contests.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    No, but we have huge experience developing such codes for Russian AI Cup contests.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excellent thread @Psyho. Would love to see more stuffs on bots and AI from everyone in this world. Its time to build make machines do some crazy shit. We have already repeated the same things million times, now lets think big. Delegate what we do to the BOTS.

All I dream is of Artificial general intelligence.

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

    Heuristic contests are actually about very different things than the ones which drive current progress of AI. Bot programming competitions are theoretically closer, but I still never heard that anybody used sophisticated ML or NNs and got a good result in such a contest (tagging eulerscheZahl here to confirm). Genetic and evolutionary algorithms are the most AIsh things you can meet here, IMHO. And the most relevant contests in terms of state-of-art AI are Kaggle-style ML competitions, I would say, which are very different from the mentioned ones.

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

      I meant in terms of optimization. Heuristics are like cherry on top of the cake.

      From rocket landing algorithm to image classification via Neural Networks, everything uses optimization of some sort. I am freaking amazed by those algorithms.

      Optimization + Heuristic FTW

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

      Bot programming competitions are theoretically closer, but I still never heard that anybody used sophisticated ML or NNs and got a good result in such a contest

      In this contest reCurse managed to train a neural network. And he won by a massive lead. CodinGame doesn't really support it, so he had to code his own NN framework and fit it in a 100k character submit limit. See his forum post for more details. Mad Pod Racing (formerly known as Coders Strike Back) has NNs at the top4, but only some years after the contest they got good enough to beat more standard techniques. Most simple board games on CG are dominated by machine learning approaches now. For more complicated ones you still see some other search (like GA or MCTS) at the top.

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

        Wow, I always thought that it's almost impossible to reach top places with NNs in such a contest because of very limited time for NN development/training and various environmental constraints (no external libs, source code limit etc). So thanks for this incredible counterexample and hats off to reCurse!

        Most simple board games on CG are dominated by machine learning approaches now

        Yeah, because they were training for months if not more :) In contest time it's still more like the exception, I would say.

        → Reply
»
23 months ago, # |
  Vote: I like it +54 Vote: I do not like it

link

Contests aside, this is also extremely important in the professional life (especially in areas which touch data science one way the anther). I've seen it countless times — people brush off something which doesn't make sense, only to waste many months later because of it (sometimes because of bugs, sometimes because their understanding of what is happening was wrong).

So if someone wants to follow a single advice from the thread — this is the one to choose, its importance goes well beyond the competitions.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is heuristic contest? What is the difference between heuristic contest and competitive programming?

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

    @cf-coder, I think heuristics are more fun at least when they solve some interesting problem. Competitive programming is like pure mathematics vs heuristic is like applied mathematics :P

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

    Long story short, CP requires to find exact solutions to the problems, when in heuristic contests getting exact solution is usually impossible and the task is to get the best approximation you can.

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

Worst fate a man can bestow upon another

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

Directly asking people for likes is distasteful. I would never do such a thing

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Please upvote me

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    How about asking for money? Which is more despicable?. Likes mean nothing unless each like was worth some dollars.

    → Reply
»
23 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I am new, but does something like this(Mike himself publicising activity of others) take place regularly? Or is Psyho an active contributor that's why?

→ Reply