Introduction

So, I set myself that challenge to retire as a red coder before 24.09.2020... and I failed miserably. At least I am less delayed than most civil infrastructure projects.

This blog will be a recap of this short challenge with a mixture of some tips on practicing (for all levels!), some random life advice and, of course my bad sense of humour. It is dedicated to all those who aren't wonderkids, go from failure to failure and feel like banging their head into a wall during most of their competitive programming journey. Whatever your goal is, I'd like to strengthen your beliefs — you can do it!

How it all started

My skill level has been in constant stagnation for years. I've always thought that I'm just not talented enough to be a grandmaster. Although I've been red twice in the past, it was quite lucky and the next contests were solid $$$-137$$$ and $$$-189$$$ so that life could get back to normal. If you know a bit about chess titles, you are probably aware that you need to score three so-called norms to be granted a title for your lifetime. Thus, I wanted my third one.

In 2019 I noticed that an acquaintance of mine, kostka did something very impressive. His rating just exploded. I was inspired by Bartosz's improvement. Maybe I wasn't doomed to be yellow forever?

By the way, there's also a thread about users with inspirational rating graphs

What didn't work — the beginning

At the beginning of the challenge (spring 2020) I didn't really change much in my CP. I was kinda doing the same thing over and over, orbiting around 2300, hoping that a good performance is bestowed upon me and I can finally get red. Oh, how foolish it was... Just participating in contests did not, obviously, increase my skill.

Around June 2021 I was already almost late one year with completing the challenge. My exams were over, the delayed ICPC finals (September 2021) were coming. I decided to take my practice seriously. I wanted to be a better competitor and team member. For that, I needed to seriously improve. I started doing virtual CF contests and upsolving almost every day. That was quite a challenge, because I had already started a full-time job. I would wake up before 7 AM, do some CF contest, and then go to work. I, the lazy night owl, had to become a morning coder, it was painful at start, but doable. That was the only way if I wanted to keep up with my training partner, tnowak (ahh, those lucky university students). I did around 45 contests during the summer, upsolving usually at least one problem per contest. Yet, my CF rating wouldn't move. Actually, despite feeling much more confident in implementation, I lost around 200 rating points after the summer. I was quite purple then, and I needed to climb 450 rating points to regain GM title. Yikes.

The truth is that although older CF contests were very good practice for ICPC, they are not a very good source if you want to gain rating in 2022 (at the end of my trainings I was doing some contests from the 200-300 range...). Modern problems are different, rarely focusing on implementing some standard algorithms, much more mathematical instead. A nice library won't help anymore.

What worked for me

Six months ago demoralizer wrote a blog (it is deleted/hidden now, I can't find it anymore) offering coaching for yellow competitors hoping to get better. I reached out, and he, being a really nice guy, shared with me his recipe: First solved 100 2000 rated problems then 100 2100 then 100 2200 and so on...I reached red before I could solve a 100 2300 problems...

Fair enough, such a grind seemed doable. But I added a little twist to it — I practiced on AtCoder since I was notoriously bad at problems involving combinatorics or other mathsy stuff. And I needed to improve my thinking skills, too. With the help of kenkoooo website (great website, check it out!), I could easily find problems at the right level. In the next three months, I solved 100 yellowish (2000-2400 rating) problems. After that, tnowak became curious about effectiveness of this training and suggested I do a couple of virtual contests to compare my performances. The results were astonishing. The average of five contests I did was around 2500, two hundred rating points above the summer average. After two years of struggle, I finally became better.

Seeing the tangible results, I continued my trainings this way, skipping to orange (2400-2800) problems this time. I got red on the 23rd April, by the time I managed to solve 50 of them. Roughly two years after I started the _simple_challenge of gaining 100 rating points.

A universal practice method

If you're stuck or wondering how to improve, here's a simple recipe how to get better. The advice to "solve more problems" always irritated me. You may be unsure which problems to solve, how long to solve them, or just want to have a practice method that worked for someone else, here is what you need to do.

1. Find a range of Atcoder problems which you can solve in around 60-90 minutes.
2. Solve them, one by one, in some order which sounds reasonable to you. You can open many problems and think about them in parallel. You don't need to get them accepted in order, but try to get all the problems you see accepted eventually. Try not to look at editorials, but don't be too afraid to look at the editorial if you spent significantly longer than expected. You failed to solve that one, it happens.
3. Repeat. You'll improve quickly if you just follow this routine. Probably quicker than I did.

Here's some rationale why it should work. This problems range are the critical problems for you, they are in something that Um_nik in the best and truthest blog on Codeforces ever calls an interesting interval. If you haven't read his blog, go and do it now. Seriously, it's the best advice. Worked even for me. Thanks, Alex! (though to be precise, I have already been applying the takeaways from the blog before he published them. But I wanted to mention his name since he described it first and very well — I'm just highlighting that this indeed DOES work).

