1325A - ЕхАб И нОд
$$$a=1$$$ and $$$b=x-1$$$ always work.
Code link: https://pastebin.com/ddHKD09B
First AC: sevlll777
Bonus task: can you count the valid pairs?
1325B - КопияКопияКопияКопияКопия
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$$$.
Code link: https://pastebin.com/hjcxUDmY
First AC: socho
1325C - Ехаб и неПутевые MEXы
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.
Code link: https://pastebin.com/u4H7Dtbd
First AC: vintage_Vlad_Makeev
1325D - Ехаб, XORминатор
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$$$.
Code link: https://pastebin.com/7XuMk1v8
First AC: jqdai0815
1325E - НАСТОЯЩАЯ Теория чисел от Ехаба
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.
Code link: https://pastebin.com/4ixLQyvg
Bonus task: try to prove the answer can't exceed $$$2\sqrt{maxAi}$$$.
1325F - Последняя теорема Ехаба
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!
Code link: https://pastebin.com/b9phCSW8
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$$$!
Code link: https://pastebin.com/1VwZYPCj
First AC: imeimi after only 11 minutes!
There are probably other solutions and heuristics. Can you share yours?
woa, so fast, I feeling so good to know how to solve those. Thanks alot for your effort
Could anyone please tell me why this was giving TLE? https://codeforces.net/contest/1325/submission/73271304
Thanks!
It's the submission for C
you're using python and your algorithm is n^2
Actually, the set size will never grow more than 3 elements (the inner loop). It looks N^2 but it's not
i believe this is n^2 but I don't know python either
Oh, graph is a dictionary here (HashMap), constant lookup.
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.
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
Sir, it's not N^2. Could you please see my above reply to bleh0.5
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.:)
oh is it so? It's so frustating and unfortunate that python is slow. Thanks a lot!
How about input optimizing? input — slow method, use alias:
But the main problem is partial reading. It could be too much faster if you'd read all lines, for example:
Good luck!
Really Cool. Thanks for looking at the code!
I think it's because your complexity is $$$O(n^2)$$$. Take a look at these lines:
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:
I'll keep that in mind from now. Thanks a ton!
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
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.
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
nice explanation sir.
One can visualise the equation using Venn diagrams
I still can't get it. Can you please show us the diagram? Thanks
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.
See bicsi's video at that timestamp: https://youtu.be/fpxArbp3FLo?t=8456
Thanks, Bhai. Understood it on the second go. Hail bicsi!!
In editorial for problem D, what does this mean "if u and v have different parities, there's no array"
"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.
Can you explain why solution will not exist for different parity u and v?
Don't think too hard. Just focus on the very last bit (right most). Parity means whether the last bits are same or not.
XOR and ADDITION acts same on last bit. Hence the XOR and ADDITION should end with same bits i.e should have same parity.
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.
Such a fast editorial !!!
Thanks for the quick editorial !
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?
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.
what do u mean by g|x?
It means g divides x.
Check out the video solution to the bonus task
How did u judge the solutions of problem C?? I mean there are a variety of solutions..
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.
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.
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.
I did the same thing, but failed test 7. Can someone take a look? https://codeforces.net/contest/1325/submission/73250194
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?
how would you calculate the number of times edge occur in paths ?
for an edge lets say a-b where a is parent of b, edge a-b will occur in (number of nodes in subtree of b(including b)*remaining nodes) paths.
got it ! thanks a bunch !
Why in problem C we need to check node with exactly three or more edges?
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.
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/4P89Jga
In the first diagram max MEX value comes out to be 6 In the second diagram max MEX value is restricted to 3 only
how come the max MEX is 6 in the first case .. I guess its 1 ?
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
MEX(2,7) contains weights 1,2,3,4,5 not 0 . Hence MEX(2,7) = 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.
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
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,...,n
This 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.
Yes you are definitely right, thanks for correction. I missed this point. But the algorithm still applies however.
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)?
In line 32 you should use long long instead of int
Woa..A great contest and a quick editorial... Really appreciate this... Thanks alot for your effort
Suppose 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.
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.
This is test 151: https://codeforces.net/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$$$
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.
Can you give some proof that if a node has sq-1 backedge,then there surely exists a cycle of length atleast sq.
The solution to problem E is truly beautiful!
can you explain the editorial. Why are we diving with perfect square?
to eleminate the factors having even frequncy in factorization
true I figured everything but got stuck on getting the Length of the smallest cycle the final trick is amazing!
Really!
How to solve C ? Please explain simply .
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
thank u so much .. :D
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
Same, my dumb ass realized this after wasting 40 mins because I thought test 19 wouldn't be something so simple :(
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.
Great explanation:):)!!
In D how can we say that the max length of such an array can be at most 3?
Because ,u (v-u)/2, (v-u)/2 always work.
Is there any formal proof of it?
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$$$
Hey, Can you please answer my following questions?
v-u
is odd, why isn't there any solution?(u & (v-u)/2) ==0
, how are we sure of two numbers to beu + (v-u)/2
and(v-u)/2
?I have a hard time understanding bit operators. Thanks
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.
Why cannot it have more than 3 elements in the array?
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
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 finda
andb
.n= 3:
u, (v-u)/2, (v-u)/2
is the answer ifv-u
is even.Suppose both the above case fails, then why are we not checking for n= 4, 5, 6... ?
$$$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.
How come a⊕b≡a+b mod2 consider a=2 and b=5 then how the above holds?
$$$1+2=3$$$
$$$1 \oplus 2 = 3$$$
$$$3 \equiv 3 \mod 2$$$
The RHS becomes 1 but LHS is 3?
You're reading it wrong. https://en.wikipedia.org/wiki/Modular_arithmetic#Definition_of_congruence_relation
Pardon me again. But I don't understand why are we not checking for n= 4, 5 ...?
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
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.
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.
When will there be rating changes?
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/
The code is giving wrong ans for s=6 and x=1.
if (S-X) is odd return false
I think the First AC of E is in the middle of F
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.
Can you please elaborate?
Alternative DP Solution to D: https://codeforces.net/contest/1325/submission/73276587
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
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?The path from one leaf node to the other leaf node will definitely have a MEX equal to n-1.
Ah, thx!
Randomized solution to F
First 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.
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'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...
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
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.
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?
non-greedy solution for problem D 73264903
Can you please explain the approach you have used to solve it?
u > v
the answer is-1
arr
sum
and you want to distribute it on some numbers to give you the requiredxor
.1
in the current bit inxor
you need to leave a bit in this position inarr
from thesum
you havexor
, there will be a remainder, you don't wan't this remainder to affect thexor
, so divide the remainder by 2 and put 2 bits in the positions that has1
in the binary representation of the remainder.-1
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 thearr
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?
to not affect the
xor
, as xor of the same number = 0Can you give an example of the same?
xor(a, a) = 0
Thanks for such a clear explanation.
Question D was great... looking forward to participate more of your rounds in future :)
How to solve A ? Please explain simply
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.
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.
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!
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!!
I guess we have to!!!
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.
Oh yes.I was wrong. sorry jury!sorry codeforces!
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.
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.
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.
How to prove ( a+b=a⊕b+2∗(a&b) ) in problem D ?
Visual proof using Venn diagrams:
Note that A + B is not actually union, its actual addition.
Hence, both the complete circles will be added.
Thx
where can i learn stuff like: a+b=a⊕b+2∗(a&b).
gfg
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!
can anyone explain how the graph works in E
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
Can you tell why the time complexity is not O(sqrt(MAXA)*MAXA).
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..
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.
Yeah. Thanks :)
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.
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
Can Anyone explain problem E logic, I still haven't understood the Editorial?
Can someone recommend me XOR related problems?
Thanks!
look at the this comment and this blog and this question
Thanks!
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??
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.
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
Interesting way to think!
How to solve bonus task for problem A?
Check out the video solution to the bonus task
In problem 'D' , why the array does not exist if the parities of 'u' and 'v' differ ?
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.
In question E , I am not able to understand how to get shortest path cycle in less than O(n^2)
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}$$$.
Why can't the product be larger than maxA?
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)$$$
Fine :D
In problem c testcase number-61 is wrong . in these test case graph is not forming tree.
This definitely looks like a tree, atleast to me.
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
I wrote another solution to the F problem using dfs trees. I have described it here.
https://codeforces.net/blog/entry/74800
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!
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
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?
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 .
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
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.
can u pls explain why?
https://codeforces.net/blog/entry/74235?#comment-589141 this comment has a wonderful explanation. I have done the same. Here's is my submission.
Thanx, that comment was helpful.
For problem E why is not enough to make a dfs and check every back edge to find the minimum lenght of a cicle?
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 )
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.
Never Mind, got the mistake!
Hello! Could anyone tell "can we find longest simple cycle using DFS tree"?
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.net/contest/1325/submission/73650985
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.
Here are video editorials.
From the problem C editorial:
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.
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?
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$$$.
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?
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..??
In D,if u>v no solution exists....but why?
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
Can anyone explain the solution for problem E? (I am not understanding the editorial)
can someone help me with my solution for F
Ah, the two necroposters who made me wonder why the contest problems and editorial are different.
Does problem D not have checker?