I like that feature on AtCoder that allows you to register unrated on any contest, because sometimes I'm not sure if I would have time to solve till the end of the contest. Although when you think about it, if you get a positive delta, and you are unrated, it's a bit sad. :D

I admit, at first, I didn't want to believe that AI would, in the near future, be able to solve CF problems just because they are extremely convoluted and require multiple steps and observations. But after losing ~300 rating points over ~10 competitions due to cheaters, now I have to believe it. I guess cheaters are training ChatGPT and other LLMs and this have become a feedback loop. The better the AI is, the better it can be trained by cheaters to solve even more complex problems. In short, that is why I no longer want to compete here. This is getting ridiculous. Until there are some reporting features and stricter bans, the rating system will be completely broken.

D fails when using std::map and std::set and cleverly swaping elements with overall time complexity of O(Q log N), but apparently passes easily when using GNU's Tree structure with very similar constant factors. Come on, test better next time. Absolute bs.

I saw that the bounds allow for $$$O(N^2)$$$, but since I quickly saw greedy should also work, I was too lazy to think about index handling for the $$$O(N^2)$$$ solution, so I just went and solved it $$$O(N)$$$. :)

Great problem btw!

I immediately thought of DFS trees, but it seemed too complicated to track the cases, so I tried using SQRT decomposition. For nodes with more than SQRT(M) degree, do DnQ over all N nodes excluding the edges coming from that node, and for nodes with less, do a DnQ over time. But it comes out to O(sqrt(M) * log(M) * (M + N)) which sadly doesn't pass all :(

I will try to solve it with DFS trees some day... Is there some other interesting solution for it?

Correct me if I'm wrong, but Treaps will allow you to do exactly what you want, online, as well as when the queries are mixed:

• Insert query in O(log(N)): Just insert a single node treap at position k. To get to position k you maintain the size of each subtree in the treap. And update them accordingly when you modify the treap.
• Get by index query in O(log(N)): Just go down the treap and by knowing the subtree size of the left child, you know if the index is in the left child, or in the right. If it's in the right, don't forget that the new index is id - sz[left] to offset it.

Most of the time, if you can't come up with a modification of a treap, what you can do is for each sqrt(Q) queries, you can iterate across the whole treap (which takes O(N)) time and update proper indexes in some other array. And in the queries in between these sqrt(Q) events, you will remember the newly inserted indexes by brute force (at most sqrt(Q) of them) and thus solve the problem in something like O((N + Q) sqrt(Q) + Q log(N)), which will be fast enough for most problems.

As a tester, I can say that the problems are very educational and I really enjoyed them! Hope you have fun practicing and good luck to all!

I'm a simple man. I see adamant blog, I click it. :D

Wow, dude, this is really nice! Because of commutativity of AND, this is possible! I thought that I could solve it as well with convolutions, but didn't see the commutativity and ended up solved it using the standard n * 2^k dp.

That's great, it will save so much time!

It would also be wonderful if the users can switch through the languages when they are presented with the problems. A few weeks ago, I organized a contest on my faculty with my own problems, but because of the rules on the faculty, the tasks had to be in Slovene. So, because of this limitation, I wrote the Slovene statements in the "English" tab and the English statements in the "Slovene" tab. This way, the Slovene statements were "default" and I only exported the English as .pdf file.

Adding such a language chooser would be greatly appreciated by many! Thank you.

Can you explain the proof of the expected number of collisions and the meaning of $$$w$$$ in $$$2^w$$$? Thank you.

First, let's take a look at the case where the size of array a is 1. We'll have the following answer:

answer = GCD( a[0] * b[i], a[0] * b[i+1], ...)

This can be simplified to answer = a[0] * GCD(b[i], b[i+1]...) = a[0] * GCD(b).

Now, what if we have a bigger array a, then we have the following derivation:

answer = GCD( a[0] * GCD(b), a[1] * GCD(b), ...)
       = GCD( a[0], a[1], ...) * GCD(b) =
       = GCD(a) * GCD(b)

I agree that it may collect false statistics, but regardless, it's a good step forward. Sometimes there are just bad problems, you can't deny that. And, I appreciate the effort of the authors to step forward and give chance for feedback. This says that the authors are careful and I hope we'll finally have some good problems, not just edge-case work.

https://www.codechef.com/problems/GERALD07