Can anyone explain in detail problem c div2?

Can Some Explain Div2 B with more detail and Example.

Could anyone explain this sentence "if remainders sequence has k steps while you consider numbers by some modulo it will have at least k steps in rational numbers" in problem 901B - GCD of Polynomials?

In Div 2 C, is there any solid prove to this: if there is such a height k that a[k] > 1 and a[k + 1] > 1, then we can create 2 non-isomorphic trees from the current sequence? I mean how can we know if 2 created trees from that sequence are non-isomorphic or not?

Can we solve 1B through a random algorithm? As we all know, there are hundreds of thousands of possible solutions, and I have no idea on construction of such a sequence, so I used a random algorithm and passed system test.

Here is my code. Hack is welcomed.

How does the checker work for problem B div 1? It would seem that it might require large (how large?) bignums. I guess it can compute the GCD sequence with a random prime modulus. If it works then great. If not then try another modulus. Once the product of the primes you try is larger than the largest number you'd ever need, I guess you can declare it "good".

can someone please explain the idea behind DIV2-D. How fibonacci polynomial leads to the desired answer?

I was upsolving problem C in Div2, using PyPy2 and got a TLE on test case 14. The complexity is O(sum(a)) which is fine, but still got a TLE. However it was accepted when the same code was submitted in Python2 and Python3. I had always known PyPy to be faster than native Python. This has been true in Codechef platform. Can anyone reason as to why it TLE'd in PyPy2?

Python2 Accepted, Python3 Accepted, PyPy2 TLE (14)

For Div1B:

Why does xp_n +/- p_{n-1} always have coefficients in {-1,0,1} for some choice of plus/minus? Is there a reason, or does it just happen to work for the given bounds?

Could you tell me which knowledges are required to understand div2 D's solution?

To come up with the solution like in Div2D / Div1B, I would rather thinking like this:

We already know that it takes two steps to find (x² + 1, x).

Let's say we need to find the pair that takes three steps. If we call it (A, B), such that the polynomial division A / B will have the divisor equal to x² + 1 and the remainder equal to x. By that way, we will find (A, B) by continuing finding (x² + 1, x), which takes two steps. Therefore, it takes three step to find (A, B). Now, as I stated, the divisor equal to x² + 1, then B = x² + 1. The remaining task is to find A which has the form of A = (x² + 1)Q + x.

We can freely choose Q to obtain A. However, to satisfy the restriction that coefficents must equal to  - 1, 0, or 1, Q should be x or  - x. This solution is pretty close to what is stated in the tutorial. (Mine is p_n + 1 =  ± xp_n + p_n - 1. You can easily figure out that if the tutorial's solution satisfies the restriction then so does mine)

Proof by Terry Tao

After we have A and B, we continue applying this algorithm with four steps, five steps, ..., and finally n steps.

Using the characteristic of two consecutive Fibonacci numbers to propose a solution of two consecutive Fibonacci polynomials is, though correct, a little vague (!)

In div2B why dfs gives the minimum answer.when to apply dfs or bfs i am weak at it plzz help

Simple solution for 2B:

int ans=1;
for(int i=0;i<n-1;i++)
  if(color[parent[i+2]]!=color[i+2])
    ans++;

AC solution

Div1B can be solved with backtracking — http://codeforces.com/contest/901/submission/33452328

Can someone elaborate on the idea behind div2/E? I still don't understand after reading the editorial.

In Editorial of Div 1.C, this sentence

To answer the query, we need to take the sum over mxi - i + 1 for those who have mxi ≥ r and the sum over r - i + 1 for those who have mxi ≥ r

I think it should be

To answer the query, we need to take the sum over mxi - i + 1 for those who have mxi < r and the sum over r - i + 1 for those who have mxi ≥ r

In DIV 1D's description，what does it mean "It is guaranteed that the given graph is connected and does not contain loops and multiple edges." especially 'loop' here, isn't it crashed with the sample?

Div 1 B. Can anyone prove that mod 2 of the coefficients of series p(n+1) = x*p(n) + p(n-1) will give the correct answer? The given explanation isn't very clear. :/

problem A(div 2) says It is guaranteed that ai ≥ ai - 1 for every i (2 ≤ i ≤ n). but my submission failed at test 17 which was: 1 10 0 10 so is 0 greater than 1 ? link :http://codeforces.com/submissions/tibialAcorn98

I can not understand the isomorphic statement . i got WA on test 2 .

How these two trees are isomorphic ?

Can someone please some implementation details about Div 2E? It would be really helpful.

My thinking of why the mod approach works for div2 D:

consider always making A = B*x + C where degree of C is less than degree of B, the problem we will face is that sometimes the result will have coefficients greater than 1, but the leading term coefficient will never be greater than 1, because degree of B*x is higher than degree of C, so the leading term will always be existing once in the expression B*x+C (and so will not be affected by the mod).

now think of A%2, this is = (B*x + C)%2, and similarly B%2 = (C*x + D)%2, and C%2 = (D*x + E)%2, and so on till the rightmost term (E in the last expression) is 0. before we reach this point, all expressions A, B, C, ...etc will always have the leading element coefficient = 1 after and before the mod. so with the mod, we took the same number of steps we would take without the mod.

Div 1.E

Do we need a root of unity of order 2n because when we evaluate polynomial at points {zⁱ} with Bluestein's algorithm we work with elements which are in cyclic subgroup of order 2n? (z has order n)

Just making sure I got everything right.

Div-2, Problem(C) : Anyone please clarify me this line ai equals to the number of vertices that are at distance of i edges from root.

Thanks in Advance.

I have a different, possibly unintended, $$$\mathcal{O} \left( N \log N \right)$$$ solution using LCT >.<

Denote $$$f(l, r)$$$ to be the graph produced such that there is an edge between $$$u$$$ and $$$v$$$ iff there is an edge between $$$u$$$ and $$$v$$$ in the input graph and $$$l \le u,v \le r$$$.

Observation 1: A graph is bipartite iff it has no odd cycles. Since the graph is guaranteed to have no even cycles, this means that if $$$f(l, r)$$$ is good iff it's acyclic.

Observation 2: There's a sort of monotonicity going on here: if $$$f(l, r)$$$ is valid, then $$$f(l, r - 1)$$$ is also valid.

Observation 3: We can use a two-pointers approach, in lieu of observation $$$2$$$, to find the maximum $$$r$$$ for which $$$f(l, r)$$$ is valid. If we can increment $$$r$$$ while still maintaining acyclic, then do so. If we can't, increment $$$l$$$.

The key issue is how we can increment/decrement $$$l$$$ or $$$r$$$ and still check for cycles. LINK CUT TREE. To see if adding $$$(u, v)$$$ will form a cycle, check if $$$u,v$$$ are in the same connected component (can be done using link cut). To remove vertices adjacent to $$$l$$$, well, "cut" those edges. To add vertices adjacent to $$$r$$$, well, "link" those vertices.

Observation 4: Querying is simple. It' just $$$\sum_{i = l}^{r} min(arr[i], r) - i + 1 = -\frac{(l + r) \cdot (r - l + 1)}{2} + r - l + 1 + \sum_{i = l}^{r} min(arr[i], r)$$$. To compute $$$\sum_{i = l}^{r} min(arr[i], r)$$$, use the fact that $$$arr$$$ is increasing. Binary search for first time something is less than $$$r$$$: on this interval, it's just a range sum. Afterwards, when everything is greater than $$$r$$$, keep adding $$$r$$$.