To improve, you want to be tackling the problems that you would be reasonably hoping to solve during the contest, and be faster in getting them accepted. That has three factors: coming up with the solution idea, clarifying the solution and making sure that it works, and only then implementing it. The third step should usually be straightforward -- if you have troubles implementing your solution, it means you haven't thought through it well enough. The faster you are at getting these challenging (for you) problems accepted, the more likely you are to solve more problems during the contest (as you have more time), and by facing obstacles on the right level you also don't waste too much time. Some may argue that usually solve within the contest level is too easy, or that reading editorials is bad. I didn't have infinite time to think about problems, and I wanted to feel confident that the problems are within my reach so that I can avoid the temptation to look at the editorial. That felt very important to me. When I was in high school, my teacher would usually give the same extremely difficult problem over and over to the top students until someone finally solved it. I developed sort of a PTSD for too difficult problems, wanting to quit as soon as I saw one of them again.

If you're on your own however, nobody will be torturing you with too hard problems, but you need to find a way to efficiently select problems to solve. I would always solve problems randomly — from various online judges, competitions or from my juniors. But overall I wasted a lot of time searching for tasks or solving ones that were not developing me (that includes participating in contests that mostly consist of problems you can solve). This is where the proposed practice method excels — you don't do that at all. Because AtCoder problems are all (or almost all) of very high quality, you have a nearly infinite supply of good problems to practice on. A word of warning here — if you're preparing for ICPC or some other coding-and-algorithm-heavy competition, consider moving to something ICPC-like from time to time).

If you really like contests, you can also use the kenkoooo website to create contests out of the problems from your range. It's also a fun way to challenge yourself. An additional tip would be to try to do it page-by-page. While it may not work like that for everyone, I found it useful to set mini goals for myself, and felt very happy after filling the entire page with shiny green colour. I practiced here

Do you have to do it?

I'd like to conclude with a small remark to be wise about your goals. Writing software is all about tradeoffs. Your life is all about tradeoffs. There's always an opportunity cost, for all things you do. During your practice time you could instead be hanging out with friends, practicing your interview skills to get a real job, or getting involved in some random machine learning startup that will make you rich. Before you declare you want to be a Legendary grandmaster (while cyan at the moment), look into the mirror without blindly following the crowd and ask yourself if it's really worth it. If CP is your passion and red/orange/purple is your dream, go ahead and do it! I believe in you :)

Motivation

Many people in the CP community are truly concerned about the war in Ukraine. Rightly so, it is currently affecting millions. Regardless of how many political discussions are held here, they don't really change that much. Let's try to address genuine human suffering instead.

CP mentoring for charity

I would like to host a couple of 1-hour CP mentoring sessions this Saturday. The prerequisite for attending one is donating at least 20$ to any charity supporting victims of the war. Of course, you are more than welcome to donate more.

If you think this is something for you, sign up for one of the six slots via this Doodle link:

https://doodle.com/meeting/participate/id/ZdP68j6a

The slot should disappear after it is chosen by one person. But I have never used Doodle as a booking management system before, so I don't guarantee that everything will work as planned... we'll sort it out :)

Please donate only after you are sure that your slot is secured, and write to me in DM on Codeforces. I will be quite upset if people are trolling, please don't.

A bit about me

My name is Kacper, I'm 23 and have been around in competitive programming since 2013. Together with my University of Cambridge team we've won a silver medal in the last ICPC finals. I've organized two Codeforces rounds: 8VC Venture Cup Elimination Round 2017 and Codeforces Round #683 (by Meet IT), and been a tester of many. I've set problems for various competitions, gave numerous talks and private tutoring sessions (mostly under Meet IT banner). I've worked at Huawei and now I am an employee at TwoSigma in the London office.

I'm happy to talk about pretty much anything, including:

• how to get better at CP

• how to prepare for interviews and land a good job offer

• how to get to a good university

• how to annoy antontrygubO_o

If you have some special suggestions, please let me know alongside your CF DM.

FAQ

Edit

Thanks for everyone who signed up via Doodle! Unfortunately, I cannot easily link your name and surname with your Codeforces account, so please let me know your contact details via a private message!

Edit 2

Meeting link: https://meet.google.com/eis-eayp-ffp. Send me a message if your slot is secured and you haven't done it yet!

