Absolutely agree. This was defintiely a thing that stopped me from competing at some point (after LGM, but before comfortably above it).

(Nowadays is different and I just give up, I recongize my skill issues due to AIs and unrelated to AI.)

Even if just the max rating may seem to make it too easy, we can also consider variants like

(1) requiring max rating + epsilon (50,100,150 or 200), or

(2) stayed there for at least 6 contests

Then you earn the colour for a lifetime.

You are right, I didn't realize even maintaining the sizes are much more difficult than it seems. It felt like it can be done (1. maintain subtree sizes at every heavy chain top, 2. a light edge p-v (p is the parent) is rebuilt if subtree size of v is 2* any previous rebuilds on p, I didn't check all the math carefully), but I am now convinced the random is easier to code.

Also feel like this is extremely close to applying BBST (Treap, scapegoat) directly on HDL tree, but I cannot quite draw the parallel.

You can also just rebuild when a light children exceeded 2/3 in size. The random part doesn’t seem necessary at all. It looks all analysis are identical.

Actually, with the way you put it in the latest comment, I probably agree with more things than disagree.

that the umbrella of talent in general is used as a scapegoat when you don't progress

I agree, in the sense that among the things I believed to be somewhat related to Codeforces rating as a factor, actually not much are conventionally attributed as "talents" (even though I would call them talents). I feel in general that reasons you hit a roadblock isn't that "you are bad at something", but rather "you have not done enough good things", so in that sense any scapegoat is probably wrong.

I don't think you should conclude that your career is over the moment you hit a roadblock. If so, I probably would have quit powerlifting at least 10 times by now (including a period of 1.5 years when I got absolutely zero improvement at all on squats and deadlifts; my coach had a similar experience that lasted 38 months) and CP 2 or 3 times by now.

I think this is a fundamental difference of how I view things. For me, it is totally ok to quit. If the utility calculation doesn't line up, quitting is correct. There are frequently more important things to take care in life. But for me this never means I will quit forever. Life situation and utility calculations always change. Besides, every time I return to CP, I usually carry a fresh perspectives. The previous roadblock are generally not an issue anymore ( or rather, a big reason why I return is I believed I have found a solution to my previous roadblock). I quitted probably 3 times before LGM, and at least 3 more times after, but I am still active now.

I also do want to re-emphasize the placebo point — worrying less and just being the best version of yourself that you can leads to better results

That could be one way, but I will share my personal view of how I handle this. I always view myself and long accepted myself as not having the best (conventional) talents. I may be reasonably talented, but likely not the "average amount of talent" you would expect at the top of the Codeforces leaderboard. It doesn't worry me, but rather, it just ends up being knowing my own strengths and weaknesses correctly.

I feel very weird with this blog, because the literal meaning is likely defensible, but all of the soft implications are wrong. If you ignore all the soft implications, the blog said literally nothing (IQ is not that big of a factor, sure, I can easily name lots of factors that are equally or more important)

Implications I don't like

(1) You cannot cope.

Let A = Things you cannot control B = Things you can control C = work

Then I will use the following model: Codeforces Rating = A + B + C + $$$\lambda$$$ ABC

IQ is just one of the many things inside A. Somethings, not called IQ, but have effects very similar to IQ on codeforces -- rational backgrounds, scientific methods, statistical methods, planing and decisions making, time management, ability to focus, resources to focus, emotional control, good memory, general state of mind and health, inherent randomness by relying of experiences in past successes, inherent randomness by resources you read or problems you practice on. Some of these are inside A and some are inside B. The general idea that IQ is a cope could be defensible, but can you say that to all of these factors? If someone may have ok IQ, but bad at some or lots of these (things that are in A), they might be able to correctly conclude that they will be bad at Codeforces. The exact attribution can be wrong, but they do have something that is genuinely out of their control and prevents them from doing well on Codeforces. Then, why is it an issue that they just call them IQ? Does it matter that I cope without being semantically accurate?

(2) Just put in more work bruh

Softly implied from "Time /self-deception" and your model.

No one maximize their Codeforces rating unconditionally.

Given your (totally not what I would use, but same conclusion) model

Codeforces Rating = IQ + work

If your objective is to maximize your Codeforces rating, yes, you can ignore the IQ component.

But that is not how sensible people think. People think in utility, for this amount of work, you get higher Codeforces rating, how beneficial is that to you? You don't maximize Codeforces rating just because you can. If you are doing Codeforces for fun, you don't need to maximize it this hard.

Depends on your social situations and where you live, the same Codeforces ratings can range for having absolutely no practical utility (for fun/self accomplishments) to some fun (get to go to competitions, ICPC, meet great people) and sometimes genuinely life changing (lands you very good jobs, gets you into great universities, or just give you enough experiences to excel in other parts of life).

Even in your (wrong) model, the same amount of work would have very different utility outcome, depending on your IQ. Putting in more work has a cost, you cannot assume the work factor is something that you can fully tune to infinity.

Feel free to comment if you think (1) and (2) is not what a reasonable person might take away from reading this blog.

Also see https://en.wikipedia.org/wiki/Sorting_network#Zero-one_principle, this is the first time I saw the trick documented. To me, I view it as an extension of the binary search technique. They have the same flavor, generally applies the same way (if you look deep enough)

I think the methodology is good and I would consider this actual finding. It is just 50 samples may really be too small (might be report a t-stat or other statistical tests as applicable)? Also may be interesting to see a correlated sampling of how the same person rating changed in the two eras, though this definitely biased towards long time competitors.

Well I assume this post is because you don't know what 3000 is in scale, so this isn't really a reply to this post anymore but just whatever I wanted to say. Let me describe a few things:

I reached 3000 in about 2 years, but I solved 4 problems on the first contest (1900 rated).

There might be an implicit assumpttion in that working very hard (say full time, or even 12 hours a day 6 days a week) AND being talented is enough to go from just starting ->3000 in a year. Well, those are very good, and you will hit LGM eventually (though I also see arguments for getting stuck at 2700/2800 with this), but to reach 3000 in one year you need extremely substantial edge, find and discover something that all LGM haven't, and do it on a daily basis.

Oh and I hope you got enough material resources (to your current standard of living) to last while you commit all of the time to Codeforces.

See blog if you want an example

It doesn't work like that. If your DS is not better in any single way, why should anyone know about it?

If you think the ideas about the DS is cool and what not, you should clearly say why, and what it is different. Make it clear, unquestionably clear that it is the focus of the blog. You cannot just write down the definitions and expect readers to help you discover why it is useful.

