The problems are great, but I feel that the editorial is written rather poorly.

Here is a (hopefully) more intuitive editorial of problem F -

Let us consider the inverse of the operations given in the original problem, for the sake of better understanding.
Given a sorted array in non-decreasing order $$$s$$$, you can perform two operations:
- Shift Inverse: move the first element of the array to the last place, and shift all other elements to the left, so you get the array $$$s_2,s_3,...,s_n,s_1$$$.
- Reverse: reverse the whole array, so you get the array $$$s_n,s_{n-1},...,s_1$$$.

By observation, we realize, that there are three types of arrays that arise when we perform the above operations on some sorted array $$$s$$$:
i) The most basic of it is the reverse of $$$s$$$ — the array $$$s_n,s_{n-1},...,s_1$$$.
ii) An array of the form $$$s_k,s_{k+1},...,s_n,s_1,s_2,...,s_{k-1}$$$, $$$1 \lt k \le n$$$.
iii) An array of the form $$$s_k,s_{k-1},...,s_1,s_n,s_{n-1},...,s_{k+1}$$$, $$$1 \le k \lt n$$$.

Thus, we can break down the original problem into the following cases:

1. If $$$a$$$ is sorted — No moves required, answer is $$$0$$$.

2. If $$$a$$$ is sorted in reverse order — reversing the array solves it, answer is $$$1$$$.

3. If $$$a$$$ is of the form presented in case ii) above —
   Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k+1},...,s_n$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_1,s_2,...,s_{k-1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
   (a) perform the 'Shift' operation on all elements of $$$S$$$. So total number of moves = $$$|S|$$$.
   (b) perform the 'Reverse' operation on $$$a$$$, perform 'Shift' operation on all elements of $$$F$$$, and then perform the 'Reverse' operation again. So total number of moves = $$$|F|+2$$$.
   We take the minimum of (a) and (b), and that is our answer.

4. If $$$a$$$ is of the form presented in case iii) above —
   Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k-1},...,s_1$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_n,s_{n-1},...,s_{k+1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
   (a) perform the 'Shift' operation on all elements of $$$S$$$, and then perform the 'Reverse' operation. So total number of moves = $$$|S|+1$$$.
   (b) perform the 'Reverse' operation on $$$a$$$ and then perform 'Shift' operation on all elements of $$$F$$$. So total number of moves = $$$|F|+1$$$.
   We take the minimum of (a) and (b), and that is our answer.

5. If $$$a$$$ is neither of the cases presented above, then the answer is $$$-1$$$.

C++ code for reference.

Was quite frustrated with multiple wrong answers for D, but couldn't help laughing out loud when I saw the solution. XD
Great problems, keep it up! :)

Sorry for the necro-post.
I posted an english explanation to problem D here. Since the original blog is in Russian, it does not show up in the English version of codeforces, hence my comment here.

Can anyone give an insight as to why the same code TLEs in C, yet passes comfortably in C++?

Define $$$dp_{i,j}$$$ as the maximum number of magazines we can save upto index $$$i$$$, where $$$j=0$$$ if the current box does not have a lid on it, and $$$j=1$$$ if the current box has a lid on it.

The transitions can be formulated in the following manner:
- Case 1: $$$s_i=0$$$, which means this box does not have a lid on it. Here, $$$dp_{i,1}=0$$$ because there is no way for us to have a lid on this box, and $$$dp_{i,0}=max(dp_{i-1,0},dp_{i-1,1})$$$, since we can consider either of two cases for the previous box and take the maximum number of magazines saved either way.
- Case 2: $$$s_i=1$$$, which means this box has a lid on it. Here, $$$dp_{i,1}=max(dp_{i-1,0},dp_{i-1,1})+a_i$$$, since we can consider either of two cases for the previous box, and we are also saving the magazines of the current box. But in case this box were not to have a lid on it, then we must pass on the lid of this box to the previous box. Thus, $$$dp_{i,0}=dp_{i-1,0}+a_{i-1}$$$, since we are considering the case when the previous box does not have a lid on it, and adding the number of magazines of the previous box to our current dp state, since the previous box now does have a lid on it.

Our answer is $$$max(dp_{n,0},dp_{n,1})$$$.

C++ code.

I can attribute that a lot of negative feedback (including mine) stems primarily from lower rated contestants. I, personally being a lower rated contestant can probably give an insight as to why this contest was not that appealing for people similar to or below my rating.

