There is a feature now, that it cannot be earlier than the systests, so don't hope for much in the future :P

Well, I think that we should always assume that people have to believe a bit, but ofc during the preparation it's good to have proofs.

A priority queue is enough to maintain the function. You can just maintain the turning points of the increasing and decreasing parts. Adding |x| will result in the movement of $$$O(1)$$$ turning point between two parts.

61176125

We actually don't think this problem can be solved in $$$O(n^{2 - \varepsilon})$$$ time for any $$$\varepsilon > 0$$$ — we can prove that it's at least as hard as 2-Orthogonal Vectors problem (definition 6 in this paper). If we assume that the Strong Exponential Time Hypothesis is true, then 2-Orthogonal Vectors (and therefore Div2D as well) cannot be solved faster than $$$O(n^{2 - \varepsilon})$$$.

At every node, we are sending all the possible gcds from the ancestor as well as the current node. Now, this current node can take logn different values and if the height of the tree is n, wouldn't it become nlogn different values. Can you help me where I am going wrong?

I have not understood yet. why not 20?

can you explain this case

10 3 3 5 5 6 6 1 2 4 7 1 1 1 1 1 1 1 1 1 1

ans : 9

For n=7 it's similar to n<=6 but we can have two nodes having same number as long as the number of dice and given condition ensured.So, iterate on pair of nodes for having same colour and find max among all cases

I did that too, and it works

Just keep an array of all dominoes you have left, by their upper half number and their lower half number

Edit : A person in the group should not be better than every other person in the group.

I understood it as follows.

Consider the change in potential after each query: (number of edges that start pointing left to right but were pointing from right to left before) (positive change) — (number of edges that start pointing right to left but were pointing from left to right before) (negative change).

Consider the process of adding edges too at the beginning (while forming the graph, before performing any query) as adding 1 to potential if edge is left to right.

Now, the positive change can only happen at most sqrt(2*m) times for each query and hence all the positive change would sum to m+q*sqrt(2*m) at best.

The negative potential change sum can't exceed the positive change sum (as potential can't be negative), hence its max value is also m+q*sqrt(2*m).

One operation of one query basically only increases or decreases the potential by 1. So, the total number of operations would be (positive change sum) + (negative change sum) which is 2*(m+q*sqrt(2*m)) at best.

Or maybe it's a subliminal message to make his channel more popular than T-Series. Who knows :P

Thanks for finding a typo!

s/increasing order/decreasing order/

We'll push a fix shortly.

THe problem states that the the '7' can only be in the group, if he isn't better than each of them In that case the 7 is better than all the other numbers (you have to check one by one)

You have to check the entire group. Pretest 2 is 1,2,3. If the team is 1,2,3 then 3 will think he is better than everyone if the team 1,2; both will think they are better than everyone(only one teammate in this case) if 1,3, 3 will think he is better than everyone

I solved it with the same idea. I add an edge from $$$i$$$ to $$$j$$$ iff $$$j$$$ has all the skills that $$$i$$$ has. As you mentioned we can see that we can add all the nodes to the answer that have a path to a cycle (or are part of a cycle). I run $$$dfs$$$ on every node but keep a $$$dp$$$ which prevents to run $$$dfs$$$ if you already know whether this node leads to a cycle or not. — 61210128.

I also solved this building a directed graph. But instead of finding cycles I stored out degree of nodes and the reverse graph. Then for each node with out degree 0, decreased out degree of every other node that it came from(From the reversed graph). And finally took the values with at least one out degree remaining. Code

Note that $$$n \leq 7$$$ by problem constraints.

For $$$n \leq 6$$$, the answer is just $$$m$$$, since we can always place dominoes such that the ones point to node 1, the twos point to node 2, etc, and we end up using the dominoes with the same pip numbers as the edge numbers given in the input. Since there are no duplicate edges, every edge can have a domino placed on it.

For $$$n = 7$$$, things get slightly trickier, as two vertices must have the same domino number pointing to it. We can brute-force every pair of vertices as a candidate for same-domino-number assignment. For each such pair $$$u$$$ and $$$v$$$, the number of "colliding" edges is equal to $$$|S_u \cap S_v|$$$, where $$$S_u$$$ is the set of vertices connected to vertex $$$u$$$ (or in other words, the number of vertices connected to both candidate vertices). Find the pair with the minimum collisions, and subtract the collisions from $$$m$$$ for the final answer.