Hi! Two weeks ago I made a survey link here: about making Codeforces better. In this blog I am sharing the results. Consider reading the previous blog first, but this one should be self-contained as well.

TLDR

The quality of Codeforces problems has increased over time, and people are mostly happy. Participants would probably be even happier with a greater variety of problem topics. It's important for setters to consider the contest as a whole, including the target audience of a given task. Some users wrote essays longer than the entire survey.

How to access the results

Before we start, I would like to invite everyone to take a look at the raw data. If you are keen on showing off your data analysis skills, please do so! I hope that some of us will manage to find more interesting insights taking into account preferences of users from various skill groups.

Raw results

General info

I got 329 responses from users of various skill levels and experience. Most of the questions have more interesting results than others, so apologies if I have omitted something uninteresting. Plots and charts are presented in spoilers to increase readability.

There was one non-question which I purposely left blank to see some creative answers. I was moderately disappointed, but a honorable mention goes to Markadiusz for a comment "Kocham prezesa". And to an anonymous high-rated user who advised me to learn how to use Google forms. Okay, enough shitposting, let's get back to the point. This is probably the most important of all charts:

I honestly don't know whether this is an indicator of good rounds or not. Perhaps the statement is too opinionated and some people are leaning towards lower grades? I guess everyone has their own perception about this, but the later answers clearly show there is still a room for improvement.

Problem topics

Over $$$50\%$$$ of respondents agree with me that there are too many adhoc problems in recent rounds, and only $$$28\%$$$ disagree. Other problem topics are somewhat neglected, and geometry is who would have thought mostly undesired. Two questions about standard techniques in contests show nearly contradictory results, which probably is my fault for stating them too ambiguously, as some respondents pointed out, apologies.

I also put some more controversial statements to see how people react. While there is no consensus on "IMO with a keyboard", an overwhelming majority expresses their belief about existence of potential in algorithmic problems. I am excited to see what new algorithmic problems are featured in future contests. Oh and by the way, "Standard problems have been used to oblivion" is just a clickbaity title, not my actual opinion. In fact, my personal opinion is "strongly disagree" on this :)

Codeforces Contests as a whole

Sometimes a bad detail can ruin a work of art. And so is the case with competitive programming contests. In this paragraph, answers to questions concerning the contests are featured.

In my opinion, the most important outcome arises from the "Problem target" question. If you are a problemsetter, please consider considering this.

Some people did not see that the following two questions were intended as opposites of each other (keyword: primarily). I mean, how can you both primarily care about two different things?

Surprisingly many are not afraid of implementation challenges and would like to see some in contests. I expected most people to disagree with me on this, but was pleasantly surprised.

Stories in problems are generally unappreciated. Some people have pointed out in the comments that stories are good if they ease understanding of the problem, but short formal statements are strongly preferred over completely unrelated details that just waste your time.

Several people expressed their concerns over combined rounds. However, I believe not much can actually be done here. Sponsored rounds are preferred to be combined because of prizes, and there are many sponsored rounds (or thematic events like Goodbye 2021) recently.

