Two days ago, a infamous problem in BOJ, a Korean OJ was solved(by me).

It is named 814-3 and it can be found here

The problems ask you to solve a TSP problem with 8000 randomly placed nodes on integer coordinate in square (0,0)-(814000,814000) and 140 salesman to travel them. The goal is to minimize the max distance that a salesman needs to travel. You do not have to find the exact solution, but you need to get an average score of 416280 or lower in order to solve this problem in 50 fixed test cases. Do note that this problem is not output only, and you need to do all the calculations in 4.814 seconds.

Input looks like this:

8000 140(fixed)

129309 230298

198309 129380......

Output should be 140 lines like this:

(Number of nodes that salesman 1 will visit) (list of them)

Example: 5 13 37 420 365 24

Wanna give this problem a try?

"As mentioned earlier, practice hard. This is the only common factor that experts have. And for whom reached expert, I'll write a sequel from expert to master soon." (From my blog, Tutorial and tips to reach Expert). That soon happened to be 1.5 years after the first blog...... First, I'm sorry for the immense delay. Many bad things happened to me, like not staying in the Master rating range, having a health problem, etc. That's why I wrote the blog this late.

Introduction

This is a sequel, but I am going to write the steps to Expert from scratch since the original blog(https://codeforces.net/blog/entry/81882) has poor quality.

Your journey is going to be divided into 4 sections. Each section contains the knowledge you need to have, the practice you must do, the performance you need to have in a contest, etc to advance to the specific rating.

Section 1. From the beginning to escaping Gray(1200)

The beginning

If you found the site Codeforces and entered this blog, you will probably be able to code in a language or more(C++ is recommended for advancing higher for the reason explained later), but if you don't, search the basic material online or buy a book, and learn the language. But you don't have to learn crazy-complicated features of programming language like templates (Which I don't know). You only need to learn until if statement, for statement, and basic functions and classes. Other features are often unused in codeforces. For example, the code I used in the Contest when I got the performance of red only included these features and some standard library(which I will talk about in the next section)

What you need to learn to escape gray

Honestly, not a lot. Most of the 1200-rated problem(Which means people who have a rating of 1200 has a half-half chance of solving, and you should solve it if you want to escape gray) requires only basic mathematical and computational thinking, basic programming skills, and a small dip into the basic algorithms(dp, greedy, basic graphs, sorting, etc.) which you can escape gray, or at least get over 1100 rating even if you don't learn them.

Example of mathematical and computational thinking

I will show a few 1200-rated problems and solutions. These should give you an idea about how to approach problems and solve them.

https://codeforces.net/problemset/problem/1583/B This problem includes trees that you might not know, but don't be scared of. You can solve without knowing the tree. The only thing that you should know is since m is smaller than n, there exists a node that can lie in every simple path. And, why not make it that every simple path passes through the node? That is the solution.

https://codeforces.net/problemset/problem/1537/C This problem is quite hard, and you need two observations. First, a minimum of h1-hn can be found by sorting the numbers and getting the minimum difference of adjacent numbers. Then, you have to maximize the difficulty. You want more uphills and fewer downhills. Therefore, the uphill needs to be small and the downhill needs to be big. Start from the bigger number of minimum difference pair and make the smallest uphill by picking the next element in the sorted array. Then, make a big downhill from the biggest one to the smallest one, and repeat making the smallest uphill. You will arrive at the smaller number of minimum difference pair, and that's the answer.

How to practice

First, go to problemset and search problems having difficulty 800. Pick a random problem and try to solve it. These problems are not that hard, so you should not spend more than 20 minutes thinking about the problem. If you got the idea, you should note how you got the idea and what is the idea. This will help you get the idea for future problems. Then implement the solution.

If you didn't get the idea or your solution is wrong, see the editorial. You should note why you failed to get the idea and learn from it. If you didn't know the topic, you should learn it using the online materials, and solve a few problems involving the topic since it is going to be important in escaping gray, or later on. Do it until you can solve about 80% of the problem, and move on to the next difficulty until you can solve most of the 1200 difficulty ones.

Participating in the contest

After solving some problems, you should participate in a contest. First, take a div.2 or div.3 virtual contest to learn contest format, judge your skills, etc. Install carrot, and see if the contest near your standing has the performance of 1100(due to rule change, carrot is quite inaccurate, and having a carrot performance of 1100 is enough to make you escape gray), participate in the real contest. If you do well in 6 contests, congratulations! You escaped gray! otherwise, repeat "How to practice".

Section 2. Escaping div3 and into Expert(1600)

Fast solving

Solving problem is often not enough to get a higher rating. You often need to solve problems fast, and that's not easy, especially if you are fast-solving difficult problems. There, I recommend you to do fast-solving practice on the problem that has difficulty around the current rating-300. You should be able to solve these, so get yourself a timer, and see how fast you can solve these!

If you want to be a cyan, you should solve 800 difficulty one in 7 minutes, and 1100 difficulty one in 25 minutes. If you want to be a blue, then you should solve 800 difficulty one in 5 minutes, 1100 difficulty one in 15 minutes. Also, you should try to improve the accuracy of solving, since each wrong answer costs points and time. You can achieve this by testing the solutions before submitting them (though it costs you some time), looking for simple errors while coding, trying to prove your solution, and practicing to have fewer mistakes.

STL(standard template library)

If you are a c++ user then you MUST use STL. STL has implementations of lots of algorithms, and it will save you time implementing them. the most important ones are vector(array with dynamic size), stack, queue, priority_queue, set, map, string, lower_bound, sort. Learn them, solve problems using them, and try to understand them.

If you are not a c++ user, consider switching to c++. c++ can make your code run faster, and it provides the most standard library. If you are not going to switch programming languages, learn your language's library that has a similar function to STL.

Necessary topics

As you progress. The problem requires you to know specific topics, and there is quite a lot to learn to reach a 1600 rating. You should learn DP, DFS and BFS, Dijkstra, bitmasks, binary search, basic combinatorics, two-pointer, and number theory. As you learn these topics, search for these topics in codeforces, and solve about 20 problems each. When you first learn them, start with a 1200 difficulty one, and gradually move up to 1700 difficulty one. You should allocate more time to each problem since it gets harder, but don't surpass 40 minutes of thinking, and see the editorial if you aren't able to find solutions.

Virtual participation

Virtual participation is a feature that allows you to take contests at any time, allowing you to practice like real contests. You should participate in div2 or div3 since div1 is probably too hard for you until you reach the 2000 rating. Make sure you have 2 hours, take a contest, and use Carrot to examine your performance. If you can get 1600 performance consistently, you are going to go to expert after you take part in a few contests. Also, always solve problems you weren't able to solve in virtual participation until 1900 rating problems(the rest is unnecessary to upsolve until you reach an expert since it is too hard and/or has a topic that isn't needed until you reach an expert).

Using other sites

As you know, codeforces is not the only site you are able to solve problems. There are other sites that you can practice in, and the best of them is atcoder. Atcoder has lots of problems that require mathematical thinking and brilliant ideas. You can also learn some well-known ideas from problems there, especially in atcoder beginner contests(ABC). ABC has 8 problems each(it once had 6 problems, but the difficulty of problems C, D, E, didn't change that much), but you are only going to use problems C, D, E since the others are too easy or too hard.

Problem C: has a problem rating of around 1100, and should be quite easy once you reach cyan. Topics on problem C are basic math and implementation, and some computational thinking. Also, you can practice fast-solving in these problems.

Problem D. has a problem rating of around 1300(around 1500 in 6-problem contests), and they require topics required on problems C and basic algorithms I mentioned to reach expert. You should also try to fast-solve them once you reach a rating of 1400.

Problem E. has a problem rating of around 1900, but it varies a lot. Also, some problem requires you to learn topics that are not needed to reach expert or even reach master, so I suggest solving easier ones using this site.

Understanding types of contests

As you know, there are many types of contests, and understanding which one has a higher chance of increasing your rating is important. General rule: If you are highest among the participants, you have a high chance of increasing your rating. The following data is made by djm03178.

For cyans: You should participate in div3. cyans within rating 1501~1549 had their average rating increased by 27 in div3, but their average rating only increased by 3~4 in other contests. The same trend continues for all cyans except unrated(1500)s.

For blues: You can't participate in div3, so there are three options. Div2 only rounds, combined round(Div1+Div2), and Div2 with Div1 rounds. And the best among them is Div2 with Div1s. blues having rating 1750~1799 increased their rating by 17 on average in Div2 with Div1, 10 on average in div2 only, and their rating decreased by 3 in combined rounds.

For purples: There are two options for you. Div1 and Div2. And Div2 is far better. Not only div1 problems are quite challenging and foreign to you, but also participating in div2 means you're top, therefore increasing your rating a lot. Purples having a rating 2000~2049 had an average 15-rating jump in div2, but their rating dropped by 10 in div1.

Section 3. Entering div1(1900)

New topics and practice

As your ratings get higher and higher, there are more topics for you to learn. Not only do you have to solve more advanced problems you have learned before, but you should learn quite a lot of new topics. I recommend learning all topics that have a tier 1 rating in this blog. This is enough topics to reach purple or even orange. After you learn these topics, solve about 10 problems using the topic you just learned. This will give you an idea of how to use the topic in real problems. Note that these problems sometimes don't have the tag in codeforces, so you might consider using other sites such as USACO, and Baekjoon online judge(Unfortunately, this site is in Korean, so I will write a tutorial about this site soon.)

Your view of the difficulty

As you solve more problems, you should know which problem is too easy, and which one is too hard for your level to practice efficiently or not to waste any time in contests. A, B, Atcoder 100~300: Too easy. You should solve them in under 15 minutes, and solving them in practice is just a waste of time.

C, Atcoder 400: They are quite easy, but not too easy. It is quite a good idea to practice speedsolving in these problems if you are lacking speedsolving skills.

D, Atcoder 500: Its difficulty varies a lot, but it is just in range to practice efficiently for going to purple. For easier ones, you should try to solve them with no WA and in a fast time. For harder ones, just solving them in any way is enough. Try to think for an hour, and come up with a solution if you encounter these.

E or higher, Atcoder 600 or higher: These problems are too hard. You might use E or Atcoder 600 to go to the master, but all the others are unnecessary until you want to reach red someday.

Difficulties and how to overcome them

While you try to go to a higher rating, you'll overcome many difficulties. Your skill may be stagnating. Your rating might drop. You might perform well in practice but fail in real contests. Here's my advice to help you overcome them.

Your skill is stagnating: Check how much time you spend practicing. If you spend less than an hour a day, You are practicing too little. You should practice more, probably about two hours a day(or a virtual contest a day). If you are practicing quite a lot but feels stagnated, you might solve problems that are too easy or too hard. If you are, solve problems that are similar to your own rating. These problems are not going to be too easy or too hard.

You perform well in practice but fail in real contests: I suggest you do some virtual contests. They have the same format as real contests, and you should participate as such. You will learn skills such as time management, contest strategy, and a good mentality. If you are performing well in virtual contests but fail in real ones. It is likely a mental issue. Participate in real ones just like it is another virtual contest.

Your rating drops for no reason: Sometimes, it is going to happen. You might have bad conditions, the problem might not be best for you, your internet suddenly fails, etc. Don't care about your rating too much, and remember that as your rating drops, you have a higher chance of rating going back up in the next contests.

Section 4: To the orange(2100)

The two ways to go to the orange

As you know, purples can participate in both div1 and div2. While you will gain more ratings on div2, it becomes unrated after you get to the orange. Therefore, you have two ways.

1. Practice div2 problems and speedsolving more: This will quickly get you to the orange, and help you to solve easier problems of div1 quickly, but you might have a hard time solving Div1C or harder.

2. Practice div1 from here, and focus on solving harder problems: This path is going to be slow in reaching orange, and you might fall into blue sometimes, but it will help you to advance to a higher rating once you reach orange.

I will write about both ways in this blog.

The first way

What to do

You are going to be orange if you are able to consistently solve 4 problems fast enough or 5 problems in easier rounds. Therefore, your main focus is going to be speed-solving through easier problems in div2(solving the first three problems in under 20 minutes, and the fourth one reasonably fast), and extending your solving range to div2 E and atcoder 600 points(This is going to make your performance in the high orange range, and it will make you have an easier time in div1).

How to practice

You can get to orange without learning any new topics, since the list of topics I provided is a bit excessive for getting to purple, and learning only them is enough to get to orange. If you haven't learned all of them, you should learn them since these topics will pop up in harder div2 problems and div1 problems. What you should spend time on is solving problems.

Solving easier problems(div2 A~D) is done mainly to practice speedsolving. You should be able to solve average A in 4 minutes, average B in 7 minutes, average C in 15 minutes. If you are not able to do this, then you should practice speedsolving by grouping 5 to 10 problems of similar difficulty and solving them in one sitting. Problem D's difficulty varies a lot, so you should solve them one by one or in virtual contests, and compare your time to the real contestant's time. Don't mind speedsolving E, and just focus on coming up with an idea. If you want to solve harder problems, you might think about an hour. This is completely normal, and trying a hard problem for a long time is the skill you need if you are willing to go past orange and solve harder problems in div1.

The second way

Div.1 problems

Before taking the second path, you should note that div.1 problems require you to know a lot of topics and also come up with a hard observation to solve. This is different from div.2 where there are not a lot of topics until F, and there are a lot of problems that don't require hard observation. Therefore, you should solve mostly div.1 problems from here on out, since div.2 problems don't help you perform well in div.1.

Here are the difficulty viewpoints from the people who are trying to reach 2100. It will help you to practice efficiently.

A. Quite easy, and should be solvable in 10 minutes.

B. Quite challenging. You are sometimes not able to solve them, and it usually takes more than 30 minutes to solve them.

C. Very challenging. Your chance of solving them is about 20%, and even if you solve, it's at the end of the contest and/or has a lot of penalties.

D and onward. Almost impossible to solve.

How to practice

Your main focus is solving B, since solving B consistently and within a reasonable time is what you need to reach orange. I suggest you make a list of B problems and solve them one by one, thinking about a problem for about an hour. If you are not able to solve it, see the editorial and get the idea. It might help you to solve another problem.

That's it. Div.1 B doesn't(yet) require topics out of tier 1 in the topics list, and speedsolving Div.1 A doesn't really matter a lot(also, you should be able to do it from the practicing of div.2C). There's only one thing you can do to get to the orange and that is to solve problems. lots of them(There are virtual contests too, but they're still just solving problems).

Final Words

I talked a lot about the way to improve your rating. However, that's of no use when you are not practicing hard enough. Practice a lot, possible every day. Try to improve yourself, and try to understand problems you weren't able to solve. If you practice hard enough, you will soon reach your desired rating.

Before the start of the blog, I'd like to thank this blog for motivating me to write it.

However, this blog is quite outdated in many factors like the rating system, and people starting cp in 2020 may have trouble following these. Therefore, I would like to write new tips for doing well in codeforces. The goal is getting to expert, or rating 1600.

I would write this in 3 steps, but the most important thing here is Practicing hard. You won't get to 1600 if you don't practice, you don't have to do it on the blog's way, but you should practice.

Step 1: from 1000(grey) to 1200(green)

First, read introduction to the new rating system and judge your skill. Note that you'll need to take part in about 5 contests to judge your skill. If your rating is under 1200, read the next part and practice.

If you use div3, you'll need to solve 3 problems in 30 minutes. That means you should solve div3C in 15 minutes. To practice it, you may choose 1000~1200 rated problem and try to solve it in 15 mins. If you have no idea in 15 mins, you should see the editorial.

If you use div2, you'll need to solve 2 problems in 30 minutes. The practice methods are the same, but do it in 1100~1300 rated problems and 20 mins.

You should solve problems until you get to green(it applies to all the other steps.

Step 2: from 1200(green) to 1400(cyan)

In order to get to cyan, you should know basic dp, greedy, bit operation, and math. Other things such as graph theory are not required to go to cyan.

First, you should learn about the algorithms. First, you need to know the concept of them, and you should practice. Practicing these algorithms can be done by solving 1300~1500 rated problems having these tags. You should see editorials quickly(15 mins) to learn fast.

You need to solve 4 problems in div3(You don't need fast solving) or 2~3 problem in div2(highly depends on difficulty, if it's 2 problems, you need to do fast solving). I would recommend to solve 1300~1600 rated problem(you can tag search them) and try to solve them in 15~30 mins and see editorial after 30 mins.

Step 3: from 1400(cyan) to 1600(blue)

Rating 1600, or the title "expert", requires quite a lot of algorithm knowledge. You need to know a bit advanced form of former four, graph theory, sorting, and binary search.

Again, you need to study these algorithms, the methods are similar to that of the cyan, but search them in the 1500~1700 range, and see editorial after 25 mins.

Div3 is not an option after 1600, so you should do div2 contests to get to blue. Div2 has varying difficulty, but you should solve 3 problems or more by 90% possibility. You should solve two types of problems. 1400~1600 problems(easy div2c) with fast solving in 15~20 mins. 1700~1800(hard div2c) problems without that much fast solving.

Virtual contest is a nice way to practice from here. You can pick a contest that you haven't seen any of its problems, do a virtual contest, and check your score at this site. You should type contest number, score, and penalty if you did an educational cf virtual contest. Set rating to 1600, and if the rating increase is +, that means you did well.

Conclusion

As mentioned earlier, practice hard. This is the only common factor that experts have. And for whom reached expert, I'll write a sequel from expert to master soon.

Have you ever implemented a sort(not using stl)?

I am a master and I implemented my first nlogn sort algorithm recently.

Do you implement sort during contest time?

I am a one who gets benefit from ratism, but I hate it. Every newbie and pupils asking a question gets downvote. It's not because they wrote useless stuff. Even bug reports from them got downvotes. Please stop giving frustrations to them.

P.S. It would be upvoted, but green writing the same thing will be downvoted because of ratism.

Today, in lots of contests, hacks are unrespected. There are no hacks in 90% of div1 round. However, find someone's mistake is a nice skill. I suggest a hacker contest. 1. There is no score for the problem, only for hacks. 2. You are allowed to copy someone's codes into local. 3. 2 hour solving and 12-hour hacking, like educational codeforces. 3.5. You could hack the problem only if you solved it. 4. No pretests except samples, and no systest either. The only real test would be from hacks. 5. Score is 100*successful hack-50*unsuccessful hack. Of course, the contest should be unrated, because it is hackforces, not codeforces.

In a div2 only round, when the person with rating 2099 is the first, he jumps 200 points or more. However, if he is 2100, he does not get anything. Therefore, I suggest a gradual division boundary. First, we calculate the standing including every person that his rating could change and calculate the rating.

In div2, if his rating is lower than 2000, it is fully rated for him. If his rating is between 2000 and 2200, he would get ratingchange*(2200-rating)/200 ratings. If his rating is greater than 2200, he is unrated and doesn't include in the standings. Same thing for div3 and div4, with different bound. However, I think it should not be done in div1+2 separated round since 1900 could just join div1.

The codeforces round 610(Div.2) starts at 3 days after now, but the registration is only open for 14 hours. Is it intended? UPD: fixed

I saw something strange on rating. Example His real rating is 1882 and he is an expert, but the contest rating is displayed 1356, colored blue. Isn't it strange?

If there are these types of the contest, I think codeforces would be more interesting. 1. hackforces. This type of contest has absolutely zero pretest and weak system test. Some wrong code may get right if there is no hack. (Maybe no uphacking update would be good) 2. the G takes it all. The point of the problem would grow like 100 400 1600 6400 25600 102400. Exponentially. Who only barely solved g wins against who solved a~f in fast time. 3.Speed! The point of the problem reduces by half in 30 minutes. The first to the tenth solver of each problem would get the increased point. 4. The shortest round ever. Contest time would be 30 minutes, no reducing points for time, and LOTS of implementation problem! Who is the fastest typer in the world? Dear MikeMirzayanov

I am on round and I didn't submitted any solution. Is it rated?