Besides the fact that you invented it, why should the readers not know about any of the following trees first? Red black tree, treap, implicit segment trees (mergable), scrapegoat tree, general B-tree, 64-nary or similar tree, splay, AVL tree, or leftish redblack tree or aa tree(Reasons: all rounded good tree, short and simple mergable, saves 1 log when doing small-to-large like merges, shortest BBST in code, theoretical slight generalisation of red black tree, best way to make use of AVX, good amortizations when accesing the same node, best if large number of reads due to near constnat depth, nearly identical with red-black tree but shorter and less cases)

Where is the educational part besides that I know you write a new BBST?

Edit: To be clear, you don't need to make a better DS -- it is impossible to, red-black tree is very good, but you need to give ONE (1) reason that it could be better in at least one situation.

Calling complete BS, bannable in fact. Convince me why this one is useful in a single situation against the 1e7 other BBST options. The better you polish the blog withou real content, the more you waste everyone's time.

You can't just mention segment tree and treap and pretend you have proposed a better option.

I don't understand is this intend to be a lower bound or upper bound.

The expressions of taking it as a product is very suspicious. It is wrong for both upper bound or lower bound. For lower bound, you cannot assume the opponetn follows your strateyg of always guessing near the posterior mode. For upper bound, you cannot assume uniform prior (see comment above).

If you always guess near the posterior mode (which is what the product implies using only what you said) there are very nontrivial correlations and your bound is definitely wrong.

Let's make useless guess for $$$k$$$ rounds, then with probability at most $$$1-\frac{1}{k}$$$, the $$$E_p$$$ is within $$$(p-x,p+x)$$$ (approximateely, weird things happen when p is close to 0 or 1) where $$$x = g(k)/\sqrt{k}$$$ where $$$g(k)$$$ inverse cdf of normal, roughly $$$g(k) = \sqrt(log(k))$$$. I am too lazy to formally combine the expression or deal with $$$p$$$ being close to $$$0$$$ or $$$1$$$, but you see that another $$$O(1/sqrt(k)\epsilon)$$$ that partitions this desired range would be sufficient. Optimising (only caring about asymtoptics) $$$k + \frac{1}{\epsilon \sqrt{k}}$$$, you get something like $$$\epsilon^{-\frac{2}{3}}$$$ times log like slow glowing factors. (Carefully bound the exponentail taiil for a formal proof, ask LLMs I guess)

The converes is asymtoptically clear, well, intuitively. Using only $$$k$$$ samples, it is not possible to reliably distinguish any probability $$$p$$$ between $$$(p - c\frac{1}{\sqrt{k}}, p + c\frac{1}{\sqrt{k}})$$$ for some small constant $$$c$$$, so anything in this region is basically just random guesses, so we can assume we need this length divided by $$$\epsilon$$$ guesses.

If you still want to go for constnat factor problem, you should probably set explicit values and set a heuristisc contest typed problem. I am not believing it is particularly interesting though.

this is wrong conceptually because the problem statement says that p is sampled adverserially, not just uniformly over [0,1]. You should theerfore assume a clever adversary that takes p to be some werid distribution, which likely incorporates your best strategies.

For this reason, it is also not easy to run a simulation. You need to also train the adversary weights during it. It is closer to solving a probablistic game.

It would be great if you can further clarify, and list out the current variants that you know are $$$O(\log n)$$$ vs types that you proved are $$$\Omega(\log^2 n)$$$. I simply haven't studied segment tree beats techniques that much to make such a summary, but if it is relatively easy for you to do I would really appreciate.

There should be some clarification of some general threshold where x% of the same submission has to be accepted before rejudging. I think there is some balance between “something wrong/slow with systems” vs “solution works most of the time” (which if FST should be final).

Can you state clearly which segment tree beats problem this hack is for? Does this work for the simplest segment tree beats (Range Chmax, Range Add, Range max), or it only fails for more complicated beats setup? Does this work for point change only?

Yes I did check it, I know that it cannot provide a linear solution as written, but it was somewhat incorporated into the third log of the solution here.

Even making the idea work for the third log was already a pain and needed lots of additional ideas (which was the ideas I had for O(n log log n)) before this operation is able to shine.

That was really surprising to me, considering I also wrote a preprint for it. Well, being 17 points only is a good reason to ignore (though, with my particular scores on solving C, it actually make sense for me to consider this problem instead of a 18 points one)

btw I forgot to update with you/your co-authors , but here it is preprint/paper

I don’t have anything important to say regarding the topic but -12 isn’t massive, it is doing fine.

Ensure that everything is correctly and clearly defined. Also there are lots of typos, grammatically awkward sentences. A little bit is fine but this time there are so many that it is very hard to understand what you meant.

If you have written it in another langauge, simply translate it. If you are far more comfortable writing in anotheer language, write in that langauge then translate. Or, ask LLM to fix up the entire post would be much better.

This is unreadable. Please use an LLM to translate

EDIT: That aside, after actually understanding what you meant (with an LLM) , this seemed exceptionally useful

Adding some context as someone who had some understandings on randomness due to academic research in combinatorics: Generally, it is not the fact random can be applied to some situation is hard (at any situation you can think about random), but more about the ability to correctly analyze the probability of failure. To learn this, you probably need to learn at least the following tricks (1) estimation of (1-x) by e^-x , (2) some approximations of binomials by the appropriate normal (central limit theorem), (3) Markov (first moment method), Chebychev (second moment method), and Union bound. In a sufficiently hard problem that involves random (say >= 3000), you definitely need to know the difference between an algorithm that fails 1e-2 (which cannot pass) and an algorithm that fails 1e-7 (likely pass unless super unlucky).

a few things I didn’t see mentioned: (1) Schwartz–Zippel lemma (also see random verification of matrix product), seems to be the most advanced random method applicable in CF (2) estimation of error of Monte Carlo algo, see the things mentioned above for bounding/approximatiin (3) Random 64 bit xor hashing. This is generally much more clean and nice to illustrate ideas of random hashing (4) some algorithms really needs to be random because we don’t know better about the underlying structure , such as finding a primitive root (worse bounds if not random), also see Miller-Rabin

Ok you are right, sorry for that. Every time I encountered that I just assumed it doesn’t cost penalty without checking (I think I encountered this at least 5 times). That sounds like a pretty serious bug to me.

