scott_wu's blog

By scott_wu, history, 5 years ago, In English

Hey all!

We've created a new 1v1 programming contest format: Lockout. Like in most contests, each round has a set of problems and contestants work to solve them as quickly as they can. In Lockout, however, contestants compete head-to-head and only the first contestant to solve each problem gets the points. Contestants can work on problems in any order, so speed and strategy are crucial to avoid getting sniped! The head-to-head action also makes the contest much more exciting for viewers.

We ran the first edition of Lockout at TCO Finals last month as a double-elimination bracket tournament. All of the finalists who were available competed (and even some of the problem writers) and we got to see a lot of exciting back-and-forth matches! As you can see though, there's still one set left to play. So we'll be streaming Grand Finals of Lockout 0 featuring tourist vs. Um_nik at 9:30 AM PST, right after the end of Good Bye 2019 on Sunday. Tune in at twitch.tv/ttocs45 to see the finals with live commentary from myself and ecnerwala! We'll watch the screens and scoreboard live, talk to tourist and Um_nik to hear their strategies, and even have a special exhibition match afterwards. :)

The finals will feature five problems with the following scoring: 100 — 200 — 300 — 400 — 500. There are 1500 points total, so the first person to get 800 or more points will be the winner. What strategies would you try? Start with A and B, then jump to E if you get them both? Or start with E, and try to win outright with either C or D afterwards? Read all the problems first and then choose a strategy based on what your opponent solves first? Let us know your thoughts!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

So exciting.

»
5 years ago, # |
  Vote: I like it +69 Vote: I do not like it

Then Here comes another problem. If there are n people in the contest and they're going to solve m problems. people x solve problem y in p[x][y] minutes Then what's the score for each person if all of them compete properly? I think it's a nice problem.

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

    I guess this is assuming that everyone has knowledge of the p matrix? Another possibly interesting problem is if you don't know p for sure, but you have some prior distribution on what it looks like and you have to devise a strategy while updating over the course of one/multiple contests.

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

    I believe this is an impossible problem like rock paper scissors. There is no optimal strategy. It depends on what your opponent does.

    There are 4 problems A, B, C, D, and 2 contestants X, Y

    X solves the problems A, B, C, D, in time (minutes): 5, 5, 9, 11

    Y solves the problems A, B, C, D, in time (minutes): 9, 9, 5, 5

    The "obvious" strategy would be for X to A and B (draw) Y can counter this by solving B first. Now with points tied, Y can solve problem C then D, winning the match. X can counter this by solving B first. Then X can force a draw by solving A. Y can counter this by solving A first, etc. Playing optimally, There's 50% chance of draw and 50% chance of Y winning. I couldn't think of an example where X and Y both might win. I feel like with more problems/more contestants, there must be an example.

    I think additional constraints should be added to make the match have a clear winner. I guess this is also a reason why tonight's match (it will be night time here) is going to be really fun to watch.

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

      Yes,I get your meanings. You can't make the 'right' decision before you know others. So there won't be a 'proper' way to compete.... Then the luck is a huge factor of winning and losing. But it's still great fun ^-^.

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

      There IS an optimal strategy in rock-paper-scissors: play each of them $$$\frac{1}{3}$$$ of the time. No matter what strategy your opponent uses, you win at least 50% of the time, hence as the game is symmetric this is provably the optimal strategy. In general, there is an optimal strategy in all finite two-player zero-sum games.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        But what if the opponent recognizes the pattern and plays accordingly

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

          There is no pattern if in each turn, you choose randomly any of the three with equal probability.

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

            The pattern is that you're choosing the options equally randomly??

»
5 years ago, # |
Rev. 2   Vote: I like it +77 Vote: I do not like it

rick-and-morty

»
5 years ago, # |
Rev. 3   Vote: I like it -34 Vote: I do not like it

[deleted]

»
5 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Huh, you can shuffle problems and do not show the cost of them to participants. It would make the ability to rate problems really useful. Also it would be more entertaining than classical format

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

    But then luck will be a huge factor. Whoever opens the easiest question first will be at a huge advantage.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This is so exciting, but I thought this is only for the real legends, since for the ones who can't jump into E that is simply not a choice! Very nice thing to watch though.

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

Will playbacks be available after the competition?

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Will we be able to challange our friends in CF ?

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

Were any previous sets streamed / available to watch?

»
5 years ago, # |
  Vote: I like it +121 Vote: I do not like it