- Problem A was hard, and I mean really hard to be a problem A. I do agree very much with dario2994 on the opinion that it's a nice problem, but problem A-s are supposed to be pretty much solvable by everyone above a rating threshold (say 1000). This problem was clearly not one of them. Again, maybe I wouldn't have complained so much if it'd been a Div 2B (or even Div 2C), but it was just way too hard to be an A for a combined round.
- Since I didn't use sqrt or any other such function, I did not face any problem in B. I found it a rather nice observation-based problem. But many newbies (or rather newcomers to programming in general) did get a bit stumped by the rather inconsistent behavior of C++ compliers with the sqrt functions, and that might've generated a lot of negative feedback from them.
- Though I did bash problem C in my earlier comment, I do think in retrospect, I was being harsher than necessary. However, solving C wasn't necessarily a pleasant experience either. The problem statement was rather long, the problem statement could've been a lot simpler, and the images of the crickets were rather repulsive. (I know I'm being weird with this, but I think by simply replacing "crickets" with pawns or something similar, it'd have made a much better reading experience (is that even a thing?)). Also it was way too ad-hoc to be actually an interesting experience to solve. I know I might sound even weirder saying this, but it was an ad-hoc problem with no "ah-ha" moment in the solution, which made it, IMO, a not so nice problem.

Overall, the problemset was probably not that bad (given that I see so many higher rated users appreciating D and above problems), and I did love your attitude towards constructive criticism. Keep making problems, and I do hope and wish your next contests would be even better. :)

Sorry, but this is the worst contest I've ever participated in.
Also, C is the worst problem I've ever seen in a Codeforces contest. And A is the hardest A I've encountered.

I was trying to solve problem D, and not being able to solve it, I came to search for the solution here. But I found no intuitive or clear solution either in the editorial, or in the comments for people with unicellular brains like me. I looked at a few solution codes, and finally solved the problem. So I decided to attempt to write a simpler explanation than what's already here for problem D.

Let us define $$$dp_i$$$ as the minimum number of leaves in the subtree of node $$$i$$$ that we have to consider to get the maximum possible value at node $$$i$$$. In other words, say, if $$$dp_i = 2$$$, then we have to consider at least $$$2$$$ leaves as the possibility of containing the number which will be stored in node $$$i$$$. Which means, we can narrow down the number of necessary leaves to consider as the answer for node $$$i$$$ as $$$2$$$. So, if $$$dp_1=p$$$, then our final answer will be, (choosing greedily), the $$$p$$$-th largest possible number to be assigned to a leaf in the tree. So, say, there are $$$k$$$ leaves in the tree, our final answer will be $$$k-p+1$$$.

Now that we know what exactly we have to compute, let us move on to how we will compute it.

Let $$$choice_i=1$$$ if node $$$i$$$ has max written on it, and $$$0$$$ if node $$$i$$$ has min written on it.
Case 1 (MAX): If $$$choice_i=1$$$, then we can choose the child of node $$$i$$$ which has the least number of necessary leaves in its subtree. We can, thus, narrow down the answer as much as is possible to be done by node $$$i$$$. Thus, if $$$choice_i=1$$$, $$$dp_i=min(dp_{child_i})$$$.
Case 2 (MIN): If $$$choice_i=0$$$, then we do not have an option of narrowing down the number of necessary leaves at node $$$i$$$. We must consider all the necessary leaves of all children of node $$$i$$$ to compute the number of necessary leaves for node $$$i$$$. Thus, if $$$choice_i=0$$$, $$$dp_i=\sum dp_{child_i}$$$.
If node $$$i$$$ is a leaf, we do not have to consider $$$choice_i$$$ as it does not have any children. Thus, if node $$$i$$$ is a leaf, $$$dp_i=1$$$.

Thus, we can summarize the solution as:
- if node $$$i$$$ is a leaf, $$$dp_i=1$$$.
- if $$$choice_i=0$$$, $$$dp_i=\sum dp_{child_i}$$$.
- if $$$choice_i=1$$$, $$$dp_i=min(dp_{child_i})$$$.
$$$answer=k-dp_1+1$$$.

C++ solution

This comment does not have enough downvotes for destroying almost the entire comment section of the editorial.

Standings for individual divisions are broken: Division 1, Division 2

omg vovuh div3s are back!!! :D

