std::set is a powerful data structure: it allows to do insertions/deletions pretty fast, while also being able to access the smallest/biggest element. On top of that, you can also find the smallest element in the set which is greater than some $$$x$$$. If you can use it properly, it is already enough to solve some of the 1800-2000 rated problems.

On the other hand, what could ordered_set possibly offer? It can do 2 things (other than std::set):

• st.find_by_order(x) — returns the iterator of the $$$x$$$-th smallest element
• st.order_of_key(x) — returns the number of elements less than $$$x$$$ (i.e. index of the smallest element $$$\ge x$$$)

One of the basic applications of ordered_set would be counting the number of inversions of an arbitrary permutation.

For comparison:

Ordered set way

ordered_set<int> st;
int ans = 0;
for (int i = n - 1; i >= 0; i--)
   ans += st.order_of_key(p[i]), st.insert(p[i]);

Merge sort way

// too long to fit in 65536 characters

"There's not much you can do with this, other than count inversions", you might foolishly say, without having solved 2400-2500 rated problems using just ordered_set. Let's take 2064E - Mycraft Sand Sort as an example. In the editorial it says "blah blah blah, use dsu and segtree". But little does the foolish author of this problem know, is the existence of ordered_set (Intellegent is actually noob). As you can see in 306417199, it can easily be solved using 2 ordered_sets. Why use 2 different data structures when you can use a single one twice? Another example would be 2059E1 - Stop Gaming (Easy Version), which is also intended to have a long-implemented solution, yet still solvable using just the ordered_set, which will end up being a lot shorter than the intended code. There are a lot more problems than these which could be solved using ordered_set, it's just that I couldn't find worthy candidates for this blog(maybe you can help).

Another funny (but not really useful) application, is handling point update and range sum queries in $$$O(log\ n\ log\ A)$$$(where $$$A$$$ is the max element). It can be done by creating $$$log\ A$$$ ordered sets, and inserting each bit of the element being added to the corresponding ordered set. To get a sum in $$$[l, r]$$$, we can just count the number of elements between $$$l$$$ and $$$r$$$ for each bit, and sum everything up.

At the end of today's contest after solving A-E, I was like "yay, finally, 2200+". But as system testing ended, my submission for D got FSTed (I still don't know why). Moreover, It seems like it's the only FST for problem D in the entire contest, which makes it even more disappointing. I don't know how to feel about this, maybe I invented new ways to fail system testing?

Hello everyone!

In this blog, I’d like to share my journey into Competitive Programming (CP), along with some tips and insights.

Math to CP

Before I got into CP, I was a math Olympiad enthusiast. I participated in competitions like AMC, SEAMO, IMC, and others, achieving pretty good results—even without significant training. I think my logical thinking helped a lot.

However, I never made it to the IMO. In 9th grade, during my last math Olympiad, I had a disappointing result—I scored 0/50 on the written portion, where you had to prove your solutions. Around that time, I already knew about Codeforces, but the problems seemed too difficult, and I felt it wasn’t for me that time.

That’s when I decided to give Competitive Programming a serious try.

Transitioning to CP wasn’t that hard, since I already had some experience with basic C++. A friend of mine, C0deN1nja, helped me get familiar with the platform and how the system worked.

Unexpected Growth

At first, I thought I would converge somewhere in the middle of the Expert rank. Improving seemed tough, and I didn’t think I had what it took to progress much further. But to my surprise, I reached Expert in just two months—and then I began aiming for Candidate Master.

At the time, I couldn’t imagine becoming a Master anytime soon. It felt like a whole new level, and I thought I’d first need to become a consistent CM.

Then came Educational Codeforces Round 174 (Rated for Div. 2). I was solving problems as usual, until I reached Problem E. As I read through it, I instantly recognized it was very similar to 1686D - Linguistics. The only twist was converting “exactly” to “at most” using some mathy techniques.

Thanks to that familiarity, I got a bit lucky and performed well in that contest. I knew I’d likely drop in the following rounds, but it didn’t take long before I bounced back and regained Master.