I also know that in contest managements, rejecting solutions and skipping solution are two different buttons, I was expecting rejecting solution costs penalty and skipping does not.

That is exactly why the first submission is skipped. It doesn’t count towards any possible penalty. This is only an issue if your first submission isn’t skipped.

This generally does happen many times when codeforces is in heavy load, but if it is skipped correctly nothing to worry about.

Adding to this: Anyone that improved fast didn't know they improve fast -- as in they cannot prove something they did actually improved fast. If they can do that, they have such a deep understandings of learnings that they should be looking at a rating of 3500 or higher. If they can give advices for every person that works for everyone, they should be looking at a rating of 4000. There are so many things that I don't know are actually useful for me, they are mostly educated guesses.

This doesn't mean that they didn't improve fast, this just means that (1) It is hard to attritbue why (2) It is a mix of something that is done well and something that is not well, and the good is more than the bad (3) It could be completley upto luck that it aligned with what they need/have

Another note is that my IMO background isn’t actually that high. I believe my IMO background as is, would translate to a rating of about 2500 in CF. So it is possible that anything before 2500 are direct translation (with some effort), but rating ranges from 2500-3000 are real gains above and beyond what I already know.

During those times, I simply go to problemset in codeforces, select a rating range, and solve in order. I didn’t do anything more sophisticated, and it is likely that I can absorb more easily just from my background.

It was generally a simple cycle that goes like this: solve problems, think that I am at a level X, do rated contest and realize this statement is false because of Y, do something related to Y. Repeated this a few times then I ran out of Y. That was the 2600 stage.

So you see it is extremely basic idea that is sufficient for 2600 for me, but that is also because I had a lot more time available at that point (tbh, wasted some fo them)

There are so many ways to get good. Every slightly sensible optoin is sometimes correct. It depends on what yuor mood is, what are you weak at, what are you foundations, how rustly are you, how much time you are able to commit, how focused can you be during work, whether you enjoy solving hard problems or easy problems or enjoy virtual contests. The answer to all of your questions for me have personally changed from yes to no repeatedly. Believe in yourself that if you believe (with reasoning!) something you did is right, then it is right.

Natural talents also include knowing how to improve quickly, the general "intelligence", the ability to strategically optimise for anything using all optoins available. It does not only include matheamtical intuitions or how fast you can absorb actual materails, or how you can visualise stuff -- the commonly said kind.

The next fundamental currency is time, (quality) time that you can fully invest into improving. I alawys wish I can have more time to improve but I have a job (more specifically, it is stupid to quit the job for competitive programming), and that had been an extremely serious roadblock for me. That means I need to be fundamentally extremely efficient in order to get anything done in competitive programming. If you have a lot of time to spend, our considerations would be totally different.

Finally, here is what I am doing recently: I am solving many problems vastly below my rating. Almost the first advice anyone would give to newbie is to solve problems above your rating. Well I am LGM I get to doubt and break fundamental principles. Because of this, my answer (at current moment of time) to all of your questions are obvious: Don't bother upsolving, they are way too hard. Don't bother solving problems if you don't have any clues -- they are way too hard. A special exception: if a problem is within the your typical rating range but you failed catastrophically -- just read editorial, it is probably a huge blind spot that you have missed for a long time.

But once again, I made this deduction and evaluation because I know my own strenght and hidden, unique-to-me abilities. I believe everyone will have to find their own set of parameters at a level of late red to LGM+.

Also how did I reached LGM? I literally just solved enough problems (roughly 5000) + IMO background + math degree background.... All the struggles and strategizing in my own pre-lgm days are basically non-existant compared to the current things that I am thinking.

Here is a implementation only solutin for problem F and avoids any thinking.

Use a reroot-able tree hash. It suffices to compute all the desired tree hashes and compare it with the hash of the tree rooted at each point.

Kotlin submission 352762369

Sorry, I don’t know the context in which this is said, but please clarify how everyone at the level of 2500 is perfect in knowledge and implementation? That does not even begin to sound right to me

for problem D: small to large merging can be done in O(n log n) (and is recommended in general). It doesn't seem like you really need the flexibility of a map here (which is the only reason to need a O(n log^2 n) merging, aside from ease of coding outside of prewritten code.)

This may be extremely unrealistic, but I really do hope onsite finals could happen.

I am still very sad that the exact year I am capable to get into finals is the (almost) exact year onsite finals got discontinued. Getting into finals feels a bit without substance now...

my solution (small to large based) counted 26 additional lines for D, 10 of which is declaring empty arrays and reading the graph, only 1 line have any substance.

inclusion-exclusion (i.e. mobius function or the like) is assumed.

For the main part, I directly do small to large. You need to be able to add $$$(size[t]) * (totalsize[t] - size[t])$$$ for each $$$t$$$ from $$$1$$$ to $$$n$$$, and perform point update. This can be handled like segment tree beats historic sum. (For each entry, store when was it last modified. When you modify a value, process the backlog of this old time stamp to the current time). Complexity is $$$n ln n log n$$$ (log from sieve and from small to large).

Not only is repalcing all X with Vs much needed, the fact that you have to prepocess the string to get what you want is also pretty anonying. If your only concern is the second "hard" part, then you can simply maximize the number of "01" substrings (neglecting the first very easy observation). Another place is allowing the available counts > number of '?', that alone added 10 lines for no good reasrons.

I have heard of a much more direct solution using convex convolution (presumably merged small to large), Unfortunate, with some thinking the code would probably be equally long, not to the only "hard" part but to the above reductions.

Another problem is that it is placed before problem E.

Thank you for that. As with the comment on your blog, I also don't have a good view of "how verbose/how concise" something should be, but I think that generally (1) predict the level of readers that would be most interested in it, (2) make it good for yourself, are both very reasonable choices to me. For this particular topic I predict >= LGM.

ALso, personanly, readers can skip the proofs easily (as long as the statement is clear / you explain any essential thinking additionally), so adding proofs in general isn't that boring -- just ensure people who skip and don't both have good experiences.

I have "read" this but ultimately I would like to comment that is too long to fit in the comment section. It became a seperate blog: https://codeforces.me/blog/entry/148691.

Regardless, the content is defintely good. It saved me some thinking and enable me to quickly find the relevant references. As for being less wordy, I think doing feels the easiest to read (to yourself) is the best option. I prefer very abstract and concise mathematics and there is no way you could or should even aligned it to me. Though, since this is a difficult topic, there is some arguments to gear it towards the higher rated users. I don't think any high rated user would ever struggle with basic binary logical relations or exchanges.

