Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### mohammedehab2002's blog

By mohammedehab2002, history, 4 months ago, ,

### 1325A - EhAb AnD gCd

$a=1$ and $b=x-1$ always work.

First AC: Sevlll

Bonus task: can you count the valid pairs?

### 1325B - CopyCopyCopyCopyCopy

Let the number of distinct elements in $a$ be called $d$. Clearly, the answer is limited by $d$. Now, you can construct your subsequence as follows: take the smallest element from the first copy, the second smallest element from the second copy, and so on. Since there are enough copies to take every element, the answer is $d$.

First AC: socho

### 1325C - Ehab and Path-etic MEXs

Notice that there will be a path that passes through the edge labeled $0$ and the edge labeled $1$ no matter how you label the edges, so there's always a path with $MEX$ $2$ or more. If any node has degree 3 or more, you can distribute the labels $0$, $1$, and $2$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with $MEX$ $n-1$ anyway.

### 1325D - Ehab the Xorcist

First, let's look at some special cases. If $u>v$ or $u$ and $v$ have different parities, there's no array. If $u=v=0$, the answer is an empty array. If $u=v \neq 0$, the answer is $[u]$. Now, the length is at least 2. Let $x=\frac{v-u}{2}$. The array $[u,x,x]$ satisfies the conditions, so the length is at most 3. We just need to figure out whether there's a pair of number $a$ and $b$. Such that $a \oplus b=u$ and $a+b=v$. Notice that $a+b=a \oplus b+2*(a$&$b)$, so we know that $a$&$b=\frac{v-u}{2}=x$ (surprise surprise.) The benefit of getting rid of $a+b$ and looking at $a$&$b$ instead is that we can look at $a$ and $b$ bit by bit. If $x$ has a one in some bit, $a$ and $b$ must both have ones, so $a \oplus b=u$ must have a 0. If $x$ has a zero, there are absolutely no limitation on $u$. So, if there's a bit where both $x$ and $u$ have a one, that is to say if $x$&$u\neq0$, you can't find such $a$ and $b$, and the length will be 3. Otherwise, $x$&$u=0$ which means $x \oplus u=x+u$, so the array $[u+x,x]$ works. Can you see how this array was constructed? We took $[u,x,x]$ which more obviously works and merged the first 2 elements, benefiting from the fact that $u$&$x=0$.

First AC: MiFaFaOvO

### 1325E - Ehab's REAL Number Theory Problem

Notice that for each element in the array, if some perfect square divides it, you can divide it by that perfect square, and the problem won't change. Let's define normalizing a number as dividing it by perfect squares until it doesn't contain any. Notice than any number that has 3 different prime divisors has at least 8 divisors, so after normalizing any element in the array, it will be $1$, $p$, or $p*q$ for some primes $p$ and $q$. Let's create a graph where the vertices are the prime numbers (and $1$,) and the edges are the elements of the array. For each element, we'll connect $p$ and $q$ (or $p$ and $1$ if it's a prime after normalizing, or $1$ with $1$ if it's $1$ after normalizing.) What's the significance of this graph? Well, if you take any walk from node $p$ to node $q$, multiply the elements on the edges you took, and normalize, the product you get will be $p*q$! That's because every node in the path will be visited an even number of times, except $p$ and $q$. So the shortest subsequence whose product is a perfect square is just the shortest cycle in this graph!

The shortest cycle in an arbitrary graph takes $O(n^2)$ to compute: you take every node as a source and calculate the bfs tree, then you look at the edges the go back to the root to close the cycle. That only finds the shortest cycle if the bfs source is contained in one. The graph in this problem has a special condition: you can't connect 2 nodes with indices greater than $sqrt(maxAi)$. That's because their product would be greater than $maxAi$. So that means ANY walk in this graph has a node with index $\le\sqrt{maxAi}$. You can only try these nodes as sources for your bfs.

Bonus task: try to prove the answer can't exceed $2\sqrt{maxAi}$.

### 1325F - Ehab's Last Theorem

Let $sq$ denote $\lceil\sqrt{n}\rceil$.

#### A solution using DFS trees

If you're not familiar with back-edges, I recommend reading this first.

Let's take the DFS tree of our graph. Assume you're currently in node $u$ in the DFS. If $u$ has $sq-1$ or more back-edges, look at the one that connects $u$ to its furthest ancestor. It forms a cycle of length at least $sq$. If $u$ doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most $sq-1$ other nodes, the ones connected to it by a back-edge, so you'll find an independent set!

First AC: imeimi

#### A solution using degrees

There's a pretty obvious greedy algorithm for finding large independent sets: take the node with the minimal degree, add it to the independent set, remove it and all its neighbors from the graph, and repeat. If at every step the node with the minimal degree has degree $<sq-1$, that algorithm solves the first problem. Otherwise, there's a step where EVERY node has degree at least $sq-1$. For graphs where every node has degree at least $d$, you can always find a cycle with length $d+1$. To do that, we'll first try to find a long path then close a cycle. Take an arbitrary node as a starting point, and keep trying to extend your path. If one of this node's neighbors is not already in the path, extend that path with it and repeat. Otherwise, all of the last node's $d$ neighbors are on the path. Take the edge to the furthest and you'll form a cycle of length at least $d+1$!

First AC: imeimi after only 11 minutes!

There are probably other solutions and heuristics. Can you share yours?

• +288

 » 4 months ago, # | ← Rev. 2 →   +71 woa, so fast, I feeling so good to know how to solve those. Thanks alot for your effort
 » 4 months ago, # |   0 Could anyone please tell me why this was giving TLE? https://codeforces.com/contest/1325/submission/73271304Thanks!
