Блог пользователя tourist

Автор tourist, 7 лет назад, По-английски

There's been much controversy lately about the late submission strategy not penalized by scoring systems of AtCoder and CS Academy. Most of the relevant discussion happened earlier at http://mirror.codeforces.com/blog/entry/53431 and http://mirror.codeforces.com/blog/entry/53449.

I have a lot of thoughts on the topic, so I've decided to share them in a separate blog post.

I really like the strategic part of programming competitions. Of course, problem solving is more important. But every contest consists of multiple problems, so there has to be a way of comparing participants which performed better at different problems. There's a huge variety of scoring rules, and I find it truly amusing.

The "submit after solving all problems" strategy looks widely attributed to me now, mostly due to Petr's remarks regarding my participation in AtCoder contests. In my opinion, it's wrong for multiple reasons.

A closer five-word description of my strategy is "implement after solving several problems". It's still quite inaccurate, though.

Here is my typical behavior during the last few contests:

  1. Read all the problems. Usually starting with the last one, but it's not important.
  2. While reading each problem, try to understand what it asks for, think about it for a minute.
  3. Start thinking about problems in random order, frequently jumping from one problem to another.
  4. Strive to make progress or look at a problem from a different perspective every time you get back to it. For easy problems, this usually means solving them from the first try, as there's little progress to be made.
  5. Look at the scoreboard to get a grasp of the amount of time people typically spend on each problem. This helps understand whether one should look for a simple solution.
  6. At some moment, I feel stuck in every problem I haven't solved yet (possibly an empty set). This usually happens during the first half of the contest. Implement solutions to solved problems in any comfortable order. Submit them. Here, there are two main options: submit a solution after implementing it, or do a batch submit after implementing all of them. I've tried both, and I think it doesn't matter too much. At least the latter option doesn't make me upset with WA in the process of implementing another solution, and also saves me from the urge of refreshing the submissions page for each problem separately :)
  7. Try to solve the rest of the problems, again jumping between problems if there's more than one, but spending more time on one problem in a row. Once a problem is solved, implement its solution and submit.

I feel like this strategy has only one major disadvantage. Time spent in the beginning on problems one doesn't eventually solve is counted towards the penalty, which doesn't happen when using the standard "solve -- implement -- submit -- move on to the next problem" working cycle. For example, this could've cost me several places during AtCoder Grand Contest 018 -- I spent more than 10 minutes thinking on E and F before deciding to implement A-D, so if I hadn't solved problem F, I would've taken place 10 instead of place 7 with the normal strategy. It would've been even worse if both E and F had turned out to be unsolvable (which happens sometimes too) -- place 5 instead of place 1 for me. So, there's a prerequisite which one might call a disadvantage too: it's important to estimate problem difficulty well and feel when it's time to move from thinking to implementing.

On the other hand, I see multiple advantages. The first and foremost advantage for me: I feel very comfortable with this kind of behavior. I know that for many people it's hard and non-profitable to switch between problems too often, as it takes time to change the context. But I'm used, if not say addicted, to switching between problems often, and it seems in this case I come up with new ideas faster and better. Maybe that's due to subconscious thinking happening in background, or just a fresh look at the problem helps, it's hard to say. Implementing several solutions in a row also turned out to be comfortable and effective enough for me, as unlikely as it may seem.

Another slight advantage is, as Petr mentioned, not giving information to other participants. Intentionally withholding submissions to prevent giving information does help sometimes. It's a rare thing, though. In most cases, if you want to optimize your own result, you want to submit when it feels like you should submit, not when the scoreboard tells that you may submit.

And a small advantage I also consider important is seeing the whole picture of the problemset this way. Like, when you come to an exam, you can either start working on the problems one by one until you run out of time, or consider all the stuff you need to do and start with the most important things. The latter option feels better to me, though it might be very subjective.

Finally, the most controversial point is the possibility to bail out of the contest if your performance is poor. I wouldn't call it an advantage of this strategy. I believe considering the option of leaving the contest without submitting is disadvantageous, as you spend time thinking whether you should submit, while other participants work on the problems at the same time. The only profit you might get is the possibility to save your rating, which is a way of comparing contestants over many rounds but doesn't influence anything except one's self-esteem. And leaving the contest doesn't boost your skill anyway, so this is a meaningless thing to do in the long run.