But isn't that exactly the point of div 3 rounds too?

Given what chess.com was a few years back (before the chess boom in 2020), and how it is now, I still stand by what I said. CC might have hired Um_nik and Anton, and yeah, I do agree that the problem quality has improved since, still I don't feel it has reached the consistency level of conducting such well prepared and well organized contests like CF. It still has a long long way to go before it reaches such consistency IMO.
Also given how CC is introducing some recent changes, I think it's quite evident that the gap between the target audience of CC and CF is widening. CC caters more to job seekers and people seeking to utilize their problem solving skills to obtain a better job in the tech industry, while majority of CF is an international audience who are passionate CPers, who either do CP for fun, or for performing better in some CP related event (like OIs, ICPCs, etc.), and not necessarily to crack a job interview as such.

I just feel sometimes that CC is like LiChess while CF is more like Chess.com
Well, not really. Except the rating part, everything is equivalent to lichess for CF and chess.com for CC.
CC got the job offers, the cash, the big brands, the ads (equivalent to say, streamers, brands, big money tournaments like chess.com), while CF got the quality problems, and simple but excellent UI (equivalent to quality of players, and UI in lichess).

Maybe he is not a cheater but i think he uses some other account to avoid penalties.
That is exactly what he did, and was called out for, and he admitted to doing so. But that was long back, and I'm pretty sure he doesn't do it anymore. (That account's last visit is 6 months ago, and given that he was called out for it, and now that he has a lowkey reputation in the CP community (having set a few problems on both CC and CF), I find no logical reason why he would do so.)
But this current case is clearly false positive, and you tried to shame him for it, by necro-posting on a blog whose issue was done and dusted months back. I don't understand what motive you would have for it other than personal, and you've been repeatedly trying to accuse him of "cheating", even though anyone with a couple or more brain cells would understand that it clearly isn't.

maybe i am a stupid but getting accused 4 times even in ICPC is not an accident.
Learn to read.

Are you jealous and have something personal against him, or are you really this stupid?

Nice problems. Thanks for the contest. :)

Please increase the TL for E in practice at least by a few seconds. Non-standard IO optimisation shouldn't be the difference between AC and TLE.

Yeah, understandable. Separate div 1 and div 2 rounds seem much better then for div 1 participants, since they take away the speed-typing part of it.

Why though?
From what I understand (admittedly having never been in div 1), shouldn't combined rounds ideally be, for div 1 participants, a 30 mins or so speedtyping contest and after that a normal div 1 round?

Guess they aren't insomniacs then. :)

In your case, MLE was caused because you were allotting too much memory (5000*5000*5000*sizeof(int) bytes). In some other cases, MLE can be caused due to overflow during recursion (while performing recursive dp, probably).
But coming to states of a dp problem, it is a technique which can only be mastered by practice and practice only. There is no shortcut route in instantly understanding what should be the states for a particular dp problem. In general, you can sort of get an idea about the states from the constraints (say for a problem, where $$$N,M \le 2e5$$$, the intended solution obviously isn't $$$dp[N][M]$$$). This is something you can understand better by practising more and more problems on dp.

I had been trying to solve problem E, and in failing to do so, tried to look for a solution in the editorial. However, I found the editorial for E a bit unclear, and both my brain cells struggled hard to comprehend it. Fortunately, I found kostia244's (sorry for the ping) solution in the standings page, which was quite clear and understandable to me, and was finally able to solve the problem after 1010 attempts. Hence, I decided to explain my (rather kostia244's) solution, just in case someone drops by here in future. So here it goes:
We maintain $$$dist[N][W]$$$, where $$$dist[i][j]$$$ stores the distance of node $$$i$$$ from node $$$1$$$ and the weight of the last visited edge is $$$j$$$. Initally $$$dist[i][j]=\infty$$$. To perform dijkstra on the graph, we maintain a heap, $$$q$$$ (or set, depends on your taste) which contains an item with three parameters:
1. the vertex, $$$u$$$
2. distance of the $$$u$$$ from the first vertex, $$$d$$$
3. weight of the edge through which we reached $$$u$$$, $$$w_{last}$$$
We relax the vertices in the following fashion:
If $$$w_{last} \ne 0$$$, it means we reached $$$u$$$ from another vertex $$$u_{prev}$$$, and the sum of the edge weight between $$$u$$$ and $$$u_{prev}$$$($$$w_{u_{prev}u}$$$) and the distance of $$$u_{prev}$$$ from node $$$1$$$, is stored in $$$w_{last}$$$. Now if we want to go to a new vertex $$$u_{next}$$$ from $$$u$$$, according to the problem, we can travel from $$$u_{prev}$$$ to $$$u_{next}$$$ with cost $$$(w_{u_{prev}u}+w_{uu_{next}})^2$$$. Hence, we update $$$dist[u_{next}][0]=(w_{u_{prev}u}+w_{uu_{next}})^2$$$, and push $$$u_{next}$$$ into the heap with no overhead cost, which means for $$$u_{next}$$$, $$$w_{last}=0$$$.
Otherwise, if $$$w_{last}=0$$$, it means we can reach $$$u$$$ from node $$$0$$$, with cost $$$dist[u][0]$$$. Hence, if we want to travel to an adjacent vertex $$$u_{next}$$$, we update $$$dist[u_{next}][w_{uu_{next}}]=dist[u][0]+w_{uu_{next}}$$$, and push $$$u_{next}$$$ into the heap with an overhead cost ($$$=w_{last}$$$) of $$$w_{uu_{next}}$$$, and we move on in life.
Now, the answer for $$$u$$$ is $$$dist[u][0]$$$, and we print it accordingly.
C++ implementation.