I placed 22nd in Codeforces Round 1011 (Div. 2), and came close to reaching International Master in Codeforces Round 1012 (Div. 1)—if only it hadn’t been for Problem C1. (Who knows, maybe IM is not that far either?)

Tips(?)

I’m not the best to give advices—everyone has their own training methods. But I can give a couple tips which could be helpful to you:

• Don't practice topic-wise (unless you need to), if you want to improve your pattern recognition and avoid "idea forcing".

• Try many different ideas on a problem if stuck, this will be helpful to improve your intuition and it will be a huge experience boost. (I believe)

I was never afraid of learning new things, I think that's why I could reach Master so easily.

If you have any questions, feel free to ask them in the comments!

I managed to solve 2 problems on Codeforces Round 1004 (Div. 1), which may not be much, but it was quite frustrating to see that I was ranked 800/1080, while I was used to seeing something like 300/27K on Div. 2s. Is it even worth taking part on Div. 1s as a CM?

Hello, everyone!

I’d like to share a problem I came up with, which I believe to be quite unique (as I haven’t come across anything similar elsewhere).

I’ve created many problems for various platforms, but Timosh and Number Theory is the one I consider the most original. I hope you find it intriguing!

The problem is quite challenging — only 5 participants managed to solve it under contest conditions. If you’re looking for an even tougher challenge, there’s a harder version available: Timosh and Number Theory #2.

I’d love to hear your thoughts on this problem!

UPD:

from math import gcd
for _ in range(int(input())):
   a, b, x, y = map(int,input().split())
   g = gcd(a, b)
   a //= g
   b //= g
   L1 = a*x - a + 1
   L2 = b*y - b + 1
   R1 = a*x + a - 1
   R2 = b*y + b - 1
   if max(L1, L2) <= min(R1, R2):
      print("Yes")
   else:
      print("No")

from math import *

q = int(input())
for i in range(q):
    a, b, x, y = map(int, input().split())
    g = gcd(a, b)
    a //= g
    b //= g
    if abs(a * x - b * y) <= a + b - 2:
        print('Yes')
    else:
        print('No')

In the recent National Olympiad in Informatics in our country, there was a problem, that many struggled to solve, it was worth 16 points, for being "the hardest problem". I got a great result then, for solving it fast. However, I forgot the actual solution. Anyways, here is the problem statement, ignoring the stories and drama:

You are given 3 integers, $$$a$$$, $$$b$$$ and $$$n$$$. Your task is to find any integers $$$x$$$ ($$$x \ge a$$$) and $$$y$$$ ($$$y \ge b$$$), such that $$$xy \ge n$$$, and $$$xy-n$$$ is minimised

I remember using a $$$O(\sqrt{n})$$$ solution, but not what it actually was. Anyone has ideas?

I always wanted to help organize a contest, however I see almost every problemsetter is atleast a master. On top of that, I tried to create a problem statement in polygon, it was sophisticated, all those validators, chekers, thing called testlib.h. So, I want to atleast be a tester of a contest. Who can tell how to be one?

Hello Codeforces. Recently I faced a problem which I couldn't solve in an hour. It is as follows: Max Sum Subarray of atleast 2 numbers. Of course, for just max sum subarray it is Kadane's algorithm in O(n) time, however, I couldn't think of a way to solve for atleast 2 numbers faster than O(n^2). Any idea or a solution?

UPD: Thanks everyone. Now I know how to solve this problem

Hello Codeforces!

This is my first ever blog entry. My name is Timur, 15 y.o., from Uzbekistan. I joined Competitive Programming recently(even though in Codeforces for 4 years). From a young age i thought coding was fun, so I found out about competitive programming, and started out with Robocontest(uz). Solving problems was like a logic and an intuitive puzzle, if it's easy, you find solution immediately after reading the problem, if it's medium, you think a little bit and still find a solution(maybe not), but if it's hard, then you don't even try to do it. Same with Codeforces, never did a F|1800 task. It's crazy that some people can solve them in 5 minutes O-O. And all those data types, structures, algorithms. brrr. Anyways, I hope to get help and support from the community, and maybe meet some friends. :D