•  » » 4 months ago, # ^ |   0 It's the submission for C
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 you're using python and your algorithm is n^2
•  » » » 4 months ago, # ^ |   0 Actually, the set size will never grow more than 3 elements (the inner loop). It looks N^2 but it's not
•  » » » » 4 months ago, # ^ |   0 for i in range(n-1): u, v = map(int, input().split()) if u not in graph: graph[u] = {i} i believe this is n^2 but I don't know python either
•  » » » » » 4 months ago, # ^ |   0 Oh, graph is a dictionary here (HashMap), constant lookup.
•  » » » » » » 4 months ago, # ^ |   0 python dict worst case is O(n),so the whole complexity of code becomes n^2. https://wiki.python.org/moin/TimeComplexity
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +1 temp = "" for j in range(n-1): if j in graph[maxi]: temp += str(w) + "\n" w += 1 else: temp += str(t) + "\n" t -= 1 this part is the reason for TLE. As in python strings are immutable so it creates new. It takes O(n) time and make it O(n**2). Instead, use a list to print results.
•  » » 4 months ago, # ^ |   0 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
•  » » » 4 months ago, # ^ |   0 Sir, it's not N^2. Could you please see my above reply to bleh0.5
•  » » » » 4 months ago, # ^ |   0 if it runs in n ir nlogn then it should pass i am not good at python but it may be helful to check the complexity of python core function it may cause overhead and wish you more luck in figuring the problem out
•  » » 4 months ago, # ^ | ← Rev. 2 →   +7 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.:)
•  » » » 4 months ago, # ^ |   0 oh is it so? It's so frustating and unfortunate that python is slow. Thanks a lot!
•  » » 4 months ago, # ^ |   +1 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!
•  » » » 4 months ago, # ^ |   0 Really Cool. Thanks for looking at the code!
•  » » 4 months ago, # ^ | ← Rev. 3 →   +10 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)) 
•  » » » 4 months ago, # ^ |   0 I'll keep that in mind from now. Thanks a ton!
•  » » 4 months ago, # ^ |   +1 my java solution also initially timedout. I used fast output, it passed. May be fast input output is the key!
•  » » 4 months ago, # ^ |   0 Your code works in Python but times out in PyPy. Don't know why. Usually PyPy is faster than Python.
•  » » 4 months ago, # ^ |   +1 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
 » 4 months ago, # |   +8 In problem D, there is a formula a+b=a⊕b+2∗(a &b), how to prove its correctness? I couldn't find a proper google keyword for it.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +12 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
•  » » » 3 months ago, # ^ |   0 nice explanation sir.
•  » » 4 months ago, # ^ |   +35 One can visualise the equation using Venn diagrams
•  » » » 4 months ago, # ^ |   +1 I still can't get it. Can you please show us the diagram? Thanks
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 I already understand it, but I didn't use the Venn's diagram approach. Here is how I visualize it:Imagine all bit position where bit in a is different with bit in b (this is a^b). If we sum a and b, all these positions contribute (a^b) to the sum.Now imagine all bit positions where bit in a is the same with bit in b (this is a&b). If we sum a and b, all these positions contribute 2*(a&b) to the sum.
•  » » » » » 4 months ago, # ^ |   0 I understood the equation but I couldn't understand the proof and sorry your statement doesn't contain a proof.
•  » » » » 4 months ago, # ^ |   0 See retrograd's video at that timestamp: https://youtu.be/fpxArbp3FLo?t=8456
•  » » » » » 4 months ago, # ^ |   +6 Thanks, Bhai. Understood it on the second go. Hail retrograd!!
 » 4 months ago, # |   +1 In editorial for problem D, what does this mean "if u and v have different parities, there's no array"
•  » » 4 months ago, # ^ |   +8 "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
•  » » 4 months ago, # ^ |   +3 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.
•  » » » 4 months ago, # ^ |   0 Can you explain why solution will not exist for different parity u and v?
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 Don't think too hard. Just focus on the very last bit (right most). Parity means whether the last bits are same or not. A=....0, B=....0, Then A^B = .....0, A+B = .....0. A=....0, B=....1, Then A^B = .....1, A+B = .....1. A=....1, B=....0, Then A^B = .....1, A+B = .....1. A=....1, B=....1, Then A^B = .....0, A+B = .....0. XOR and ADDITION acts same on last bit. Hence the XOR and ADDITION should end with same bits i.e should have same parity.
•  » » » » » 4 months ago, # ^ |   0 Got it! Thanks.
•  » » » » » 8 days ago, # ^ |   0 But that's only the case where in you are assuming that array size is 2
•  » » » » 4 months ago, # ^ |   0 from the equation, a+b=a^b+2(a&b) you can see that a+b-a^b=v-u=2(a&b), which shows v-u is divisible by 2, because of 2 as a multiplier. that could only be possible if v and u both have same parity, otherwise their difference would not be multiple of two and above equation will not hold.
•  » » » » » 4 months ago, # ^ |   0 Yeah. Thanks.
•  » » » » 8 days ago, # ^ |   0 An easy way would be to think like this. If the last bit of u is set(=1) this means that number of times the last bit occurs should also be odd(in all array number) and if last bit is occurring odd number of times then v should also be odd(check by binary addition). Hence the contradiction.
•  » » 4 months ago, # ^ |   0 it means that no array if one is even and other is odd
•  » » 4 months ago, # ^ |   0 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)
•  » » 4 months ago, # ^ |   0 It also means that difference of u and v is odd.
 » 4 months ago, # |   +1 Such a fast editorial !!!
 » 4 months ago, # |   +6 Thanks for the quick editorial !
 » 4 months ago, # | ← Rev. 2 →   0 Bonus task 1325A : A. 1 for odd numbers(?) B. 2 or more for even numbers : {n/2,n/2}, {1,n-1}, ...Can you help me out how to find these 'more' numbers?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 4 months ago, # ^ |   0 That was helpful. Thanks.