My concerns about Educational Rounds have been validated. This can be a lost case, too (as they are rated for users under 2100 so in theory shouldn't contain terrible standardness). Maybe awoo and BledDest can comment on this?

And finally, there aren't many, but still exist people who would like to see hacks on system tests. if you are one of those, please let me know about your round so that I can skip it

Long comments from respondents

Some people have written essays longer than my survey. I decided to not list them here. The authors, if they wish to share their opinion, should be rewarded contribution for their work. If you are author of a meaningful long long comment that made a point, please post it under this blog. Or message me if you would like to do it anonymously.

Instead, I will cherry-pick some short sentences of particular wisdom. Possibly slightly edited.

• Problems where it's cousin timmy's toy encryption on a tree but with cute bounds or whatever are beyond too synthetic to care.
• Real programming looks a lot closer to implementing a to-brainfuck compiler, than counting paths in graphs by modulo 998whatever.
• You can't expect to solve global warming and cure cancer with some subset of the exact same classic tricks.
• I honestly want there to be more diversity, which includes "obscure topics" — I'm here to learn, not for rating, anyway. HOWEVER, accordingly, the editorials should be more clearly written.
• The harder the problem the more important it is that it hasn't appeared in some old contest, it makes no difference for d2E/d1C but very important for d1E/d1F
• I don't want codeforces to be atcoder 2.0. I promise I did not write that answer
• We often "prefer" topics we're good at and bash on everything else. For topics/problems we don't practice (we're bad at) we lose the opportunity to like them; so I think having a variety of concepts ("adhoc", math, implementation, geo, etc.) forces us to be more open-minded and potentially like them.
• Combined rounds are too lethal if you brick on one of the early problems.
• As a writer of AtCoder Beginner Contests, I have huge respect for CF round setters(Especially, ECR and Div3 writers) because CF's "interesting problem" is unique to other contests, and I cannot solve this kind of problems in other contests, and mass-produce such problems. Keep it up, CF!
• The real gigantic issue I have with recent Div2A, B, C problems is that they feel... somewhat arbitrary and unmotivated. Define some weird arbitrary operation/sequence/whatever and prove some random thing about it. Okay, I guess?

Takeaway

Problemsetters cannot make everyone happy. No round will be perfect for everyone, and there will always be complaints. That doesn't mean, we shouldn't pursue better rounds. I hope the survey (despite some flaws) has created a field for a data-driven discussion about how to make Codeforces better. The floor is yours!

Hi! Sorry for this rather click-baity title, but if you're reading this, you likely care about making Codeforces better. And so do I! And so, I've made a survey...

Motivation

Some of the recent rounds, especially Div1 have been rather poorly received. Technocup and ByteDance rounds have been downvoted like hell, other rounds don't have particularly impressive contribution either. GR18 also has received a lot of criticism and as far as I remember had more upvotes before its start due to PurpleCrayon's incredibly wholesome announcement. There seems to be something wrong; people rarely compliment the writers for the bits they enjoyed which seems to draw an overall picture of rather unhappy audience.

So, what's wrong exactly?

Well, I know what I don't like, but it of course may differ for you. For me, the spirit animal of modern competitive programming is a snake that grew so large it started biting its own tail. It's been around for a while, and more and more things are considered standard. Problemsetters, afraid of being downvoted for putting standard problems or accused of copying are inventing increasingly bizarre adhoc problems, especially as easy tasks. And suddenly we're ending up with atrocities like 1615D - X(or)-mas Tree. Parity of popcount of xor on paths on tree, really? Most of the "problem-solving" in such tasks is removing whatever garbage is in the statement. Or guessing the right way to approach a deeply complicated process. I can't count how many times I have recently solved a problem by guessing "if this problem's position is X, the solution must be...". Or brute-forcing to find a pattern (but that goes more for AtCoder tasks, I guess). Anyway, I've been quite annoyed and wondering whether others also feel the same.

The survey

https://forms.gle/x6wVQvQVSQk6zUiv9

If you would like to help making Codeforces better, please consider filling in the survey. It's short, and won't take you more than 10 minutes. It states a bunch of statements expressing different viewpoints about competitive programming, (like the one in the blog title), and asks you to rate each one in a scale from 1 to 5. Thanks to Monogon, tnowak, Linkus and Amtek for proofreading and question suggestions.

I hope that a sufficient number of participants expresses their views for the results to be statistically significant. After Hello 2022 I will close the survey, analyze the answers and probably compile a summary blog. If you've always been afraid of saying your opinions and being downvoted (#ratism), now it's the time to do it! I'll be very thankful, your voice really matters. Ultimately, it's the community who keeps Codeforces running.

Please, please, please, share your thoughts!

UPD

The survey hit 128 responses in just a couple of hours, can we get to a bigger power of two?

UPD 2

We now have more than 256 responses. I'm proud of us all :) Some people wrote essays longer than this blog or the survey, legends. We also have 5 tourists, so I think I'll do some postprocessing before sharing...

UPD 3

The survey closes tomorrow after Hello 2022, if you're willing to contribute and forgotten, now is the time. And if you have done it already, thank you very much!

UPD 4

The survey is now closed with 329 responses. Lots of love to everyone who contributed. I'll try to write a summary blog tomorrow. After some cleanup, the data will also be available to download so that everyone can analyze on their own :)

Codeforces Global Round 18 is currently scheduled at 18:35 MSK time on Friday, December 24. This is a day of Christmas, and it's not even on the weekend. Every year, billions of people celebrate Christmas with their families, and I believe many coders would prefer to enjoy GR 18 on a different date.

Therefore, let me suggest rescheduling of the round to some other day. If many people agree and there is no official parallel round of some contest, maybe MikeMirzayanov can consider moving it to a different day?

Please share your thoughts in the comments.

As part of recovering from my PTSD appreciation after participating in rounds coordinated by my dear friend Anton (antontrygubO_o) and testing his AtCoder Grand Contest 055, I committed a poem. Don't take it too seriously.

Thanks to Amtek for lifting up my spirits while writing and arthurconmy for enhancing my poor English language skills.

The end of ICPC and the ruling of Anton Trygub in the competitive programming universe.

1. One day, maybe even soon,
   Gone will be The colorful balloons
   And irrevocably forgotten will be
   Bill Poucher with his ICPC.

2. The AtCoder Grand Contests,
   are what truly is the best.
   Lord Anton with his mighty questions.
   Will be a hero for generations.

3. O, the problemsetter who’s smartest,
   you’ll always be the greatest artist
   Appreciated forever will be
   Ad-hocs and combinatorics.

4. Learn finally what the good contests are,
   Dearest ICPC with your unique style.
   Team competitions with real-life tasks.
   Only infuriate the participants.

I sincerely apologize to anyone who is offended by my bad English. I tried hard...

Disclaimer

This isn't really a first tutorial in the series. If you are interested in reading what participating in ICPC World Finals feels like, you can enjoy my pathetic behind-the-scenes story of the Cambridge silver-medal performance in WF2020. I tried to write a spoiler--free blog so that it contains minimum information about the problems.

Motivation

In 2016 I have written a blogpost My first ACM experience. It made sense to me to also close some chapter of the book by writing up about how my last serious contest went. I advise not to take the blog too seriously, it is just an honest stream of consciousness (some facts may not even be 100% accurate, though I will fix things people point me). Feel free to comment, praise, or hate. For a different perspective, check out IBaloff's blog.

The hero and heroine of the story other than me are David (_h_) and Maja (zdolna_kaczka) to whom I am very grateful for allowing me to share our experiences.

The contest

Thanksgiving

Attending ICPC finals was a fulfillment of my childhood dreams. I have met so many Codeforces friends and legends of the competitive programming world. I would like to thank:

• Maja, David, and our coach Andrej, for a beautiful trip to Moscow together

• Uni of Bucharest: freak93, livlivi, bicsi, theodor.moroianu for hanging out together when my teammates were too tired of me, and for not being able to use long longs properly.

• The legends: Petr, MikeMirzayanov, Benq and andrewzta for agreeing to have a picture taken with them.

• Other contestants whom I talked to and can recognize their CF handles: Monogon, awoo, TheOneYouWant, SecondThread, yarek, Anadi, w0nsh, znirzej, tabasz, kobus, Devil and probably many more I don't remember.

• Last but not least, MikeMirzayanov Bill Poucher for an awesome platform of Codeforces event, and everyone from the hosts who helped to make it possible.

Some pictures

Hi Codeforces,

Following a silver medal at ICPC Moscow WF 2021, I'll be finishing my 10 years long competitive programming career. It was a fun time, and I think I've learned quite a lot of useful things which helped our team to win a medal.

If you'd like a series of blogs containing useful tips, tricks and other random remarks, upvote this blog so that I have sufficient motivation to create them. I already have outlines of four tutorials touching different topics, maybe there'll be more if I have something interesting to say. But ofc I won't write anything if the community is not interested.

Also credits for YouKn0wWho as his blogs and library inspired me to also share some stuff.

Today after the round #707 I managed to get Time Limit Exceeded on problem B. Surprisingly, when I resubmitted after system tests, and got AC fitting tightly into the TL.

So I resubmitted $$$5$$$ more times. Each one got Accepted, too.

It's not a first time this happens. During the round #683, when I was among writers team, in one of the problems someone managed to get TLE on system tests even though we had pretests=tests.

Did you also experience something similar? Any idea what causes the judge to become slower during the contest? And, most importantly, should it be considered a bug or a feature?

Hello, Codeforces!

On behalf of Meet IT, I'm glad to invite you to (Codeforces Round #683 by Meet IT (Div1, Div2) which will take place this Sunday (15th November).

The round lasts 2.5 hours and is rated for both divisions.

What is Meet IT?

We are a family of enthusiastic and motivated young people passionate about programming and mathematics. We build a community where people learn together, motivate and help each other.

Meet IT family members worked hard over the last few months to provide you with our favourite challenges we came up with. We hope that you will enjoy them as much as we did :)

We are enthusiasts of short and clear problem statements, strong pretests, and happy participants!

Every effort is valuable for us, and therefore I'd like to thank everyone who has contributed to the creation of this round:

• Co-founders of Meet IT: Mateusz and Paweł for guiding Meet IT projects and making things happen.
• Maciej, Piotr and Michał. Without their commitment in early years of Meet IT the Family would not exist.
• Round coordinator antontrygubO_o for endless discussions about the problemset.
• pawelek1 for coming up with problem ideas.
• tnowak for massive support in the work on harder tasks.
• staniewzki and jjaworska for developing the most challenging problem of the round.
• pasawicki for interest in tennis which was an inspiration to one of the problems, and for preparing another problem.
• lcaonmst for preparing a problem quickly and diligently.
• Mohamed.Sobhy for coming up with a nice easy problem and preparing it.
• Amtek for enduring my repetitive reminders to prepare a problem.
• flaviu2001 for his excitement about the round after testing and help to improve the shortcomings.
• _h_ for help in providing a high-quality editorial to one of the problems.
• dorijanlendvaj for firmly complaining about one edgy problem that pushed us towards substituting it with a better one.
• kobor for providing beautiful pictures for the removed problem. :(
• Devil for coming up with the substitution problem :), without you we would be still finalizing the problemset.
• arsijo for paying special attention to statements clarity during testing.
• zdolna_kaczka for winning the virtual contest among testers.
• Anadi for inventing an alternative solution to one of the hard problems as well as his kind comments and suggestions.
• Farhan132 for his ideas on how to improve the problemset in the second division.
• Linkus and a.piasta for showing the need to reduce the round difficulty a bit.
• The Army of Testers: ffao, RetiredPlayer, Retired_cherry, Whistleroosh, ijontichy, coderz189, AwesomeHunter, H4ckOm, TeaTime, hg333.
• MikeMirzayanov for the amazing platforms Codeforces and Polygon.
• all the people who strive for Meet IT Family to grow.
• Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round.

UPD

I'm also thankful for Swistakk for testing the round thoroughly. Sorry for forgetting! I wrote the announcement sometime before that. I totally don't get why he got downvoted, please give him as much contribution as he deserves!

UPD 2

There will be $$$6$$$ problems in each division, with $$$4$$$ problems shared. One of those will have a subtask!

We strongly recommend to read all the problems. You have been warned :)