Entering e-sports territory in 5 4...

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Interesting at the top level with very few participants, but I don't see it as something the vast majority of people here will ever encounter in a meaningful way simply because it doesn't scale. You need too many problems if there are many contestants, and if you split people into separate groups/rooms, then luck can be a massive factor.

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

    I agree, but the same applies in most of the tournaments of a similar kind, right? And I think if this gets some hype and some try to do it on a large scale, there can be some ideas that reduce the luck portion.

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

    I think it actually scales quite well, in each "round" of the bracket, you can use the same problems for everyone, so you only need a few rounds worth of problems. If you want, you can even run single rounds (not tournaments), just as a fun opportunity to play lockout.

    I'm not sure what you mean by "split people into separate groups/rooms"; the tournament is head-to-head (1v1), so people are always paired up and compete with one other person. (You can pair people who are close in rating for a ladder-tournament, or you can use a bracket or swiss-style tournament.)

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

      Oh, I missed that it's 1v1 with parallel matches. Matchups matter even more then.

      Imagine that in the first round, you have two people who competed against each other, and both solved 3/5 problems very quickly — of course, one of them had points for at most 2 problems, but let's say you have enough AC submissions from both which show that paired with anyone else, each of them would have comfortably gone to round 2. Yet, one of them won and the other one is out. It doesn't even have to be a question of reds competing in local Indian competition, just being familiar with problems / having a good day / something works. It poses a question which was almost completely (only in room assignment) non-existent until now: should the general skill you demonstrate correspond to your final place?

      Swiss tournament seems to be the only reasonably working format for events on a bigger scale than TCO Finals, but the matchup concern is still there — a tournament costs much more time (rounds) and problems than a single round for everyone with fine partial scoring.

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

        Yeah, it's true that matchups definitely could affect the outcome, but I think it's less extreme than you're saying. Other competitve sports and games have these same problems, and there are a lot of known solutions for matching players and seeding.

        First off, I think seeding by CF rating makes a lot of sense. From the tournament we ran, it seems like outcomes are actually pretty highly correlated with rating.

        Once you have seeds, you have a few options: instead of a single-elimination bracket, you could expand it to a double-elimination bracket (like many fighting games) or even a Swiss-style tournament (which also has the benefit that everyone gets to compete every round). All of these formats (including single-elimination) reduce variance by putting high-seeds against low-seeds in early rounds, and they're pretty well understood from other sports.

        Alternatively, we could run a ladder-style contest and pair people with similarly ratings to make it more fun and competitive; then, whether you won or lost obviously doesn't determine your absolute rank, but can be used to update rating and track general progress.

        Finally, I agree that the actual rank you get is probably less stable than, say Codeforces rankings, but that's okay; this is designed to be a fun format for people to compete in and spectate, and I think CF-style rounds still have their place in this community. I do think the 1v1 format will make it more exciting to compete in though, even if there's some luck involved!

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

        So what? That's for fun

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

Do ACD

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Well, first i would solve a and b and c then i would read d and e then choose the easiest then ill go through f. I think this is a good strategy! By the way, its too exciting!

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

scott_wu I think it will be too exciting if you do not let them know the standing!!!

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

    That kills strategic part. If we cannot adjust strategy then it's just solving problems.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -89 Vote: I do not like it

      Could you tell me what strategires you follow?

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

        Strategy is important. For example if I am reading problemA (easiest), and the other person has already solved A, B, then I should immediately skip A, B and jump to D, assuming that the opponent will target C, (if they fail to solve C and I do D, then I win) :) And so on and so forth. So showing the opponents solved problems is important here.

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

        Good for you, but did you read the blog?

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

          After reading many comments I felt that they are completely overlooking that one problem can be solved (for points) by only one of the participants.

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

      Good luck for the match Sir.

»
5 years ago, # |
  Vote: I like it +96 Vote: I do not like it

teamum_nik

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

    For reals?!

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

      Well, I don't want to be rude, but in sport there is a rule "cheer the weaker" if you are not on any side xd

      Anyway, who if not you? :P

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

        None taken, I just hope I will be able to solve at least something before tourist crushes me.

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

Woah ! Nice ! This seems super fun and exciting !

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

Optimal paths are : 500->300 and 400->300->200/100 problem with 300 score seems crucial here, and 400 or 500 needs to be solved first... But as they would think that their opponent would try to take the 500->300 path... maybe 400->300->* would be a better strategy..! xD

This match for sure would be too exciting to see ! Just to see at what level of psychology and reverse psychology both of them would need to operate at :P !

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

Do you have any good system to do that? If I remember correctly CS academy has a great system to choose problems randomly and run a contest every hour. Is there anything like that?

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

By the way, watching some screen live could be unfair because it may give one participant a piece of information about what another one is solving and how is he close to the submission

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

    Yes, for people who are willing to cheat in for fun competitions, it could.

»
5 years ago, # |
  Vote: I like it +462 Vote: I do not like it

