scott_wu's blog

By scott_wu, history, 4 years ago,

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!

• +1220

| Write comment?
 » 4 years ago, # |   +33 So exciting.
 » 4 years ago, # |   +69 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.
•  » » 4 years ago, # ^ |   +20 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.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 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, YX solves the problems A, B, C, D, in time (minutes): 5, 5, 9, 11Y solves the problems A, B, C, D, in time (minutes): 9, 9, 5, 5The "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.
•  » » » 4 years ago, # ^ |   0 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 ^-^.
•  » » » 4 years ago, # ^ |   +18 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.
•  » » » » 3 years ago, # ^ |   -8 But what if the opponent recognizes the pattern and plays accordingly
•  » » » » » 3 years ago, # ^ |   0 There is no pattern if in each turn, you choose randomly any of the three with equal probability.
•  » » » » » » 3 years ago, # ^ |   0 The pattern is that you're choosing the options equally randomly??
 » 4 years ago, # | ← Rev. 2 →   +77
 » 4 years ago, # | ← Rev. 3 →   -34 [deleted]
 » 4 years ago, # |   +48 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
•  » » 4 years ago, # ^ |   +48 But then luck will be a huge factor. Whoever opens the easiest question first will be at a huge advantage.
 » 4 years ago, # |   +7 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.
 » 4 years ago, # |   +31 Will playbacks be available after the competition?
 » 4 years ago, # |   +22 Will we be able to challange our friends in CF ?
 » 4 years ago, # |   +24 Were any previous sets streamed / available to watch?
 » 4 years ago, # |   +121 Entering e-sports territory in 5 4...
•  » » 4 years ago, # ^ |   +27 Soon competitive programming will be a spectator sport.
•  » » 4 years ago, # ^ |   +65 Liquid.tourist is coming
•  » » » 4 years ago, # ^ |   +37 OG.Um_nik coming too.
 » 4 years ago, # |   +27 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.
•  » » 4 years ago, # ^ |   +3 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.
•  » » 4 years ago, # ^ |   +52 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.)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 4 years ago, # ^ |   +36 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!
•  » » » » 4 years ago, # ^ |   +69 So what? That's for fun
 » 4 years ago, # |   0 Do ACD
 » 4 years ago, # | ← Rev. 2 →   0 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!
•  » » 4 years ago, # ^ |   0 no.. that doesn't seem to be optimal! D and E are crucial for sure.
 » 4 years ago, # |   0 scott_wu I think it will be too exciting if you do not let them know the standing!!!
•  » » 4 years ago, # ^ |   +112 That kills strategic part. If we cannot adjust strategy then it's just solving problems.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -89 Could you tell me what strategires you follow?
•  » » » » 4 years ago, # ^ |   +5 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.
•  » » » » 4 years ago, # ^ |   +52 Good for you, but did you read the blog?
•  » » » » » 4 years ago, # ^ |   +5 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.
•  » » » 4 years ago, # ^ |   0 Good luck for the match Sir.
 » 4 years ago, # |   +96 teamum_nik
•  » » 4 years ago, # ^ |   +62 For reals?!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +194 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 xdAnyway, who if not you? :P
•  » » » » 4 years ago, # ^ |   +197 None taken, I just hope I will be able to solve at least something before tourist crushes me.
 » 4 years ago, # |   +13 Woah ! Nice ! This seems super fun and exciting !
 » 4 years ago, # |   +11 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..! xDThis 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 !
 » 4 years ago, # |   +9 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?
 » 4 years ago, # |   +11 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
•  » » 4 years ago, # ^ |   +25 Yes, for people who are willing to cheat in for fun competitions, it could.
 » 4 years ago, # |   +462 xd
 » 4 years ago, # |   +21 What is the penalty for a wrong attempt?
•  » » 4 years ago, # ^ |   +103 Forehead flick
•  » » 4 years ago, # ^ |   +13 None
 » 4 years ago, # |   +11 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?
 » 4 years ago, # | ← Rev. 2 →   +8 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 :)
 » 4 years ago, # |   +47 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.
•  » » 4 years ago, # ^ |   +16 I think longer is also OK. What about reducing to 0 in 30 minutes linearly?
•  » » » 4 years ago, # ^ |   +25 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!
 » 4 years ago, # |   +25 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.
•  » » 4 years ago, # ^ |   +9 MikeMirzayanov. He is rich.
•  » » 4 years ago, # ^ |   0 I'm in.
•  » » » 4 years ago, # ^ |   +10 Deal.
•  » » 4 years ago, # ^ |   +145 I cannot bet against myself, right?
•  » » » 4 years ago, # ^ |   +56 Yup, you can't. I see a possible exploit here :>
•  » » 4 years ago, # ^ |   +21 Sorry :|
 » 4 years ago, # | ← Rev. 2 →   0 .
 » 4 years ago, # |   0 Well, just one thing remains ... are you guys seriously going right after good bye 2019 ?
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   -46 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.
•  » » 4 years ago, # ^ |   +17 Then don't watch...??
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -23 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".
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   -8 Who knows. Maybe there is someone who thinks "oh, this is right". If not, then let them be (at least i offended them).
•  » » 4 years ago, # ^ |   +11 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.
 » 4 years ago, # |   0 Too excited
•  » » 4 years ago, # ^ |   0 Don't spread your arms in such situations, earth's gravity is not that strong
 » 4 years ago, # |   +3 Has it begun?
 » 4 years ago, # |   +6 its 9:32 when it is going to start?
 » 4 years ago, # |   +8 Stream is live at https://www.twitch.tv/ttocs45!
 » 4 years ago, # | ← Rev. 3 →   +3 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 ?
 » 4 years ago, # |   +11 congrats tourist !!!
 » 4 years ago, # |   +10 Last minutes were so exciting !!!!
 » 4 years ago, # |   +9 Does tourist use this to do modular arithmetic automatically ? I can't find it in the STL using Mint = Modular ::type,md>>; 
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +57 I didn't have access to the source code earlier, I just saw that line on the stream and was curious.I was able to find an old problem on cf, with tourist using the same template https://codeforces.com/contest/1264/submission/66335577 , and I got it.I don't understand why you're being passive aggresive though
 » 4 years ago, # |   +2 Where can we see their solutions' source code please ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +13
•  » » » 4 years ago, # ^ |   +2 Thank you!
 » 4 years ago, # |   +23 scott_wu + ecnerwala wins against Um_nik + tourist
 » 4 years ago, # |   +86 I really want this format to be made into something you can play on codeforces. Something like Code Arena on Hackerearth but better!
•  » » 4 years ago, # ^ |   0 yeah ! That would be really great !
 » 4 years ago, # |   +8 I missed the stream :( will the video be available somewhere?
•  » » 4 years ago, # ^ |   0 https://www.twitch.tv/videos/527984026this makes me want to train so I can solve hard atcoder problems like them...really cool format and I hope it can bring more interest to watching competitions.
•  » » » 4 years ago, # ^ |   0 Thanks. The video name was "Codeforces Round 493" so I didn't even click it :D
 » 4 years ago, # |   +2 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..
 » 4 years ago, # |   +5 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.