Scoring:

Div 2: 500 — 1000 — 1250 — 2000 — 2250 — (2500 + 750)

Div 1: 500 — 1000 — 1250 — (1750+750) — 3000 — 3000

UPD 3

We would like to host a stream shortly after the contest. We haven't yet figured out the details, you can expect some backstage stories about the round, Meet IT, and casual discussion. Stay tuned!

UPD 4

We've added the link to the stream which shows on the Streams pannel on the right. You're more than welcome to join our stream

UPD 5

Editorial is ready!

UPD 6

We hope you've all enjoyed the round despite some minor issues. Congratulations to the winners!

Division 1:

1. Um_nik (the only person to solve all problems!)

2. ecnerwala

3. Benq

4. ainta

5. ksun48

Division 2:

1. shb

2. jz_597

3. 1700012703

4. XueYJ

5. zybkl

Thank you very much for taking part in the contest!

1447A - Добавьте конфет

1447B - Коробка с числами

1447C - Рюкзак

1447D - Ловя мошенников

1447E - Ксор дерево

1447F1 - Задача о частотах (простая версия)

1446E - Долгое выздоровление

1446F - Расстояние до прямой

I was first red in my second year of high school, now I'm barely yellow. But this is not going to be a whining blog, you can just laugh at what I did.

A few weeks ago I thought: crap, I was 2400 years ago, now my CF rating is pretty shit. I don't like the fact that the rest of my ICPC team has around average 2700 rating, and I don't like the idea of posting a contest announcement as a non-red.

