Топ постов
Автор creep, история, 15 часов назад, По-английски

actually i haven't even visited topcoder website

but i condemn canceling (bela)russians and banning accounts, which is happening according to many residents of these two countries

i'm wondering why hasn't anyone posted about it yet? i can understand if nobody cares about losing their profile, but the problem itself is pretty interesting

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +142
  • Проголосовать: не нравится

Автор kpw29, 16 часов назад, По-английски

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 :)

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +234
  • Проголосовать: не нравится

Автор maomao90, история, 8 часов назад, По-английски

Slope trick is one of my favorite algorithms, so I have been considering writing a blog about it. However, there are already a lot of resources about slope trick, so I am not sure whether anyone would benefit from yet another slope trick blog.

If I were to write a slope trick blog, it would focus more on the intuition behind how I solve slope trick problems together with multiple difficult example problems (not 713C - Sonya and Problem Wihtout a Legend) where I show my step by step thought process. If you would like to see this slope trick blog, please upvote this blog. I will write a slope trick blog if this blog receives more than 100 upvotes. Thanks for all your support 👍

EDIT: Wow, already more than 100 upvotes in such a short time. See you in my upcoming slope trick blog 😉

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +191
  • Проголосовать: не нравится

Автор sid., история, 2 дня назад, По-английски
 
 
 
 
  • Проголосовать: нравится
  • +289
  • Проголосовать: не нравится

Автор chokudai, история, 30 часов назад, По-английски

We will hold AtCoder Beginner Contest 252.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +63
  • Проголосовать: не нравится

Автор KunalSin9h, история, 3 дня назад, По-английски

Yesterday I created problems using the Polygon system.

there is one Problem with two Parts($$$n \le 400$$$ and $$$n \le 2\times10^5$$$)

i would love if you see and solve the problems!

gym link : https://codeforces.com/contestInvitation/ef9be4fa454826fa1bcc152a56c098d0b5c260f8

UPD : I have also Uploaded Editorial, Link : Editorial

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

Автор shivangtiwari, история, 28 часов назад, По-английски

Introduction

Hello Codeforces,
I came across this problem a while back — https://cses.fi/problemset/task/1139/. Here the task is — "Given a colored, rooted tree, determine the number of distinct colors in each subtree of the tree". It is possible to solve this problem by flattening the tree and then using a binary indexed tree(now that subtrees have converted into subarrays). I will discuss an alternate technique to solve this, which can help in cases where it is useful to have the entire subtree as a set in a DFS call.

$$$O(n^2)$$$ solution

If $$$n$$$ were small, we could have stored for each node, the set of elements in its subtree. A DFS can be used to evaluate this, which will take $$$O(n^2log n)$$$ time and $$$O(n^2)$$$ space.

vector<int> color(n);
vector<set<int>> subtree(n);

void dfs(int i,int parent){
	subtree[i].insert(color[i]);
	for(int node : graph[i]){
		if(node != parent){
			dfs(node,i);
			subtree[i].insert(subtree[node].begin(),subtree[node].end());
		}
	}
}

The number of distinct colors in the subtree of the $$$i^{\text{th}}$$$ node is just the size of the set corresponding to it.

An Improvement

The problem with this technique is repetition. Each element occurs in $$$depth[i]$$$ different sets which is inefficient. For an improvement, we can consider the same idea used in heavy-light decomposition and union-find optimizations, which is "small-to-large merging".

We will use a DFS as before. To construct the set of all elements in the node's subtree, we will pick the child with the largest subtree set. Instead of making a new set for the current node, we will use the same set as the child with the largest subtree and insert all other children's sets in it. To avoid consuming extra space and time, we will use pointers to accomplish this task.

vector<int> color,distinct;
vector<set<int>*> subtree;
 
void dfs(int i,int parent = -1){
	int largest = -1;
	vector<int> children;
	for(int node : graph[i]){
		if(node != parent){
			dfs(node,i);
			children.push_back(node);
			if(largest == -1 || subtree[largest]->size() < subtree[node]->size()){
				largest = node;
			}
		}
	}
	if(largest == -1){
		subtree[i] = new set<int>; // new set for leaf node
	}
	else{
		subtree[i] = subtree[largest]; // largest sized child
	}
	
	for(int child : children){
		if(child == largest)continue;
		subtree[i]->insert(subtree[child]->begin(),subtree[child]->end());
	}
	subtree[i]->insert(color[i]);
	distinct[i] = subtree[i]->size();
}

Time complexity

Every time we copy an element over, the set it is now in will be at least 2 times larger than the set it was previously in. Hence the time complexity is $$$O(n log^2 n)$$$ (or $$$O(n log n)$$$ if we avoid using sets).

Thanks to -is-this-fft- for this

Conclusion

Here is my solution for the CSES task — https://cses.fi/paste/e75f5efc2e1cd2fc3c8a66/

This technique can be used in various other tree problems. Examples of such problems could be to find the most frequent element in each node's subtree or to find the pair with minimum difference in each node's subtree.

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

Автор bill_lin, история, 2 дня назад, По-английски

Bro why does this keep happening I just want to reach CM :(

how do i stop dropping every time im close to cm??????

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +140
  • Проголосовать: не нравится

Автор adamant, история, 34 часа назад, По-английски

Hi everyone!

You probably know that the primitive root modulo $$$m$$$ exists if and only if one of the following is true:

  • $$$m=2$$$ or $$$m=4$$$;
  • $$$m = p^k$$$ is a power of an odd prime number $$$p$$$;
  • $$$m = 2p^k$$$ is twice a power of an odd prime number $$$p$$$.

Today I'd like to write about an interesting rationale about it through $$$p$$$-adic numbers.

Hopefully, this will allow us to develop a deeper understanding of the multiplicative group modulo $$$p^k$$$.

Tl;dr.

For a prime number $$$p>2$$$ and $$$r \equiv 0 \pmod p$$$ one can uniquely define

$$$ \exp r = \sum\limits_{k=0}^\infty \frac{r^k}{k!} \pmod{p^n}. $$$

In this notion, if $$$g$$$ is a primitive root of remainders modulo $$$p$$$, then $$$g \exp p$$$ is a primitive root of remainders modulo $$$p^n$$$.

Finally, for $$$p=2$$$ and $$$n>2$$$ the multiplicative group is generated by two numbers, namely $$$-1$$$ and $$$\exp 4$$$.

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

Автор piyush_pransukhka, история, 6 часов назад, По-английски

Hi everyone,

Welcome to CSOC, 2022.

The topics for the first week shall be implementation and greedy algorithms.

Few resources have been hyperlinked below:



Nahh, just kidding, here are the links.

Expected outcome: Ability to write readable, non-repetitive and efficient code using the appropriate containers depending on context.

Mash-ups have been added for the above topics. They were prepared by Scythe, TARUN_0304, mankypanky, ayush567, mayank_singh_ and rahul_shrestha. Those found skipping interactive problems will be blacklisted. Top performers for every week will be added to the corresponding blogs.

If you have any queries, feel free to ask us in the comment section below. Since we won't be checking the comments regularly, please ping one of us in the comment by adding their CF handle.

See you on the leaderboard :)

Полный текст »

 
 
 
 
  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится