Hi!
Codeforces round #628 (vintage Codeforces round #2) will take place on 14.03.2020 17:35 (Московское время). It's rated for the second division, but, as usual, first division participants can take part out of competition.
The problems were created by me. I'd like to thank, and orz, antontrygubO_o for coordinating the round; ramchandra, pajenegod, aryanc403, taran_1407, Kuroni, mcdx9524, dorijanlendvaj, Andreasyan, 300iq, zoooma13, Osama_Alkhodairy, Mohammad_Yasser, and TripleM5da (special shout-out) for testing the round; and of course MikeMirzayanov for the great codeforces and polygon platforms.
You'll be given 6 problems and 2 hours to solve them.
UPD: the scoring distribution will be 500-750-1250-1750-2500-2750.
UPD: the editorial is out.
UPD: congratulations to the winners!
Div.1:-
Div.2:-
Good luck & Have fun!
Good to see Round pi*200 on pi day.
Hope to see one problem related to XOR and problems name as Ehab and ... .
Aha,you really hit the truth
before the contest my comment was having a lot of downvotes now its come to 0. <3
1325B - CopyCopyCopyCopyCopy In the second test case of this problem there is a Pi Number;3,14159.what a coincidence in Pi Day :D.
Are you sure you're going to be available on that day?
Depends on the timezone you consider ;-;
the internet connection is not stable now a days here in Egypt
inb4 anton quits coordinating rounds like he quit AC
kostia orz
tau is superior
Another contest by one of my favourite problem setters — mohammedehab2002. I'm going to revise XOR problems to prepare !
UPDATE — I will lose ratings but I enjoyed the hell out of it ! Thanks mohammedehab2002 for preparing an excellent contest and I hope to see many more from you in the future !
yeah...looking forward for "Ehab and..." problem :3
make the problem description short like the announcement ^_^
Most of the Problem title would look like 'Ehab and bla bla bla ....'
orzing is forbidden
rotavirus orz
what do you mean by (vintage Codeforces round #2) ?
*le xor problems
here we go again.
If i registers for contest. But will not give this contest. Will it affects my rating?
No, as long as there is no submission from your account
No, but if you do at least one submission during the contest you will be affected.
if submission doesn't pass first test_case, then it doesn't affect rating.
No. If you do at least one submission during the contest, it will affect your rating (even if it fails the first test case). But of course, it doesn't add to your penalties (-50 points for the classic Div. 1/2 or +10 minutes for Educational or Div. 3).
I think you missed this:
مرحبا كودفورسز (hello codeforces)
xor problems, here we go again.
Is it rated till 1900 or 2100 ?
As mentioned here.
The 1900+ rating means that you're part of the first division
So, 1900 i believe.
No, when a div1 round and a div2 round both are going on simultaneously then the div2 round is rated for participants upto 1900 rating. If only a div2 round is being conducted, its rated for participants having a rating upto 2100
Well I know this fact. And I'm sure even you would know that each and every time, any Div 2 contest is hosted alone, it is always mentioned in the contest announcement post 'rated till 2100'. That was why I preferred confirming once.
I don't understand why people here just start downvoting the comments. If the query was so stupid, please accept my apology and don't mind :)
Yes, I agree, people often downvote genuine comments as well without a proper reason, maybe just because it has already accumulated a few downvotes.
Maybe this comment of mine will be downvoted for no reason.
But one more thing is there, maybe people thought your question was a little stupid (the part you wrote about the 2100 rating always being mentioned wasn't written)
Oh yeah, that's right. I'll take care from the next time. Thanks Sixpathsguy :)
2100
I hope the the expected XOR Problem is replaced by a constructive or number theory problem. orz
1)
Is it rated?
Hello. Can you please reschedule the round for 12 hours (Moscow time), in connection with the holding of another Olympiad at 15:00 (Moscow time). Thanks in advance
Hello. Can you please reschedule the round for 12 hours (Moscow time), in connection with the holding of another Olympiad at 15:00 (Moscow time). Thanks in advance
You can give virtual ,as it will be unrated for you anyhow.
I'll ask my coordinator.
Hello. Can you please reschedule the round for 12 hours (Moscow time), in connection with the holding of another Olympiad at 15:00 (Moscow time). Thanks in advance
Get ready for more XOR problems !
Can the contest be delayed 1 hour please because I wouldn't be available at this time. mohammedehab2002
Hello. Can you please reschedule the round for 12 hours (Moscow time), in connection with the holding of another Olympiad at 15:00 (Moscow time). Thanks in advance
Hello, aihay.
Ah, i see, Mike didn't discuss contest timing with you this time. Forgive him, he's a bit busy preventing corona from spreading through CF, you know.
I'll make sure this will not happen again! My apologies for this awful inconvenience. CF stuff will be punished, I promise!
Hope you like the new timing! If you have any other problems with CF feel free to DM me!
Best regards, kostia244
Will this contest effect my rating ....if my current rating is 1255,._???
Yes, it's rated for you.
Xor here u are
Waiting for interesting problems as expected from you
Hope that I can solve ABC <3
Seeing the score distribution: 500-750-1250, I think the difficulty gap between A and B will not be as big as other contests.
Oh, you are so smart!
Why you are still newbie, phps?
It's exciting that Codeforces is holding more and more vintage rounds (ʃƪ ˘ ³˘)
Why a lot of comments are about XOR-problem. Could you explain me this joke
https://codeforces.net/contests/writer/mohammedehab2002
Literally every contest he has written has a problem about XOR.
Lets starts xorforces...
owee great new XOR problem is coming ... :)
Maybe today I will reach master before CoronaVirus reaches me :D
tedesjo fire ||| _ __ _ ## (_ " + __ _ )) )) + || | | _+ _
ReAd?Y?!
PWPSD
15600+ registration! Get ready for long queue! O_o
Deleted
timelimit on c with O(n) with python :(
MathForces > ArrayForces
I did A and B in 30 minutes, still my rating is going down, C is too much for me, oh well.
As expected , Another xor problem D.
When I submit, the output that is on your testing is different from the output when I run the program on my computer. How do I fix this?
How to solve C?
set smallest numbers to edges to leaf, and others randomly)
You would have to take care that the parent on the leafs where you place the edges 0 and 1 is not the same vertex. Because if it is, that MEX will be 2 instead of 1.
Edit: It turns out I am completly wrong with this. There is no need to take care for the parent. The only thing to take care of is not placing the edge 2 between the edges 0 and 1. For that it is perfectly fine to simply place the numbers 0,1,2 in leaf edges.
If it's a chain, then fill all the edges randomly.
Otherwise, choose a node of which degree is 3 or above, fill three of the edges using 0, 1, 2; others random.
It can be proved to be one of the best answers.
Here's what I did : Sort all vertices by their degree in descending order. Now, starting from the vertice with the maximum degree, try and fill all its unfilled edges with numbers in a serial manner( Maintain a count variable. Fill edges with the count variable and increment it everytime you fill an edge )
How to solve problem D?
I tried to construct bit by bit, starting at lowest bit and the xor input. Then add bits to get the sum, by adding the one lower bit twice to two numbers in the array. And so on...
Did not work for some reason.
max length of the answer is 3
The answer is at most 3 or it is impossible.
If $$$u$$$ and $$$v$$$ don't have same parity or $$$u>v$$$, it is impossible.
If $$$u=v$$$ the answer is $$$0$$$ if $$$u=0$$$, $$$1$$$ otherwise.
Otherwise, try to build a pair which xor gives $$$u$$$ and sum gives $$$v$$$. Let $$$t=(v-u)/2$$$. If $$$u$$$ and $$$t$$$ don't have any bits in common, a pair of solution is $$$u+t$$$ and $$$t$$$.
Otherwise, $$$t$$$, $$$t$$$, $$$u$$$ is a solution.
Look at the bitwise representation of $$$u$$$. Every bit that equals 1 means that there is an odd # of elements with that set bit. Every bit that equals 0 means there is an even # of elements with that set bit (because 1^1^... odd number of times = 1, 1^1^... even number of times = 0). So one of the array elements is at least equal to u. Suppose first element of array = $$$u$$$. Then we have to add two elements such that we don't change the parity of set bits; i.e., we must add two of the same element, call it $$$y$$$. This is 3 total. But then we can consolidate one of the $$$y$$$ into $$$u$$$, iff $$$u$$$ AND $$$y$$$ equals 0.
I had this idea, too. if u-v is even, add (u-v)/2 twice. But how does it work if u-v is odd?
We cannot add both numbers, because one bit will be set wrong then.
Edit: Fuck it, the parity of u and v is same! I had this before, checked and output -1. So, if the parity is same, the difference is allways even. The odd case does not exist.
You can make array of one element if the XOR value equals to SUM,
the one's bits in XOR must appear in odd numbers in array.
so we can make array of two elements if the following conditions comes true,
one of the two numbers has the one's bits in XOR
and the remainder rem = (XOR — SUM),
can be distributed among two numbers (must be half in the first and half in the second to get XOR ZERO)
and the XOR of those two number must be the same of XOR in the input
and you can make array of three elements if the following conditions comes true,
one of the three numbers has the one's bits in XOR
and the remainder rem = (XOR — SUM),
distributed among the other two numbers equally to get (XOR zero) when XOR them,
so when we XOR the input with zero we got XOR.
otherwise there is no answer.
Me after solving ABCD:
Me toooooo!!!
So do I
what is test case 18 in problem D
I got wrong answer in testcase 18 because of not handling the answer for size 3 properly.
Basically, for size 3 you have to print u, (v — u)/ 2, (v — u) / 2
Instead, I printed u, v / 2, v / 2
I think you have missed this point too.
Though, thankfully i spotted my mistake quickly during the contest time. :3
i got my mistake something like your's..thanx for answer
Is: (a + b + c) = (a XOR b XOR c) + 2 * (a AND b AND c) ?
Nope, i guess it is (a^b^c) + 2*(a&b + b&c + c&a — 2*(a&b&c))
is E shortest cycle detection after reducing prime divisors to a graph?
Something like that, couldn't solve though
How to solve C & D?
Solution of D.
You can check this.
https://codeforces.net/blog/entry/74683?#comment-589082
How to solve the case in E, when you must find the shortest cycle in the graph? :c
Disclaimer: I don't have an accepted version yet.
There are 168 primes below 1000 and ~75'000 primes below 1'000'000
Lets call primes < 1000 "small" and primes > 1000 "big"
We cannot have an edge between two "big" primes (this would mean that some $$$a_i > 1000^2 >= 1000000$$$, a contradiction!
If there's a cycle, then it needs to have at least 1 "small" prime in it.
For each vertice corresponding to "small" prime, do a BFS from this "small" prime — find a shortest cycle that contains this vertice, update the answer.
It is rated?
How to Solve C?? Is there any Pattern ?
Label any 3 edges, which connects a leaf vertice, with 0,1,2
You can label other edges with any numbers avaliable.
If the tree is a chain, all of the labeling way are acceptable.
if you find one node like x that has 3 neighbors then use 0,1,2 for labels of edges between x and neighbors and you can chose labels of other edges in any order and you will get MEX(u,v) = 2
if you can't find node like x then chose all labels of edges in any order and you will get MEX(u,v) = n — 1
How to solve D?
Obviously, if
u > v
oru % 2 != v % 2
, there isn't a solution.If
u == 0 && v == 0
,0
should be the answer.When it comes to
u == v
,u
could be a answer.Otherwise:
You can check it :P
Appreciated it, thanks
This submission is passing but This one is failing Where this is wrong?
In this line
int bit = log2(sum);
You must cast sum to double or long double to get right answer.
int bit = log2(1.0L * sum);
for 2 length why can't number be (u,v-u)?
'cause you may not guarantee that
u^(v - u) == u
though their sum is u.You can check this.
https://codeforces.net/blog/entry/74683?#comment-589082
Thanks a lot for explaining it
Was problem F related to finding if the graph is triangler graph?
For problem C - I took number of leaf nodes of the tree
count
and assignedcount to n-2-count
to those edges and remaining values to the nodes with children. Was I wrong?For second sample, count=3, you assigned 3 to (6-2-3)=1. Even 0 must be used for those edges.
So, how do you solve E?
Please help me in solving question D. Thank You.
You can check this.
https://codeforces.net/blog/entry/74683?#comment-589082
Sorry, but why are you copy-pasting the same answer everywhere? You could simply write your answer once and share the link.
Ok thanks, i will update all comments.
Does anybody know how to solve F?? i thought the articulation point.. but i can't solve this
Please help me in solving D. Thank You.
you think that first value is v and rest value is adding number to u to satisfy xor
if bit of difference of v-u is 1, you can make two number (1<<(bit-1) and (1<<(bit-1) because (1<<(bit-1))^(1<<(bit-1)) = 0 and (1<<(bit-1)) + (1<<(bit-1)) = (1<<bit)
so you can make three values in array
but if (1<<(bit-1))^v == 1, you just add the number v to (1<<(bit-1)) so you probably make the two number in array
The editorial is out. It's the fastest editorial I've ever seen. Orz
E:
We can divide every number by square of a prime until it is a product of primes. If there is an $$$1$$$ or 2 indices with the same number, we already found an answer.
Also observed that in each number there will be at most one prime larger than 1000.
What can be done next to get the solution?
UPD: seems I miss that its "divisors" not "prime divisors", thanks editorial.
Screencast
Was waiting for this Thanks
Screencast with commentary
Hey, can anyone please tell me the total hacking time for this particular contest?[contest:628][contest:628(Div2)]
There is no hacking time, when it is finished, it is finished.
Thanks
Usually, it is the Div 3 and the Educational Rounds which have hacking phases after the coding phase of the contest. In Div 2 and Div 1 contests, there is only the coding phase but not hacking phase.
Thanks
Global Round in 5 days...Yayyaya
No, there another one within 5 days
How can you say? It doesn't mention any
Strangely, I started to read coronavirus instead of codeforces :o
You mean CoronaForces > Codeforces
Other Solution for C:
count = no of leaf node(node with degree == 1)
if(count >= 3):set any three leaf node to 0, 1, 2 that will set the upper boundary for MEX to 2
because any path in tree can have maximum 2 leaf nodes
if(count < 3) arbitary
I did this too! The editorial solution made me realize that there exist at least 3 leaves iff there exists a vertex of degree 3. It is a special case of this theorem
Can anyone help with what is problem with test 143 in E? Its too large to debug by hand, and I can't find small counter to my code...
My code: https://codeforces.net/contest/1325/submission/73272537
Lol. Didn't solve D because I didn't consider just 1 case:
if(u == v) {cout<<1<<'\n'<<u; return 0;}
My Java solution for E passed in 2979 ms. Talk about scraping the time limit.
Is this solution (73271134) for F hackable, or is it accidentally correct? I sort of combined both of the editorial solutions without understanding either of them.
First, I attempt to find the independent set with exactly the editorial's "A solution using degrees" algorithm. In a set, keep a list of (degree[i], i) pairs, and keep taking the node with minimal degree and invalidating each node's neighbors, updating the degrees of the neighbors of each invalidated node in the set.
The
if (n <= 16)
brute-force part is only there to counter some of the manually generated edge cases, which tend to be small.Then, I run DFS from random starting nodes. This DFS runs in arbitrary order, and when it hits an ancestor in the DFS tree, checks if the cycle is long enough/prints it. It runs until it either finds an answer, doesn't, or TLEs (might be $$$O(n^2)$$$ at worst).
is it just me or has codeforces slowed down on the contests! The next one is after 5 days! :(
Hi, i was banned for copy pasting. But it's system error :) There are some reasons, why it is impossible to stole his solution: 1) Code is really simple and there were too many participants, that's why chance of two similar codes is really hight 2) I am from Russia, he is from France))) 3) Also i wrote him, and i believe, that he will agree with me, because it's really strange, i didn't know him before this :| Thank you for your attention and i hope that you will solve this problem, because it's really sad(
Hello, I am the person the system claims Witless_Deer copied from. For the reasons he mentioned (especially reason #1), it is ridiculous to claim that he copied me. Look at our submissions for B to see for yourselves.
Can anyone explain me Problem C. i am not able to understand it.
Consider the paths between all nodes. If the edge with value 0 is not on such a path, the MEX of that path is 0.
So, consider the paths with the 0. The MEX of these paths is 1, except if the edge with value 1 is also in this path. Then it is at least 2.
So, is it possible that there is no path with edges 0 and 1 in the path?
It turns out, no, that is not possible. Since by the simple fact that the path from two nodes of the edges with value 0 and 1 has both edges in it. So it allways exists.
But now we are close to the solution. How can we place the edge with value 2 in a way that it is not on that path, too?
Well, more or less simple, we place that edge not on the path between the edges 0 and 1. Then it is not.
Last question to answer is, how do we implement this, how can we find suitable vertex and edges? The tutorial answers this clearly: We search an vertex with at least 3 edges, and use these 3. Then the edge with value 2 will not be on path between the edges 0 and 1.
Nice Contest <3 :)
I like how all Ehab contests are based on intense maths and number theory.
your nickname is very suitable for your comment about math)))
Few Hour ago i got a message from System. I'm sharing it here.
My PC is too slow. So i use ideone to compile my code and also i feel comfort at online IDE but I've made a mistake. Today's morning (Bangladesh Standard Time), By mistake I change my code sharing option private to public and i didn't notice this before contest. So someone got my code on internet. I admit that it's my fault and also i promise that, I will never make this kind of mistake again.
I think you can start using other IDEs such as
https://www.jdoodle.com/online-compiler-c++17/
or
https://ide.geeksforgeeks.org/
These are much more safe than using ideone.com .. There used to be one more IDE from hackerearth: https://code.hackerearth.com/, but it's out of service now.. So please try using any other IDE or local compiler.
That sounds great. But it's okay now. i change my ideone setting. Thanks for your suggestion.
You're Welcome.. !
I don't know why but my submissions from that contest are still shown as pretests passed. Moreover, all of them were evaluated as failed attempts. And my rating has dropped :/ I firstly thought maybe system evaluated my submissions like I cheated. However, I did not receive anything regarding to that. Can someone check this?
It happens when your submissions are evaluated and you are found guilty under Plagiarism check. I think you should reach out to Codeforces Authorities regarding the same.
Have a nice day!
Really amazing and Mathematical contest. Loved it.
Exactly.. One more thing which I liked was that problem statements were to the point rather than long paragraphs, and properly framed.
.