Cool problems. Thanks for the contest. :)

Multiple solutions passed which weren't intended. So basically it wasn't just one particular hack or idea, but it was just weak pretests.

Truer words were never spoken.

Your dad should've used protection.

Not really, I guess. Been there, done that. Good for you if you prove me wrong. But short term goals like this, without sufficient dedication and will, don't usually work.

On a more serious note, to be good at anything, including CP, you must be willing to invest time in it, especially if you aren't inherently that skilled enough. Realistically, if you want to invest an hour a day for a couple of months, I feel 1500 is a much more achievable goal. For 1800, if you aren't that good, and are willing to put in no more than an hour a day regularly, then it may take a bit longer, say around 6 to 7 months at least. A bit of math skill always boosts up the rate of your improvement, especially at this rating range.

AFAIK to be 1800 u just need to be good with adhoc ,& basic tree/graph/dp/number theory
And to be "good", you need WAY more than a couple of months, especially if you're weak at math.

Coz that's how life works.

No.

Choose better testers next time. :(

I rage quit when I saw my "friends" solve D in 5-7 mins, and I went on scratching my head on that problem for like an hour or so, without any solutions.

And here I was, shocked, bamboozled, confused whether I am crazy, hallucinating, or just sleepy when I saw blue Indian kids solve D in like 5 mins or so. To whoever authored this problem, if it was a weird coincidence, then oh well, shit happens. Otherwise, fuck you.

I used to prepare for olympiads when I was in school. Now I am in a college with pretty much zero CP culture (hence no ICPC or such stuff), and I'm quite happy with it. Also realized a while back I'd pretty much never reach orange perhaps, let alone red. So, I do CP just for the sake of having fun, and given my current level, I'm for sure not a contest winner or anything around that spectrum. The pure adrenaline rush which CP contests give me (more so in the CF 2 hr format), along with the joy of getting an AC, and a better rank than what I expect for myself (which is sometimes pretty low), is all that makes me do CP now. :)

sus deserves his spot. Try entertaining a bunch of programmers without sounding stupid or "nerdy". It's hard.

One of the best problem sets in recent times. Thanks ScarletS and flamestorm for the contest! :)

saarang orz

+3, if you need an extra blue tester, ping me :)

Can somebody please help me figure out, why my code, which quite literally implements the solution described in the editorial (except that I am scanning from left to right instead of top to bottom), not work? It gives runtime error because my queen somehow enters the 8th column, whereas it should be able to checkmate while it is in the 7th column. Any help in figuring out the error (either in the solution or the implementation) would be appreciated.

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debugger.h"
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", debug(__VA_ARGS__)
#else
#define dbg(...) 5
#endif
int main()
{
    int test;
    cin>>test;
    while(test--){
        int curfile=1,currank=8; // curfile=current column, currank=current row
        cout<<currank<<" "<<curfile<<endl;
        int cur=1; // keeps count of number of moves made in the current column
        bool firstmove=true;
        while(true){
            string king;
            cin>>king;
            if(king=="Done"){
                break;
            }
            else if(king=="Right" || king=="Up-Right" || king=="Down-Right"){
                if(firstmove){
                    currank--;
                }
                else{
                    curfile++;
                    cur=1;
                }
            }
            else if(king=="Left" || king=="Up-Left" || king=="Down-Left"){
                cur=1;
                currank--;
                if(currank==0){
                    currank=8;
                }
            }
            else{
                cur++;
                if(cur==9){
                    curfile++;
                    cur=1;
                }
                else{
                    currank--;
                    if(currank==0){
                        currank=8;
                    }
                }
            }
            firstmove=false;
            assert(curfile<8);
            cout<<currank<<" "<<curfile<<endl;
        }
    }
    return 0;
}

