Maybe this isn't news to some people here, but it was kind of surprising to me. These are the standings of cf round $$$1085$$$ (unofficial standings):

The account tickcross.y (ranked 9th officially) seems suspicious to me, going from around $$$1000^{th}$$$ place in div $$$3$$$ s to $$$9^{th}$$$ place in a div $$$1$$$ in just a few months. If I were to guess, I would say that this guy is a cheater, but okay there is a slight chance that it is some high-rated user messing around.

Also, I think that the account ChatGPT4.0 ($$$1^{st}$$$ place unofficially) is an account dedicated to testing $$$AI$$$ models, so I think that there is a good chance that this user used some $$$AI$$$ model (probably an expensive one for the time being) to $$$AK$$$ the contest unofficially.

I guess this means that soon the ratings here really will be close to meaningless throughout the entire rating range. The skills gained through actual effort won't be meaningless, but the actual rating will be, and that is kind of disappointing.

cf contests these days

https://www.youtube.com/watch?v=tiMIt5CAErY

First of all, it seems like the plagiarism checker isn't doing a great job at removing a good portion of the $$$AI$$$ cheaters. It is alright, but it isn't great. And as $$$AI$$$ tools get better (and cheaper), the amount of cheaters in the top $$$1000$$$, $$$500$$$ and $$$100$$$ spots in $$$div$$$ $$$1+2$$$ s will increase.

In my opinion, I don't see any way to reliably automate the removal of $$$AI$$$ cheaters. You pretty much need actual people to look at potential cheaters and determine if they are actually cheating.

Of course, the codeforces admins don't have the time or resources to do all of this by themselves (that is, look at all of the potential cheaters and then ban the ones that they determine are actually cheating). But the cf community actually can do this, and I think that some members would enjoy doing this. There is already a pretty good cheater database out there, and a lot of the cheaters in it have not been officially caught by cf, so the community is definitely capable of identifying cheaters that codeforces itself isn't identifying.

So I think that codeforces should give the community limited permission to ban users. This would have to be done in a careful way, though, like maybe there are $$$4-6$$$ trusted community members that can vote on banning a certain user, and if the vote to ban them is unanimous, the user gets banned. The admins wouldn't even have to do anything.

It doesn't have to be done that way, though, like another way to do it would be to just ban everyone in the current cheater database. If the database is carefully maintained, this would also not be a bad option, in my opinion.

My point is that if we continue to leave most (all?) of the banning up to the admins, a good deal of cheaters simply won't get caught. And since codeforces has an active community that cares a lot about identifying and banning cheaters, not using the community to directly assist in banning cheaters is a waste. That is all.

hopefully

“For God so loved the world that He gave His one and only Son, that whoever believes in Him shall not perish but have eternal life.” — John 3:16

I think that it would be convenient to have a feature that allows you to filter problems based on whether or not they appeared in a rated contest. Because problems that have appeared in unrated contests (referring to ICPC mirrors and such) are usually like $$$500+$$$ points overrated, so when you filter by rating, you basically have to ignore these problems.

I thought of this problem a while back, but I'm not sure if it has been created before. Anyway, I think that it is a pretty fun (possibly easier) problem, but I might be a bit biased. I'd appreciate it if you could give it a try and rate it. Also, maybe someone can find a simpler proof for it.

Problem statement:

A derangement of length $$$n$$$ is a permutation $$$p$$$ where $$$p_i \ne i$$$ for all $$$1 \le i \le n$$$.

You are given an integer $$$n$$$. You have to count the number of permutations $$$p$$$ of length $$$n$$$ that can be converted into a derangement using the following operation some (possibly $$$0$$$) number of times:

• Choose any two integers $$$l, r$$$ such that $$$1 \le l \lt r \le n$$$ and sort the subarray $$$p_{l...r}$$$ in descending order.

For example, $$$p = [1, 2]$$$ would be counted for $$$n = 2$$$ as you can pick $$$l = 1,\,r = 2$$$ and transform the permutation into $$$[2, 1]$$$.

Constraints: $$$10$$$ testcases per test, each consisting of a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$.

Examples:

$$$n = 1$$$ gives $$$0$$$, as $$$[1]$$$ cannot be converted into a derangement.

$$$n = 2$$$ gives $$$2$$$, as each permutation can be converted into a derangement.

$$$n = 3$$$ gives $$$5$$$. The only permutation that cannot be converted is $$$[3, 2, 1]$$$.

Vote:

Good problem

Mid problem

Bad problem