I've also noticed that there were 2 months before my wedding (24.09), so I set myself a challenge to retire before that date, as a red coder.

I started daily practice, took a few virtual contests and did daily upsolving around 2400-rated problems. I was really looking forward to catching up. But round #664 didn't really go as I wanted — I skipped B because C looked very nice, and then got stuck on the arising geometry. Around zero rating change didn't interest me, so a minute before the end I thought: well, of course I'm not going to finish C in time. My previous (unrated) performances were consistently really good in Div2. Why not just fall and gain rating in Div2? It will be much quicker.

So I resubmitted my beautiful problem A in 1:59.

So far, so good. I looked at CF-Predictor during the contest and thought: "I should be OK." What could possibly go wrong?

Guys, be smart. Don't try to fall to Div2 intentionally.

Hi! I'd like to do ask the wise men of Codeforces if they know any resources related to SPFA (Shortest Path Finding Algorithm). The short description of the algorithm can be found in PrinceOfPersia's blog:

According to this comment by romanandreev it works on average in $$$O(m log n)$$$, but there are counterexamples. Is anyone aware of any papers trying to tackle SPFA complexity?

Remember Camp IT? Well, it’s ok if not, because we’re organizing a new one and the summer one won’t be worth mentioning compared to this one anyways.

There won’t only be programming tasks on IOI level, but also ML workshops! You might think they won’t be challenging enough for you... The advanced level of the workshops will be hosted by profesionalists with years of experience (for example, Marek Bardoński from AI Revolution). They are prepared to grasp interest not only needs of students with little or no experience in Machine Learning, but also of those who have already worked in ML projects or interned at companies such as Boston Consulting Group or Facebook.

