Really happy to get to know this! Many congratulations to you Dominater069

Well deserved!

With a tougher implementation it is possible to solve E in (3n/2) moves instead of 3n moves. (the bonus version of the problem)

Idea is somewhat like:

• use 2 moves so that there is a pair (2 elements with sum = k) on first and last position. should be trivial to those who have solved the main version.
• now make first element equal to any element that is not on its correct position — that's 1 operation, this will make a cycle of minimum 3 elements (including the first element). If the size of the cycle is P, it will take (P-1) more moves to put everything in the correct place and it will put (P-1) elements in their right place (because we're not counting the first element).

So basically, we can use P moves to put (P-1) elements in their right place. Since the smallest P is 3, in the worst case, it'll take 3 operations to put 2 elements in their correct position. Notice that we only need to put (n-2) elements in their place.

• At last, use 1 operation to make the first and last element 0 and k

Contest announcements should be on the front page right? I wonder why this one is not there, even when it's a rated contest.

vector< vector<int> > pos(100010);

multiplied by the number of test cases, this is TLE, need to make pos vector global.

Anyone who wants video solutions, can check out my screencast of this contest along with the solution explanations: https://www.youtube.com/watch?v=8WPZwkMQWng

(My solution to H is the same as the editorial but I didn't think it was neat enough, so I tried reallly hard to come up with another solution for that, but couldn't, and ultimately implemented the editorial solution)

Here is my screencast of this contest along with the solution ideas and thought process: https://youtu.be/6suW6LZyYtY

I am planning to do more of these videos if my schedule allows it.

Solved using Trie without 2ptr: 314650347

Excellent contest! I really liked 3 of the problems.

(Btw an interesting coincidence, the first problem of this contest is named "Easy Problem", there is another problem on CF of the same name 1096D - Easy Problem, which happens to be the first DP problem I solved in my life.)

[deleted]

Me wondering when did I ever discuss rerooting with pajengod orz sir. (probably 2-3years ago on AC or Errichto discord server)

That is amazing!

I thought what more could be done here, and got 779ms by moving the branching outside the critical loop. I doubt if anything more can be done here.

Alright, so there were some bugs in your implementation (plus i didn't know a few things about Java, like unsigned right shift), but ultimately I managed to get AC with your code in 2947ms, by modifying your Java BitSet implementation.

Should be possible to optimize it further easily. (i % 64 can we written as i & 63, along with some other minor adjustments and optimizations)

EDIT: AC in 1762ms with some minor optimizations such as i % 64 -> (i & 63) and i / 64 -> (i >> 6) and i * 64 -> (i << 6)

Your solution seems N^2/8 instead of N^2/32, why didn't you use all 32/64 bits of your int/long.

I'll try to explain my simpler solution.

The basic idea is that, if I have at least 3 numbers with a common prefix in the binary representation, then no matter how I partition the sets, at least 2 of those will be in the same set, and all bits of the common prefix will be 0 upon xorring those numbers. So the idea is to find the longest prefix such that there are at least 3 elements with that prefix.

n = 2 is a corner case, which can be solved independently. Now assume n >= 3.

It is guaranteed that there exists some B such that right-shifting all elements by B will result in 3 or more equal elements, let's find the smallest such B.

Since I have picked the smallest such B, one can observe that there won't be more than 4 equal elements upon right shifting every element by B. (If there were 5 or more elements, then B-1 also would've worked.)

After making some cases manually, [VERY IMPORTANT:] one can observe that the minimum xor will be obtained by xorring the elements that become equal after right bitshifting by B. (because any other 2 numbers will have the xor >= $$$2^B$$$)

So, the solution is simple:

• find B,

• then make groups, such that all elements of the group become equal upon right shifting by B (size of all such groups <= 4)

• within each group, try every way of partitioning them into 2 sets. (can actually be narrowed down to much fewer cases, but this much is enough for a complete solution)

Here is my solution with some slightly ugly casework at the end, but one can get the general idea from it: https://mirror.codeforces.com/contest/1849/submission/216361206

