Hello, Codeforces Community!

I have a question for those problem setters of CF contests: How did you guys come up with such brilliant ideas?

Would really love to hear from CPers like awoo BledDest harsh__h

Back in my high school years, I used to train in competitive programming intensively. However, I made little progress and eventually failed to realize my dream (of becoming a gold medalist in Chinese NOI). I've done some self-reflections these days and want to give some suggestions to the new CPers in this community.

1. Don't compare yourself to others. Please always choose the training method that fits you best. For example, you may find yourself bad at solving constructive problems (like me lol) while some of your peers can solve them with ease. That's not the end of the world! The difference between you and them is probably just a fair amount of practice. And, you may have some advantages you did not even realize, too. Remember, everyone's way of success is different. Don't lose confidence!

2. Don't always look at the editorials. I used to solve a lot of hard problems (e.g div1EF) in high school. However, I didn't make any improvement at all by doing so. The reason behind this is that I was always impatient and almost never solved any of them by thinking independently. The process of thinking about a problem greatly helps to train your mind and is an indispensable part of training. If you are a new CPer, I would suggest you look at the editorials of the problem only when you don't know about the algorithms/data structures needed.

3. Don't cheat. When I was in high school, I used to discuss problems with others during the contest. I feel deeply ashamed about this even to this day. Bear in mind that rating is just a number, and you are here in this community to LEARN something!

Several months ago, I completely abandoned my old account and started to practice step by step with this new account. After 12 contests, I finally reached purple in last week's div2 contest. I clearly understand that this cannot even be called an "achievement" to some talented programmers. However, I still feel great because I know that I solved every problem in the contest by myself, and that makes me proud! Moreover, I gained confidence because I realized that I can also solve problems that I used to fear just with an appropriate way to practice!

I hope this post will give some insights to new CPers. And finally, about myself, I wish I could just be like my account name: See you guys in the ICPC World Final!

Hi, Codeforces Community!

Today I virtually participated in the SWERC2023 Contest with my ICPC teammates. We ended up solving 8 problems. Among all of those problems, I particularly enjoyed B. However, I noticed that the approach I use is very different from the standard solution. Let me share the problem with you:

There are $$$N$$$ countries, each country's (let it be $$$i$$$) flag uses $$$k_{i}$$$ colors (There are at most $$$M$$$ distinct colors in total). You want to "buy" some colors to paint all the countries' flags. If the colors you bought cannot paint a certain country's flag, you have to buy the flag. The cost of buying a flag and buying a color are all $$$1$$$. What's the minimum cost to make all the flags (by buying colors and flags)?

$$$N \leq 1000, M \leq 100$$$

The standard solution is as follows:

Build a graph that has $$$(N + M)$$$ nodes which represent the countries and colors. Connect each country to all the colors of its flag. Now we want to find the minimum amount of nodes to "cover" all the edges (for every flag, select itself or all of its colors). This is a classical "minimum vertex cover" problem. Since the graph is bipartite, the answer is equal to the maximum matching. We can either use the Hungarian algorithm or any max-flow algorithms (Edmonds-Karp, Dinic...) to solve it.

But I solved this problem by greedy:

We initially select all the colors available. Each time, we remove one of the color from our set and maximize the number of flags that are covered by the remaining colors. Add the number of flags that are not covered by our colors to the cost. And we use this cost to update the answer.

This approach works in $$$O(N^2M)$$$

However, I cannot prove the correctness of this algorithm. Can anyone give some hack cases or a formal proof of it?

Link to my code is Here

Hello, Codeforces Community!

Since my middle school days, I've been deeply involved in Olympiad Informatics, which sparked my passion for algorithms and data structures. Now, as a first-year computer science undergraduate, my ambition is to pursue a career in theoretical computer science (TCS) research.

I would greatly appreciate any advice from those currently engaged in TCS or combinatorial optimization research.

Is pure mathematics much more difficult compared to CP math or CP in general?

When I read Rudin's book Principles of Mathematical Analysis, for example, I feel like I am an idiot...

Hello, Codeforces community!

Today's contest was a nightmare for me. Let me tell you what happened.

First of all, I was 2 minutes late due to the networking issue. When I start the contest, 1000+ contestants already solved A. This made me extremely stressed.

I eventually calmed down, and passed both A and B in 15 minutes.

The next problem is C, which looks very trivial. However, I did not expect that I got stuck and could not figure out the solution in 20 minutes!

So I had no choice but to go and look at other problems.

My English is not that good. So I chose problem E, the one with the shortest problem statement.

I found it unbelievably easy and solved it in just 10~15 minutes.

Now I still have 75 minutes left.

I looked at D. Very easy, I can just use some STL (std::map and std::set) and binary search to solve it. However, it might took me a while (like 20~30 minutes?).

I looked at F. Seems not so difficult as well.

By the time, around 2000 contestants passed C. I thought "Maybe I overcomplicated the problem. I should be able to rush it." So I decided to work on C, which might be the stupidest mistake I made today.

I got stuck for another 40 minutes despite I already found out that x is equal to the greatest common divisor (GCD) of all the difference between adjacent elements.

20 minutes before the contest is over, I finally finished the code. However, since I initialized the maximum element of the array to be 0 (actually it should be -10^9 because there are negative elements), I received 3 WAs, which cost me lots of penalty.

I eventually passed C around 5~10 minutes before the end of the contest and then I had no time for D and F...

This is not the first time that I being destroyed by "easy" problems....

In Codeforces Round 903 (Div 3), I solved everything but C (which is a 1200 rating problem).

In Codeforces Round 907 (Div 2), I solved problem F (2000 rating problem) but failed to solve C (which is a 1500 rating problem), again.

In Codeforces Round 910 (Div 2), something even crazier happened. I solved D (1900 rating problem) and E (2200 rating problem) while failed to solve both B (1500 rating problem) and C (1700 rating problem).

So I am just wondering, what should I do to be good at solving Div2 B and C?

Also, I observed that there is an extremely big difference between OI and Codeforces/ICPC. I actually had some OI backgrounds, but it seems that my past experience can't help me do well in CF contests, at all.

Sincerely, I am looking for your suggestions (especially those who also had problem solving trivial problems before, or those who did OI in high school).

Also, I hope someone can help me with the writings of this post. I am pretty bad at English, as I said.

Thanks in advance!