(Usually with LLMs, as long as your content is good, I can always find a way to read it/ find what I care the most about)

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

It depends on how good you want to get.

The actual issue is this: any incredible advices is likely brain and person dependent. They do exist, and is likely the next place to look after you spent enough time and resources.

Wrong implementation, radix sort can be implemented without growing vectors. Also for both of your implementations, replace modulo/ division with appropriate bit AND/ bit shift.

in each round: count up (x % base), do one prefix sum on the bin size, then directly write to the second array.

You seemed to have provided a new radix sort implementation that seeming saves 1 array sweep, but additionally costs in using vectors and growing them.

Your benchmark should be against the standard base 256 (4 cycles) or base 1<<11 (3 cycles) 1<<16 radix sort (2 cycles). It is clear that radix sort is faster than standard sort by a lot on large arrays. I fail to see the vector creation and capacity expansion are faster than just doing a radix sort normally with 2 cycles, and empirically 4 cycles seem to do better than 2 cycles anyways.

In summary, please prove it is superior to radix sort base 256 and 1<<16, but I don’t think this is the case.

The most significant difference is you don't always prepare for exactly what is needed at the job when you are in college. If there is some gap (frankly, there are like 15 important components and it is simply not possible to prepare for all), it is up to the company to decide if they think LGM capabilities is enough to cover that risk in a sense. I got it at the end, but I still have more rejects than I would like. In particularly, it is defintiely not guaranteed in a sense that you would receive offers from all companies as LGM.

Of course, getting a job is extremly different from getting all jobs, but just for context.

Who knows, even if you get LGM or a bit higher, it is still not a guarantee for a job (speaking from personal experiences), it just helps.

You can interpret a permutation as a function, then you can write the symbolic statement of $$$a = b * c$$$ or $$$a =b\cdot c^{-1}$$$ or similar. After having the matheamtical as expression in terms of functions, you can translate it into code easily. You can create two functions, one corresponding to matheamtical composition in right-handed order ( so ab means apply b first, then a) , and one corresponding to inverse.

How to decide which formulation? This is an extremely difficult question, and is no easier than generally how to write down the correct counting formula in a counting problem, for example.

I think CP had always been about in-sample knowledge. The more I improve, the more I can move things that used to look like novelty into a somewhat predictable framework. If a problem is to be solved quick enough (<= 30 minutes), it is almost always a combination of existing ideas, executed in the correct order or with the correct parameters.

About innovations, well there still are, but I do think simple, widely applicable innovations (e.g. segment tree, FFT, Linear Algebra) had all been found, maybe except one or two. There are harder innovations but they have proven to been too difficult (implemention-wise) to be included in actual contest for humans: say full dynamic connectivity, or fully dynamic convex hulls. Even proper uses of BBST seems to be out of the question for Codeforces. There are some innovations that are generally knowledge based, but I don't think people generally appreciate them too much as a problem (e.g. segment tree double descends, segment tree beats).

A competition of this kind roughly exist, it can somewhat be found in academia that seeks to answer unsolved (but generally not the extremely well known) mathematical/ algorithmic problem. There are two issues, (1) is due to the true innovative nature the natural "contest duration" would be months and in some case years, and (2) most solutoins to non-obvious problems generally exceed 30 pages, which I think is already beyond what humans can easily digest.

• The above discussion relies on my opinion that for example, problem B today, is still very much standard -- it doesn't use anything unimaginable. And I think as long as every step is imaginable, the whole process is still not very creative.

Proud to present screencast again

Proud to present screencast

Proud to present a screencast, it is the first time I managed to have a div2 #1 recorded.

(No problem A solve because I accidentally leaked something at the first minute of the screencast).

Depending on the ratings of the problems that you work on, and also relative to your own abilities, I frequently find missing the correct ideas is not as bad. Many paths of thinking will point you to the same idea (if done sensibly), so you will look at it again sooner or later.

It is much more dangerous to incorrectly assume something is correct. If it happens early on, it corrupts all following thinking and make it impossible to recover. In particular, I am not sure which component are considered under the correct or incorrect assumption.

In short, it is not as serious of a problem.

On that note, practictall speaking a proof is only 97% valid -- you can mess up reading the statements, copying the wrong assumptions, or the proofs looks right but are subtely incorrect. There is always a risk, depending on the person it may or may not worth it to trade false negatives for false positives, but from my experience I think false positive costs way way way more.

Bad news, this doesn't work.

Good news, there are considerable efforts from codeforces team to make sure the top of standings are at least reasonable.

Googleable or not, the whole problem is standard and is a test of implementation (basic loops/recursions/divisions depending on what you use). If half of the component is replaced by a google search it isn’t that bad. You corrected saw that it is a standard subtask and is rewarded (to be honest, I would not expect the subtask can be found online as it seems way too specific to me).

I think this is an isolated case. The whole div3 today is far more implementation heavy than usual. Googling in general is not effective on CF, so I would say this is a one off lucky thing.

Is it a good idea to have an implementation heavy div3? I have no opinion.

Your ideas are nice, but I like doing a Reroot-tree dp in $$$O(n)$$$ without ever engaging with the problem

Online Mo in general could potentially be done in same complexity or $$$O(n^{3/2})$$$ if you only need to store a single number.

It is only in this problem where you truly need to remember n things, that you need $$$O(n^{5/3})$$$ for online version. Alternatively you can do $$$O(n^{3/2} log n)$$$ using persistence. This is practically worse but conceptually obvious.

Mo with updates are known to be done in O(n^{5/3}), this exists independently of online thing.

I do not believe you have meaningfully illustrated the dependency of knowledge (and the novelty/choice) that is demonstrated in this approach. It reads like you copied an editorial without giving any more insight than what is already present in this one problem. You are overfitting explanations on this one solution. (It is also difficult to filter out which part of what you said is new/uncommon, and what isn’t).

Put it another way, you didn’t really explain how to do online mo adequately. You should have just titled it a solution to this problem. I know maybe this is your aim all along, but I just want to say I learnt something from the blog while but am unhappy because I didn’t get what I expected.

Think of it as a funding mechanism for competitive programming. I do hope competitive programming professionally even pays 1/10 of that.

Why do you need CF this badly to justify “going through pain”? Even if you succeed in breaking out of grey this way, every stage of rating is more challenging than the previous, the amount of resources and energy it takes will be even higher, and if you already spend every bit of resources (mental+time) you can at this stage, you will not make it much further.