Problem E was a very interesting problem. My initial idea was to use a lazy segtree for an NlogN solution, but it turns out that the O(N) solution is much cleaner and simpler.

https://mirror.codeforces.com/contest/1849/submission/216349588

Honestly, you can't compare two people like this, everyone has different strengths. For example, CoderAnshu is a coder, he's good at coding, while I am a demoralizer, I am good at making other people feel worthless, and a bit ashamed of themselves.

oh yes, my bad, thanks.

Oh i didn't know that there's a direct formula for that.

Btw, after that, we also need to divide by (1-x)^N, all i can think right now is binary exponentiation and inverse series, but that will be log^2. Is there a faster approach for this, that i'm missing?

It can be proven that it is always optimal to choose the Path as the longest path from among the vertices of the set. (Try to prove by contradiction, it is quite simple)

So the problem boils down to finding the longest path in a given subset of the tree. For this, we used a concept called auxiliary tree (which is basically, making a tree which contains all the vertices of a subset of the tree along with some more vertices to make sure all the LCAs are present in the auxiliary tree). The size of such auxiliary tree is never more than twice the size of the subset of the tree. The weights of the edges of this auxiliary tree is the original distance between the 2 points in the original tree. Thus we can simply find the longest path using 2dfs method.

However, solving each query in MlogN gave us TLE, and we had to use O(1) per query LCA, that was quite strange in my opinion, we lost rank 1 due to those penalties :(

Edit: Refer to radoslav's video on Auxiliary Trees

Agreed.

I simplified it though, basically the answer can't be more than 2, you can just change 1st and 4th element to get a beautiful array.

You can easily check if answer is 0, now just check if answer is 1.

If 1st and 4th elements are equal, you just wanna make 2nd and 3rd element different from 1st, if that can be done in 1 move, answer is 1.

If 1st and 4th element are unequal, then either 1st element will take 4th's value or vice versa, so just try both and this case can also be checked pretty easily.

Another way could've been, to make a check function and then try every move on the array and check.

You forgot to resolve 3-length cycles, i guess...

Consider the array,

[1,2,3,1,2,3,1,2,3,1,2,3, 2,3,1]

is your answer 2 for this case?

Video: A very interesting Multiset Hashing Solution to Problem E

Posting this because the Editorial to problem E is not posted yet (and I talked to the problemsetters and their solution is different from mine)

My solution ideas for E, G, since there is no tutorial for E and G, yet.

E Code

G Code

(Sorry for not including formal proofs and latex, i find it easier to understand and explain intuitions)

When I use my muscle memory to open the Contests page, the Catalog opens up :(

Small suggestion: I noticed that all of the problems in "< x" ladder are of rating "x — 100", so maybe just rename them to "x — 100" instead?

Video Solutions of all problems

This gives me the vibe of those memes which are like... "Your birth month will decide who you'll marry" and there are pics of 12 actresses, one for each month...

Upvoted because of propaganda against propaganda against anime propaganda

I tend to use both Implicit and Dynamic Segment Tree. Sparse Segment Tree also sounds correct and is often used by people.

However, Compressed Segment Tree reminds me of this blog by bicsi. Plus implicit segtree doesn't "feel" like it uses compression.

Lazy Creation Segtree is technically kinda correct but it sounds lame (and can be confused by lazy segtree), so nope, rejected.

Lastly, if you think about it, implicit segtree is actually a Bitwise Trie!

Thanks for this Mathematical Proof of the technique!

Before this, I always thought of this technique as a fast way of substituting the value of the highest order term repeatedly, and assumed that the operations involved are just "coincidentally" the same as poly mod poly.

This is where this discussion began:

So if I participate from Div1 and solve all problems, you donate 6.255 USD, that's nice. But that's too tough, I'll just donate 7 USD myself instead.

Observing The Universe Really Does Change The Outcome, And This Experiment Shows How

When you use cout, you "observe" it, I think it has something to do with Quantum Entanglement.

So you think a random grey from CF (you) knows about it, but he (my college mate) doesn't know.

Also, I talked to Anshu, he doesn't even want the channel.

I didn't know being a youtuber is so cool. You can literally clickbait people by simply being fired from your job.

Moreover... Here's a paragraph:

"Formally, we say that the connection between districts i and j is smooth if there is a series of wires starting from i and ending at j such that none of the wires is under repair. Otherwise, it is laggy. Under a laggy connection, gamers on districts i and j unfortunately have to be polite to each other, even though the lag is really to blame."

Notice how the statement which starts with formally leads to something that is totally useless to the problem. When I read this part, I got confused and started figuring out if there is something related to blame.

AT LEAST, change the paragraph after a formal statement before adding useless bullshit.

"misdirecting"

Let's take G for example. If I read the whole story carefully. There are some gamers connected in form of a tree and during a maintenance day "a subset" of tree edges is marked as laggy. and so on

That's what one would understand from the story. Later you plainly tell us that only 2 edges per maintenance day.

That's exactly what I meant by "unnecessary" also. The story fails to explain the key details of the problem. At least include it in the story that somehow it's not possible to repair more than 2 wires in a day or something.

I don't mind a good story but in this contest the stories were: boring, annoying, unnecessary, irritating, bad, confusing, lengthy, misdirecting and (in some problems) counterintuitive.

chup chapri.Don't write these useless messages.

Anton now has a nutella colored bee. Orz

I think the number 250 is more "round" than 300.

If you can't believe that then you're in for a treat. Below are the categories in which the prizes will be given:

• Top 10 global Div1
• Top 10 Indian Div1
• Top 100 Indian Div1
• Top 200 Indian Div2 (only first time)
• Top 200 Indian Div3 (only first time)

Nope, only me.

But I don't "already got a job that pays them lakhs rupees per month", I'm a college student. And I made 97 videos not "2-3 youtube videos".

So this post is about nobody.

Omja's Last Idea.

Count me in too (as a mentor).

Ok so let's say you have a big segtree of size $$$N$$$, and instead of that you could have had smaller segtrees of size $$$n$$$ each. (Here I have assumed for simplicity that all smaller segtrees are same in size but it doesn't matter)

Anyway... We have $$$n \le N$$$, so obviously, $$$log(n) \le log(N)$$$ (cost of a single update/query). Using multiple segtrees is the asymptotically better option.

Regarding cache-friendly behaviour, I am not very sure about this but it seems like smaller segtrees are more likely to be better but can't explain why.

I find it hilarious that the first account on CF you created... You named it "not-an-alt"

Suggestion: there should be an option to add a short description about the problem while saving... I mean, if I save problems, I'd have short descriptions:

1097D — Easy String DP

622F — Linear Time Polynomial Interpolation

Or maybe even something like... "Solve this before Saturday"

One short sentence will increase the usability by a lot.

Alright so I'm finally mentioned in a blog with the tag shit_ytubers.

I had seen this day coming but in a different context.

You're already an expert, CF has more expectations from you. Just show CF that you can live up to their expectations. Best of luck :)

Even if you couldn't solve the problems, you at least tried. The +216 points are for your effort. Keep Practicing!

Regards Utkarsh Gupta

Wow you redeemed yourself!

AKS primality test originated from IIT Kanpur. (Indian Institute of Technology Kanpur)

No need to watch my video for that. The solution is just... weighted bipartite matching... There will be N² edges in total... So if you use Hungarian Algo, it's $$$O(N^4)$$$

But this is not required, DP+Bitmask is more than enough for this problem.

While we're at it, let's solve the Solution vs Answer debate also, it's causing bugaboos to a lot of people.

This is a little funny because I believe I myself take a lot of time in implementing a binary search :)