Hello everyone, I think that I might have a good idea to combat some of the cheating in online contests. Basically, we can split the rankings (and rating calculations) of div. 2 rounds into one containing users with $$$1600+$$$ rating and one containing users with $$$ \lt 1600$$$ rating.

Here is why. In div. 1 rounds, there are hardly any cheaters (yes, there are some, but they are few and far between). I think that the reason for this is because, in order to reach div. 1, you have to be a bit serious about competitions. Most cheaters aren't serious enough, as they get caught before they reach div. 1, so div. 1 is left with a bunch of honest participants.

But I think that this holds true for those rated $$$1600+$$$, too. Of course, the cheaters become more frequent as the rating threshold goes lower, but I think that finding a cheater expert is quite uncommon, too. This is shown by the standings of the most recent round: most of the cheaters in the top $$$100$$$ aren't even expert.

Another reason why div. 1 has so few cheaters is because div. 1 only has $$$900$$$ participants each round, so cheaters are much more obvious. If we split the div. 2 rankings like this, the cheaters above $$$1600$$$ would be much more apparent, as there would only be a few thousand participants with ratings above $$$1600$$$ (as opposed to $$$10k+$$$ with how the rankings are split now).

You might say that this is just handing the cheating problem to those with $$$ \lt 1600$$$ rating, but I don't think that this would be the case. I think that cheating below $$$1600$$$ would more or less stay the same, while cheating above $$$1600$$$ would go down a bit due to the increased visibility of each individual cheater (because of the smaller standings table). So the $$$1600+$$$ table would have very few cheaters.

This is not that serious of a post, but I feel like this could be a good way to make money. Maybe the people who scam foreigners in Europe can try this to see if it actually works well.

It would work by using the game of Nim. Basically, in the game of Nim, two players take turns removing a positive number of stones from exactly one of some number of piles of stones. The player who can't make a move loses. You can read about it here. Basically, if the $$$XOR$$$ of the number of stones in each pile is greater than $$$0$$$, the player who makes the first move, Alice, can always force a win. Otherwise, Bob can always force a win (because after Alice's turn, the game would transition to a state where the $$$XOR$$$ is greater than $$$0$$$).

So here's what you would do. First, set up a table near some popular site. When someone (Bob) comes your way, explain the rules of the game to them. Then gather $$$30-40$$$ matches and tell them to arrange the matches in $$$4-7$$$ piles however they want. Also, make a bet for some amount of money. Then you make the first move. If you know what you're doing, you will win in most cases, because the probability that the $$$XOR$$$ of the matches is greater than $$$0$$$ is very high. Furthermore, if you have an odd number of matches in total, the $$$XOR$$$ of the piles will always be greater than $$$0$$$, so you can never lose the game as long as you go first.

But this trick has more potential. If they get suspicious that you are making the first move, tell them that they can make the first move (or ask them if they want to flip a coin for the first move). The chance that the $$$XOR$$$ of the match piles is greater than $$$0$$$ after their turn is still very high. And even if it weren't, they would likely make a mistake somewhere along the way, unless they also know what they're doing.

If they lose and they want a rematch but they are suspicious of you, you can switch it around: now the player who makes the last move loses. Luckily, this variant (called a misère game) works almost exactly the same as a Nim game, so you still have a very high chance of winning.

Now if you're at your table alone, no one is really going to approach you. So you should hire a few people to come up and "play" a game with you every now and then so that you seem more approachable. Also, you should lose maybe half of the "games" you play with your employees so that the onlookers feel like they have a chance.

If you combine all of this with a personality that implies that you don't really know what you're doing, I think that you could really make a lot of money. Many people will think that they're smarter than you, but not many will be well-versed in the Sprague-Grundy theorem.

You are given a grid with $$$n$$$ rows and $$$m$$$ columns filled with zeros and ones. In one move, you can choose any cell in the grid and flip all of the bits in the adjacent cells. You do not flip the bit in the cell you chose.

For example, if you choose the cell $$$(3, 1)$$$ and then the cell $$$(2, 2)$$$.

0 0 0      0 0 0      0 1 0
0 0 0 ->   1 0 0 ->   0 0 1
0 0 0      0 1 0      0 0 0

You are given that you can make the grid into all zeros in some number of operations. Find the minimum number of operations to make the grid all zeros and output any minimum sequence of operations.

are they all bots or what?

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?

let us rejoice and be glad in it

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://mirror.codeforces.com/contest/733/problem/E

is the exact same as this one: https://mirror.codeforces.com/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?

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.