•  » » » 4 months ago, # ^ |   0 what do u mean by g|x?
•  » » » » 4 months ago, # ^ |   0 It means g divides x.
•  » » » » » 4 months ago, # ^ |   0 ok
•  » » 6 weeks ago, # ^ |   0
 » 4 months ago, # |   0 How did u judge the solutions of problem C?? I mean there are a variety of solutions..
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 I labeled three edges with 1-degree vertices as 0,1,2. So it should be the correct solution, right? But it didn't pass pretest 3.
•  » » » » 4 months ago, # ^ |   0 Did you check the case that there exist only 2 1-degree vertices? like a simple path graph. if you did, then your solution is exactly what i've done, you have to made a mistake in checking degrees or input/output.
•  » » » » 4 months ago, # ^ |   0 I did the same thing, but failed test 7. Can someone take a look? https://codeforces.com/contest/1325/submission/73250194
 » 4 months ago, # | ← Rev. 2 →   +4 Isn't problem C can be solved by sorting edges according to number of times it occurs in any of the path in ascending order then label each edge from 0 to n-2 in this order?
 » 4 months ago, # |   0 Why in problem C we need to check node with exactly three or more edges?
•  » » 4 months ago, # ^ |   +7 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.
•  » » » 4 months ago, # ^ |   0 Thanks! Helped!
•  » » » 4 months ago, # ^ |   0 I don't think so . There is one case where degree three and arbitrary combination of 0,1,2 will fail . Check this out https://imgur.com/4P89JgaIn the first diagram max MEX value comes out to be 6 In the second diagram max MEX value is restricted to 3 only
•  » » » » 4 months ago, # ^ |   0 how come the max MEX is 6 in the first case .. I guess its 1 ?
•  » » » » » 4 months ago, # ^ |   0 MEX of vertex (2,7) in first diagram . Degree of vertex 3 is 3 so we have assigned 0,1,2 to the three edges now labels from (2,7) are 1,2,3,4,5 so MEX(2,7) comes out to be 6.The maximum value of MEX comes out to be 6
•  » » » » » » 4 months ago, # ^ |   0 MEX(2,7) contains weights 1,2,3,4,5 not 0 . Hence MEX(2,7) = 0
•  » » » » » » » 4 months ago, # ^ |   0 Wait ....so 0 is allowed ? UGHHHHHH Same mistake every time . Half of my headache comes from either not reading the problem correctly or assuming something that isn't there in the first place . Thanks for pointing it out tho
•  » » » 6 weeks ago, # ^ |   0 i cant understand the problem C, can you please explain
•  » » 4 months ago, # ^ |   0 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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 4 months ago, # ^ |   0 Your last conclusion isn't true --->> Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,nThis is true only if any of the node has a degree at least three otherwise no matter how you put up the weights , you'll end up getting maximum MEX(u,v) equal to n-1 . And here's a counter example. 4 1 2 1 3 3 4 So the answer will be just n-1 and here you get 0,2,1 at the same time.
•  » » » » 4 months ago, # ^ |   0 Yes you are definitely right, thanks for correction. I missed this point. But the algorithm still applies however.
•  » » » » » 4 months ago, # ^ |   0 Welcome buddy :-)
•  » » » 4 months ago, # ^ |   0 Im.new to graph theory..and I couldn't even understand the problem Statement..it would be really helpful if someone can explain it to me :(
 » 4 months ago, # | ← Rev. 2 →   0 I was debugging D for about an hour, and then five minutes before the end wrote a solution in python — it worked)) Actually, could someone tell me why C++ solution fails (I suppose it's something to do with overflows, but can't figure out)?
•  » » 4 months ago, # ^ |   +9 In line 32 you should use long long instead of int
 » 4 months ago, # |   0 Woa..A great contest and a quick editorial... Really appreciate this... Thanks alot for your effort
 » 4 months ago, # |   +40 Another way to think about DFS solution for FSuppose each vertex has at most $sq - 1$ back edges. Then we can run through all vertices in DFS order and color the whole graf in at most $sq$ colors (for each vertex we can pick one of $sq$ colors that doesn't occur among vertices connected to it by back edges). Vertices of one color form an independent set, and there are $sq$ colors, so we can pick a color with at least $\left\lceil\frac{n}{sq}\right\rceil$ vertices colored in it.
•  » » 4 months ago, # ^ |   0 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!
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 This is test 151: https://codeforces.com/contest/1325/hacks/625397 (so it means your solution would pass during the contest xD)It looks like this with middle cycle of length $13$, and all other of length $14$ (those vertices are $1$ and primes less than $1000$, which gives exactly $169$ vertices), whilst all larger primes are connected to vertex $1$
•  » » » » 4 months ago, # ^ |   +10 Interestring, I think I now fully understand. If at least two of the edges in the middle cycle are not in the dfs tree, the middle cycle can't be found.
•  » » 3 months ago, # ^ |   0 Can you give some proof that if a node has sq-1 backedge,then there surely exists a cycle of length atleast sq.
 » 4 months ago, # |   +8 The solution to problem E is truly beautiful!
•  » » 4 months ago, # ^ |   0 can you explain the editorial. Why are we diving with perfect square?
•  » » » 4 months ago, # ^ |   +1 to eleminate the factors having even frequncy in factorization
•  » » 4 months ago, # ^ |   +14 true I figured everything but got stuck on getting the Length of the smallest cycle the final trick is amazing!
 » 4 months ago, # |   +1 How to solve C ? Please explain simply .
•  » » 4 months ago, # ^ |   +7 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
•  » » » 4 months ago, # ^ |   0 thank u so much .. :D
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +1 It's satisfying to know, what i thought during contest was correct. But it is more disappointing to know my code during the contest failed only one test case . Case no 19:: 2 1 2
•  » » » » 4 months ago, # ^ |   +4 Same, my dumb ass realized this after wasting 40 mins because I thought test 19 wouldn't be something so simple :(
•  » » » » 4 months ago, # ^ |   +2 Oh haha I failed at test 19 too. But fortunately I figured it out quickly. Usually, when your code fails at tests like 19 (later tests) it means that probably your general solution is correct but you didn't consider corner cases. Otherwise, if such corner cases are tested too early, you might falsely think that your solution is totally incorrect which would be worse.
•  » » » 3 months ago, # ^ |   0 Great explanation:):)!!
•  » » 4 months ago, # ^ |   0 Sort nodes according to their degree and then assign numbers from 0 to n-2 to the children.
 » 4 months ago, # |   0 In D how can we say that the max length of such an array can be at most 3?
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 Because ,u (v-u)/2, (v-u)/2 always work.
•  » » » 4 months ago, # ^ |   +1 Is there any formal proof of it?
•  » » » » 4 months ago, # ^ |   +20 If you know that $a \oplus a = 0$ and that $a \oplus 0 = a$ then it's obvious why that works:$u \oplus \frac{v-u}{2} \oplus \frac{v-u}{2} = u \oplus (\frac{v-u}{2} \oplus \frac{v-u}{2}) = u \oplus 0 = u$
•  » » » » » 4 months ago, # ^ |   0 Hey, Can you please answer my following questions? If v-u is odd, why isn't there any solution? If (u & (v-u)/2) ==0, how are we sure of two numbers to be u + (v-u)/2 and (v-u)/2? I have a hard time understanding bit operators. Thanks
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 since a^b=a+b-2(a&b) now you are given a^b as u and a+b as v therefore u=v-2(a&b) 2(a&b)=v-u as our ans is [a,b] as elements of the array in case there exists 2 elements therefore v-u has to be even for a solution to exist.
•  » » » » » » » 4 months ago, # ^ |   0 Got it. This is in case of two numbers.
•  » » » 4 months ago, # ^ |   0 Why cannot it have more than 3 elements in the array?
•  » » » » 4 months ago, # ^ |   0 We are supposed to find minimum possible length, and for any u, v such that a valid array exists we have an explicit way to construct an array of length 3, thus the optimal solution can't be more than 3
•  » » » » » 4 months ago, # ^ |   0 Pardon me. Let n be the number of elements in the required array.For: n= 2: we use a+b = a⊕b + 2∗(a&b) to find a and b. n= 3: u, (v-u)/2, (v-u)/2 is the answer if v-u is even. Suppose both the above case fails, then why are we not checking for n= 4, 5, 6... ?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 $a \oplus b \equiv a + b \mod 2$. And this can be inductively generalized to $a_1 \oplus a_2 \oplus \ldots \oplus a_n \equiv a_1 + a_2 + \ldots + a_n \mod 2$, so if $v - u$ is odd, then there is no answer.And in the same manner knowing that $a \oplus b \leq a + b$ we can conclude that if $v < u$ there is no answer as well. So if both those cases fail there is no answer.
•  » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 How come a⊕b≡a+b mod2 consider a=2 and b=5 then how the above holds?
•  » » » » » » » » 4 months ago, # ^ |   0 $1+2=3$$1 \oplus 2 = 3$$3 \equiv 3 \mod 2$
•  » » » » » » » » » 4 months ago, # ^ |   0 The RHS becomes 1 but LHS is 3?
•  » » » » » » » » » 4 months ago, # ^ |   0 You're reading it wrong. https://en.wikipedia.org/wiki/Modular_arithmetic#Definition_of_congruence_relation
•  » » » » » » » 4 months ago, # ^ |   0 Pardon me again. But I don't understand why are we not checking for n= 4, 5 ...?
•  » » » » » » » » 4 months ago, # ^ |   0 If case with $n=3$ failed then $v-u$ is either odd or negative and in both cases I proved in a comment above, that there is no way to construct a valid array
•  » » » » » » » » 4 months ago, # ^ |   0 consider the case of three numbers (v-u)/2,(v-u)/2 and u. The xor of these three numbers will always be u as (v-u)/2 xor (v-u)/2 is equal to 0. Hence for every case, we can say that the minimum length array will be 3.
•  » » 4 months ago, # ^ |   +1 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.
 » 4 months ago, # |   0 When will there be rating changes?
 » 4 months ago, # |   0 Can anyone tell that why the mentioned link solution give WA for problem D when checking whether array of length 2 is possible or not https://www.geeksforgeeks.org/find-two-numbers-sum-xor/