Sample code (in Kotlin) 61213061

Codeforces runs on 32-bit systems, hence long int is only 32 bits long here.

Just put those values in Berlekamp–Massey, easy xd

+1

Let $$$S_u$$$ be the multiset of all values $$$f(t, u)$$$ where $$$t$$$ is an ancestor of $$$u$$$. Then if $$$v$$$ is a direct child of $$$u$$$, $$$S_v = \{x_v\} + \mbox{map}(S_u, \{ i \mapsto \gcd(i, x_v) \})$$$. ($$$\mbox{map}$$$ refers to the higher-order function that makes a new collection with each element in the old collection transformed by the given function)

How is this derived? The $$$\{x_v\}$$$ part comes from the new element $$$f(v, v) = x_v$$$, while the $$$\mbox{map}$$$ part comes from the fact that $$$f(t, v) = \gcd(f(t, u), x_v)$$$

The number of distinct values in $$$S_v$$$ for any vertex cannot be more than $$$\log_2 \max(x)$$$, as noted in the editorial.

This transition can thus be efficiently implemented by computing $$$S_u$$$ as a hashmap, then passing that map to the children for use in computing their own $$$S$$$ multisets.

Example code (in Kotlin): 61249254

Hi, i did that approach.

The main idea is that for a fixed node $$$u_0$$$ you can decompose the path from $$$u_0$$$ to $$$1$$$ in differents paths like this ( let $$$f[v]$$$ be the parent of node $$$v$$$ ) :

From $$$u_0$$$ to $$$u_1$$$ , from $$$ f[u_1] $$$ to $$$u_2$$$ , ... , from $$$ f[ u_{k-1} ] $$$ to $$$u_k = 1$$$, such that $$$u_1$$$ is an ancestor of $$$u_0$$$. Such that the $$$gcd$$$ from node $$$u_0$$$ to a node $$$v$$$ its equal to the $$$gcd$$$ from node $$$u_0$$$ to a node $$$w$$$ if and only if $$$u$$$ and $$$w$$$ are in the same semi-path.

In other words, the nodes of a same semi-path has the same $$$gcd$$$ to node $$$u_0$$$ and nodes from different semi-paths has different $$$gcd$$$ to node $$$u_0$$$.

And to do this, you can use binary lifting to find first node of every semi-path.

I don´t know if i explained it well, but here is my code 61246386, ask me every thing you want. :D

Binary representation of $$$1$$$, $$$2$$$ and $$$3$$$ are $$$01$$$, $$$10$$$ and $$$11$$$ respectively. If you put all these people in a group then $$$11$$$ will think he is better than $$$10$$$ because he knows an algorithm that the $$$10$$$ doesn't know. And again $$$11$$$ will think he is better than $$$01$$$ because he knows an algorithm that $$$01$$$ doesn't know. So he will think he is better than everybody else. That's why you can't group $$$1$$$, $$$2$$$, and $$$3$$$. Both $$$10$$$ and $$$01$$$ will think that they are better than the other one. So you can't find a group at all.

In this problem you need to find the cummulative gcd of vertices from the current vertex to it's ancestor and then sum it all up. The way it's to be done is using the fact that there won't be more than logn different blocks with same gcd for a given vertex.Take an example [2 3 6 6]. Suppose u are at vertex 6, there are 3 blocks here 6,6 with gcd 6, 3 6 6 with gcd 3 and 2 3 6 6 with gcd 1. Basically each time you go left you will either get the same gcd or a gcd that divides your current gcd. And as the smallest divisor in this case can be 2. It proves that there will be atmost log(n) different blocks with same gcd. Now seeing this the rest in implementation and easy to do. just go through each node and then store all the gcd along with their counts in a map. Now what you can do is use the gcd of parent vertex and then find gcd wit the current vertex and add to answer cnt*gcd(prev_accumulatedgcd,va[current]. After doing this for all prev_accumulated gcds update the map with all the gcd's you just found and then do dfs. This way you will get your sum. So overall complexity is O(n -> for dfs * logn -> for inserting values into map * logn -> for counting of values with logn blocks of previous gcd).