I hope 2100 isn't his Hyperbolic asymptote.

Are you AtCoder Grand Contest? Because you always make me cry

Are you Monogon? Because I'm going to give you contribution!

My solution is same as this https://mirror.codeforces.com/blog/entry/89979?mobile=false#comment-784021

The dfs tree just automatically defines a toposort, which is something i realised after the contest.

https://www.youtube.com/watch?v=2y3stYERBAI

This is my screencast(rank 77) for the contest along with solutions for all problems, do check it out if you're interested.

Someone: Ehab round is tomorrow or yesterday?

Me: Yes

I believe you misunderstand the situation. It is common in India(and possibly in a lot of other countries too) to write things in English even if you're speaking in your native language. That's why the titles are in english, it's not supposed to "trap" foreign viewers (moreover the YouTube Algorithm anyway punishes clickbait videos).

Nice try but I keep telling people that I couldn't get shortlisted by Google and Microsoft, why would I do that if I wanted to sell something to get into those companies?

The view expressed in the analogy seems to assume money only comes from taking a cushy job at someone else's company

It does, obviously free content would be beneficial to people who just like being good at CP for the sake of it... I am only talking about people who only want SDE jobs (like the people buying the course mentioned in this blog). I have 100s of people asking me the secret to getting a good job at a multinational company. Even if there was such a secret, revealing it would nullify its value, and that's how I came up with my idea that resources aren't really helping people who want jobs.