If you don’t already know, apart from the tasks and ML workshops there will be fun Evening Activities — as if the like-minded people, with whom you can talk for hours, was not enough.

Everyone 16-21 years old can apply (if you don’t fit into this gap, contact us and we’ll see what can be done). Yes, everyone can apply, as there won’t be any quiz to get in. The Winter Workshops won’t be free, but you can apply for financial aid if you would like to attend but financial circumstances would prevent you from doing so.

If that doesn’t convince you, just come and check for yourself... Be fast though, because the places are selling like hotcakes!

Book your place at our : website

Make sure you like our Facebook fanpage so that you can hear the freshest news

Hey! Together with Meet IT Foundation, we're delighted to present Camp IT!

So, what is it actually about? The main objective is to provide a place for development and networking for young programmers. This relates not only to algorithmic olympiads, but also to computer science activities of any kind!

Yet another IOI camp? Of course not! Although you will spend some time during the day doing IOI-styled problems, there are also Practice Activities and Evening Activities which aim to show you cool parts of computer science and give entertainment after a day of hard work.

Who can apply? You can apply if you're under $$$21$$$. Don't forget you need to fill in the Applicant Questionnaire, for which the time is May 2019.

What about money? We're happy to announce that you can attend Camp IT not caring about economical issues. We cannot reimburse travel costs, however.

If you would like to know more, refer to:

Camp IT website: Click!,

Meet IT website: Click!,

Meet IT Facebook Fanpage: Click!

See you in September! =)

Disclaimer: this post contains my thoughts and suggestions. Feel free to discuss the topics in the comments

[TL;DR] Cool problems, issues, why not semi-rated.

First of all, I'd like to congratulate Um_nik for making the simultanously best and worst round I've seen in a while :) On a more serious note, I've really enjoyed solving your problems, in contrary to some yet-another-segment-tree-problems. Especially B was quite unusual when it comes to CF.

However, there are some issues brought up by geniucos here which I completely agree with. Memory limit issues are really rare, and you usually realize that when you get MLE1 after submitting. Unfortunately, it was not possible today, so some participants were affected quite much (hello Swistakk.

Moreover, it wasn't only a case of MLE. "Incorrectly" solved problem B required using random generators. And now the standard CF feature — RAND_MAX is 32767. I've tested my solution locally and was quite shocked to see WA10 after the long queue ended. Looking at my submission: oh, RAND_MAX. Let's fix it. Wait. The round has ended 3 hours ago =) Of course you can say this should fail. But the problem is that such solutions passed. Look at 38734837 or 38747568. Especially no tests with N = 1000 and answer Um_nik — seem quite weak.

And well... the queue. 30 mins is in no circumstances a "very end of the contest". Even in an OI-style contest it's quite a lot of time. Of course, participants who didn't submit anything during this time were not affected at all. Usually submits during this time belong to most important problems — or at least the hardest we could solve. So it is imho the most important period of time. Some participants passed systests without any problems, some got FST and some got errors on pretest1. My C submission fortunately passed pretests with 3950ms (with TL = 4 seconds). Of course, everyone would realize his implementation is not efficient enough after getting such verdict.

Now, the most important part. There were some other options used in the past other than binary rated. If semi-rated didn't sound like a good idea, then maybe you could at least allow participants who were severly affected by the long queue to be excluded from the official ranklist, just like cheaters are (but no bans please)? I'd be very grateful an for official response. Attention tag. KAN.

My apologies for everyone who had to read this boring wall of text. Cheers :D

Disclaimer

The post will be mostly in Polish, as it will just contain solutions for training contests. I found Codeforces the most convenient place for writing them and allowing the participants comment.

Pierwszy krok (23 grudnia)

Obydwa zadania pochodzą z 11 oia. Szczegółowe rozwiązania można przeczytać w niebieskiej książeczce olimpiady.

Wiecznie drugi (24 grudnia)

Dzisiejsze zadania były z 2 etapu 17 oia i powinny się wykazywać trudnością większą niż poprzednie. Czasem do wejścia do finału wystarczą tylko 4 bruty ;)

Trzej muszkieterowie (26 grudnia)

Trudniej już nie będzie :) 10 oi, ale zadania z siekierą. Myślałem, że autostrady są łatwiejsze, bo źle zrozumiałem na początku treść.