(1) The answer won't change if xi could be any arbitrary real values.

You can model the problem as minimum-cost flow: take $$$n$$$ vertices $$$v_1, \dots, v_n$$$ corresponding to the scales, and add a source $$$s$$$ and a sink $$$t$$$. The units of flow will correspond to the paths taken by each coin. Let $$$M > \max(n, \sum_{j=1}^n a_j)$$$. The edges go as follows:

• $$$s \to v_i$$$, with flow $$$a_i$$$ and cost $$$0$$$ (we put $$$a_i$$$ coins on the $$$i$$$-th scale),
• $$$v_i \leftrightarrow v_{i+1}$$$, with flow $$$M$$$ and cost $$$1$$$ (we can move the coins along the circle),
• $$$v_i \to t$$$, with minimum flow $$$l_i$$$ and maximum flow $$$r_i$$$ and cost $$$0$$$ (the number of coins after all shifts has to be in some interval). We can implement this e.g. by adding two edges: one with flow $$$l_i$$$ and cost $$$-M$$$, and the other with flow $$$r_i - l_i$$$ and cost $$$0$$$.

We can see that the minimum cost of the maximum flow in this network is equal to the minimum time needed to solve the riddle, minus $$$M \cdot \sum_{j=1}^n a_j$$$. Now, it's a well-known fact that in the flow instances with integer capacities, there exists an optimal flow using only integer flows (even if we allow any real flows). This solves part (1).

(2) The arithmetic mean of two feasible solutions is a feasible solution.

If $$$(p_1, p_2, \dots, p_n)$$$ and $$$(q_1, q_2, \dots, q_n)$$$ are feasible solutions, consider a solution $$$(r_i)$$$ where $$$r_i = \frac{p_i + q_i}{2}$$$. We only need to prove that $$$a_i - r_i + r_{i-1} \in [l_i, r_i]$$$. However, the left-hand side is the arithmetic mean of $$$a_i - p_i + p_{i-1}$$$ and $$$a_i - q_i + q_{i-1}$$$. Both these expressions were in $$$[l_i, r_i]$$$ interval, therefore $$$a_i - r_i + r_{i-1}$$$ is good as well. This solves part (2).

Let's now prove that $$$F(p) + F(q) \geq F\left(\frac{p+q}{2}\right)$$$ for any real $$$p$$$, $$$q$$$. Take $$$(p_1, \dots, p_n)$$$ as the optimal solution for which $$$p_1=p$$$, and $$$(q_1, \dots, q_n)$$$ as the optimal solution for which $$$q_1=q$$$. Now, notice that $$$x \to |x|$$$ is a convex function. Therefore, $$$|r_i| = \left|\frac{p_i + q_i}{2}\right| \leq \frac{|p_i|}{2} + \frac{|q_i|}{2}$$$ for each $$$i$$$. As $$$(r_1, \dots, r_n)$$$ is some solution (not necessarily optimal) for which $$$r_1 = \frac{p+q}{2}$$$, we have that $$$F\left(\frac{p+q}{2}\right) \leq \sum |r_i| \leq \frac12 \left(\sum |p_i| + \sum |q_i|\right) = \frac12 (F(p) + F(q))$$$.

Therefore, $$$F$$$ is convex and has an optimum at some integer point. Hence integer ternary search works.

We create a set of $$$O(k)$$$ generators: $$$g_1, g_2, \dots, g_\ell$$$. Each element of the subgroup is then a product of these generators in some order, possibly with some generators occurring multiple times (or not at all). You can therefore have at most $$$|V| \cdot k$$$ edges in your graph: you only need to multiply by $$$g_1, g_2, \dots, g_\ell$$$ in each BFS/DFS iteration.

Therefore, each BFS/DFS will take at most $$$k!k$$$ time. This would suggest that the total runtime of processing each prefix is $$$k!k^2$$$. It's not true, though — each new subgroup in the subgroup chain is at least twice as large than the previous one. Therefore, the running time is something like $$$\sum_{i=0}^k 2^{-i} k!k = O(k!k)$$$.