tech companies will die off

depends on whether things we learn in CP are actually required at jobs... i have no personal experience but I've heard that most of the CP knowledge is useless outside CP.

1. I'm saying a less-accessible resource would be more beneficial to the user, obviously private tutoring by a good teacher would be the best resource.

2. every person gains different amount of knowledge, true, but slow-learners would perform even worse without resources and quick-learners would still do ok, so it doesn't affect the overall situation.

I know of quite a few people who didn't pay for private lessons and yet landed a good job (and/or did well in competitions)

My whole point is, they would've performed really good even if the free resources didn't exist. In a competitve setting like "getting a job" where the bottleneck is "number of jobs", freely available resources don't reward the ones who use it, they punish the ones who don't use it.

Consider a simplified example... There's an exam with relative grading, there's only 1 book, you study it and get good marks, now imagine if there is 1 more books in the market, now if you don't study that also, you get worse marks, but since everybody can use it, nobody has any advantage.

I believe the prisoner's dilemma applies in advertising etc as well, I see a similarity here.

See this Sport Doping example from Wikipedia.

Doping in sport has been cited as an example of a prisoner's dilemma.

Two competing athletes have the option to use an illegal and/or dangerous drug to boost their performance. If neither athlete takes the drug, then neither gains an advantage. If only one does, then that athlete gains a significant advantage over their competitor, reduced by the legal and/or medical dangers of having taken the drug. If both athletes take the drug, however, the benefits cancel out and only the dangers remain, putting them both in a worse position than if neither had used doping.

It can easily apply here as well... It is better if people on the large scale co-operate and not study using a freely available resource (if getting a job is their only motive). Using the resource gives them an upper hand, but if everybody uses it, the benefits cancel out and everybody just wastes a lot of time and effort in studying.

I don't see how I'm wrong here.

While I agree with the other stuff on this blog. I just wanna casually point out that "free on youtube" content would never help anyone get a job due to a game theory concept called "Prisoner's Dilemma"

And yes, I'm saying this despite having a youtube channel of my own.

EDIT: well of course this doesn't mean you should stop watching cp youtube videos, read my subsequent replies for more info.

To the 5k people pinged by this, hope you have a nice day, and remember to drink enough water :)

Can you tell 1 example problem of the "Distribution DP" trick?

I am not able to figure out what it is from the name alone...

Is it another name for "Tree Convolution DP"?

I believe it's better to make the participants click a "confirmation button" like 1~2 minutes before the contest starts...

This sounds fair to me, cuz like during an onsite contest, you have to kinda report at the place a little before the contest starts, so why not in online contests too? 2 minutes isn't a lot of time anyway

If somebody makes this thing for competitve programming, it certainly won't be tree. It'll be a huge graph with cycles and self loops and multiple edges (idk what those signify but it sounds cool)

If you want to introduce gr9 students to CP, you should show them one or two easy problems like Watermelon (4A), at least that's how I was introduced to CP.

