Hello everyone, these are some cf-related shower thoughts. I must warn you that some of them weren't thought of in a shower, though. If anyone has any ideas they thought of, I'd be interested to hear them.

Shower thoughts:

Pronouncing Euler incorrectly makes Euler Tour sound much more catchy.

It is easier to get a top 1000 placement in div. 1 than it is in div. 4.

Eggs are one of the most wholesome foods for you because, out of them, a whole chicken can be formed, which is not too dissimilar from a human. So they have all the nutrients you need.

Type 1 diabetics are always quick to mention that they have type 1 diabetes as opposed to type 2 diabetes. So people would rather be seen as genetically cursed than fat.

A big portion of competitive programming teaching talent is not having an Indian accent.

That is all.

Would you rather:

instantly teleport to the age of $$$30$$$ but with $$$10^9$$$ US dollars

stay as you are right now

(comments might have spoilers)

rock

paper

scissors

my choice

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

For an array $$$a$$$, $$$A = \max(a)$$$.

Could such a thing actually be made to be more efficient than normal sorting algorithms?

Just for reference, Chris Langan is considered by some to be the smartest man in the world. He got a perfect $$$1600$$$ on the $$$SAT$$$ amidst a nap, signaling an $$$IQ$$$ above $$$170$$$. His real $$$IQ$$$ is likely a bit higher. Terence Tao also has a very good $$$IQ$$$, and he is probably one of the most prolific math researchers today.

So competitive programming skill depends on $$$3$$$ major factors. Of course, there are smaller factors, but the three major factors (in no particular order) are:

1. $$$IQ$$$.

2. Practice.

3. Starting early.

Now these super high $$$IQ$$$ people are given $$$5$$$ years to get good at competitive programming, with a rigorous practice schedule. $$$5$$$ years is a long time, but the majority of people at the top have been doing it for longer. Combined with the fact that these high $$$IQ$$$ers aren't starting at a young age makes me doubt that they'd be able to get to $$$tourist+$$$ level in just $$$5$$$ years. What further makes me doubt this is the fact that those currently at the top are probably somewhat close to their intellect. So, while they will have the $$$IQ$$$ advantage, it might not be huge.

What does everyone here think? I'd appreciate a vote because more votes will produce a more accurate result (google wisdom of the crowd).

Yes, a super high IQ older person can become #$$$1$$$ with $$$5$$$ years of rigorous training

No, a super high IQ older person cannot become #$$$1$$$ with $$$5$$$ years of rigorous training

let us rejoice and be glad in it

There is so much talk about prime numbers, but there isn't much discussion about whether they're inherently good or bad. So let's see this. Prime numbers are:

good

bad

Would you rather:

Have $$$140+$$$ IQ

Be $$$6'4"$$$ or $$$193$$$ $$$cm$$$

Live until at least $$$200$$$ years old with good health

Teleport to the US with legal status and $$$30\,000$$$ dollars

Guarantee that after death, you will be at peace

yes

no

It seems clear that one day, possibly in the near future, tourist won't be the only one at $$$4000+$$$ rating. I think that this raises a bigger issue, though: there are too many LGMs. Of course, this is just an opinion, but I don't think that the word "legendary" should be thrown around this often. For example, wrt chess, Magnus Carlsen and Bobby Fischer are legendary. Hikaru Nakamura is very very good, but he is not legendary. Also, I don't think anyone would consider the current world champion Ding Liren legendary.

To be honest, the only person on cf with true legendary status might be tourist. In fact, we can tell that he is the only legendary one because he has his own rank. If any of the other LGMs were legendary, they would also have their own rank (or something like that to signify true legendary status). So maybe $$$3000-3999$$$ should have a different name.

