E can be solved with 2-SAT

It would be interesting to see how cf rating correlates with a specific CF contest.

Thanks for the stream! I found A-C to be interesting and quite difficult.

What are some of your favorite problems at different ratings? Are there any that stand out?

I thought C was nice even though I bricked it for an hour

While I agree with the message overall, D1B (and I think D1C) today were very stress testable. It takes at most 5 minutes to write and I found your bug pretty quickly.

Crazy statistics though.

The fact that C is 1300 is crazy to me. We weren’t very worried about the D -> E gap and were very worried about the B -> C gap.

You are right. If carefully implemented and analyzed the editorial solution is also $$$O(nlogA)$$$. We were describing a different way to implement it.

This requires one more observation. First we fix the LSB to be at least $$$x$$$ for all numbers. It is always optimal to pick the minimal number at least $$$a[i]$$$ that has that LSB. You can precompute all of these values and their cost for every element.

This is true to get a number with the same LSB that’s different, you must first go through a number with a greater LSB which is smaller.

It's technically correct, but I can see why it is confusing. If you take an odd number from the $$$-1$$$ group, then the alternating sum after that would start with a negative. So that negative alternating sum would need to be $$$+1$$$ overall. However, the way we defined alternating sum is that it starts with a positive number, so we can just negate the value we need to reach and use the same term.

Does that make sense?

What is your failure probability? There are 40 pretests.

Auto comment: topic has been updated by 0mar (previous revision, new revision, compare).

There is a very clean solution for C. The editorial will be out soon

Yeah but the checker can't be written that way

It's just some knapsack dp. Comments were removed since they were during the round

I’m manually adding contests to google sheets. If you’re interested I can dm you a link

:)

Auto comment: topic has been updated by 0mar (previous revision, new revision, compare).

Can't you just compare yourself to your friends and others who you know aren't cheating and still get almost all of the fun from the competitive part?

Cool project, but I have a few questions/ideas.

1) Are there any plans on calculating a new community Elo, which would basically be your codeforces rating but only considering highly trusted users when doing the calculations?

2) I don't think you need tens of thousands of trusted participants in your database to get a good gauge of contest and problem difficulty. I would make the trust requirements as strict as possible. For example: allow only participants that are problem setters, testers, coaches, in person competitors, or similar. Give each person that is trusted one invite code to "vouch" for someone else. I think none of the filters you have for ranking are that strict, and that the strictest filter you have right now is that most cheaters won't be bothered to apply to be on this.

3) Under stricter verification rules, it is inevitable that a large amount, probably the vast majority, of legitimate contestants won't be able to be verified. I don't think that should be considered an issue. I would add an option (assuming you do add a community Elo) for someones community rating to be calculated without it affecting everyone else.

You initially have $$$1$$$ segment of indices of size $$$n$$$, and every time you split a segment of size $$$x$$$ into segments of sizes $$$k$$$ and $$$x-k$$$, you do $$$O(k)$$$ work. Let's "charge" that work to the first $$$k$$$ elements of a segment. Then observe that every time you charge an element, the new segment it is in is at most size $$$\lfloor\frac{x}{2}\rfloor$$$. Therefore each element can be charged at most $$$log_2(n)$$$ times, which gives a total bound of $$$nlog_2(n)$$$.

According to this blog: " Because of how Codeforces works, when a code gets TLE, it will rerun the code several times to see if the code is on the edge of the time limit. By doing this you increase the chances of your code passing significantly!"

Probably around 3-4 hours a day. I'm trying to do something similar to what lnsuyn did here. I'm open to suggestions though.

This market resolves before summer starts.

its fake money, its a social prediction website

Hi, thanks for the contest! Can you provide a proof for the intended solution? I can't figure out the details myself despite guessing it in the contest.

some details:

you can put 1 in the correct position immediately with EV 2, and you then try to put n in the correct position as well. Let x be the number of swaps it takes to fix n. We know that x = 1/2(1) + 1/2(2+x) -> x = 3 (either you fix n immediately or you ruin 1 so you have to fix it with two swaps and then you have to fix n). This takes 5 swaps, and you do this n/2 times