To the admins of AtCoder and CS Academy: I think there's no need to change the rules. In my opinion, the "loophole" of leaving the contest without submitting doesn't create any big troubles. Clicking on the "Read Problems" button making the round rated for oneself requires a higher level of commitment from contestants which sometimes they aren't ready to provide. There are people for whom the rating is more important than participating in the contest; let them be. We are not reaching any goals by requiring much commitment, we're just decreasing participation.

Have fun!

  • Проголосовать: нравится
  • +972
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

I am just curious, why discussion about changing rules has started? Because of the Petr's blog?

Every strategy has own advantages and disadvantages. IMHO, submitting late isn't so bad for problemsetters and it could intrigue participants too (look for apiad's performance on last AGC :))

Even if admins change the rules, who is jealous for his rating can create fake account as well.

Spirit of the contest? Who cares? E.g I participate in contests for improving my knowledge (sometimes just for a joy :)). Maybe if I had a high rating, I would think different, who knows?

P.S "submitting late" sometimes might save you from failing for just nothing. E.g You solved the easiest problem fast, but then you had a big trouble with your connection.

»
7 лет назад, # |
  Проголосовать: нравится +199 Проголосовать: не нравится

Thanks a lot for sharing the details! They make perfect sense after you have explained them, and there seem to be much bigger advantages involved than the tiny ones I could find myself.

To summarize, you have come up with a strategy that allows you to be a better competitor, by more effectively utilizing the freedom provided by the penalty time rules at AtCoder/CS Academy(/Code Jam?). I think this is an amazing breakthrough, congratulations on that! This is in the style of the breakthrough we once had when we learned to debug printed solutions at ACM ICPC instead of using computer time, even if it requires more wall time. (To Um_nik: yes, I'm admiring a tourist's idea again — but I think it is a very well-deserving idea)

I was indeed very wrong about how your strategy works, and what goals does it have. No wonder when I tried to use it myself with the broken understanding, things did not go so well :) Thanks again for sharing it — now I'll try it again with the better understanding, with the hope of adapting it to my strengths and maybe finding some further improvement to share with the community, too.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    Its very inspiring and great to see the respect you guys hold for each other within the community.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +91 Проголосовать: не нравится

    You are right, I'm doing something similar at Code Jam too.

    Well, my idea feels much less of a breakthrough :) I don't expect it to be widely used by many contestants.

    It will be interesting to see you try it, though!

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

      Well, my idea feels much less of a breakthrough :) I don't expect it to be widely used by many contestants.

      How to say. Obviously, major part of contestants wouldn't use it "as is" because this strategy works great only if you expect to solve all or almost all problems in set and most of them require more thinking than implementation. But, on the other hand, your observation that your can solve problems better if you switching between them often is very interesting and such behavior is peculiar for some other people when many of them still didn't undertstand it. Really, I think many of people who read this have situation when you stuck on some problem for a while, forgot about it and when you returning to it after some time — you quickly see how it should be done. Such thing happened to me on this year's KPI-Open. I found one of problems hard (let call it A) and switched to another one (further B). When I couldn't solve B and returned to A — I immediately understood on which way it can be approached. And it's me, with my small experience and comparatively ordinary mind. For other people this observation may become more important. Maybe, in the future, this technique will be widely investigated, scientifically explained and become very popular, like brainstorm, for example (they have something common, btw). But now it isn't and we can only make experiments and share results with each other. And it's cool that you start it with describing your strategy on foregoing contests.

      TL;DR: Though your idea is not a breakthrough, but it can grow into breakthrough. And it can in one way or another be useful to other competitors.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        This often happens to me also (immediate solve on context switch). Context switch does what hours of fruitless pondering couldn't.

        Probably a context switch is a rebuild of our mental model of a problem. It's rebuilt from partial memories, so it turns out differently each time.

        The well-known practice of explaining a stuck problem to a peer (which sometimes goes like this: "I can't solve it because [...], which leads to [...], oh yes, that's the solution") is probably another way of rebuilding the mental model. Noting that, often, the peer doesn't have to say anything for this to work, gives rise to Rubber duck debugging. In my experience, typing an explanation into a text document works well too, as long as it's aimed at an audience who hasn't thought about the problem.

        An alternative theory is that progress is made by zig-zagging between conscious and subconscious efforts, so that upon a context switch we only receive the result, it just seems to happen in that instant, but that's an illusion. Academician Migdal talks about that in his book, suggesting that subconscious processes are characterised by uncontrolled associations and refers to Poincare's similar ideas.

        I guess that according to the first theory, maximising the number of context switches would be optimal, whereas the second suggests that the optimal switch rate might be less than that.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +18 Проголосовать: не нравится

          I think it's not even about context switching but about focused or diffuse thinking modes. When you think about a problem, you are in focused mode. When you do something else, you are still thinking about the problem, but in diffuse mode. These two modes together are much more powerful than either of them alone.

          During a contest, one rarely have time to switch to diffuse mode by e.g. washing dishes, so probably diffuse mode on problem X is while in focused mode on problem Y (or while reading it). That is probably less efficient than real diffuse mode (although I have no scientific evidence on that) but you don't waste time on the non-contest activity.

          I recommend the Coursera Learning how to learn course that elaborates on these two modes, as well as other useful things.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            The focused vs diffuse aspect is backed by imaging evidence. For example, the default mode network (DMN) is the imaging correlate of the diffuse mode (except sometimes), i.e. it is the volume of tissue in the brain that is active when the mind is not focused on anything in particular, but is still awake. So there really is a distinct mode of thinking.

            This is related to another kind of phenomenon. Many, many times I've been debugging a problem intensely right up to the end of a contest. Then the contest is over and I just stare at the ceiling. Often within a couple of minutes of this idleness I suddenly realise what's wrong with my solution. No thinking necessary. (And I might have spent 10+ minutes on the purposeful debugging efforts.)

            The thing with the mind is that there isn't any one simple law for how it works. So maybe all of the above models are valuable. Also, imaging is currently heavily dependent on achieving a useful signal-to-noise ratio by repeating measurements many times over. So, when we're talking about creative problem solving, introspection might still be the best tool for studying some aspects of it.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +59 Проголосовать: не нравится

      I've been using a very similar strategy on IOI-style contests where time does not matter: read all problems first, think on each problem, implement solutions and submit, switch at any moment when you're stuck.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Cool, but can you tell what is your strategy at IOI-type contests? It would be great if you will.