International Tournament in Informatics is starting soon. The official website is here: http://iati-shu.org/en/home/

I'm wondering whether there is going to be an online mirror on csacademy or another site. Also, we can discuss the problems later here.

Hi guys. Today I was solving a problem together with minimario and we came across a well known-looking subproblem we couldn't solve.

There are two sequences of length N, A[] and B[] with N, A[i], B[i] <= 10^5.

Our goal is to answer queries: a, b, x, y which mean : find the i in range <a, b> with the biggest value of A[i] * x + B[i] * y. 1 <= a <= b <= n, -10^5 <= x, y <= 10^5.

Is it possible to do it offline?

Is it possible with operation erase as well? (erase can be seen as setting A[i] = -inf and B[i] = -inf).

Thanks for any suggestions.

I tried to solve CEOI 2017 Day1 problem — Mousetrap today during the csacademy mirror.

My idea is a bit different than what model solution does, but in the same time complexity O(nlogn).

I'll describe it briefly. First, let's assume we can freeze the mouse for a while and prepare the way for her. Let's calculate answer for this case and call it pathOnly. This is computed by the simple formula.

Now let's unfreeze the mouse. We will do binary search on answer — how many additional operations do we need now. Let's precalculate cost[] for each vertex x, meaning: how many additional operations if mouse gets to vertex x and stays there forever. Forever means in this case: until we prepare the rest of the graph for her.

Cost is computed by a simple recursive formula : cost[onPath] = 0 and cost[x] = cost[parent[x]] + degree(x) — 1 otherwise.

Now let's move to the last step of the solution. Assume we are at some step of binsearch checking if the result can be not greater than k now. If a vertex has cost bigger than k, we should never let the mouse reach it. Otherwise, the mouse can safely get to that vertex. We compute dp[x] now -> how many operations do we need to succeed to be done before the mouse enters vertex x, dp[x] can be either 0 or 1. When a vertex is forbidden or sum of dps from its sons is greater than 1, dp[x] equals 1. Otherwise, it is 0. In the end, if dp[root] > 0, the answer for our current k does not exist and does exist otherwise.

The problem is that this solution doesn't work in at least two ways. I believe the implementation is O(nlogn) and should fit in the time limit, but it fails a lot. It gets WA twice, too. I would be very grateful if someone expressed his opinion about it.

Code (pastebin)

Thanks in advance. PS. How to link the submission on csacademy?

Hi everyone!

Baltic Olympiad in Informatics is being held in Bergen, Norway. Here is the official competition site.

I am wondering — will there be any online mirror? It would be great if there actually was one, it doesn't seem probable :/

8VC Venture Cup 2017 — Elimination Round[Editorial]

Hello everyone! The first round of the 8VC Venture Cup 2017 will be held on Sunday.

I am honoured to be the problemsetter of the round. Reyna helped me a lot. Huge applause to KAN for his valuable coordinator's help, and MikeMirzayanov for his admirable work for the Codeforces comunity. I also want to thank testers very much (Alexey ashmelev Shmelev and Alex AlexFetisov Fetisov).

This round is a first stage of 8VC Venture Cup 2017. If you want to acknowledge yourselves with the competition, try here.

The main character of the round is PolandBall. It's a small friendly Ball who lives in a forest along with other Balls. You'll surely like it :)

I tried to fulfill your demands with a various, interesting and challenging problems described in a concise way.

Hope to see you soon, good luck and have fun!

UPD1: Scoring 500 — 1000 — 1500 — 2250 — 2500 — 2750 — 3500.

UPD2 Thank you for participation! Contest is over. Did you like the problemset? Feel free to comment =)

UPD3 Editorial

UPD4: Winners

1. tourist
2. jqdai0815
3. W4yneb0t
4. ilyakor
5. ainta.

Hope you've had a good time with PolandBall solving the problems.

Congratulations to all the winners and TOP-200 who advances into 8VC Finals =)

Hello Codeforces writers,

How long were you waiting for your contests? Were the stuff answering?

Here is my short, sad story.

I written email with propositions of the tasks about one YEAR ago. After few days I've got a response from GlebsHP "Okay, your proposition is received and will be evaluated in a few next weeks. "

The delay turned out to be huge. My question is : Should we take it for granted that this is how it looks like?

More seriously, this is something which should be dealt with. Of course, we are all trying to make the community as satisfied as possible. But anyway it is really uncomfortable and also discouraging. Problems may get outdated or improved, the proposal should be probably rewritten after such a long period of time.

What could the Codeforces stuff do about it? Do you have any ideas?