•  » » 4 months ago, # ^ |   0 The code is giving wrong ans for s=6 and x=1.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 if (S-X) is odd return false
 » 4 months ago, # |   +16 I think the First AC of E is in the middle of F
 » 4 months ago, # |   +27 Bonus task for E:Let T = sqrt(maxAi)A cycle of length K has atleast ceil(K / 2) vertices with value <= T.Because if it didn't, it would mean that two vertices that are > T come next to each other in the cycle, which isn't possible as their product would exceed maxAi.So if the length of the smallest cycle more than 2T, it would mean that at least T + 1 vertices in the cycle have value <= T.Which means a vertex repeats in the cycle, causing a smaller cycle to exist. Reaching to a contradiction.
•  » » 4 months ago, # ^ |   0 Can you please elaborate?
 » 4 months ago, # |   0 Alternative DP Solution to D: https://codeforces.com/contest/1325/submission/73276587
 » 4 months ago, # | ← Rev. 2 →   0 I'm interested to know why the $D$ problem preferred an empty array if $u = v = 0$ rather than an array of a single element $= 0$Here are my solutions along with explanations if anyone wants to refer
 » 4 months ago, # |   0 I don't understand this part of explanation for C: Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX n−1 anyway. If n=4, and I label  *---0---*---2---*---1---*  none of the paths will have MEX higher than 1, will they?
•  » » 4 months ago, # ^ |   0 The path from one leaf node to the other leaf node will definitely have a MEX equal to n-1.
•  » » » 4 months ago, # ^ |   0 Ah, thx!
 » 4 months ago, # |   +26 Randomized solution to FFirst try some permutations (10 seems enough to pass tests) of the vertices and then check for independent set greedily.If we haven't found any independent set let's do the following until we get an answer: shuffle all the edges and then run dfs. Inside the dfs if we look at a used vertex lets try to make it the cycle.I don't know how to prove it works fast, but it does. I guess it's just close to the editorial solution.
•  » » 4 months ago, # ^ |   +8 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
•  » » » 4 months ago, # ^ |   +10 I'm investigating further and it seems that if we couldn't find a big independent set we will have to run dfs for cycles only once! I'm just too weak to prove it...
•  » » » » 4 months ago, # ^ |   0 Of course you should run dfs only once, because if I understand correctly what you are doing is a correct algorithm for finding the longest cycle in the graph
•  » » » » » 4 months ago, # ^ |   0 Well, of course it's not true because not every dfs tree gives the longest cycle. It's not hard to come up with an example.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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?
 » 4 months ago, # | ← Rev. 3 →   +5 non-greedy solution for problem D 73264903
•  » » 4 months ago, # ^ |   +3 Can you please explain the approach you have used to solve it?
•  » » » 4 months ago, # ^ |   +4 obviously if u > v the answer is -1 you need to solve it bit by bit let's keep the count of bits that will construct the required numbers in arr initially you have a sum and you want to distribute it on some numbers to give you the required xor. if there is a 1 in the current bit in xor you need to leave a bit in this position in arr from the sum you have after distributing the bits on the xor, there will be a remainder, you don't wan't this remainder to affect the xor, so divide the remainder by 2 and put 2 bits in the positions that has 1 in the binary representation of the remainder. if the remainder not divisible by 2, the answer is -1 now you need to construct the required shortest array of numbers, so iterate over the arr and try to remove the maximum possible number of bits from it and put them in a number, do this operation untill no bits is left in the arr
•  » » » » 4 months ago, # ^ |   0 What is the need of dividing the remainder by 2 and putting the 2 bits in the positions having 1 in the binary representation of the remainder?
•  » » » » » 4 months ago, # ^ |   0 to not affect the xor, as xor of the same number = 0
•  » » » » » » 4 months ago, # ^ |   0 Can you give an example of the same?
•  » » » » » » » 4 months ago, # ^ |   0 xor(a, a) = 0
•  » » » » » » » » 4 months ago, # ^ |   +3 Thanks for such a clear explanation.
 » 4 months ago, # |   +5 Question D was great... looking forward to participate more of your rounds in future :)
 » 4 months ago, # |   0 How to solve A ? Please explain simply
•  » » 4 months ago, # ^ |   0 gcd(x-1,1) = 1 lcm(x-1,1) = x-1 answer is 1 and x-1
•  » » » 4 months ago, # ^ |   0 thanks @Karamany2
•  » » 4 months ago, # ^ |   +6 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.
•  » » » 4 months ago, # ^ |   0 it's very clear now, thanks
 » 4 months ago, # | ← Rev. 3 →   0 mohammedehab2002 If u doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most sq−1 other nodes, the ones connected to it by a back-edge, so you'll find an independent set!How you deduce this type of facts so easily. How to come up with a good proof which requires this type of things.
 » 4 months ago, # |   -23 Problem statement of especially C was not well enough and unclear.The algorithm of D has no proof.It is nothing but a result from searching find two numbers whose xor and sum is given .. Not a good contest !! Problems should be more classy.
•  » » 4 months ago, # ^ |   +12 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.
•  » » 4 months ago, # ^ |   +6 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!
 » 4 months ago, # |   -29 in problem D, we don't have to print the answer with minimum length of array.so,the answer 1 1 1 1 1 1 1 1 1 1 is true for pretest 7,but I got WA because "the jury had a shorter answer" than me.please fix this,mohammedehab2002!!
