Top Recent Blog Posts
By rivalq, 3 days ago, In English

I hope you all liked the round. Please share your feedback in the comments section.

1682A — Palindromic Indices

Hint
Tutorial
Solution

1682B — AND Sorting

Hints
Tutorial
Solution

1682C — LIS or Reverse LIS?

Hint
Tutorial
Solution

1682D — Circular Spanning Tree

Hints
Tutorial
Solution

1682E — Unordered Swaps

Tutorial
Solution

1682F — MCMF?

Tutorial
Solution

Read more »

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

By awoo, history, 11 hours ago, translation, In English

1681A - Game with Cards

Idea: BledDest

Tutorial
Solution (BledDest)

1681B - Card Trick

Idea: BledDest

Tutorial
Solution (awoo)

1681C - Double Sort

Idea: BledDest

Tutorial
Solution (awoo)

1681D - Required Length

Idea: BledDest

Tutorial
Solution (BledDest)

1681E - Labyrinth Adventures

Idea: BledDest

Tutorial
Solution (awoo)

1681F - Unique Occurrences

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

Read more »

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

By creep, history, 3 days ago, In English

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

Read more »

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

By dawgzzzz, history, 9 hours ago, In English

I am in my 30's working as a musician. I was not good at math in school or science or standardized testing. In elementary school I was diagnosed as learning disabled and placed in special, slower classes. In the early days school was a laborious struggle for me. I'm not smart. I'm not gifted. In terms of programming, I took one java course in college and nearly failed it.

But here I am attempting competitive programming. This is my journey. I plan on documenting progress here.

For the past 6 weeks I've been practicing roughly 2 hours a day. I can solve 800 — 1000 level problems in 15 to 30 minutes. I don't know many data structures and mostly rely on brute force and implementation and some knowledge of the cpp standard library. I've been practicing mostly with USACO bronze level problems which I find far more difficult than the 800 — 1000 level problems I've seen on codeforces. Often these problems take 1.5 to 2 hours for me to solve. Often times I do not pass all test cases. Often times I have to look up the answer as I am completely stuck. I have difficulty understanding the problems. I tend to overthink and somehow add layers of complexity that don't exist. If the problem asks for the sum of time intervals, in my head, I'll try to solve it for the sum of contiguous time intervals. I don't know why my brain modifies the problems to make them more difficult. But that's something I am dealing with right now.

Read more »

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

By kpw29, 3 days ago, In English

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

Read more »

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

By adamant, history, 25 hours ago, In English

Hi everyone!

Let $$$R$$$ be a ring, $$$d_0, d_1, d_2, \dots \in R$$$ and $$$e_0, e_1, e_2, \dots \in R$$$ be linear recurrence sequences, such that

$$$\begin{gather} d_m = \sum\limits_{i=1}^k a_i d_{m-i}\text{ for }m \geq k, \\ e_m = \sum\limits_{i=1}^l b_i e_{m-i}\text{ for }m \geq l. \end{gather}$$$

In some applications, the following two sequences arise:

$$$\begin{gather} f_k &=& d_k e_k & \text{(Hadamard product)}, \\ f_k &=& \sum\limits_{i+j=k} \binom{k}{i} d_i e_j & \text{(binomial convolution)}. \end{gather}$$$

Today I'd like to write about the framework that allows to prove that both the sequences defined above are also linear recurrences. It would also allow to compute their characteristic polynomials in $$$O(kl \log kl)$$$, which is optimal as their degrees are $$$O(kl)$$$ in both cases.

Read more »

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

By maomao90, history, 3 days ago, In English

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 😉

Read more »

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

By ilia_rr, 2 days ago, In English
 
 
 
 
  • Vote: I like it
  • +179
  • Vote: I do not like it

By FairyWinx, 31 hour(s) ago, translation, In English

The following task is given: an array of integer $$$a_1, \ldots, a_n$$$ is given, as well as $$$q$$$ queries of one of two types:

  1. $$$a_i+=x$$$, where $$$l \leq i \leq r$$$.
  2. find out the number of indexes $$$i$$$, where $$$l\leq i\leq r$$$ and $$$a_j < a_i$$$, for all $$$j:$$$ $$$l \le j < i$$$. (Or humanly — the number of prefix maxima on the segment)

We want to solve this faster than for $$$O(sqrt(n))$$$ per request.

Let's consider an easier option when we don't have change requests. Then we can make a just Segment Tree, where a sorted list of prefix maxima is stored at the vertex, if our segment is the segment corresponding to the vertex of the segment tree. Then we should just make an algorithm, anological Merge Sort Tree, only we should consider the vertices into which we split the query from left to right and store the maximum among the previous elements on a suitable segment, and add to the answer the number of elements in the vertex larger than the maximum before, and then update the maximum.