»
7 лет назад, # |
  Проголосовать: нравится +216 Проголосовать: не нравится
My favourite line in this post.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -79 Проголосовать: не нравится

    Once more. Mike cak you explain?

    If the blog sessions are so critical that only high rating people can use than feel free to restrict it based on rating.

    This is ridicululous people downvoting without reasons. Kind of lobbyism.

    Or why not have a forum where anybody can talk. I understand that bad language/ racism/ segrregation should be prevented but this is inexplicable

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 7   Проголосовать: нравится -34 Проголосовать: не нравится

      Dear Codeforces Community.

      First, thank you very much for tourist to open your strategy at AtCoder and csacademy.

      I read this comment. I think the downvote reasons are following:

      • I think the comment of the favorite line, which is getting ~150 votes is talking about "He can feel stuck though tourist is god of programming", and everyone think that this is interesting. (I think this is why blue's comment got +150. It's just my opinion and some people may have some different opinions.)
      • Your comment wrote about "he feel stuck less than nanoseconds", and this is not written about "feel stuck though he is god", which is everyone interested. So most people disagree about your comment.
      • Downvote means "I do not like it", but sometimes it means "I disagree about your comment". So I think disagree is one of the reason to getting downvotes.

      If your reason to do down-vote his comment is different than my opinion, I'm sorry to suggest this reason.

      But you wrote 2 times "why downvotes?". What do you think if you see a comment with -50 votes and 10 replies about "why downvotes?" by the author of the downvoted comment? I think most people annoyed about this. I think this is one of the reason to getting downvotes in the comment of "why downvotes?".

      In addition, -50 votes is not so high to say "why doenvotes" two times. It often occur and 10% of my comment got >50 downvotes. So I think the best way is forgetting about this.

      Sorry for my poor English.

      P.S. I know that my comment will get 700+ downvotes because rating difference between tourist and me is more than 1500, this is just my opinion and I think that most people will disagree about my comment, and my English is very poor.
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +65 Проголосовать: не нравится

        I actually laughed at that line because of what's said in the parenthesis (possible an empty set XD), so i found his comment kinda unrelated (didn't downvote though XD), but oh well, this is only my viewpoint, for others that comment might not be really unrelated afterall

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +43 Проголосовать: не нравится

        Hey,
        1. No offence but either call me by my handle or I will change to purple.
        2. 700 downvotes is way too much fucks to ask for.
        3. Such complex analysis is not needed. You should keep that restricted to your graphs only.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +49 Проголосовать: не нравится

          Since understood your comment, finally, I decided to answer the task which made by you.



          The answer is:



          Sorry for using this place for opening this graph.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +122 Проголосовать: не нравится

      I'm a simple man.

      I see downvotes... I press downvote.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Only if there was a laughter reaction in Codeforces XD

