As a tester, Monogon orz.

If you don't upvote Monogon, you won't get positive delta. Good luck!

1-gon,just remember one thing ,with great power comes great responsibility. Orz 1-gon Orz

You can still be VIP coordinator...

Yet another blog where Monogon has more upvotes than the blog itself

why

hii rotavirus

call it a bad round 3days before the round begins -> bad comment

ah, a man of culture indeed

Maybe not speedforces, but balanced like 1300 A, 1500 B, 1700 C or something like that but harder than normal round ABCs.

Thank you for your reminding, I have updated the announcement :)

If we are given 5 problems so why the scoring distribution is saying we're ganna have 6 problems ?

The problem is that you are not in the tester's list...

Top 10 before-contest commenting rituals

Wow, this round was prepared by students from Beihang, which my ideal university is!

Wish all the best to you. And I hope I'll be able to get the lost rating in my last contest.

How to bitwise?

Please don't start hopeforces

Ya too much long queue!

Dude, Why are u searching that in contest time. xD

??

Actually I am the shit

The same answer for how I can become you.

first 4 problems were like 4 problems of div3.

Ah ♂ That's ♂ Good

I'm not sure what was intended, but I used a randomized approach until there existed a connected component of large size, then I just tried all edges that have an endpoint not in that large component.

How would this version be solved?

I have thought of a way in which we can find if the first element is 1 (to check for chains like n+1,1,2,3,4,...n) and to ask if a[n]==0 to check for chains like 1,2,3,4,5,...n,n+1.

However how to check for other cases where the answer is possible.

Yea, nice one.

But I personally don't like it when problem consists of 10 easy subproblems, so I would make this as a standalone problem

What type of queries we can ask from interactor?

It exists on cf https://mirror.codeforces.com/problemset/problem/1019/B . It is one of my fav problem.

E was just like you calculate total number of sequence or pairs with gcd == x, like go from end

pseudo code be like
for j = m to j = 1:
ans[j] = calculate(j)
for(int i = 2 * j ; i <= m; i+=j) ans[j] -= ans[i]

calculate(j) is of complexity m / j * n, using dynamic programming
in total its $$$\sum_{y=0}^{m} (n * (m / j)) = O(m n log m)$$$

let f(i) = number of sequence of length n with gcd == i for each range [lj,rj] 1 <= j <= n , there will [ (lj+i-1)/i , rj/i] number of element which are of multiple of i and therefore number of choices as well.

Now, to compute f(i) we need to find a solution to the equation

a1 + a2 ... an = m/i where each aj : [(lj+i-1)/i,rj/i] we can use PIE to solve above equation.

Now, total number of sequence with gcd 1 will be sum of mu(i)*f(i) over 1 <= i <= m

can you share some resources to learn the topics u mentioned for problem e ?

In problem D, you can add all possible edges from $$$1$$$ to other vertices. Then, divide all vertices into two groups: the first group consists of vertices in the same CC with $$$1$$$ in the first graph and in different CC with $$$1$$$ in the second graph, the second group is vice versa (some vertices may not lie in any group). Now we can add an edge between any pair of vertices from different groups, so we just have to maintain two queues of these groups and delete a vertex from a queue if it becomes bad at some point. Overall, it works in $$$O(n \cdot DSU(n))$$$.

Interesting, that the mu function makes it straightforward. But since I have no about what it is (:P), I ended up with a separate DP which counts arrangements for all GCDs efficiently, eventually ending up with GCD = 1 arrangements.

Edit: I am talking about D2

I also had the $$$(\log{n})^2$$$ idea initially (small to large merging with some multiset-like data structure). I optimized it by using the following simple idea to construct edges:

If any forest becomes connected, we are done. Otherwise, both forests have at least $$$2$$$ components. Consider any two nodes $$$x$$$, $$$y$$$ in distinct components of the first forest and any two nodes $$$p$$$, $$$q$$$ in distinct components of the second forest.

If $$$x$$$ and $$$y$$$ are in distinct components of the second forest, then add edge between $$$x$$$ and $$$y$$$. Otherwise, at least one among $$$u$$$ and $$$v$$$ will be in a different component than $$$x$$$ and $$$y$$$ in the second forest, say $$$u$$$. Now, at least one among $$$x$$$ and $$$y$$$ will be in different component than $$$u$$$ in the first forest, say $$$x$$$. So merge $$$u$$$ and $$$x$$$.

This construction in fact acts as a proof for the solution!

I think it was not guessing the answer.

If you have read/studied Krushkal algorithm it uses Dsu to ensure that the new vertices do not form cycle with previous edges. Same is the case with this problem.

I took all the unaccounted edges in a set and traversed through all and checked whether adding would lead to a cycle in any of the 2 graphs. However, I got time limit exceeded on test 6. Can you tell what extra optimization did you do? Here's my submission.

My explanation is that:

$$$[1]$$$ Let $$$u$$$ and $$$u'$$$ are any 2 nodes in Mocha graph that not in the same connected component

$$$[2]$$$ Let $$$v$$$ and $$$v'$$$ are any 2 nodes in Diana graph that not in the same connected component

There will be at least a way to connect $$$u-v, u-v', u'-v, u'-v'$$$ to form 2 forests without making a cycle to it.

If there is no such $$$u'$$$ or $$$v'$$$ then there will be no more edge since no matter how we add edge it will form a cycle else we can repeat this multiple times

No matter what is the order you choose for the edges to be add, it will always such edges that satisfy the statement — which is not making a new cycle into graph — such $$$u-v$$$ or $$$u-v'$$$ or $$$u'-v$$$ or $$$u'-v'$$$ satisfied $$$[1], [2]$$$

Therefor we will have the result of maximum possible edges can be added, by keep finding new $$$u, u', v, v'$$$ satisfied $$$[1], [2]$$$

By using brute-forces algorithm for each possible $$$i$$$ and $$$j$$$, we tested for all for cases ($$$i = u$$$ or $$$i = u'$$$) with ($$$j = v$$$ or $$$j = v'$$$) for any $$$u, u', v, v'$$$ satisfied, those who are not will not included in the result, those of which are needed will added to result

We don't need to redo the brute-forces every times we add a new edges, since those are which either already an edge or will make a new cycle, and will never satisfy again

Using Disjoint Set Union Data Structure, we can check for any 2 nodes that in the same connected component or not

Therefore we only need brute-forces for $$$O(n^2)$$$ with a little help of data structure $$$O(\alpha(n))$$$ amortized per query

Well some proofs for D1 did help in solving D2. For example my proof (and solution for D2) described here.

Yes, there will always be an answer.

Case 1:jumping from n+1 to 1 Case 2:jumping from n to n+1 Case 3:jumping from i to n+1, then n+1 to i+1

was it easy?

u just use the & operation over all the elements...

ans=a1&a2&a3&a4&...&an, since a&b is always not greater than a and b themselves.

I just apply operation on the whole array until i get an array with all element being equal.

man that is so easy yet so complicated :D

Well, DSU is quite a common data structure nowadays most of the newbies and pupils know about them if they have gone through the kruskal's algorithm.

Hey, I solved C using DFS with Toposort you can check it here 125991523.

I think there is all 1's in 2nd pretest.