ASDAQWQWE xd

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

What is the penalty for a wrong attempt?

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

What a brilliant format!

I really want to watch the epic blitz between the two legendary participants and feel the thrills...if the starting time wasn't that late like 2:30 AM in my timezone. Will the matchup broadcast be stored for the future for those who missed?

»
5 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Wow, sounds really cool. Maybe Codeforces can add possibility for each one to participate in contests of that format later? For example 2 people with most close raitings make a pair of contestants, that the best one get some rating, other loses. Or even forget about rating, this is really cool idea just to duel against your friends, who think they are better. Idea of such format is the great New Year's present to whole Codeforces community, thank you, Mr scott_wu :)

»
5 years ago, # |
  Vote: I like it +47 Vote: I do not like it

I think it might be better if, after one of the contestants solve a problem, the problem's score for the another contestant gradually reduce to 0 within 2 minutes..? As in the original way if a contestant is delayed by website and is few seconds slower than the other, he'll get nothing at all, which brings a lot of uncertainty.

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

    I think longer is also OK. What about reducing to 0 in 30 minutes linearly?

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

      That's closer to CF round.

      It's strange that many people don't get the basic idea why scott_wu and ecnerwala came up with the idea of this competition format. It's faster, it's more head-to-head, it is an attempt to make a competition more fun and enjoyable to watch.

      Yes, one round could be a bit unfair, just like most other sports. But that's the point!

»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I'm betting 20$ for Um_nik with 40:60 odds (I get 30$ if I win). Anybody interested? I need to know you though.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

Well, just one thing remains ... are you guys seriously going right after good bye 2019 ?

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

As a suggestion, I think it would be good if there is a peer-to-peer code battle of this kind of format. For example, anyone can create a room and there will be three team: team A, team B and spectator team (or individual A and B if you want to have a person battle rather than a team one). It could be an extra type of mashup, a battle intended for (coding) friends. I think it would be fun and exciting for everyone if it is played with friends or people you've known.

»
5 years ago, # |
  Vote: I like it -46 Vote: I do not like it

For me, I don't like the idea of streaming div-1 level competitive programing. The viewers who could truly enjoy the content will be limited to div-1 users, while mostly div-2 users have nothing to do while watching. You will likely have to sit for 2 hours just to watch codes which you don't understand and wait for them to be accepted.

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

    Then don't watch...??

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it -23 Vote: I do not like it

      Of course i wouldn't watch this kind of content, at least for now, since i'm not be able to truly enjoy it. I believe there would be many div-2-3 people who think the streaming is worth watching then end up wasting time instead.

      By the way i think sharing my thought is better than "just don't watch".

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

        I believe there would be many div-2-3 people who think the streaming is worth watching then end up wasting time instead.

        Well. What other people want to do with their time is their business isn't it? Just like there are many shameless shitposters here. Just let them be.

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

          Who knows. Maybe there is someone who thinks "oh, this is right". If not, then let them be (at least i offended them).

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

    Yep, these are common issues for live/streamed Div. 1 contests featuring the top competitors.

    We think that Lockout improves on this significantly. First the duration of the contest is much shorter, around 30 minutes rather than 2 hours. On top of that, the problems include a much wider range of difficulty, from Div. 3 all the way to Div. 1, so everyone watching can find an interesting problem at their level.

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

Too excited

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

    Don't spread your arms in such situations, earth's gravity is not that strong

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

Has it begun?

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

its 9:32 when it is going to start?

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
5 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

Are the problems for this contest chosen from a contest which is already over and whose editorial is already released ?

What if the participants have already solved the exact same problems ?

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

congrats tourist !!!

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

Last minutes were so exciting !!!!

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

Does tourist use this to do modular arithmetic automatically ? I can't find it in the STL

using Mint = Modular <std::integral_constant<decay<decltype(md)>::type,md>>;
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Have you considered looking at the previous 200 lines? It only contains the string Modular about a hundred times. You know, maybe there's the class definition.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Where can we see their solutions' source code please ?

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

scott_wu + ecnerwala wins against Um_nik + tourist

»
5 years ago, # |
  Vote: I like it +86 Vote: I do not like it

I really want this format to be made into something you can play on codeforces. Something like Code Arena on Hackerearth but better!

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

I missed the stream :( will the video be available somewhere?

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

add this new feature to codeforces so that two friends can compete each other.they would make fun and i think it is great idea..

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

Instead of only giving points to the person who submitted first, what if all points were given to the person with the fastest program? During the competition you can see which problems your opponent has solved but not their runtime. If you are worried that their program is faster, you can improve your program and submit again. Constant factors will be very important but I think it could still be fun :)

People who like code golf could play the same thing but with code length instead of runtime.