Codeforces round #628 editorial

#	User	Rating
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

1325A - ЕхАб И нОд

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

Code link: https://pastebin.com/ddHKD09B

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?

**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.me/contest/1325/submission/81356364)

Comments (202)

Show archived | Write comment?

hata_saa

5 years ago, # |

← Rev. 2 →

+71

woa, so fast, I feeling so good to know how to solve those. Thanks alot for your effort

→ Reply

adivannik

Could anyone please tell me why this was giving TLE? https://codeforces.me/contest/1325/submission/73271304

Thanks!

5 years ago, # ^ |

It's the submission for C

bleh0.5

← Rev. 3 →

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

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

Oh, graph is a dictionary here (HashMap), constant lookup.

ibalram

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.

bahaaEldeen

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

Gaurav1

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!

alexanderanchishkin

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!

Really Cool. Thanks for looking at the code!

Norrius

+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))

I'll keep that in mind from now. Thanks a ton!

nagabhushan

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

VioletVal

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

alvinpiter

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.

+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

Hamim99

nice explanation sir.

iprakhar22

+35

One can visualise the equation using Venn diagrams

suraj021

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!!

_nathan_drake_

In editorial for problem D, what does this mean "if u and v have different parities, there's no array"

user14767553

"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.

arpa.sh

Can you explain why solution will not exist for different parity u and v?

khulegu

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.

antriksh007

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

ajaymalik

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)

MubtasimShahriar

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

LeBongIsMyLove

Such a fast editorial !!!

__I_love_Jeon_Soyeon__

Thanks for the quick editorial !

Sankalan7

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.

Show_2.5_Need

what do u mean by g|x?

himanshupareekiit01

It means g divides x.

harshilbhatia2001

4 years ago, # ^ |

Check out the video solution to the bonus task

xenowits

How did u judge the solutions of problem C?? I mean there are a variety of solutions..

rupav

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.

egoods

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.

DeadlyCritic

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.

oCaixeiroViajante

I did the same thing, but failed test 7. Can someone take a look? https://codeforces.me/contest/1325/submission/73250194

Induber

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?

kstheking

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 !

orangeorange

Why in problem C we need to check node with exactly three or more edges?

kush_153

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.

donkumar

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

coding_panda

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.

adel54321

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

cs234_shrey

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.

r.zay699

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)?

Graphter

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

tribute_to_Ukraine_2022

+40

Another way to think about DFS solution for F

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!

iamhpp

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.me/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.

utkarshh12

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

dulatcodes

The solution to problem E is truly beautiful!

Akshay184

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

bagheldevender

to eleminate the factors having even frequncy in factorization

HadyKo

+14

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

Devised_positive

3 years ago, # ^ |

Really!

hasib_hossain

How to solve C ? Please explain simply .

thank u so much .. :D

ashu_moudgil

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

Dsxv

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.

kaneki_007

Great explanation:):)!!

The_Phenomenal

In D how can we say that the max length of such an array can be at most 3?

Arcane

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

Is there any formal proof of it?

dorijanlendvaj

+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$$$

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

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 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... ?

$$$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?

sempav

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.

JNU_dh_AK_WF

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.

sxpg

When will there be rating changes?

aayushgarg_03

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/

sourabh54singh

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

if (S-X) is odd return false

kyo20111

+16

I think the First AC of E is in the middle of F

sinus_070

+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.

Can you please elaborate?

Java

Alternative DP Solution to D: https://codeforces.me/contest/1325/submission/73276587

ghoshsai5000

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

bas

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?

EvenX

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

Ah, thx!

okwedook

+26

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.

tfg

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...

oleh1421

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.

Ice_Cream

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?

Muhammad98

non-greedy solution for problem D 73264903

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

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

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 = 0

Can you give an example of the same?

xor(a, a) = 0

Thanks for such a clear explanation.

Ankit__

Question D was great... looking forward to participate more of your rounds in future :)

if417021

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.

nayeem_shahriar_joy

-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.

spirited_away_

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.

Ahmadsm2005

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!

Mahfel

-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!!

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.

+28

Oh yes.I was wrong. sorry jury!sorry codeforces!

vivek2020

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.

theBanzaiPredicament

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.

+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.

Bedoo

How to prove ( a+b=a⊕b+2∗(a&b) ) in problem D ?

adzo261

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

rishursx

where can i learn stuff like: a+b=a⊕b+2∗(a&b).

atishay127

gfg

sh_maestro

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

lucifer_1502

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

ILoveBitches

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..

mohammedehab2002

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 :)

iabhishek15

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.

KnightKnight

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

manoj_269

Can Anyone explain problem E logic, I still haven't understood the Editorial?

risolutore

Can someone recommend me XOR related problems?

ya_hossein

look at the this comment and this blog and this question

gyan_p_t

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.

Marshmello

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!

pj28105

How to solve bonus task for problem A?

ateev_mishra7

In problem 'D' , why the array does not exist if the parities of 'u' and 'v' differ ?

alhasan

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.

iit_ya_ism

In question E , I am not able to understand how to get shortest path cycle in less than O(n^2)

JustInCase

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}$$$.

Magdy_Sedra

Why can't the product be larger than maxA?

KaitoHH

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)$$$

MonsieurV

Fine :D

SJD1206

In problem c testcase number-61 is wrong . in these test case graph is not forming tree.

gupta_samarth

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

demoralizer

I wrote another solution to the F problem using dfs trees. I have described it here.

https://codeforces.me/blog/entry/74800

Falcon__

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!

ggdwbg

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?

anup_b170628cs

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 .

sudoBug

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

person123

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.me/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.

Fanurie

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 )

_blast

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!

dream_is_real

Hello! Could anyone tell "can we find longest simple cycle using DFS tree"?

Whiplash99

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.me/contest/1325/submission/73650985

ivan100sic

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.

Updown

Here are video editorials.

swapnilr

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.

sigma_g

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$$$.

mightymercado

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?

nivedh

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..??