r/wooosh

Would this prize structure hold even for unrated contests (like Lunchtime)?

Speedforces, redefined.

Yes, he won IMO gold in 2019 and IMO silver in 2018.
Why did I get downvoted tho QwQ

p-square ftw!

Yes

Imagine having multiple LGM accounts o_0

They were quite interesting indeed. :)

This contest made me realize that besides being dumb, I am also a brick.

bruh

Queue 260 pages long :(

If someone is caught cheating, say more than once (it is hardly a coincidence if someone is caught unintentionally plagiarizing twice or more) then maybe their accounts can be disabled/closed with a "mark" on their profile which states the reason why their account was closed. (It is similar to what the online chess website chess.com does.)
Maybe making a compulsion for the users to mention their name and country and having a verified email address (even when someone changes it) would help a bit too (since it may make it a little less easier to create alts).

Anish Giri eliminated already so there is no point in watching anymore :/

And the award for the CF astrologer of the year goes to...

orz

Nice. :)

Even I solved the problem using the approach that you described. And now I see this solution. :(

Good problems, pathetic memes.

Why unnecessary $$$O(n^2)$$$ editorial solution for B? Even the explanation describes a $$$O(n \log n)$$$ solution.

The problem: Given the set of integers from $$$1$$$ to $$$n$$$, $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, find a set, $$$M$$$ of size $$$i$$$ such that max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is minimized.

The solution: Firstly, note that $$$1$$$ must always be included in the optimal set. Next, note that if there are $$$P$$$ primes from $$$[2..n]$$$, then max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is always $$$1$$$. Hence, for the first $$$P$$$ numbers, answer will always be $$$1$$$. Now from the $$$p+1$$$ th number onwards, if we include an integer $$$x$$$, the optimal set always contains at least $$$1$$$ divisor $$$d$$$ $$$(1\le d \lt x)$$$ of $$$x$$$. Why? Since we have already included all the primes from $$$[2..n]$$$, all the numbers we are left with are composite. Now if we add $$$x$$$ to the set $$$M$$$, max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is the largest divisor of $$$x$$$, since $$$\gcd (\texttt {largest divisor of } x, x) = \texttt {largest divisor of } x$$$. Hence, we have to add elements to set greedily such that the largest divisor of $$$x$$$ $$$\forall$$$ $$$x$$$ $$$\epsilon$$$ $$$M$$$ is minimized. For this, we can find out the largest divisor, $$$d$$$ $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, and store it in a list $$$v$$$. The answer is the sorted list $$$v$$$.

#include <bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

#define MS(x,a) memset((x), (a), sizeof(x))
#define F0R(i,n) for(auto (i) = 0; (i) < (n); (i)++)
#define FOR(i,a,b) for(auto (i) = (a); (i) <= (b); (i)++)
#define ROF(i,a,b) for(auto (i) = (a); (i) >= (b); (i)--)

using namespace std;

const int INF = 1e9+2;
const ll LINF = 1e18+2;
const int MX = 2e5+5;
const ll MOD = 1e9+7;

int lf(int n) {
    int ans = 1;
    for(int i = 2; i*i <= n; i++) {
        if(n%i == 0) {
            ans = max(ans,i);
            ans = max(ans,n/i);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<int> oof(n); 
    oof[0] = 1;
    FOR(i,1,n-1) {
        int n2 = lf(i+1); 
        oof[i] = n2;
    }
    sort(all(oof));
    FOR(i,1,n-1) cout << oof[i] << " ";
}

It passed o_0

They'd probably FST.

I do CP as it is the best way to exercise my two brain cells, plus it is fun.