•  » » 4 months ago, # ^ |   0 I guess we have to!!!
•  » » » 4 months ago, # ^ |   +3 The statement says:Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v.
•  » » » » 4 months ago, # ^ |   +28 Oh yes.I was wrong. sorry jury!sorry codeforces!
 » 4 months ago, # |   0 can anyone explain the problem statement for the 3rd question
 » 4 months ago, # |   0 In problem D, how can we prove "u and v have different parities, there's no array"? Maybe there is some relation that I am missing.
•  » » 4 months ago, # ^ |   +9 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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 If i^th bit of u is 0, it means that there are even number of 1's at that bit position, and if there are so, the sum of even number of 1's will leave 0 at that bit. Hence, i^th bit of v must be 0 if i^th bit of u is 0. Similarly, you can make an argument for when i^th bit of u is 1, i^th bit of v has to be 1.
 » 4 months ago, # |   +13 Here is how I thought about D: First take care of the impossible cases and u=v=0. Let's start off with an array that satisfies the xor condition, then modify it until it satisfies the sum condition. So let's start with just the array $[ u ]$. We need to add $v-u$ somehow without changing the xor. For the $i$'th bit that is turned on in the binary representation of $v-u$, we can add two elements with value $2^{i-1}$, which doesn't change the xor, and let's do this for each on bit in $v-u$. Now note that the sum and xor is only affected by the number of on bits in each position, so instead of adding new elements, we can keep track of how many on bits in each position we need and try to squeeze them into as few elements as possible. Clearly we never need more than 3.
 » 4 months ago, # |   0 How to prove the answer for C is always correct by the editorial above.
•  » » 4 months ago, # ^ |   0 because we can't draw a simple path passing via a node including more than 2 edges that are incident on that particular node.
 » 4 months ago, # |   0 How to prove ( a+b=a⊕b+2∗(a&b) ) in problem D ?
•  » » 4 months ago, # ^ | ← Rev. 3 →   +20 Visual proof using Venn diagrams: Note that A + B is not actually union, its actual addition. Hence, both the complete circles will be added.
•  » » » 4 months ago, # ^ |   0 Thx
 » 4 months ago, # | ← Rev. 2 →   0 where can i learn stuff like: a+b=a⊕b+2∗(a&b).
•  » » 4 months ago, # ^ |   0 gfg
 » 4 months ago, # |   +16 Easy-to-read problem statements, good difficulty distribution, and interesting problems. To top it all, an editorial that was written 3 weeks ago! Nicely done!
 » 4 months ago, # |   +1 can anyone explain how the graph works in E
 » 4 months ago, # | ← Rev. 3 →   0 And why is the time complexity of the solution for E is O(sqrt(MAXA)). Shouldn't it be smth like O(sqrt(MAXA)*MAXA), because you firstly bruteforce over the sorce (O(sqrt(MAXA))) and then build the bfs tree (which is O(MAXA))OK, that was not the time complexity, sorry about that useless coment
•  » » 4 months ago, # ^ |   0 Can you tell why the time complexity is not O(sqrt(MAXA)*MAXA).
 » 4 months ago, # |   0 mohammedehab2002 In problem E — Bonus Task, how about answer can't be more than ~170.Proof — Worst case is when there is a chain numbers — (2*3), (3*5), (5*7), ..., (991*997), (997 * 2) after 997, numbers will exceed the bound on Ai — 10^6.Correct me if I am wrong..
•  » » 4 months ago, # ^ |   +4 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.
•  » » » 4 months ago, # ^ |   0 Yeah. Thanks :)
 » 4 months ago, # |   0 can anyone explain the question C ?? i am trying for the last 2 hours and still not able to understand the question. i read the tutorial and code but still the question is not clear.
•  » » 4 months ago, # ^ |   0 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
 » 4 months ago, # |   0 My solution for E based on parity of Prime factors power{ if even then they form a perfect square } of each number in the input, I have two choices for every number pick it or leave it then if I picked it, does it get the answer or not ?! that was my solution but I got TLE, anyone could help thanks in advancehere is my solutionhttps://codeforces.com/contest/1325/submission/73290435
 » 4 months ago, # |   +2 Can Anyone explain problem E logic, I still haven't understood the Editorial?
 » 4 months ago, # |   -9 Nice contest, gg :3
 » 4 months ago, # |   0 Can someone recommend me XOR related problems?Thanks!
•  » » 4 months ago, # ^ |   0 look at the this comment and this blog and this question
•  » » » 4 months ago, # ^ |   0 Thanks!
 » 4 months ago, # |   0 I gave my 3rd contests. I am unable to solve even A problem. Only solved A problem of Educational. Can anyone suggest some links that I should prepare from first??
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 months ago, # ^ |   0 Try practising ladders: https://www.a2oj.com/Ladders.html
 » 4 months ago, # |   +3 In problem C we can simply give the leafs lowest weights as there does not exist a simple path in a tree containing more than 2 leaves 73306866
•  » » 4 months ago, # ^ |   0 Interesting way to think!
 » 4 months ago, # |   +1 How to solve bonus task for problem A?
•  » » 6 weeks ago, # ^ |   0
 » 4 months ago, # |   0 In problem 'D' , why the array does not exist if the parities of 'u' and 'v' differ ?
•  » » 4 months ago, # ^ |   0 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.
 » 4 months ago, # |   +8 In question E , I am not able to understand how to get shortest path cycle in less than O(n^2)