»
7 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

an option to leave the contest actually boost my rating. (probably not tourist's XD)

a strategy my friends often use in Codeforces is to read, solve, code problem C in the very beginning. if you do well, submit and go with other problems. Otherwise, simply discard the whole contest. the strategy assumes a strong correlation between problem C with other problems -- if you are poor in C, you are likely to be poor in other ones.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

    With all due respect i want to ask, is it right? it it fair?

    for me leaving contest after reading problems (becoz of fear of losing rating) is kind of unfair, and against my principles. Yep, there are some scenarios like if i m sick or i have to do some more important work, in such situations i read problem C and try to think about it while working or resting.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    For me it looks like you skipped your classes on conditional probability. For sure there is a strong correlation between ability to solve problem C and problem D where our events space is (participation of a guy X in contest Y taken from all possible pairs (X, Y)), but that is because there is a strong correlation between problem C and general skill and problem D and general skill. However if we restrict it to guy X and consider our event space as contests Y this guy participated in (which is event space you should consider with X=you) I think there is no correlation between solving C and D. Of course there is correlation between solving C and doing well in contest, so strategy still makes sense, but this is just because you done well on C. Maybe there are some underlying factors as whether somebody feels good that day etc, but I wouldn't call effect of that as strong correlation.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      Sound interesting. I was not so serious when I used the word "correlation". However, I still have sth to share.

      1. I actually skipped my probability course. XD
      2. I am using probability every day. So I guess I can continue on this thread.

      For me, there will be two points:

      A. What can be called by "strong correlation"? B. If (A) is true, does such "correlation" exists?

      For (A), considering the probability space C = {contests I participant}, there will be two function a_C(contest) and a_D(contest) to describe my ability to solve them. I believe that corr<a_C, a_D> is very close to 1. It should be > 0, at least.

      For (B), you mentioned that one of the factors. I think another determining factor is the author's style. I think I am good at Polish set (not really), but very poor in some truly creative set (like Petr's contest). So as I barely know most of CF authors, I should evaluate a_C and know Pr[a_D | a_C = fixed].

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      On cf there are authors of contest with very distinct style. Rather often I don't like problems of particular round, so I don't enjoy solving them. Looking at C (personally I usually look on C and D) in the beginning of contest helps to avoid such contests. 'enjoyed problems' and 'solved problems' are correlated, but not so much =)

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I see how that works, reading the problems first and have your brain subconsciously work on them while you work on others.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +72 Проголосовать: не нравится

I didn't know that tourist and me use similar strategy. I also like to delay my submissions. The only difference is that I do not submit solutions in the very end, because, well... I still have nothing to send.

»
7 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

I'm just a dumb newbie and this comment might not be well perceived but I personally feel like there should still be a penalty for registering for a contest and not participating because otherwise there's no real substance behind the "register" button and it encourages "unsportsmanlike" behavior via selectively participating in contests (i.e. participating in the contest and bailing half-way because you don't know how to solve the problems). It also doesn't emulate real-life situations too well (you can't simply bail out of SEERC or WF because you don't know how to solve the problems without consequences).

I realize that, as tourist said, if registering automatically makes the contest rated, one might have second thoughts about registering and participation might be reduced. A solution to this might be adding an "unregister" button which one can press before the contest if something comes up and they can't compete anymore. Maybe even make it clickable until 10 minutes past the times the contest has begun, but I feel like 10 minutes into the contest you should already be decided as to whether you can/want to participate or not.

That's just my two cents :)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I see your point and partly agree but there are many reasons for and against and the current solution seems to at least not hurt anyone.

    I can't bail from onsite contests, but I also don't sign up unless I know I can do it, which is not a case with regular online rounds. I remember registering for 3am TC round and just not waking up for it. Or a CF round I signed up from university but my bus was late so I didn't make it in time. The unregister button won't work in these cases.

    I think that a login-only problemset (with a button "show me problems — rated" and "show me problems — unrated") is a good idea. Surely, one can make a fake account, but that takes the classification from "unsportsmanlike" to "illegal", and I think it's a big difference.

    there's no real substance behind the "register" button

    Some people above said that it tells the organizers how much load they should expect.

»
7 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

BT!;)

»
5 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

I tried this strategy in AGC038. After solving A, I read statements of B,C,D and couldn't solve any of them during the contest. LOL.

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

If I follow this strategy I would fail for sure