It works for $$$O(log(n)^2)$$$ per request, as well as $$$O(n log(n))$$$ memory and time to build.


Note that this can be redone so that there are change requests. Then we only need to learn how to combine such lists and add value to them. And for this, for example, a persistent treap is suitable. Then we will store a persistent treap of all prefix maxima at the vertex. Then, when updating, if the vertex segment lies completely inside the query, then we will simply add the desired value to our treap (well, of course, we will push this value down). And to combine the lists, you just need to copy the values from the left subtree, and also select the desired suffix from the right subtree and copy it as well, and then combine these trees.

This already works for $$$O(log(n)^2)$$$ per request, but in this case there will be build for $$$O(nlog(n)^2)$$$, and, most importantly, memory will be $$$O((n +q)log(n)^2)$$$ at total.


Now the normal solution is for $$$O(n)$$$ memory and $$$O(log(n)^2)$$$ per request.

Let there be a just tree segment (the vertex $$$v$$$ has a left subtree — this is $$$v.l$$$, and the right one is $$$v.r$$$), then let us, for each vertex $$$v$$$, learn to count two values $$$cnt_v$$$ — the number of prefix maxima, if our segment is the segment corresponding to the vertex $$$v$$$, and $$$max_v$$$ is the maximum on the same segment.

Then we implement the function $$$f(v, x)$$$, which will count the number of prefix maxima of strictly large $$$x$$$ on the segment of the vertex $$$v$$$.

We have only three cases:

  1. If $$$v$$$ is a leaf, then everything is simple, you need to compare the value of this element with $$$x$$$.
  2. If $$$x\geq max_{v.l}$$$, then note that there are no exactly finding elements in the left subtree (since they are less than or equal to $$$x$$$), then we are only interested in the right subtree, that is, $$$f(v, x) = f(v.r, x)$$$.
  3. If $$$x <max_{v.l}$$$, then we are no longer interested in the value of $$$f(v.r, x)$$$, since the element with the value $$$max_{v.l}$$$ will definitely be among in the prefix maxima, so the number of prefix maxima on the right will be the same as and in the absence of a limit on $$$x$$$, and we already know this number — this is $$$cnt_v - cnt_{v.l}$$$, since we need the number of maxima on the right, and that's all except those on the left (logical, isn't it) (and it's not $$$cnt_{v.l}$$$, since in this case there may be elements less than $$$max_{v.l}$$$). So $$$f(v, x) = f(v.l, x) + cnt_v - cnt_{v.l}$$$.

This function works for $$$O(log(n))$$$, since each time we descend into exactly one subtree, and the depth of the tree of segments is just the logarithm.

It is clear that it is easy to solve the problem with this function, we can solve the problem, just like in the first case, only we will need to do not $$$lowerbound$$$ according to the list, but simply run this function. Building and the like is also trivial with this function. (All the subtleties can be found in the code)

implementation

Also thanks to Um_nik, who, in fact, came up with the last solution in a problem that boiled down to this and made it much more interesting)))

As well as examples of tasks for this technique 1, 2.

Read more »

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

By MikeMirzayanov, 9 years ago, translation, In English

With the help of some experienced and respected members of the community (thanks!) there was formulated a rule that allows a third party code to be used under certain conditions. Please read carefully the text.

The following text will go as part of a renewed competition rules. The closest contest will be held already on the updated rules. Thus, there are about two days for further details, if something is unclear.

Solutions and test generators can only use source code completely written by you, with the following two exceptions:

  1. the code was written and published/distributed before the start of the round,
  2. the code is generated using tools that were written and published/distributed before the start of the round.

Any usage of third-party code should not violate the right holder’s license or copyright. Remember that published code is not always free to use! At the request of the right holder, any code that violates the license or copyright may be considered as violating the rules.

All the changes in the code from exceptions 1) and/or 2) must be made solely by you.

If there are any doubts about the time of publication, possible collaboration etc., a participant will have to prove his/her complete innocence by presenting compelling and satisfactory evidence.

Currently, the only reliable proof is the presence of code on the Internet and the presence of the used edition in the cache of well-known search engines.

For example, this rule accepts the use of the code from the website http://e-maxx.ru/ if the code was written and published/distributed before the start of the round. With the help of search engine caches, it can be easily shown that such code doesn't violate the rules. Similarly, it is permissible to use the code from a book/article that was published before the contest. On the other hand, using team reference code (for example, prepared for ACM-ICPC World Finals) is not allowed if there is no reliable and objective way to prove that the code was written before the contest.

This rule doesn't loosen the rules about prohibiting of communication, discussion, or any other form of communication between the contestants on any topics about the problems during the round.

Read more »

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