•  » » 4 months ago, # ^ |   +8 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}$.
•  » » » 4 months ago, # ^ |   0 Why can't the product be larger than maxA?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +12 Because there does not exist an edge $(u, v)$ such that $u>\sqrt{\max a_i}$ and $v>\sqrt{\max a_i}$. Suppose that there is an edge $(u,v)$ in the shortest cycle, then we just need to take the $\min(u,v)$, which is must be within $\sqrt{\max a_i}$, as the source node and run bfs.Since all nodes are prime numbers, $\sqrt{\max a_i}=1000, \pi(1000)=168$, we just need to bfs at most 168 times, and the total time cost is about $\mathcal{O}(\pi(\sqrt{\max a_i})\cdot n)$
 » 4 months ago, # |   0 Fine :D
 » 4 months ago, # |   0 In problem c testcase number-61 is wrong . in these test case graph is not forming tree.
•  » » 4 months ago, # ^ |   +1 This definitely looks like a tree, atleast to me.
•  » » » 4 months ago, # ^ |   0 Thank you bro, i was misunderstood the question and i thought that its binary tree's question but i was wrong its only tree's question
 » 4 months ago, # |   +13 I wrote another solution to the F problem using dfs trees. I have described it here.https://codeforces.com/blog/entry/74800
 » 4 months ago, # |   0 So,bros,Can we solve F in this way.We find bccs in the graph and check whether there are a bcc,whose size is not less than sq,if not we sort the nodes as their degree,and add as many nodes into the independent set as possible. And I have some implenment problem. If we know the nodes in a simple circle,how can I print them in the order.Can someone answer me,Thanks bros!
 » 4 months ago, # | ← Rev. 2 →   +1 I have a different approach to D. Consider $dp[u][v]$ to be $-1$ if no solution exists for given $(u, v)$ and $a$ if $a + b = v, a \oplus b = u$.Now consider the last bit of $u$ and $v$.If they differ, the answer is definetely $-1$. Otherwise, there are two cases.If the last bit of $u$ is $1$, then the last bit of $a$ is definetely $0$ (or it is definetely $1$, depending on which one you like better, we may pick either of them as long as we are consistent in our definition of dynamic program). But then you must be able to construct $(u \gg 1, (v - 1) \gg 1)$, so if $dp[u \gg 1][(v - 1) \gg 1] = -1$, then $dp[u][v] = -1$, otherwise $dp[u][v] = dp[u \gg 1][(v - 1) \gg 1] \ll 1$.The second case is $u \bmod 2 = 0$. Then last bit of $a$ may be $1$ or $0$, so all you can say is that you must be able to either construct $(u \gg 1, (v - 2) \gg 1)$ or $(u \gg 1, v\gg 1)$.I don't really know why the number of states is low, there could be an exponential blowup in the number of states in the second case, but apparently it doesn't happen. If somebody has a proof for that, it would be interesting.Submission: 73345383
 » 4 months ago, # |   0 Didn't want to write a blog for this, so posting here. Why are we seeing " Rating changes for the last round are temporarily rolled back. They will be returned soon." so often? Is there a particular reason for doing this after ( almost ) every round?
 » 4 months ago, # |   0 I don't understand the problem C Editorial. Can anyone help me understand it more clearly? As in every case max(Mex(u,v)) over all u and v nodes will be n-2, so why can't we directly output numbers till n-2.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 i think your statement holds for bamboo path only. if you have branched tree like in example https://espresso.codeforces.com/f6df68c6c5c1b08e10c2945c8cd69295d2273c9d.png then MEX(3,6) is 2 which is the max in the example.
 » 4 months ago, # |   0 for solution of probelm f using dfs i could not understand why this is " If u has sq−1 or more back-edges, look at the one that connects u to its furthest ancestor. It forms a cycle of length at least sq" can anyone help me please .
•  » » 4 months ago, # ^ |   +1 Since there are no multiple edges, each back edge will go to a different ancestor. Each ancestor will be at a different depth from the root. In the worst case, one ancestor will be u's parent, i.e 1 level above u, another 2 levels above u, the next 3 levels above u ans so on....Therefore, it's guarenteed that the furthest ancestor will be atleast sq-1 levels above u, and hence, connecting it to this ancestor will form a cycle of length sq-1+1=sq
•  » » » 4 months ago, # ^ |   0 thanks @sudoBug it was very helpful i got it clearly.
 » 4 months ago, # |   0 There is another solution for c. One can start filling all leaves edges from 0,1,2.... and then can fill inner leaves with an arbitrary value.
•  » » 3 months ago, # ^ |   0 can u pls explain why?
•  » » » 3 months ago, # ^ |   0 https://codeforces.com/blog/entry/74235?#comment-589141 this comment has a wonderful explanation. I have done the same. Here's is my submission.
•  » » » » 3 months ago, # ^ |   0 Thanx, that comment was helpful.
 » 4 months ago, # |   0 For problem E why is not enough to make a dfs and check every back edge to find the minimum lenght of a cicle?
•  » » 4 months ago, # ^ |   0 Yeap, I got it: (1-2) (1-5) (1-4) (2-3) (4-5) (4-3) In this graph for a dfs like 1-2-3-4-5, we don't detect ( 1 — 4 — 5 )
 » 4 months ago, # |   0 I have written the code for Problem E, but it's giving me TLE. Here's my submission. I think the problem is in the way I am finding the shortest cycle. Can anyone tell me more exactly where am I going wrong? I did the same as in the editorial- for all node x find the shortest cycle including node x.