Hello everyone. I came up with this problem today (I'm not sure if it is original, but I really hope it is), and I am just wondering if it would be a good div. 2 A.

Problem statement:

You are given an array $$$a$$$ of distinct elements, and, because you like hygienic things, you want to sort it in ascending order. Unfortunately, you can't run a normal sorting algorithm on the array. In fact, you can only perform one type of operation that goes like this:

• You can reorder the array in any way you want. But one constraint must be satisfied: the reordered array must be different from what it was before. For example, the array $$$[1, 2, 3]$$$ can be reordered to $$$[1, 3, 2]$$$, but it cannot be reordered to $$$[1, 2, 3]$$$. Note that, in a string of operations, you can return to previous states of the array. For example, $$$[1, 2, 3] \implies [1, 3, 2] \implies [1, 2, 3]$$$ is valid.

Because sorting the array was too easy for you, you decide to challenge yourself by answering $$$n + 1$$$ queries. The $$$i^{th}$$$ query asks the question: can you sort the array $$$a$$$ in exactly $$$i - 1$$$ operations? Note that the queries are $$$1$$$-indexed.

Input:

The first line of each test contains one integer: $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$, which denotes the length of the array. The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \cdots a_n$$$ $$$(1 \le a_i \le 10^9)$$$. All $$$a_i$$$ are pairwise distinct.

Output:

For each test, output $$$n + 1$$$ space-separated integers, the $$$i^{th}$$$ integer being the answer to the $$$i^{th}$$$ query. If the answer to the $$$i^{th}$$$ query is true, the $$$i^{th}$$$ integer is $$$1$$$. Otherwise, it is $$$0$$$.

For example, the answer to the array $$$1\,2\,3$$$ would be $$$1\,0\,1\,1$$$, because you cannot sort the array using $$$1$$$ operation, but you can sort it using $$$0, 2, 3$$$ operations.

I'd also appreciate some feedback if you have the time. If you saw this as a Div. 2 A, would you consider it a bad/average/good problem?

bad

average

good

Problem statement:

Unfortunately, your time has come. You have just passed away, and you find yourself standing face to face with God. Since you were a decent person in your life, God decides to give you a choice. He presents you with two options.

Option 1: Your consciousness is destroyed forever. You won't be able to sense anything. You simply do not exist anymore.

Option 2: You roll a fair $$$1\,000$$$-sided die. On $$$999$$$ of the sides, the word heaven is written. On the remaining side, the word hell is written. If the die lands on heaven, you experience eternal bliss and euphoria. If the die lands on hell, you experience eternal torment.

Which option do you choose?

1

2

It looks like Rust doesn't have bitset in its std. Is there any alternative?

This problem: https://codeforces.me/contest/733/problem/E

is the exact same as this one: https://codeforces.me/contest/1936/problem/B

except the former one is like 8 years older than the latter one. The former one is rated $$$2400$$$, while the latter one is rated $$$2000$$$. Does this mean that a candidate master today would've been a grandmaster 8 years ago?

what if we just force them to stay in prison until they solve a super hard $$$3500$$$-rated codeforces IQ problem? Maybe the worst criminals would have to solve a $$$3500$$$-rated IQ problem, but the more tame ones would only have to do like a $$$3000$$$-rated problem. This could make it easier for smarter criminals to get out of prison so that they can continue contributing to society. For the most part, unfortunately, dumber criminals are pretty much a lost cause. Solving a $$$3500$$$-rated IQ problem is no easy task, of course. It might take years for the average criminal to solve one.

Hello everyone. If it took you a short time to implement C2 last contest, can you please share your solution? I'd really appreciate it.

Does anyone know how to approach this one?

You are given an undirected weighted graph $$$G$$$ that is not necessarily connected. In this weighted graph, there is a subset of nodes called highlighted nodes. It is guaranteed that the induced subgraph containing these highlighted nodes is connected.

You are also given $$$q$$$ queries. Each query consists of one integer that changes the status of the node corresponding to that integer. That is: if the node is highlighted, it becomes unhighlighted, and if it is unhighlighted, it becomes highlighted. After each query, it is guaranteed that the induced subgraph of highlighted nodes will always either be an empty graph or connected.

For each query, you must find the maximum length of a simple path having the following properties:

1. The path's length is at least $$$1$$$.

2. The first node in the simple path is a highlighted node.

3. There is only one highlighted node in the simple path.

For each query, print the answer on its own line. If there are no simple paths with these properties, print "N/A" (without the quotes) on its own line.

Input:

Each test begins with two integers $$$n,\,m$$$ $$$(1 \le n \le 10^5,\,1 \le m \le 2 \cdot 10^5)$$$: the number of nodes in $$$G$$$ and the number of edges in $$$G$$$ respectively.

The next $$$m$$$ lines contain three integers $$$u,\,v,\,w$$$ $$$(1 \le u \le n,\,1 \le v \le n,\,-1 \le w \le 10^9;\,w \ne 0)$$$, indicating that there is an edge with weight $$$w$$$ connecting $$$u$$$ and $$$v$$$. It is guaranteed that for every pair of vertices, there is at most $$$1$$$ edge connecting them. Furthermore, it is guaranteed that no self-loops exist.

The next line contains a single integer $$$h$$$: the number of highlighted nodes. On the line after that, $$$h$$$ integers follow $$$(1 \le h_i \le n)$$$ — the original highlighted nodes.

The next line contains a single integer $$$q$$$: the number of queries $$$(1 \le q \le 10^5)$$$. The next $$$q$$$ lines consist of a single integer $$$r$$$, which changes the status of node $$$r$$$. It is guaranteed that the induced subgraph containing the highlighted nodes is always either empty or connected.

Output:

For each query, print the length of the longest simple path with the properties above. If no such path exists, print "N/A" without the quotes.

For this problem: https://codeforces.me/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 < 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.