If you still decide to need CF this badly (e.g. you are externally pressured), then that is your reason. Many people are not under in this situation, at least have a mix of reasons. If you really are: then motivation does not matter, confidence does not matter, what you need is raw, calculated efficiency. Even a cold machine needs to know exploration-exploitation trade off. This is strong evidence that you do need a new training method (may or may not be a plan). The mistakes you say are small-mid scale and are definitely not enough to account for the harsh reality you are facing.

Do not take hard-work and discipline as the golden standard. Only put faith in them after they have proven their worth. This is especially false in highly dynamic, complicated environments like Codeforces. Be open to other ways to succeed. It is totally ok to give up, temporarily or forever -- because you always bring new ideas when you decide to return.

Your blog had too much natural language :(

(Just kidding. I understand your frustration, but I take this opportunity to share that I have the opposite problem. I would prefer books and blogs write introductions and most of the explainations in notations and not natural language. In general, it is hard to locate what I care about immediately with natural langauges but far easier with notations. That is also the reason why I didn't actually read your post...)

To other readers: this is not a new thing that managed to escape CPers for years, this is just https://cp-algorithms.com/graph/flow_with_demands.html

Are you living that in that famous country where it is difficult to access most of the internet? If not, do you live under a rock?

o3 had been able to achieve 2700 ratings and it more or less holds up for 3 months already now. I am sure those who have the resources to call LLMs are already well aware of this and making the best use of it, constructively. The next time it would surprise me is when it starts solving div1E consistently (at consumer-viable cost).

(interpret the 2700 number with caution since in modern CF styles + most use cases + typical computation resources you can spend on it means you probably need to deduct at least 400 from it. I also had it catastrophically failing to implement rectangle union before, but I still feel it is generally that zone)

Be very careful about extrapolating from AC counts above rating:

• you mentioned the impact of the parameter overall but didn’t say the scale/spread of the parameter. I would love to see you just calculate the beta w.r.t rating more directly
• then account for the amount of time spent per hard problem, it is not at all clear why it remains the most efficient
• then there is some leakage: when you talk about AC count (not numbers attempted, though this is impossible to track), one is more likely to AC if in fact his ability is higher than what the rating suggests. For 400+ rating a simple ELO odds mean this effect is pretty strong. You managed to predict the person is underrated but cannot conclude the person is improving.

I started high mainly because I studied theory so much, have prior coding experience for games, and have decent math Olympiad successes. This was enough for 2000 rating out of the gate, but it was some climb to stabilize at orange, then at red etc. I didn’t start at another platform, codeforces is the first.

Many of my solves are actually low difficulty, there are decent mid or high level but they probably make up only 1000. The entire >3200 section is almost untouched.

I think generally, if you are really capable of learning fast+ lucky, you can get one rating equivalent per problem solved. If you are not focusing , I feel the efficiency can be 1/10 or so. Generally I think the rule to break is amount of time spent per rating. I am thinking for most people, 6 hours per rating is enough, but it could get as great as 1-2 hours at some point. the 6 hours estimate gives 5-20 problems of similar difficulty, or 50 problems in speed per rating point.

Given my solve counts, it looks like 1 problem per rating though (excluding easy speed problems).

it is somewhat correlated, if you don’t go out of your way to improve quickly, it will fall to a general estimate, but you can beat this rate substantially if you discover what works for you.

For burnout, yes, there are plenty of times that I feel like I am not improving, or some strategies did not pay off. There are a few things to do: try new things (such as me investing a bit into solving problems fast), work on other stuff and come back (I also have to deal with academics and jobs related stuff)

I don’t think I can say much because it is really upto personal understandings of what benefit you the most. However, I think it is very useful to not miss options.

Easy problems: 800-1300 in your case, med:1400-1700 and hard:1800-2000 all serve some roles. speed and difficulty are rewarded almost equally in CF. Speed gives you time to solve the next problem and can compensate for idea. So you have to probably decide which one you can improve more effectively first.

DS: learn them if you haven’t (you should only need upto lazy segment tree for next few hundred ratings), it is relatively quick compared to solving problems.

Contest: contest serves as a sanity check/ validation test for me, I know that I won’t learn as much as other options but it is a great way to have fun and check your skills didn’t deteriorate noticeably (especially after a period of rest)

The oversimplified models always missed lots of nuances and pretend that you have a complete model, a few things that you didn’t model:

Speed: If you learn the same amount of things in a 800 and in a 1700, you can do the first one upto 20 times faster, then it is a strong argument for doing the 800. If you can learn at least 1/20 of things, you should do the 800. Trust me, no one can perfectly solve a 800, I also can’t (the ideal goal is 30 seconds per solve at 100wpm).

Energy: it simply takes lots of energy to do high difficulty problem. It doesn’t drain much to do low or mid problem. If you want to train for a whole day for many days, there is a natural cap of the amount of hard problems.

Development: you cannot get all skills from problem solving efficiently. You need to set aside time for learning DS etc. If you do this effectively, you rely less on solving difficult problems. At early levels, most of the ways you get stuck is not knowing some idea. At late levels, most of the way is you cannot think fast and exhaustive and consistent enough — this last thing is solvable with mid level problems, not necessarily hard ones.

It comes down to a very complicated calculations that is constantly adjusting of which one is more useful in the current situation.

Fun fact, I think I get saturated from improvement from either type of problem solving and now I need some substantially new ideas.

The super path in problem F seems to be the same as the left-hand rule in solving a maze, and that is how I implemented this problem.

I cannot find a proof that is intuitivem but it is probably right.

My implementation:

        var x =0
        var y = 0
        var dir =1
        markpreserve[0][0] = true
        while(x != r || y != n-1){
            dir = dir.previous(4)
            while(true){
                val ii = x + dx[dir]
                 val jj= y + dy[dir]
                if(ii !in 0 until n || jj !in 0 until n || A[ii][jj] > cost){
                    dir = dir.next(4)
                }else{
                    x = ii
                    y = jj
                    markpreserve[ii][jj] = true
                    break
                }
            }
        }

Personally, it is worth making all segment trees perfect power of 2. Descent code (your ST-walking) is simpler than binary search and custom segtree operations are easier to write.

No thinking, raw CHT solution for F2.(everything 0 indexed)

same as the editorial, we start with dp[i] for i in 0..n, and we would like the make transition of the form: for some i<=k<j , we use element L[k] to cover the range i..j. -1. If v=L[i], the cost of this is v*(j-i) + (j-1-k) + (j-1-i). Unlike in the editorial, we do not reduce the number of transitions to consider away from n^3, but just do it.

thinking about this in another way, we are paying an additional cost of (v+1) for every element before L[k] and an additional(v+2) for every element after L[k].

We can imagine this as a 2-stage DP, where each element k pulls from before and push to after. Each of these can be handled with an add-only CHT (aka line container). Li Chao tree is also applicable here and is faster, but the constraints are pretty lenient. We need two different CHT/ Li Chao Tree, one for each component of the transition.

Complexity is n log n. You can check my submission for detailed calculations. (Idea took me 5 minutes but getting the formula right took me the remaining 20….)

This is not vacuous. The statement is simply undefined for two equal strings. It reads "first position", not "exist a position v which satisfies the later condition". Any sensible logical system would RE immediately. We would not be able to tell if the string is universal from the above definitions (alone) and is undefined.

But yes I agree that the definition of lex smaller should be changed.

How are the prizes split between top participants? Evenly?

You don't need to understand anything unless there is a need to -- the only reason you need to understand something is if you are already not in control on your amount of knowledge. If you know the solutions to 1000 tasks, you better find some deeper relations and interpretation to draw from this knowledge faster. If you know the solution to 10 tasks, just remember them.

You need considerable data to make a good realisations, this is true universally (AI and what not). A realisation based on incomplete data or experience may as well have been guessing. This is the point that you shouldn't dig any deeper. For example, if you have solved 5 segment trees problem maybe it is worth looking for common pattern and understandings, but before then just keep it as a random trick that was useful one time.

This was a tough lesson through personal experience but the context why it happened is too complicated to describe here.

Please enable test data and detailed verdict: I still have no clues why my submission to E is incorrect (already made reasonable attempts of validating outputs).

Update: Thanks to communications from the problemsetters, my solution on E is incorrect because there is a (implied but not very clear) requirement of you cannot have well connected cycle of pipes but otherwise do not extract any oil. This gave a not-very-helpful message of "Unrecognized or misaligned character"

Linked list is close to the best graph representation method.

Linked list is the objectively optimal (figuratively) way (both memory and constant factor efficient) to represent $$$m$$$ integers distributed across $$$n$$$ sets in $$$O(n+m)$$$ memory. It needs the assumption that each integer can appear in at most one of the sets at any time.

A doubly linked list is present as a standard SQRT-structure that supports arbitary insertions and removals.

I made an inaccurate statement: one convolution is enough. Let S be the set of marked indices. Define array A to be $$$A[i]=1$$$ if $$$i$$$ is marked, $$$A[i]=0$$$ if not, A is indexed from $$$0$$$ through $$$n-1$$$. Define array B to be $$$B[i] = 0$$$ if $$$i=0$$$, or $$$\frac{1}{|i|}$$$. Indexed from $$$i=-n$$$ through $$$n$$$. ($$$B[0]$$$ can be anything, its value do not affect any answers)

Let $$$C$$$ be their convolution, which is defined to be $$$C[j] = \sum_{i}A[i]B[j-i]$$$, where the sum is taken over whenever both $$$A$$$ and $$$B$$$ are defined. This $$$C$$$ can be calculated with FFT in $$$O(n \log n)$$$.

Observe that $$$C[i]$$$ now stores the cost of any unmarked index $$$i$$$. ($$$C[i]$$$ for marked $$$i$$$ do not hold any meaning and can be ignored.)

It should be a bannable offense to use ChatGPT to write a solution with such confidence while being absolute nonsense.

Anyways, your desired cost for each position can be calculated with FFT. You need two separate convolutions, one for handling marked index to the left and one for the right. Hopefully there is no precision issues with Doubles.

This blog would be readable if you actually describe what you approximated $$$\frac{1}{x}$$$ with, and what brackets are they split into, and not expect everyone to read it from the code -- if only you desrcibe them in as much detail as the not-fast-enough solution.

As far as I am aware, if you directly approximate $$$\frac{1}{a+x}$$$ as taylor series, error would be extreme as soon as $$$x$$$ is on similar size of $$$a$$$. There are ways to mitigate this but that is me solving the problem and not reading your solution.

There is a big difference between "don't learn unnecessary things" and "not learning things you should know". If you said the above list when you are orange, then I think it is very much in the second class. For CM, I think it is midway between.

Besides start costing actual solves (where the technique is the only solution), you must also appreciapte how standard DS or techniques can allow you to skip observations, or allow you to look at some "apparently smart things" and they become useless. Efficient use of standard DS to simplify coding can make life so much easier.

I just don't want this blog to have a sentiment of "proud to be lazy", that's all.

Though in some sense, I hitted CM after doing aboslutely nothing — at that point I would know many of things you said but will never be able to implement it. But surely, you could reach CM without any of these, but you probably won't want to stop at CM right

This is not a solution, but is something I thought about and made me not conclude that this task is immediately impossible.

Consider replacing each element with a random submask (each bit taken away with 1/2, easily done in O(1), assuming you can generate a random number in O(1)), and replace the OR with a XOR. This now gives an O(n) solution where every '1' bit is defintiely a '1', and every '0' have 1/2 chance to be actually a '1'.

If you repeat the above enough times, then you can gurantee the answers are correct with high probability. Unfortunately, you need to repeat it $$$c \log n \log \log n$$$ times here.

But if you are for some reason working with $$$a_i$$$ lower than the allowed range of bitwise operations to be O(1), say if $$$a_i\leq 32$$$, then you can simultaneously do the above operation using the same 64-bit integers packing multiple copies of $$$a_i$$$. This means that the $$$n log n log log n$$$ can improved if not all bits are not utilised.

Again, this is not a solution and may not be useful, but it could be interesting.

this problem is exactly identical to 2D point update, 2D range sum query, as the transformation gives. In the first case, no point update necessary.

There are three optoins for the first case, wavelet tree, merge sort tree, or persistent segment tree. All of which are n log n, but wavelet tree allow bit-compression so it is actually n log n / 64 in memory, n log n time, which is the best solutoin.

The second case is a general unavoidable full on 2D queries, costing n log^2 n. but you can still choose between 2D BIT (if range small), red-black tree on segment tree, and 2d segment tree. If all queries are given ahead of time (offline) you can change the red-black tree on segment tree into BIT on segment tree after coordinate compression, which would be clearley the best option. If one of the range is dense (which is applicable here), use red-black tree on segment tree.

I think the solution to this problem is best presented by clearly splitting to a "reduction" component and an "data structure" component, I hope the examples I give show you why such a split is desirable.

Why isn't performance cap moved to 3400? With the way it is right now, it seems to discourage partcipating (rated) when rating is above 2800.

For Problem E, it actually pases with failure probabilty of at most $$$1e-33$$$. To see this, consider the event that each point stayed alive after 75 queries. This happens with probability at most $$$\frac{1}{3^{75}}$$$. Using a union bound, we can see that the probability that any point stayed alive after all 75 is at most $$$\frac{n}{3^{75}}$$$, which is somewhere near 1e-33. (Note that union bound doesn't require any assumptions about dependencies (or lack of) in ther random events).

Despite me not preferring this style of presentation (and some presentation can be improve), this blog has quality choice of content. This is something I quite like, regardless of difficulty of the content.

My only complaint is that "sweepline" shoudl really be "Offline Range Add", as sweepline describes something a lot more general and compliacted.

For $$$max(a,b)\geq 3B)$$$, reduce the larger of the two numbers by a factor of $$$X\cdot 3B^{-1/2}$$$.

I am not understanding this. I presume this steps uses the precomputed matrix and the previous lemma? How is the correct martix found? Are you computing some ranges for each matrirx where the lemma holds, and then find it using some 2D data structures (with horribly impractically large constant factors and log factors)?

Despite cleary the amount of time and effort you have put into this, which I think many people including myself appreciate. Unfortunately, you should really think about

you have written something in the style of postgraduate text -- in a highly specific and technical tone intended for people that are either close to be a mathematician or very familiar with the topic.

• Are you sure that is your target audience?
• Are you sure you are at the right level, selected the most important items with good coverage, theorems are selected with coherence, correctly balancing between going for generalisations or specific forms?
• If not, are you sure you can present it better than (or,just on par) with many of the undergraduate textbooks on group theory out there?
• If not, are you able to present the materials in a way that you are cetrain competitive programmers will find it far more enjoyable compared to textbooks?
• If not, are you certain that competitive programmers need to know this?

this is well-known in china. However, this is not as well known in CF because the amount of sqrt problems is far less on CF.

it is hard to link to a blog because you can see this trick just about everywhere in any DS problem intending sqrt solutions that involve inserting elements.

For simple loops like this , you should really evaluate it as loops unrolled. (Of course I get a cost-free way of doing this by JIT). This brings the operations down to basically 4. In fact, it is lower because of executing ahead of time (there is no dependencies to not load the data ahead of the current AND).

it is just a special rule and special case that, for simple and independent branchless sequential array access solutions, 1e9 operations can be achieved.

It felt you are just stating reasons why it could be hard to recognize this passes for a normal person with too pessimistic of a runtime estimation, without seeing that you also provided all the reasons why it easily passes: branching, memory, instruction throughput/latency are beyond perfect in this solution. It is not that you can come to this conclusion without considering branching,memory, instructions type. It is a statement that this is very easy to do on this case, with lots of margins for error, in general, both from first principles and by experiences (if you have sent any similar solution and a similar brute force nature before. If you felt 1e8 is not fast enough in this case, you should have been surprised by runtimes on so many occasions. )

Speed of __builtin_popcount is pretty hardware dependent (and for me, compiler dependent too ) so I would not dare to put it through 1e8 loops. This is why I went for the second option below.

That said, if it does not pass, it is easy to change to a pre-computation. So the options are like

• do the simple thing, -50 and a few minutes if wrong, nothing else if right
• do the correct thing, down maybe a minute but definitely OK

I think it is a fair and balanced (even interesting) decision. It is very different if you are only allowed 1 submission and no chances to correct it if TLE.

I don’t think it is bad to test understandings of big differences of constant factor, especially when that constant factor is as big as a factor of 10 away — I am very sure that an iteration of this kind with 1e9 would have passed (in C++) too. (Not all implementations equal, like bit counts has to be precomputed).

Yes, nesting (implicit) segment trees seems to be the best option.

The final one could be a BBST to save memory, giving a memory requirement of $$$O(n log^{k-1} n)$$$.

If the overall set-up is offline, generally, you can use one extra layer of cdq to remove one dimension ( so still $$$O(n log^k n)$$$ but easier to code and better constant factor).

Of course, it is unlikely that you get anything practically better than the $$$O(n^2)$$$ for 5 dimensions or higher (4 dimensions already questionable).

what I stated was inaccurate, in fact, your second task is exactly a 3D offline query ( given triples (i,j,k), calculate how many pairs satisfy $$$i_1 \lt i_2$$$, $$$j_1 \gt j_2$$$, $$$k_1 \gt k_2$$$.)

So I highly doubt there is a solution faster than $$$O(\log^2 n)$$$ on average, (given how well known this is in China).

what you described is one of the standard realistaion of a fully online 2D data structure (supporting add 2D point, and range sum query for 2D rectangle), it is highly unlikely that this can be optimised to $$$O(\log n)$$$ for this reason.

can fractional cascading be applied? defintely not directly (for reasons including it does not make sense unless it is a completely sorted array). But, I am not good enough to conclude that it is impossible, because it is possible that is some magical $$$O(n log n)$$$ solution out there (I did a quick search and it seems that this is an open problem) -- the world is waiting on anyone that can confirm or deny this.

the general DS/solution to a k-dimensinoal query is $$$O(n log^k n)$$$.

In the special case that our queries are offline, then we can reduce dimension by one, using sort+ sweepline and use an online solution for it. So an offline 2D query = sweepline plus any online 1D structure is $$$O(n \log n)$$$. The general 2D data structures, including BBST (ordered set) on segment tree, or 2DBIT, supporting online queries, are all $$$O(n \log^2 n$$$).

Wavelet tree, persistent segment tree or merge sort tree (with fractional cascading) are special cases (all $$$O(n \log n)$$$.) that can handle queries (l,r,v): count how many A[i] >= v for i in [l,r] if there are no update queries, (so, partially offline). This is weaker than the general full 2D online queries.

The first task is true 3D (offline) query. there is nothing better than except one of the many $$$O(n log^2 n)$$$ solutions. See https://oi-wiki.org/misc/cdq-divide/ and https://www.luogu.com.cn/problem/P3810. I hope you can read chinese.

Second task is very close to a full 3D query, I don't think it is realistic to expect anything simpler except n log^2 n.

The third task is a 2D query, simple sweepline + any choice of log DS will do in n log n .

Can you explain what it meant by “D and C polynomial mod” in the last paragraph making it $$$O(n log^2)$$$? I cannot quite see why modding $$$x—n$$$ helps since it is same as a typical multipoint evaluation.

Matrix exponentiation is only possible if all terms and transitions are linear. While a matrix can easily keep track of $$$l,r,n,B(l,r,n)$$$, it cannot simulate the $$$\binom{n}{l}$$$ etc or perform any types of multiplications needed to maintain the binomial coefficients added/subtracted. (So at least, integer matrix would not be enough)

If by O(qn) you mean just “For every distinct state, check and answer every queries”(this is how I used it), then this can definitely pass, as the access patterns are very predictable (looping over all q queries). I worried less about this part than the actual $$$n^3$$$. I think a $$$n^3 log n$$$ is practically a lot worse than this $$$O(nq)$$$.

I had some seroius troubles with the TLs in this round. Sure, it is about kotlin, but I feel like it could have been a little bit more lenient.

D: The direct $$$O(6C3 q log n)$$$ solution with max-matrix should have passed. I don't think it should be cut.

E: I end up taking the clean $$$O(n^3)$$$ route. I am scared of $$$O(n)$$$ many 01-BFS on $$$O(n^2)$$$ edges, but perhaps I worried too much.

F: My solution that performs O(\log MAX n) ordered set operations are not fast enough, since in many cases I need to perform 3 or 4 searches for every "normal" operation. Though, I did not completely anticipate it being not fast enough, and would have opted for a segment tree/sorting+BS/BIT apporaches instead.

G: The overhead from declaring n different arrays was too much to handle, and I ended up needing to swap n, m when n is large. Allowing extra memory for this case would have been nice. I also see no reason to make the TL this tight -- it is not like there is any significantly easier solutions if an extra log or two are allowed.

Even though it is part of my issues for using Koltin and accepted the TL issues associated with it, I feel like in quite a few cases it was needlessly harsh.

for F you can solve in $$$O(n \log n)$$$ as follows. Observe that when checking for $$$2^k$$$, only sets with size at least $$$2^k$$$ can possibly work, so delay building them until the size is $$$2^k$$$. With this, it is reasonable to use just an array of size 2^k to store the frequecny array. Insetad of merging two sets in time $$$set constnat * min(|A|,|B|)$$$, we can merge this in exactly $$$2^k$$$. A simple amortization will show that this process is $$$O(n)$$$ for each target power of two. So this part works in $$$O(n log n)$$$.

We also have to maintain the maxmium size of all working sets. This costs $$$O(X log X)$$$ for $$$X$$$ at most the number of built set, with the log from constnats of map. Notice that when checking for $$$2^k$$$, $$$X$$$ is bounded by $$$\frac{n}{2^k}$$$. Suming this over $$$k$$$, this part is also $$$O(n \log n)$$$.

Edit: I forgot that we you process queries, the same already built set can be moved in/out of working sets, so unfortunately the last seemingly easiest part is actually the slowest at $$$O(n log^2 n)$$$ I don’t see a good way to save the log in this task.

Second edit: it turns out saving this last log isn’t as bad as I thought. It is not a true savings, but vEB tree (rather, the practical base 64 variant) allows this final part to be done in O(n log n log log n) overall

Why describe Aho-Corasick in full again?

This has runtime of O(limit * sum of string length). It is also easy to do in O((sum of string length)^3 * log limit). Without other constraints given, it is not clear if either of these two what is wanted and/or fast enough.

Please formulate a mathematically sound and logical query with everything correctly defined, I cannot understand what you actually tried to ask

However, what I suspect you want is the following: suppose we are in a state, now we must decide to pay coin or not. If we pay coin, then we leave and all is good. Otherwise, we could come back to the same place after one random step. Now it seems that we have to decide to pay or not yet again, but this is not necessary as the process is Markov/Stateless/Memoryless, nothing actually changed between the first time or later time you arrived (the total sunk cost did change, but you are only asking for expected cost, so it does not affect the expected cost. Note however if you are asking for probability of total cost <=k then it will change). This means you either always pay or never pay at this exact state, giving why the DP is valid.

The rearrangement could seem surprising in a dp but that is just a general equation solving in a random (here, markov chain) process.

The editorial solution is clean. However, I cannot see a potential clean proof.

Baiscally, the first step is defintiely correct, but the tie breaking is hard. You must show that among all future paths, you can select one to commit to, and it gives the best result (due to one reason or another).

This cannot be done without any statements about the future situations, what you can do/comparing future situations.

That said, the proof given by _Kee below is correct and clean enough. Thanks.

Where is the formal proof of correctness to the editorial solution of D?

I was hoping to see the cleanest solution and proof to the problem, now the editorial for this problem is very unhelpful.

I think this is 1800

At first, I thought this problem is trivial, as you just go through and perform an arbitary match if you can. I thought it is an easy (guarnateed profit)>=(maximum cost) situation. I thought it was 1300 upto here.

Then, I realised this is wrong. There are situations where both 0 and 1 could be matched. And you could not decide it without serious lookaheads. This can happen when the number of remaining allowed matches is less than the potential matchings you could do. This would reject the simple greedy more than enough for my taste.

Turns out, it is still possible to solve from here: We just take keep the potential option if both can be matched. That is, after each matching, we can have "stuff that must be 0", "stuff that must be 1", "stuff that can be either 0 or 1 as you like".

If this were the only solution then it would be 1900. I would never have looked any further and just implement it out. However, seeing the simplest greedy is actually extremely subtle. It depends critically on the fact that a group of size $$$k$$$ would have $$$k$$$ opportunties to match with something else before. Making such number of matches must result in either (1) '0' or '1' being exhuasted, or (2) the numbers of '0's and '1's are at most the remaining number of matches you are allowed to perform. In both cases, all the matching can be conducted without any potential nontrivial choices.

If I am forced to discover this, I would even rate this as 2700 or higher.

My conclusion is: Most people that submitted this greedy either did not prove, or gave a wrong proof. There are some more involved, but certainly correct solutions, and many should have chosen them instead.

That said, guessing a greedy that then it passing is still a skill, so I think a 1800 rating is appropriate: however, it is far more volatile than what this rating suggests.