I think it was a bit careless on his part (especially because he has already solved a problem on CF which uses the exactly same idea).

While I'm NOT SAYING that he did it intentionally, but usually when you have solved a problem, you should remember that and such a mistake should be avoided.

https://mirror.codeforces.com/contest/280/problem/B

This 8 years old CF problem also has the essentially same idea. Exactly same in fact.

The interesting thing here is — Ashishgup has already solved this problem in 2018. Link to his submission

(EDIT: I added it to the main video, and for the first 15 minutes, I'm reading the hilarious comments to this blog)

In a separate blooper video that's still going on since the contest just got delayed...

I am actually making a video on this contest and this is getting slightly annoying to my future viewers that the problems aren't visible :)

there are barely any algorithms that you will need to get to blue (or even yellow these days, for that matter).

(or even red these days, for that matter). But the OP was talking about very basic algorithms like DFS, BFS etc that are not well known to newbies, so it'll be good if they learn those.

Sometimes a problem that is supposed to be hard is easy, the scoreboard helps you with finding those.

That's true, I would also like to add that you can sometimes guess a lot of things about a certain problem's solution just by looking at the standings. (For example, "a lot of people solved this problem in 5~10 minutes, there is probably a hidden observation which will make this solution a 2 liner")

Only replying to your last paragraph. There's a thing called college reputation that exists. I won't be surprised if people who have graduated from college (and hence can't participate anymore) might be willing to help their juniors.

I think the constraint of "only X number of teams from one college reach the regionals" can limit the amount of cheating to a great extent (but not eradicate it).

This thing is present in kanpur(2 teams), gwalior(2 teams) and kgp(1 team) sites but not in amritapuri although amritapuri has certain reserved seats which are filled by only 1 team per college (or at least that's what happened in 2019).

In my personal opinion, there will be a lot of cheating even with these constraints, but it would be infinitely more without such constraints.

While we're at it, how about this feature.

"Filter Recent Actions based on rating of the person who posted or commented"

I think this is important because if some LGM or IGM posted or commented anywhere, I would like to read it. Also it would give users an easy way to filter spamming done by beginners.

Yeah that was the joke. It sounded like a flex because I mentioned "first contest", but anybody would do such a mistake in first few contests only.

I only solved easy problems from a2oj ladders, I didn't know anything about levels, divisions or ratings.

You can actually check my earliest submissions, at least 150 of them are only from a2oj ladders.

CF+hackerrank combined, around 200

When I was participating in the first contest of my life, I didn't know that the difficulties increase so much, so when I couldn't solve the easier problems, I opened F thinking that maybe it would be easier than the previous problems. But obviously, I didn't even understand the statement.

-deleted-

I was just explaining why his code "has been running for a few minutes and cannot find it"

So you didn't disprove my proof.

I can prove that it is impossible.

All our initial numbers are of the form $$$(nx+my)$$$. Where at least n or m is even.

Whenever you apply an operation, on $$$(n_1x+m_1y)$$$ and $$$(n_2x+m_2y)$$$, you get $$$(2n_1-n_2)$$$ and $$$(2m_1-m_2)$$$. It is easily provable by induction that both of the terms can never be odd.

Consider the case 3,6. The answer is 8 but the bitwise OR is 7.

(In particular, the answer will be equal to bitwise OR if all non-zero bits are linearly independent)

After being asked to do it by multiple people, I finally made a video explanation of all of these problems on my youtube channel.

For problem 6, we can notice that LCA can be thought of as a monoid operation, so we can make a normal segtree on the range [1...N] and store the LCA in the segtree nodes. (we can store -1 corresponding to non-leafs, which will work as an identity element: LCA(x,-1) = x = LCA(-1,x))

To make it better we can notice that LCA(X,X) = X, so it is also idempotent, so we can use a sparse table as well. Which gives us a fast solution. $$$O((NlogN+Q) * f(N))$$$. Where $$$f(N)$$$ is the time in which you calculate LCA ($$$O(logN)$$$ or $$$O(1)$$$ depending on how you do it)