For this problem: https://mirror.codeforces.com/contest/1981/problem/D, in the case where $$$m$$$ is even, why is it true that the longest path with unique edges (but not necessarily unique vertices) happens when you remove $$$\frac{m}{2} - 1$$$ edges? I get that there is then a Eulerian path in the graph because it has two nodes with an odd degree, but how can we be sure that there isn't a path with more unique edges in the original graph without any removals?

This was the first round where a "smart" AI could've potentially been used for solutions. Aside from a cheater or two, everyone seems to have performed normally. There weren't a trillion C-E solves.

This just goes to show that the AI is just another possibility for cheaters. Other possibilities include telegram servers with thousands of users and masters who livestream A-E on youtube for fun. Even if the AI were 3000-rated, I don't think that it would significantly impact competitive programming as we know it. Keep in mind that competitive programming as we know it does have some cheaters.

I was reading this: https://cp-algorithms.com/data_structures/segment_tree.html (segment tree) and I noticed something crazy. The create function is unnecessary. You can just call $$$n$$$ update functions. This could actually save 1-2 minutes of typing. Maybe even 10-20 minutes if the segment tree is especially weird.

Edit: okay, I see how this is not optimal. It looks like this would have a time complexity of $$$O(n \cdot log(n))$$$, while the normal creation method has a time complexity of $$$O(n)$$$.

Hello everyone. The reason for this blog is that I haven't seen much talk about solutions to this type of problem here, so I'd like to provide a basic introduction of it to this community.

Let's first look at the naive solution to this problem.

The naive solution to this problem for an array-like data structure $$$A$$$ is, for each element $$$A_i$$$, iterate through the entire data structure, and if you find an element $$$A_j$$$ satisfying $$$A_j \lt A_i$$$, move onto the next element $$$A_{i + 1}$$$. If you don't, you have your answer, $$$A_i$$$.

This is how one might implement such a solution in python:

def find_minimum(A):
	for i in range(len(A)):
		for j in range(len(A)):
			if A[j] < A[i]:
				break
		else:
			return A[i]

Unfortunately, this works in $$$O(n^2)$$$ time. How can we optimize this? We can use dynamic programming.

For a $$$1$$$-indexed array-like data structure $$$A$$$ of length $$$n$$$, let's define $$$dp_i$$$ as the minimum element that appears in the substructure $$$A[i...n]$$$.

It is clear that the minimum element that appears in $$$A[n...n]$$$ is simply $$$A_n$$$. Therefore, our base case is $$$dp_{n} = A_n$$$. For indices $$$1...n - 1$$$, we can construct our answer using this recurrence relation: $$$dp_i = min(A_i, dp_{i + 1})$$$. It is clear that the answer to our problem is $$$dp_1$$$.

This works in $$$O(n)$$$ time and $$$O(n)$$$ space. A trick to reduce the space complexity is to notice that the recurrence relation doesn't need anything other than $$$dp_{i + 1}$$$ when calculating $$$dp_i$$$. Therefore, instead of creating a $$$dp$$$ array, we can simply update the value of $$$dp_{i + 1}$$$ using a variable.

Here is how you might implement this in python:

def find_minimum(cur_ind, A):
	return min(A)

That is all. I hope you learned something!

I thought of this problem today, and since I don't really have much problem-creating experience, I would like to hear the opinions of experienced problem creators on whether or not it would be a good div. 2 A. Feel free to try it if you would like. I have added the solution.

Problem:

One day, $$$n$$$ people are made aware of the website codeforces.com. Let's call this day day $$$0$$$. The day after day $$$0$$$ is called day $$$1$$$, the day after that is day $$$2$$$, and so on. If you randomly select $$$1$$$ of these $$$n$$$ people, what is the expected value of the absolute difference between the day they were made aware of codeforces and the day they created a codeforces account? If the expected value is too big to fit inside a 32-bit integer, output $$$-1$$$.

Input:

The first line of each test, $$$t$$$, is the number of testcases $$$(0 \le t \le 10^3)$$$. Each testcase consists of a single integer, $$$n$$$ $$$(1 \le n \le 10^6)$$$.

Output:

For each testcase, print the expected value. It can be shown that if the expected value is less than the largest 32-bit integer, the expected value is an integer itself.

for i in range(int(input())):
    input()
    print(-1)

You are given an integer $$$n$$$. Let $$$S$$$ be the set of all strings of length $$$n$$$ that contain only lowercase Latin characters. So $$$S$$$ will have $$$26^n$$$ elements.

You pick a random string $$$s$$$ from set $$$S$$$, then you pick a random index $$$i$$$ from the range $$$[2, n]$$$. What is the expected value of $$$z_i$$$, where $$$z_i$$$ is the value of the $$$Z$$$-function of $$$s$$$ at index $$$i$$$?

What is your least favorite type of problem / least favorite topic? I personally do not like graph problems.

I was solving a problem when I accidentally found this weird feature in python:

list1 = [1]
list1.append(list1)
print(list1[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])

You can append a list to itself. This code prints 1.

list1 = []
list1.append(list1)
print(list1[0][0][0][0][0][0])

This will print [[...]]. I guess it prints this to show that the list tunnels on forever.

It makes sense but it still seems like an odd feature. I can't see how this would be useful.

A master, as you probably know, is someone in the 2100-2299 rating range. I believe that I have made a pretty accurate estimation of the average IQ of a master, but I would like to hear CF users' thoughts on this. The wisdom of the crowd usually trumps the guesses of any individual person.

So please, add a thumbs up to the range in which you believe the average IQ of a master falls under.

IQ range:

$$$ \lt 110$$$

$$$110-119$$$

$$$120-129$$$

$$$130-139$$$

$$$140-149$$$

$$$ \gt 149$$$

For reference, the IQ score percentiles are roughly:

$$$100 = 50$$$

$$$110 \approx 75$$$

$$$120 \approx 91$$$

$$$130 \approx 98$$$

$$$140 \approx 99.5$$$

$$$150 \approx 99.95$$$

Hello everyone,

I have updated the rating distribution histogram for this year and I have created rating percentiles so you can find out how you compare against other active users. I define an active user as a user who has 1) participated in the last 6 months and 2) participated in at least 6 contests. The second condition is to ensure that the user's rating is stabilized.

Here is the chart (n = 89352):

clearer version

And here are some previous years' histograms: 2023 note: uses >= 5 contest participations instead of >= 6 participations. 2021 note: the author of this post wrote the script that creates very nice histograms so credit to him.

Some interesting facts:

The median Codeforces rating is 1143. The mean rounded to the nearest integer is 1205. The standard deviation is 378 rounded down to the nearest integer.

A rating of 1900 places you at the 94th percentile.

A rating of 2400 places you at the 99.2nd percentile.

The minimum rating for an LGM, 3000, is at the 99.93rd percentile.

55% of Codeforces users are gray.

If you want to see an exact rating percentile, go here.

If you want to see the rating data, go here. The data is in python dictionary format.

That is all, I hope this was interesting.