Help in C

If we've found such ri then all prefix goes to one group and suffix — to another. ??

I am totally not understand the solution of problem G, can anyone help me ? :(((

Fix typo: 1101F: "с некотором смысле" -> "в некотором смысле"

Your proof of the solution of problem G suggests that one can do something a little bit simpler.

Just write all the numbers in base 2 and put them as rows of a matrix (the order doesn't matter). Then the answer is just the rank of that matrix. Of course, the corner case has to be taken into account, i.e. if the xor of all numbers equals zero, then the answer is -1.

I don't care if this is downvoted but Problem D editorial is not properly written.
Problems with the editorial in D.
1. " Let's for each v calculate the path of the maximum length to pass through it "
It does not say why are we calculating it and where are we using this.
2. The last paragraph seems to be the heart of algorithm and it is written in just two lines without much explanation.
3. The code uses dp to store something but the editorial doesn't mention anything about it and so for someone who is reading through the code how the hell are we supposed to know what is dp[i].
4. The code is not properly commented.

I don't know if the author write editorial for those who already know how to solve the problem. CF editorials are fast, which is great but they need a more of detailing.
Apart from this the contest and problems were great!
Lastly can anybody explain the solution for problem D?:p

Bonus for G: Prove that answer doesn't change if we permute elements of array a.

Since awoo says so, I'll explain the model solution for D.

What does it mean that the greatest common divisor of some set of numbers is not 1? It means that there exists some prime number p that divides the greatest common divisor. Therefore, it divides all the numbers in a set. Okay, now we can fix some prime number p, find the best path that passes only through vertices with a_i divisible by p, then fix another prime, and check all the primes from 2 to 199999 this way.

What happens when we fix a prime number? Basically, the vertices of the graph are now divided into two groups: those that are forbidden to pass through (having a_i not divisible by p) and those that are allowed. Let's delete all forbidden vertices from the tree (and all the edges that are incident to at least one forbidden vertex).

What will the resulting graph look like? It might become disconnected (for example, in the first sample case, if we fix p = 2, vertices 1 and 3 are disconnected), but it's still acyclic because removing edges or vertices from a graph won't create a new cycle. So, each connected component of the graph is a tree. Now we have to find the best path in each connected component.

Okay, how to determine the "best" path? If the number of vertices on a path is x, and the path is simple, then the number of edges belonging to this path is x - 1. And since each component is a tree, then we are interested in finding the diameter of the tree, which can be done in O(|V|): pick some vertex from the tree (let's denote it as v₀), run DFS or BFS from it, find the vertex having the greatest distance from v₀ (let it be v₁; if there are muliple such vertices, pick any of them), run DFS or BFS from it, and find some vertex having greatest vertex from v₁ (let it be v₂). The path between v₁ and v₂ is the diameter.

Why does it work fast enough? Each number exceeding A can have no more then prime divisors, so the sum of sizes of the graphs we are finding the diameters in is bounded as .

Okay, how to implement it? When we pick some prime p, instead of deleting forbidden vertices and edges (which leads us to complexity of O(nA) or even greater), let's create a new graph: renumerate all allowed vertices so that their numbers become 1, 2, ..., k, and apply the aforementioned solution to this graph. That is the easiest way to make it without using some auxiliary sets or other data structures.

upd: Well, in fact, model solution is because I was too lazy to write fast factorization algorithms. But it's worth mentioning that if you want to achieve complexity of , there's no need to write Eratosthenes sieve: finding all divisors of all numbers from 1 to A in can be done using two nested for loops, the outer one iterating on the divisor, and the inner one iterating on the numbers divisible by that divisor.

In C part for the test case 1 4 1 2 2 4 4 8 5 10. the output should be 1 1 1 2 but according to the editorial it's giving -1

I get nothing from task G tutorial, could anyone explain the solution?

Can anyone please explain why opt[l][r][k] <= opt[l][r+1][k] in problem F..?? I am not able to visualize this.

I have a slightly different solution for F. We still calculate dp[l][r][k], and the recurrence is still . However, we notice that dp[l][j][k - 1] increases as you increase j, and a[r] - a[j] decreases as you increase j. Thus, the min value of will occur when they are as close to each other as possible, i.e. when |dp[l][j][k - 1] - (a[r] - a[j])| is minimized, and this quantity is unimodal so we can binary search for it. For memory optimization, we simply notice that we don't need to store all the queries, and can process them online, giving us O(n³) space rather than O(n³ + q), which barely fits into the memory. The DP calculation takes time, which also barely fits into the time limit.

48306162

Can anyone help me in finding mistake in D? I am not able to find why it is giving WA. Submission

Choose your i/o functions wisely.

Actually I think a problem shouldn't be annoyed with slow i/o.But you guys should know scanf/printf is faster than cin/cout.When the input is larger than 5MB you should use scanf/printf without hestitation.

(Also the only way to make this simple problem E harder is to hack some slow i/o's...Maybe?)

For problem D, I have used the concept that-For any vertex 'v' it can either be a part of the longest path or not. Then i calculated the longest path in its sub-tree and updated the max value, and then passed the value of the longest path obtained from its children to its parent. But this approach is giving wrong answer on test 5. Here is my code, why isn't this approach working. https://mirror.codeforces.com/contest/1101/submission/48279577

I have another idea about D but I got WA. Could anybody help me?

I tried to deal with it by DP in trees. Denote dp[i] as a set where stored some pairs (g, d). A pair (g, d) in dp[i] means a path form v to vertex i that the gcd of vertices in the path is g and its length is d, where v is one of the grandsons of vertex i. It's evidently I needn't store the pairs (g, d) where g = 1 and also I can ignore the vertex i where a[i] = 1. And if there are two pairs which have the same g, I can ignore the one with the lower d.

Of course a pair (a[i], 1) is in dp[i] if a[i] > 1. Consider all children of vertex i, assuming that now I'm consider v. Get all pairs in dp[v], assuming that now I get (g₀, d₀). Insert pair (gcd(g₀, a[i]), d₀ + 1) to dp[i] and maintain the optimal pairs if gcd(g₀, a[i]) > 1, which means vertex i links into the path. However, the answer can be the path from one of the grandsons of vertex i to another. So before the insertion, I consider all pairs in dp[i] to get the potential answer. dp[i] now stores some pairs stand for the path from vertex i to one of the grandsons of vertex u, where vertex u is one of the children which is already considered of vertex i. Assuming that I'm considering pair (g₁, d₁) in dp[i], ans = max(ans, d₀ + d₁) if gcd(g₀, g₁) > 1.

I don't know what's wrong with my approach or my code because of my poor ability. Here's my Submission 48313349. I'd appreciate it if someone help me.

Sorry for my poor English.

I just found out my solution for problem D was incorrect . But yet I got AC even after the system test . It happened because of weak test cases .

Test Case # X :
4
3 6 2 2
1 2
2 3
3 4

My Submission :
48253431

The correct answer should be 3 , but my solution is giving 2 .
Can you guys rejudge problem D

Aha! I love problem F.

I solved this problem by randomization and binary search. The code is easy to read. 48318449

Let us analyze this problem, we know every truck must have the max gas-tanks. For a truck, the more oil, the better.

We randomly choose a truck to calculate ( use binary search ), It can be considered that in general, half of the trucks do not exceed the maximum fuel consumption. In other words, we only use logm operations( binary search) at most.

Hey awoo , I am not able to understand that why solution for E getting TLE thought its complexity is O(N), but it is accepted when i used ios::sync_with_stdio(false); cin.tie(0); N <= 500000 Solution ID : https://mirror.codeforces.com/contest/1101/submission/48324180 Solution ID (without ios::...) : https://mirror.codeforces.com/contest/1101/submission/48324102

And the time limit for Question is 3sec.

Can you help with this, Thanks in advance:)

for problem D fix a prime p and find longest path with vertices divisible by p! Consider the vertices divisible by p, there are some disjoint maximal subtree with all vertices divisible by p obviously the longest path is diameter of one of these subtrees. so we will find for each vertex v and prime p as prime factor of v , the diameter of the subtree contains v , it can be done with dp on tree! we have nlogMAXN pair(v,p) and each dfs goes to some of them so in total we visit nlogMAXN state, also to avoid going to each subtree many time we should mark state (v,p) if we use a set the time will be nlog^2(MAXN) or if we use an array of sets reduce it to n*logMAXN*loglogMAXN or if we use hashing it is nlogMAXN! :)

My submission

Help T^T I still don't understand the first example provided in D. Shouldn't the output be 3 instead of 1, since the first and the third vertex has gcd greater than one with distance three? Can someone please kindly explain to me...

Can anyone Explain the approach of problem G?

Cannot understand G :(

void try_gauss(int v){
	for(int i = LOGN - 1; i >= 0; i--)
		if (base[i] != -1 && (v & (1 << i)))
			v ^= base[i];
	if (v == 0)
		return;
	for(int i = LOGN - 1; i >= 0; i--) if (v & (1 << i)){
		base[i] = v;
		return;
	}
}

Could someone please explain (or point to a tutorial/explanation) why this method indeed gives us the basis vectors ? Intuitively it looks like it's doing Gauss elimination but I am having a difficult time understanding how.

can anyone debug the code of d given bellow?why does it give one less than actual ans?or,give me any hint

What does even and odd number of pr[x] means in G? Can someone explain 2nd para in more approachable way?

(Question C)Can anyone tell me why I am getting WA. http://mirror.codeforces.com/contest/1101/submission/48462932

What about this input in problem C ?

1
3
4 12
5 11
6 10

Should'nt this have any answer ?

For G, I forgot to find basis of prefix instead calculated basis of all the a_i's and it still passes. code how to explain this?

My kotlin solution for E keeps timing out. The tutorial says to choose your IO functions carefully. Is there a better option than readLine()?

Problem D can also be done with the help of Centroid Decomposition.

Very similar to the problem PRIMEDST

Just a small change is required. Figure it out yourself. It's fun. :)

Consider this solution for reference : LINK

What are the prerequisites of problem G? This paragraph:

"This way we can collect all subsets of pr[x] for some division. Now you just want find the division that produces the maximum number of linearly independent numbers (binary vectors). That is — the size of the basis of the space of chosen numbers (binary vectors)."

has a great jump over details which need more explanation.

Can anyone please confirm the complexity of PikMike's solution for question D:Gcd Counting. As I think its factorization would take n*sqrt(A) time.

In case somebody didn't understand tutorial of problem G, here you can find a blog explaining the whole idea of gaussian elimination behind.

Isn't G an easy version of ABC 223 — H — XOR QUERY?

i am solved the problem D. using rerooted technique.

here is my solution to D in O(NlogMAXN) if someone is interested https://mirror.codeforces.com/contest/1101/submission/174363913

I get that for problem G, the maximum possible number of segments in a division is the size of the basis. However, how to prove that such division exists? Would it be possible to reconstruct an actual valid solution?