n > 3

One way you can show this is by showing that when k is even Alice can always maintain the sum for the maximum subarray sum (MSS). Hint: Consider the maximal b[i] in the range of the maximal subarray sum.

This would show that the answer is >= MSS, but you also have to show that it is <= to the MSS which is quite simple to do as well. Let me know if you want the details.

Setting Round 2 on November 15th would conflict with Pacific Northwest and Southern California ICPC Regionals.

$$$O(n^2)$$$ with heuristics passes. Should be possible to hack it though if anyone is interested.

https://codeforces.me/contest/2144/submission/338807854

Sure, but there’s no reason to believe that that heuristic should prevent it from being O(n^2).

it’s my code lol. Thats not the part thats n^2. Look at the next part of the code.

$$$O(n^2)$$$ passes for D https://codeforces.me/contest/2144/submission/338807854

My solution to D:

When $$$n$$$ is even:

Notice that the answer is of the form $$$-l_{i_1} -l_{i_2} -... - l_{i_{n/2}} + r_{i_{n/2 +1}} + ... + r_{i_n}$$$ for some permutation $$$i$$$. This means for every segment you either pick the left endpoint to subtract or the right endpoint to add. Swapping your choice of endpoint results in your answer changing by either $$$\pm(l_i + r_i)$$$.

Imagine starting by choosing the left endpoint for all $$$n$$$ segments. Now you need to pick $$$\frac{n}{2}$$$ right endpoints from segments to take. It is easy to see that it is optimal to swap segments with the largest $$$(l_i + r_i)$$$.

When $$$n$$$ is odd:

Using the solution for when $$$n$$$ is even, you can compute the answer trying to leave out every point in $$$O(n)$$$ time.

You can solve the problem using just this fact: Every even number must be at least the sum of its two neighbors.

First, lets solve the problem for the first number at an even index: $$$a[2]$$$. Notice that its always better to subtract from $$$a[3]$$$ first as that will affect $$$a[4]$$$, meanwhile subtracting from $$$a[1]$$$ won't affect $$$a[4]$$$. Now notice that when we move on to the next even number, $$$a[2]$$$ is satisfied. So again its better to subtract from $$$a[5]$$$ first.

In general, it is always better to subtract from $$$a[i+1]$$$ (where $$$i$$$ is even) before you subtract from $$$a[i-1]$$$.

I think the editorial proof works. Can you elaborate on what part you think remains to be proven?

A very simple $$$O(n)$$$ solution for C is to remove all edges u -> v except for the maximum edge. It's easy to see that this doesn't affect $$$F(s)$$$, and it also ensures $$$G(s)$$$ is zero since if there is a cycle of length $$$ \gt = 3$$$, then there must exist a node with more than one edge.

I mean he probably is a cheater tho was my point.

You marked this guy as a cheater in your screenshot above lmao

bro somehow relates it back to iq

Sure, the value comes from the scarcity, but this definitely changes things. It would be the only way to get very high ranks in the future (which is good for measuring your progress). I think that the best solution is something like that, and only giving official ratings for trusted participants (people that performed similarly well in in-person competitions). I haven’t done many in-person competitions, so I wouldn’t be verified, but I think most people wouldn’t mind not being verified at lowish ranks. And if you are master+, you probably have pretty good performances at in-person competitions. Like imagine a world where AI is better than tourist. This would be the only way to actually have accurate leaderboards.

I guess I was mostly considering GM+ ratings. If you're at that level, you should be able to do fairly well at in-person contests and I think it would be a bit sad if it was easy for users to cheat to that level.

Also at lower levels cheating isn't as big of a problem because their rank doesn't change as much (going from rank 6000 to 6300 is much better than going from 500 to 800.)

I think you can make rating changes fairly accurate by relying on:

1. Priors for problem ratings based on problem setters and testers

2. Some sort of weighted system considering users of second class of verification (ID but no in-person contests).

