It's the submission for C

you're using python and your algorithm is n^2

most likely when n is 1e5 to 1e7 the solution will require a complexity of n or nlogn but if you have n^2 you will get TLE and i will advice that you try to use java/c++ due to their time efficiency and great stl algorithms and data structures which will make solving problems more fun

Hey it's because of python only. Thanks to Pajenegod and c1729 copy the template i am using for future purposes it has fast io. submit the code in pypy2 and also be careful while printing it works like python2 in pypy2.:)

How about input optimizing? input — slow method, use alias:

import sys
input = sys.stdin.readline

But the main problem is partial reading. It could be too much faster if you'd read all lines, for example:

n = int(input())
lines = sys.stdin.readlines()

Good luck!

I think it's because your complexity is $$$O(n^2)$$$. Take a look at these lines:

temp = ""
for j in range(n-1):
    ...
        temp += str(w) + "\n"

String addition costs $$$O(n)$$$ in Python, and you do it $$$n-1$$$ times. Sometimes it's optimised away, but not always, so you shouldn't count on that. Here's what you could do instead:

temp = []
for j in range(n-1):
    ...
        temp.append(str(w))
print("\n".join(temp))

my java solution also initially timedout. I used fast output, it passed. May be fast input output is the key!

It looks like one reason PyPy might be slower than Python for your code is that PyPy is slower when you use very large dictionaries. That was a comment I read here: https://stackoverflow.com/questions/7063508/pypy-significantly-slower-than-cpython

It basically splits the result into directly added bits ($$$a \oplus b$$$) and carried bits (a & b), which should be moved one to the left since they are carried over (same as multiplying by 2).

I know that's not a real proof, but hopefully you can see why this works. In terms of googling, half-adders might be useful: https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder

One can visualise the equation using Venn diagrams

"u and v have different parities": either (i) u is odd and v is even or (ii) v is odd and u is even

"there's no array": no such solution exists

For example, if xor-sum has least significant bit = 1 and sum has 0, there is no answer. Similarly with xor ending in 0 and sum ending in 1.

it means that no array if one is even and other is odd

except u == 0 and v == 0 it is not possible that same parity u, v can have a valid array same parity means (u % 2 == v % 2) different parity means (u % 2 != v % 2)

It also means that difference of u and v is odd.

Let g be gcd of a and b.

g+ab/g = x

--> g^2 + ab = gx

--> g^2 + g^2*k1*k2 = gx (where a = g*k1 and b = k2*g)

--> k1*k2 = x/g-1.

Hence you need to find two number k1, k2 which are factors of x/g-1. To get valid g, find g such that g|x. Then, a=g*k1 and b = g*k2.

Check out the video solution to the bonus task

To check if a solution is wrong, just check if on a path between 2 edges containing val. 0 & val. 1 contains edge with val 2 or not.

how would you calculate the number of times edge occur in paths ?

let's say that a node has degree 3 so we can put values 0,1,2 in the three edges .. If you observe carefully after this step there wouldn't be any path that contains 0,1,2 together hence MEX(u,v) will be at most 2. The same is true for a degree greater than 3 too. Hope this helps.

if number of node in tree is more than 2 then ans is always greater than or equal to 2(because edge with number 0,1 will always have MEX 2). now if we have node with three edges then we can write 0,1,2 on these edges and now any path cannot contain all of these three edges. so MEX cannot be greater than 2.

Not necessary, you can do it with simpler way.

First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

In line 32 you should use long long instead of int

Omg, so stupid of me!! It seems that this construction was so deep in my habits, I wrote it unconsciously — but now, surely, I won't make the same mistake. Thanks so much!

Hello, inspired by F, I wonder if it is correct if I enumerate the root and use dfs tree in E. But I got an WA on test 151.. Here's my code .Actually, I think this method may be incorrect because dfs tree is used to get the longest cycle.

Can you give some proof that if a node has sq-1 backedge,then there surely exists a cycle of length atleast sq.

can you explain the editorial. Why are we diving with perfect square?

true I figured everything but got stuck on getting the Length of the smallest cycle the final trick is amazing!

Really!

First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

Because ,u (v-u)/2, (v-u)/2 always work.

You can refer to the contest GOODBYE2019. The problem C's solution used the same method (0 xor x == x, x xor x == 0) as well.

The code is giving wrong ans for s=6 and x=1.

if (S-X) is odd return false

Can you please elaborate?

The path from one leaf node to the other leaf node will definitely have a MEX equal to n-1.

Other random solution:

Shuffle everything and do a dfs at the same time as greedily taking vertices to the independent set. Stop if you find a good set or a good cycle.

Do that until it gets AC :D

I also have the same idea. But I didn't implement it in the contest. Because I didn't have proof about it in the probability. Can anyone prove this?

Can you please explain the approach you have used to solve it?

we know that gcd of 1 with any positive number is always 1 and in the given question x>=2... so if u will take a=1 and b=x-1... we know b>=1 since x>=2 so now gcd of 1 and x-1 is 1 and lcm of 1 with any other number is equal to other number (e.g.-lcm of 1 and 4 is 4)... so now lcm of 1 and x-1 is x-1 so the gcd + lcm of 1 and x-1 is (1) +(x-1) =x .Let me know if it's still not clear to you.

its hard to come up with proof for constructive problems. u need a good intution and guess. gutt feeling should be strong. otherwise u will keep on thinking on it forever. practice more and more to get familiar.

there was an announcement that explained the example stated in problem C. I solved problem D by proving it for sure! Otherwise, I wouldn't be able to solve it. It doesn't mean that if you couldn't solve a certain problem, then the contest is bad. Instead, the problems that you couldn't solve teaches you new algorithms,techniques and ideas!

I guess we have to!!!

Bitwise xor is like addition if we threw away all the carry bits, but obviously carries don't affect the least significant bit (parity). If we add an odd number of odd numbers, the sum and xor will both be odd. If we add an even number of odd numbers, the sum and xor will both be even.

Visual proof using Venn diagrams:



Note that A + B is not actually union, its actual addition.
Hence, both the complete circles will be added.

gfg

Can you tell why the time complexity is not O(sqrt(MAXA)*MAXA).

Well, not exactly, but yes I gave a generous bound. You can prove the answer is at most 2*169. The worst case is a chain 1-big prime-2-big prime-3-big prime-5-big prime....-997-big prime-1. The proof is exactly what sinus_070 said in his comment above + the fact that all the nodes are primes.

What MEX means is minimum excluded number for any pair of u and v between all the edges coming in between for coming from u to v some numbers are appearing and you have to make sure the MEX is not too large for it. For eg by arrow I mean a connection is present 2->3->4->5 here 2,3,4,5 are vertices and you can consider 2,5 as pair in short all the edges in this must have edges such that the MEX the number which has not appeared should me minimimum

look at the this comment and this blog and this question

try to solve problems on the first page of problemset order by solved numbers from first question, after solving about 100-200 questions then you can solve A questions.

Interesting way to think!

Check out the video solution to the bonus task

If you do not carry an odd integer, It is impossible to generate different bit after applying XOR and SUM on any array of ones and zeros.

The naive approach is to fix the root of the bfs tree and then run a bfs to compute the shortest cycle which passes through the fixed root. Now since our graph is special and it is not possible to have an edge between 2 vertices u and v if both of them are bigger than $$$\sqrt{maxA}$$$, you can check only with roots smaller than $$$\sqrt{maxA}$$$.