tourist's blog

By tourist, 4 weeks ago, In English,

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://codeforces.com/blog/entry/53431 and http://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!

Read more »

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

By tourist, history, 3 months ago, translation, In English,

Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy!

Is it rated?
T-Shirt Hunt
Success Rate
Dynamic Problem Scoring
Prairie Partition
Perishable Roads
Blog Post Rating
Test Data Generation

Read more »

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

By tourist, 4 months ago, translation, In English,

Hi everyone!

The last elimination round of VK Cup 2017, Round 3, will take place on May 7 at 18:35 MSK (check your timezone here), along with separate Codeforces Round #412 for both divisions. All three rounds will be three hours long, and all three rounds will be rated.

The contest "VK Cup 2017 — Round 3" is for teams qualified from Round 2 or Wildcard Round 2. The top 20 teams will advance to the final which will be held in July 2017 in Saint Petersburg!

Huge thanks to KAN, qwerty787788, PavelKunyavskiy, AlexFetisov, MikeMirzayanov, and VK company for making this round possible.

Codeforces will be the main character of most problems. Don't forget that it's useful to read the statements of all the problems.

Good luck!

As we're in year 2017, the scoring will obviously be static. The exact scoring distribution will be announced before the round.

UPD 1. The scoring distribution is:

Div. 1 and VK Cup Round 3: 500 — 1000 — 1750 — 2500 — 2750 — 3500

Div. 2: 500 — 1000 — 1500 — 2000 — 2750 — 3500

UPD 2. Due to yesterday's registration troubles the start of the contest is delayed by 10 minutes.

UPD 3. Congratulations to the winners!

VK Cup Round 3:

  1. zemen, Zlobober
  2. V--o_o--V, LHiC
  3. RomaWhite, witua
  4. YakutovDmitry, BudAlNik
  5. Golovanov399, I_hate_ACM

Div. 1:

  1. Petr
  2. yosupo
  3. rng_58
  4. uwi
  5. Nezzar

Div. 2:

  1. ltaravilse
  2. btk15049
  3. RCG
  4. SUSTechDFS
  5. hieutrungle

UPD 4. Tutorial is now available.

Read more »

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

By tourist, history, 6 months ago, translation, In English,

XVII Open Cup Stage 10: Grand Prix of Gomel takes place on Sunday, February 5, 2017, at 11:00 AM Petrozavodsk time.

The link to the contest. You need an Open Cup login to participate.

I'm the writer of all the problems.

This problemset will also be used at Barcelona ACM ICPC Bootcamp on Monday, February 6. Unfortunately, this means I have to ask you to refrain from discussing the problems in public until the end of the contest in Barcelona on Monday, 5:30 PM Barcelona time.

Let's discuss the problems here on Monday evening!

Read more »

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

By tourist, history, 9 months ago, translation, In English,

Topcoder Open 2016 Algorithm Final Round starts in 28 minutes.

The finalists are bmerry, Enot (aka enot.1.10), Kankuro (aka vepifanov), krijgertje, Petr and rng_58.

Live broadcast will be available on Twitch.

Watch the action in the Topcoder Arena.

Also follow my live commentary on Twitter.

Read more »

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

By tourist, 5 years ago, translation, In English,

Hello everyone!

As many of you already know, today is the day for Codeforces Round #127 missing which is really undesirable ;)

Original problems for you were created by tourist and Romka. We tried to emphasize the ideological component of the problems, thus we hope that you'll spend more time thinking than coding. Special thanks for helping in setting the contest go to Codeforces coordinator Gerald. We also thank Delinur for translating the problem statements and Alex_KPR for reviewing them.

We hope that this round won't be just a regular Codeforces round for you, but will bring you new experience and new knowledge. For the authors all problems are equally easy, yet we tried to arrange them in decreasing order of simplicity :)

Problems' point values in Division 1 are 1000-1000-1500-2000-2500. Problems' point values in Division 2 are 500-1000-2000-2000-2500.

Wish you success!

UPD: The contest is over, thanks all for participating. We hope you enjoyed it :)

In Division 1 rng_58 was a clear winner, solving all 5 problems in an hour and a half! No one else managed to solve all problems in two hours.

The winners in Division 1 are (full results):

  1. rng_58

  2. peter50216

  3. liympanda

  4. White_Bear

  5. havaliza

In Division 2 every problem was solved by somebody, but nobody managed to solve all problems. The battle was very tough and the gaps were very small.

The winners in Division 2 are (full results):

  1. Leewings

  2. snow_lotus

  3. 72VanVector_SevNTU

Congratulations to the winners!

UPD2: The editorial is available now.

Read more »

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

By tourist, 6 years ago, translation, In English,
Hello everyone!

I invite you to participate in the upcoming short contest at CodeChef.com (http://www.codechef.com/COOK16). The contest starts on November 20 at 20:00 Moscow time (check the starting time in other time zones here). This time I'm setting the problems, while Anton Lunyov (A_A_Lunyov) is the tester. Anton made a significant contribution into setting the contest, so my big "thank you" goes to him :)

Here is some information for those who has never participated in short contests at CodeChef. The length of the contest is 2.5 hours, there will be 5 problems of different difficulty levels. The contest will be held by the traditional ACM rules. No special registration for the contest is needed, it's enough to register at the CodeChef site.

Unfortunately I won't be able to monitor the contest as I'll participate in All-Russian School Team Olympiad in Programming on the same day. Nevertheless, Anton will be able to answer all your questions (if any).

Good luck! ;)

Read more »

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

By tourist, 7 years ago, translation, In English,
Contest discussion

Problem A. Noldbach problem

To solve this problem you were to find prime numbers in range [2..N]. The constraints were pretty small, so you could do that in any way - using the Sieve of Eratosthenes or simply looping over all possible divisors of a number.
Take every pair of neighboring prime numbers and check if their sum increased by 1 is a prime number too. Count the number of these pairs, compare it to K and output the result.

Problem B. Hierarchy

Read more »

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