I think the only real solution (though not a perfect one) is to verify users based on in-person performances that are close to their current rating. Obviously, this means most users won’t be verified, so it might make sense to introduce different classes of verification.

It’s not hard to imagine someone cheating to an lgm level without any clear signs of cheating, which is why I think this kind of system is necessary.

Very minimal prompting. I basically gave it the statement, it came up with the O(n^3) solution and stated that it might be too slow. I submitted and got TLE on test 10. It tried optimizing the solution, but that didn't pass samples. I told it which sample it failed on, and it fixed it and then AC.

This makes no sense. Not only can O3-mini-high solve E and harder problems consistently if you prompt it well enough, but even now it doesn't seem like the number of cheaters is high enough to stop you from getting to any specific rank.

Also, codeforces rating shouldn't be your end goal, but it does provide a nice way of comparing yourself to others who you know aren't cheating and through that determining if you are progressing.

o3, which is apparently 2700 rating on codeforces, will come out in the next few weeks and then your 1800 threshold might become 3000 instead.

Stop taking rating so seriously, stop caring about cheaters, and just try to get better relative to yourself.

fail system tests

This will probably FST but https://codeforces.me/contest/2086/submission/313817555

Another way to see it is:

Letting black cells be 1 and white cells be 0, we want $$$\sum\limits_{(u,v)\in E}^{} (u+v) = 0$$$ (mod 2). It's easy to see that this is equivalent to $$$\sum\limits_{u\in V}^{} deg(u)*u $$$ (mod 2). So cells with an even count of neighbors don't contribute to the answer.

I don't understand why you need a formal proof that it never performs more than 2n operation. Isn't enough to show that it's optimal, because then it would never incorrectly stop when a valid solution does exist.

My reasoning for why its optimal is:

1) It doesn't matter where you insert a letter in the string, all insertions of the same letter are equal.

2) The order in which you perform operations doesn't matter, in the sense that performing one operation doesn't stop you from performing any of the other operations that you could before.

3) Any optimal solution must insert at least freq(c) — freq(a) 'a's, and freq(c)-freq(b) 'b's, so its never worse to insert them first (all it does is open up more options).