•  » » 4 months ago, # ^ |   0 Never Mind, got the mistake!
 » 4 months ago, # |   0 Hello! Could anyone tell "can we find longest simple cycle using DFS tree"?
 » 4 months ago, # |   0 can anyone plzz explain me the question no c...i.e C.Ehab and Path-etic MEXs
 » 4 months ago, # |   0 My solution for F For cycle of length sqrt: compute the height of every vertex using DFS. Look at all the edges. If the vertices differ by a height of (sqrt-1) or more, then they complete a cycle of length at least sqrt.For independent set of size sqrt: Use a priority queue to find the next vertex with the lowest degree. Add it to the set. Remove all its neighbours from the graph, and reduce the degrees of the neighbours of the removed neighbours by 1.Submission link: https://codeforces.com/contest/1325/submission/73650985
 » 4 months ago, # |   0 Yet another idea for D: There's a solution using two numbers if and only if $[\frac{v+u}{2},\frac{v-u}{2}]$ works.
•  » » 3 months ago, # ^ |   0 plz elaborate this.
 » 4 months ago, # |   0 Here are video editorials.
 » 3 months ago, # |   +3 From the problem C editorial: Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges.Please do not use such terms like "bamboo" in an editorial (or at least care to mention that you are talking about the shape of the real-life tree). It took me some time to conclude that this was not a computer science term.
 » 3 months ago, # |   +3 For problem F, this is stated in the second approach: "If at every step the node with the minimal degree has degree ≤ sq−1, that algorithm solves the first problem." By solving the problem we mean finding a independent set of size sq.Now, note that EACH of the first (sq — 1) nodes (that we choose for our independent set), in the worst case, will delete sq nodes (sq — 1 nodes connected to it, and one itself). Thus, before we are able to add the last node to our independent set, we have already deleted sq*(sq-1) nodes from our graph.Note that there exist several n such that sq*(sq-1) > n (take n=17,18,19 for trivial examples, they have sq=5). So, according to this, we should not be able to add the last node for such values of n.This contradicts the editorial however. So, where did I go wrong?
•  » » 3 months ago, # ^ |   +5 Hi!Sorry, I had a small mistake in the editorial. I proceed to solve the cycle problem if the node with the minimum degree has degree $\ge sq-1$, so in order to solve the independent set problem, its degree is strictly less than $sq-1$ in every step, and it removes at most $sq-1$ nodes, not $sq$.
»
3 months ago, # |
0

# include<stdio.h>

int main( ) { int t,c,n,d,i,j,swap,count=0; scanf("%d",&t); for(c=0;c<t;c++){ scanf("%d",&n); int array[n]; for(d=0;d<n;d++) scanf("%d",&array[d]); for(i=0;i<n-1;i++){ for(j=0;j<n-i-1;j++){ if(array[j]>array[j+1]){ swap= array[j]; array[j]=array[j+1]; array[j+1]=swap; } } } for(j=0;j<n;j++){ if(array[j]== array[j+1]) { count++; } } printf("%d\n",n-count); count=0; } } It is the best solution in C.

 » 3 months ago, # |   0 In problem E, I don't get the intuition of why why we build a graph with prime labels only. My attempt is to build graph with vertices being 1, p, p*q. And then the edges being 1, p, p * q. For each node, the next node label * edge label normalized. However, this means that edges can be repeated. How do I get from this attempt to the editorial's solution?
 » 3 months ago, # |   0 In editorial of F, it is said that " If u has sq−1 or more back-edges, look at the one that connects u to its furthest ancestor. It forms a cycle of length at least sq." Can someone elaborate why should there be a cycle of length atleast sq..??
 » 3 months ago, # |   0 can anyone describe me the solution of A??
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Assuming d is GCD(a,b) we have: a=d*p b=d*q we have LCM(a,b) = d*p*q. x = LCM(a,b) + GCD(a,b) = d*p*q + d = d(p*q + 1). Since numbers a and b are picked arbitrary by us, we can try choose d = 1. Therefore, x = p*q + 1. LCM(a,b) = p*q = x - 1. Let's take p = x .- 1, then q = 1, and that's satisfies all statements above. Which is exactly what editorial saying :-)
•  » » » 3 months ago, # ^ |   0 thank you very much.
 » 3 months ago, # | ← Rev. 2 →   0 In D,if u>v no solution exists....but why?
 » 2 months ago, # |   0 If at every step the node with the minimal degree has degree < sq-1 , that algorithm solves the first problem..I dont quite understand how
 » 2 months ago, # |   0 Can someone help me with python ?
 » 6 weeks ago, # |   0 **MY SOLUTION FOR C** As Given that we have a tree and we are considering path for every pair of nodes so paths can be of 3 types 1) leaf to leaf In this case a) if number of leaves >2 so still some edges containing leaf node as one of the edges exist b) if number of leaves==2 so structure is bamboo like and is of no concern 2)leaf to non-leaf and 3)non-leaf to non-leaf In both the cases we definitely will have some edges containing leaf node as one of the edges exist So from above cases you realize can realize that any path you consider some leaf-edges will remain(not contained in that path choosen) at end of the day.. So Greedy approach to give the leaf edges numbers from 0,1,2.. and non leaf edges n-2,n-3.. * How I got this Idea I considered the following cases * 1--2--3--4 Best solution 0 2 1 since max(MEX(u,v))is 1 will in all other configurations answer is 2 [MY submission:](http://https://codeforces.com/contest/1325/submission/81356364)
 » 3 weeks ago, # |   0 Can anyone explain the solution for problem E? (I am not understanding the editorial)
 » 3 weeks ago, # |   0 can someone help me with my solution for F
•  » » 3 weeks ago, # ^ |   +6 Ah, the two necroposters who made me wonder why the contest problems and editorial are different.