Obviously this isn't a formal proof, but I feel like it's intuitive that its optimal (unless I'm missing something obvious which is definitely possible)

But you don't have to prove that the number of operations is < 2n. You can just simulate and if at any point the number of operations is too much you can stop. It's still equally correct.

Why is it hard to prove correctness. If freq(a) < freq(b) < freq(c), you need to insert 'a' freq(c) — freq(a) times, so it's not worse to insert a. You never lose any options when you do this, and every operation is independent from each other. If you don't have any options left, you are forced to insert c. It feels fairly straightforward to me. Am I missing something?

The question is just implementation. The naive brute forces passes, my implementation is O(tn^3), but passes in < 80ms. The solution is also just uninteresting, there are no observations, optimizations, or clever ideas involved. It's just straightforward simulation of adding characters to the string.

Take a look at my submission for example. It's not particularly hard to write, but slightly tedious and boring.

My submission

Try:

1

17 16

Basically to decide whether to move extras to lane 1 or lane 2, you want to see which one of them has a multiplication that comes first after that point. All of the steps are easy to prove so I would recommend trying to do that. If you need help you can ask me.

yeah bur O(n^2) easily passes and its easy to implement.

yeah

My solution was just O(n^2) greedy. It's always optimal to either send all extra to lane 1 or lane 2. There are 4 cases,

Case 1: + x, in which case it is always optimal to send extras to lane 2.

Case 2: x +, in which case it is always optimal to send extras to lane 1.

Case 3: + +, in which case you just accumulate more extras.

Case 4: x x, in which case you either send extras to the one with the larger x, or look down the line to find the first x in lane 1 or lane 2 (similar logic if they are the same).

You are printing too many things for test case 7.

Just curious, what IQ do you think corresponds to each rating?

If anyone can cheat, the incentive for cheating is greatly reduced. A clear example is chess, where top engines are publicly available and far stronger than any human.

A key difference, however, is that chess has frequent in-person contests that ground ratings. For competitive programming to have a future, in-person contests would need to become more frequent. One upside of intelligent AI is that it could make writing problems for in-person contests much easier.

I think another reason many people feel sadness because of this news is tied to the value they get from being able to solve difficult problems. Right now, if you have an algorithm problem of moderate difficulty, say, under 2000, the best course of action is often to ask someone skilled in competitive programming. But if GPT becomes equivalent to a 2700-rated competitor, that role essentially disappears. The "problem-solving skills" you worked hard to develop become little more than trivia, as anyone could achieve similar results by prompting an AI model.

Alternative solution to C and D.

C: If $$$(x \gt y)$$$ swap $$$(x,y)$$$, set $$$A_x = 0$$$, and alternate between 0 and 1 and wrap that around on the right side until $$$y$$$ (not including $$$y$$$). Also do the same for the left side. Then $$$A_y = max(A_{y-1},A_{y+1}) +1$$$. This works because $$$A_y \gt =1$$$ because $$$y$$$ connected to $$$x$$$ and $$$A_x = 0$$$.

D: Very similar to the editorial, but I set up the dp differently.

Let $$$dp[i][j][b] =$$$ the minimum cost using to get to $$$(i,j)$$$ shifting the $$$i$$$th row $$$b$$$ times.

Let $$$stored[i][j] =$$$ the minimum cost to get to $$$(i,j)$$$ including operation costs and across all possible shifts.

Intitally, $$$dp[i][j][b] = inf$$$, for all $$$(i,j)$$$. Except $$$dp[0][j] = arr[0][j]$$$.

Transitions are as follows:

$$$dp[i][j][b] = min(dp[i][j-1][b] + arr[i][j],stored[i-1][j] + arr[i][j])$$$

$$$stored[i][j] = max(dp[i][j][b] + b*k)$$$ for all $$$b$$$ from $$$(0,m)$$$

In my code, I’m accumulating plushies starting from zero. If each plushy should initially start with 1, the first one would have 1, the second would accumulate 2, the third 3, and so on. However, I started with the first one at zero instead. To account for this offset, I’m adding 3 at the end instead of 2. The reason you would add 2 at all is because if the answer is always at least 2.

Alternatively, if you initialize all plushies to 1 from the start, you wouldn’t need to compensate for the initial zero. In that case, you would add 2 instead of 3. AC

yeah basically

You can still use the same in-degree idea to solve g2 with minimal changes. You can see my submission.

Or you could start by processing nodes with an in-degree of zero and increment the values of their adjacent nodes by 1.

Look up counting sort.

Why isn't the editorial's solution clean?

My understanding of the editorial’s argument is as follows:

First, we aim to maximize the digit at index $$$0$$$, and it’s clear that we need to choose a digit from the first 10 indices. The goal is to find the maximum value of $$$S_i−(i−j)​$$$, where $$$j$$$ is the index we are currently maximizing (starting with zero). In case of ties, we select the smallest $$$i$$$. We swap $$$i$$$ and $$$j$$$, and then repeat from the next index. This ensures that $$$s$$$ is maximized.

Is this reasoning incorrect, or is it just informal?

Can you give an intuitive explanation or proof for why this always works in <= n operations?

An alternative proof would be something like:

Wlog let y > x. lcm(x,y) >= y. Assume (x ^ y)/lcm(x,y)=k (where k is some integer).

k!=1, (x^y)/lcm(x,y) <= (x+y)/y < 2. So k = 0 which would mean x=y.

There is another way to solve Problem D by treating it as a graph problem. First, I will describe the straightforward $$$O(n^2 \log(n))$$$ solution, and then I will optimize it to $$$O(n \log(n))$$$.

Graph Representation

Consider each card from $$$1$$$ to $$$n$$$ as a node. An edge from node $$$i$$$ to node $$$j$$$ exists if there is a valid trade involving one of the three other players (Queen, King, or Jack of Hearts), allowing Alice to trade card $$$i$$$ for card $$$j$$$.

For a trade to be valid, it must satisfy two conditions:

1. $$$j \gt i$$$
2. $$$p[i] \gt p[j]$$$ for at least one of the three other players.

Naive $$$O(n^2 \log(n))$$$ Solution

1. Iterate over nodes from $$$N$$$ down to $$$1$$$.
2. For each node $$$i$$$:
3. Use a map to find all nodes $$$x$$$ where $$$p[x] \gt p[i]$$$.
4. Add edges from all such $$$x$$$ to $$$i$$$.
5. After constructing the graph, run a BFS starting from node $$$1$$$ to reconstruct the solution.

This solution works but is too slow due to the $$$O(n^2 \log(n))$$$ complexity.

Optimized $$$O(n \log(n))$$$ Solution

We can optimize the solution by avoiding redundant edge additions and unnecessary checks.

1. Use a Set for Efficient Tracking:
2. Maintain a set of unvisited nodes, initially containing all nodes from $$$1$$$ to $$$n$$$
3. Iterate over nodes $$$i$$$ from $$$N$$$ down to $$$1$$$.
4. Use the set to find all nodes $$$x$$$ where $$$p[x] \gt p[i]$$$. These are the nodes that can have edges directed to $$$i$$$.
5. Add edges from all such nodes $$$x$$$ to $$$i$$$.
6. Remove these nodes $$$x$$$ from the set, as they are fully processed and no longer need to be considered.
7. Once the graph is constructed, run a BFS from node $$$1$$$ to reconstruct the solution.

This solution is $$$O(nlog(n))$$$. The reason why this works is that every node that is removed from the set is already part of a path to node n, so there is no reason to add another edge to it. We only consider visited nodes as unvisited nodes don't belong to any path to node n.

If you have any questions feel free to ask.

My solution for C:

dp[i][0] = the maximum answer up until i given that you haven't skipped any elements so far

dp[i][1] = the maximum answer up until i given that you are currently skipping elements

dp[i][2] = the maximum answer up until i given that you skipped some elements and are now back to not skipping elements

Transitions are annoying but its pretty much just casework. The final answer is max(dp[n][1],dp[n][2])

To be fair, his method of cheating is very easy to spot. He has to submit many different times and each time the code/algorithm is very different.

Just read your proof, which is very well written and actually does make me appreciate the problem a bit more.

I still think that it should be rated higher than 1200, and is therefore misleading to use for your AI point.

I'm curious why you don't like 2007C — Dora and C++. I know it's a standard Bezout's theorem problem, but don't you need to first build some intuition or proof that you can apply it despite not being able to directly subtract. I personally liked it, but maybe that's because I haven't solved many Bezout's theorems (only the two on your list lol) problems so maybe that's a standard idea and I'm just unaware. It also seems like you mainly like adhoc problems. Would you agree with that characterization?

Update:

Also just solved 1979C — Earning on Bets. I personally really disliked the problem. The only reason its rated 1200 is because a large (maybe more than 50%?) of the people that submitted the solution completely guessed it. What are your thoughts?

Well I haven't really put in all that much effort. I've only solved 500 problems since I've registered, and I've only really taken it seriously in the last two months. Before that, it was like a casual hobby for me before hand. Let's see if I continue to improve in the future.

I don't think he used it to solve D. I though so at first, but you can see that this AI submission of D which got WA is quite different. https://codeforces.me/contest/2005/submission/281197540

https://codeforces.me/contest/2005/submission/281146546

https://codeforces.me/contest/2005/submission/281156553

It seems like you're implying that competitive programming is dying. While that may be true in some regards, it seems to me that the overall general interest in algorithmic problem solving is increasing.

You can see that codeforces.com on google trends has been steadily getting more clicks in the last 5 years.

The same is true for leetcode, which has exploded in popularity recently.

Do you agree that the general interest in algorithmic problem solving is increasing, or do you think that these two websites might not fully represent the whole story?

I mean I mostly agree with that. It doesn't change (or even respond to) my point that we could live in a world where a 2500 rating AI exists without it also being able of taking all jobs.

I think people could've made the same argument about chess. Even though it seems like on the surface a 2500 rating must actually be capable of reasoning at a very high level, what if it's process of solving is:

1. It generates 1000 potential solutions
2. It writes a brute force solution and stress tests them all
3. It submits the correct solution

I think that would clearly be something that is possible without it also being world-ending AI.

Did you test o1-preview which is supposed to have a rating of 1258 or o1-mini which has a rating of 1600+? I didn’t know that o1-mini was available now.Edit: nvm it is available.

While I agree with the general sentiment, isn't this similar to the situation with online strategy games like chess? Any player can quite easily cheat. All it takes is using a few engine moves when needed, looking at opening prep, or even just having access to the computer evaluation. You could even argue that as chess computers have gotten better, online cheating hasn't increased by all that much (I'm not sure if there are statistics that disprove this).

The main reason is that everyone knows you can cheat on chess.com or lichess. Your chess.com rating and your lichess rating hold very little value. There is not that much of an incentive to cheat because there isn't that much value to the rating itself.

With that being said, I just realized that there is a concrete difference between chess and CP. With chess, there are a lot of official FIDE tournaments where your rating actually matters. There isn't really an equivalent for CP. The only equivalents are in-person contests like ICPC and IOI which are pretty hard to go to or compete and are restricted to specific age brackets.

There might be contests added before (not likely) or after (very likely) the Div. 2.

What does division number mean?

The idea is basically that they mirror each other. They both don't want to color the root first but if there's an odd number of ? than Dora has to. You can watch Adaptatron's video for details.

Maybe make it that if your rating is 4k+ you can pick your rank or your rank is your handle.

What's wrong with your rating graph? I don't see your last few contests I think.

I also misread the n*m<=2e5 constraint, and I tried to code a bfs type solution starting from the center of the grid where we greedily visit cells in the graph that have the most subarrays containing them. I failed in the implementation, but is your solution idea similar?

Both your minX and minY are correct. For the maxX and maxY, there are two things bounding it: i and j, and the distance from the edge of the grid. So maxX = min(i,n-k) and maxY = min(j,m-k).

You can calculate how many subsquares will contain a cell by calculating the minimum and maximum possible x and y for the top left square of a subsquare of size k by k by that contains that cell . If you need more hints I can help you.

Can you elaborate?

Hi. I highly appreciate the efforts to identify cheating and believe that a large amount of cheaters are being caught under the current system.

With that being said, what are your thoughts on the following suggestions to both stop and discourage cheating?

https://codeforces.me/blog/entry/132580

I think this is only a proof that it is necessary, not that it is sufficient.

they changed the code.

Attached code for C doesn't pass samples?

Can you elaborate?

Can anyone help me figure out what the time complexity is for my solution to D?

I used recursion with memoization to solve for the answer. Let the initial size of the array be N. I start with the full array, and using recursion I get the answer for every possible array of size N-K, and so on. I store the maximum answer. I keep doing that until the size of the array is smaller than or equal to K. Then I find the median of the array. I have an map which stores the indices that I have removed.

I'm thinking the time complexity is O(N^2log(n)). My reasoning is that there are ~ N^2 subbarays of different sizes, and the sort takes log(N) time. Is that correct.

This is my code: https://codeforces.me/contest/1993/submission/274435465

According to Emory School of Medicine, "IQ is an abbreviation for Intelligence Quotient. “Intelligence,” as measured by IQ tests is rather narrowly defined. An IQ is intended as a predictor of the level of abilities a child will need to be successful in school. In the general population this score becomes relatively stable after about four years of age." So no, IQ doesn't generally change when you're an adolescent.

Here are two profiles that I think have inspiring rating graphs.

1. Bakry
2. adamant his username fits his rating graph quite well in my opinion

Isn't your whole point that you can never reach red because your iq isn't high enough. Or am I mistaken? So if you can solve so called "IQ problems" than why can't you reach red?

Also I think that your claim that you can't train for such problems is clearly ridiculous. Many GMs were stuck at Newbie for months and couldn't solve div.2 A-C. Has their IQ changed?