### mohammedehab2002's blog

By mohammedehab2002, 4 years ago,

Hello codeforces!

I'm glad to announce that codeforces round #473 for the second division will take place on Tuesday April 3rd 16:05 UTC. As usual, first division participants can take part out of competition.

I'm the problemsetter and the editorialist of this round. I'd like to thank mahmoudbadawy for creating the testdata and testing the round, FalseMirror, Livace, demon1999, and vintage_Vlad_Makeev for testing the round, KAN and Ahmad_Elsagheer for giving their great opinions and thoughts and helping in round preparation, arsor for helping translate the problems, and 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-1000-1250-1750-2000-2500.

Good luck and Have fun!

UPD congratulations to the winners!

Div.1:-

Div.2:-

• +367

 » 4 years ago, # | ← Rev. 3 →   +34 "And yes it's rated (I hope)."Scoring distribution is posted and it is 2 days before the contests even begins.Contestant : Doesn't that sound like another April fool contest ?Setter : No, It isn't(I hope)
•  » » 4 years ago, # ^ |   +24 Yeah I really hope!
•  » » 4 years ago, # ^ |   0 great......
 » 4 years ago, # | ← Rev. 2 →   -26 "And yes it's rated (I hope)."how it's calculated that the contest will either be rated or not ,I really wanna know:D
•  » » 4 years ago, # ^ |   +49 CF's servers U_U
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -16 ,so what's the criteria for a contest to be rated set .... Is it the difficulty level or the implementation required to solve it
•  » » » » 4 years ago, # ^ |   +6 Pretty much every regular round is rated by default, but sometimes the servers are having a bad day and it becomes too unfair of a contest for it to be rated.
•  » » » » » 4 years ago, # ^ |   -6 What do you mean by bad day??
•  » » » » » » 4 years ago, # ^ |   +10 I just mean that sometimes the servers can get too clogged with submissions or can shut down on their side temporarily
•  » » » 4 years ago, # ^ |   0 how are you theodor?
•  » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   -7 I missed rated contests...hope it will be rated
•  » » 4 years ago, # ^ |   -24 "hope it will be rated" — M_H_H_7 April 2, 2018
•  » » » 4 years ago, # ^ |   0 maybe i dont have good english, but at least i respect others(unlike you ;) )
 » 4 years ago, # |   +11 finally ,after 7 days from the last rated contest ,we have CF rated Round :) great :|
 » 4 years ago, # |   -23 Good Luck , wish less implementation problems :D
 » 4 years ago, # |   0
 » 4 years ago, # |   -8 Why was the contest moved? (maybe because of mathmash)
 » 4 years ago, # |   +7 Woooow , Egyptian problem setters , I really proud of you
•  » » 4 years ago, # ^ |   +2 It is not the first time dude. we are everywhere ^^
•  » » » 4 years ago, # ^ |   +6 Yeah i know ^_^
•  » » » » 4 years ago, # ^ |   -9 elmasry tol 3omro ma3rof bgbroto
 » 4 years ago, # |   -28 I Hope It Will Be Rated...........
 » 4 years ago, # |   -7 Short statement. I hope.
 » 4 years ago, # |   0 Good job !!! I will have two competitons in the one day. Enjoy it !!!!
 » 4 years ago, # |   +5 Wait A and B solution on this channel https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg/featured
 » 4 years ago, # |   +20 waiting for a syrian contest Daniar :P
•  » » 4 years ago, # ^ |   +15 next week
 » 4 years ago, # | ← Rev. 2 →   +8 Yeah! 5 rated contest in the week ! High ratings to everybody! What a sad story...)
•  » » 4 years ago, # ^ |   0 I thought your handle is, "I am asshole".
 » 4 years ago, # |   0 i hope problems will not test our english and interpretation skills rather it will be short and simple.
 » 4 years ago, # |   -7 Now,Is it confirm whether this contest will be rated or not??? And Can we see 7000 participation 3 minutes before the registration.
 » 4 years ago, # | ← Rev. 2 →   -10 Good questions
 » 4 years ago, # |   +3 Interesting problem titles
 » 4 years ago, # |   0 Is anyone else seeing limited submission languages? I can't submit in C++
 » 4 years ago, # | ← Rev. 2 →   0 i can't be able to submit D code. Please look into this. It took me 20 -25 minutes just to submit solution of D again and again.The page seems to get stuck at one point meanwhile i submitted A which was accepted immediately.
 » 4 years ago, # | ← Rev. 2 →   +1 For which cases answer i -1 in C? Very good problems by the way.
•  » » 4 years ago, # ^ |   +16 N < 6
 » 4 years ago, # |   +18 how to solve F?
 » 4 years ago, # | ← Rev. 2 →   +4 I only needed one extra second to submit D, I hope my code wont pass :(
 » 4 years ago, # |   +12 Just look at the system testing . lightning speed...
 » 4 years ago, # |   0 if(n<=5){ puts("-1"); rep(i,n-1) printf("%d %d\n",i,i+1); } else{ rep(i,n-1) printf("%d %d\n",i,i+1); rep(i,n-1) printf("%d %d\n",1,i+1); }My C Code , What's wrong???
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 In the case of n>5, you just printed two different correct trees...
•  » » » 4 years ago, # ^ |   0 1 2 2 3 3 4 4 5 5 6 6 7 7 8What's wrong if I choose 2 5 7 or 2 5 8？
•  » » » » 4 years ago, # ^ |   0 ...find the minimum number of vertices that cover all the edges.You need to cover all the edges, not all the vertices. For example, if you choose 2 5 7, you will miss edge (3, 4).
•  » » » » » 4 years ago, # ^ |   0 .......I see... Thx!
•  » » 4 years ago, # ^ |   0 This formula is actually always work for the "rep(i,n-1) printf("%d %d\n",i,i+1);" type of graphs. You could easily check this.
•  » » 4 years ago, # ^ |   0 U have to read condition one more time =)
 » 4 years ago, # | ← Rev. 2 →   0 Why is this WA on test 2 in problem C ? 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 
•  » » 4 years ago, # ^ |   +1 The first tree is a correct case.oddCnt = 7 and evenCnt = 1, therefore the answer is 1, which is correct because you can choose the root vertex and all edges will be covered.
•  » » 4 years ago, # ^ |   +3 In the first case, the algorithm will give the correct result — 1
 » 4 years ago, # |   +36 Congratulations on beating the world record on systest start.
 » 4 years ago, # |   +13 It is so strange to see OEIS problem in E :(
•  » » 4 years ago, # ^ |   +3 Can you post the link?
•  » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 Unable to hack solution in the last 3 minutes the page kept loading endlessly :| PS: Internet was stable
 » 4 years ago, # |   +12 Problem F is this right? https://stackoverflow.com/questions/34136955/finding-the-no-of-subset-with-a-given-xor
•  » » 4 years ago, # ^ |   +9 Yes
 » 4 years ago, # |   +4 Fastest start of System Test ever :o
•  » » 4 years ago, # ^ |   0 Because the number of test cases is small, only around 25 — 50 lol
 » 4 years ago, # |   0 How to solve E?
•  » » 4 years ago, # ^ |   +9 You can unite in groups of 2 for price 1, then in groups of 4 for price 2 etc. This is for n that's power of two. For all other n for some steps you just don't unite last two groups. Straightforward code is O(logn).
•  » » 4 years ago, # ^ |   +21 Write brute force code(O(n^3)) to generate answer for n=2 to 20. Search sequence on OEIS. Profit!
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks! More problems using OEIS?
•  » » » » 4 years ago, # ^ |   0 Click on OEIS. Thanks to -Morass-! :)
•  » » » » » 4 years ago, # ^ |   0 Thank you very much!
•  » » » 4 years ago, # ^ |   0 Shit! I added a 0 (n = 1) in the start of the sequence, and couldn't find it on oeis. :/
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 I didn't get how did you obtain that formula from OEIS. I heard it for the first time here so I am very unfamiliar with it. Can you explain a bit more? Thanks!
•  » » » 4 years ago, # ^ |   0 how do you get formula from oeis?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 someone, please answer to this.
•  » » » 4 years ago, # ^ |   0 What is the O(n^3) solution. I'm not able to get the O(n^3) itself.
•  » » 4 years ago, # ^ |   +24 If you don't want to use OEIS, then here is a solution -Lets assume you have a MST for a complete graph with n - 1 nodes. Main observation is when you add the node with number n - 1 to the graph (resulting in graph with n nodes), the new edges will not replace any edge of the previous MST. So, you can just choose the minimum cost edge from this new node. So we have . And is just the maximum power of 2 that devides n. So our final answer is sum of maximum power of 2 that divides i, for i ranging from 1 to n - 1. Now all you need to do is, insted of counting them one by one, count how many of them will have 2x as the maximum divisor. Then just add 2x × count to answer.As = count of numbers in [1, n] that are divisible by 2x. So number that are divisible by atmost 2x but not 2x + 1, that is just (assume all divisions are integer division).So the answer is .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Another less mathsy approach is to use Kruskal. Subsequently add edges from the smallest to the largest. Edges with weight 1, will be (0, 1), (2, 3), (4, 5), ... We can calculate the number of super-node being n:=(n+1)//2. Now all edges with weight 1 cannot be added to the graph without disturbing the tree, so consider edges with weight 2, which will be (0, 2), (4, 6), (8, 10), ... We are then left with n:=(n+1)//2. At this point, edges with weight 2 and 3 cannot be added, this can be proved (but I didn't). I came up with the idea that only edges with weight 1, 2, 4, 8, ... would present in the tree, and counted at each step how many edges I added and multiplied by the weight.Just a quick observation and a bit intuition :1
•  » » 4 years ago, # ^ |   0 cal(int n){ if n == 1 return 0; return n / 2 + 2 * cal (n — n / 2) ; }got AC with few line of codes :))
 » 4 years ago, # |   0 Can Mike or Kan, or someone, please explain why am I getting compile error on my latest submission? It works fine on my PC, and I can't figure out why.
•  » » 4 years ago, # ^ |   +8 You missed #include .
•  » » » 4 years ago, # ^ |   +4 wow!..how does that magically compile on my PC?
•  » » » » 4 years ago, # ^ |   +3 Which compiler did you use?
 » 4 years ago, # |   0 how to solve C?
•  » » 4 years ago, # ^ |   +7 Painting says that for n <= 5 there no incorrect trees. For n >= 6:First tree -1 21 31 44 54 6...4 nThere incorrect algo gives 3. Correct answer is 2.Second tree -1 21 31 4... 1 n There both algos give 1.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 n = 51-2-3-4-5incorrect tree, isnt it?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 It's correct tree, because there evenCount = 2, oddCount = 3. And answer is 2.
•  » » » » » 4 years ago, # ^ |   0 oh, you are right. thx
•  » » » 4 years ago, # ^ |   0 For n = 5 : incorrect tree : 1 — 21 — 33 — 43 — 5 which gives ans = 2 . But correct tree : 1 — 21 — 31 — 41 — 5 which gives ans = 1 . so why n = 5 gives -1 for incorrect tree ???
•  » » 4 years ago, # ^ |   0 "scratch your head" a little bit more
 » 4 years ago, # |   0
 » 4 years ago, # |   0 How to solve problem D?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +6 Iterate over each number, saving its prime divisors in a visit array, once you find a number that has a divisor that came before keep increasing that number by 1 and try again.Once you found a good number for that element, the rest of the array(to the right) can be any number you want, let x be the number of elements left in the array, start from 2 with the visit array you have, find x good numbers and put them in the elements left.If you didn't find any bad one, just do nothing.
•  » » » 4 years ago, # ^ |   0 This is so cool! Thanks a lot
•  » » » 4 years ago, # ^ |   0 That's very similar to my approach, except that I use Python. Is it not possible to solve it in Python? (got TLE #6)
•  » » 4 years ago, # ^ |   +1 Generate primes up to x (I used x = 10^7); If nums a[1]..a[i — 1] are coprimes then a[1]..a[i] are coprimes if and only if all primes divisors of a[i] doesn't exist in set of prime divisors for a[1]..a[i — 1]. Use set of prime divisors. For current index i you can factorize a[i]. While a[i] cannot be used, you can increase a[i]. If there was increase of a[i], then a[i + 1]..a[n] can be initialize with first primes that don't exist in set. Example:5 2 4 1 5 10a[1] = 2. Set is { 2 } a[2] = 4. 4 = 2^2. You need to increase. a[2] = 5. Set is { 2, 5 }There was increase. So a[3] = 3, a[4] = 7, a[5] = 11.And answer is 2 5 3 7 11.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes thank you. I was thinking something like this. But what I couldn't think that how to find if a number has a factor before. You and wewark have used a similar approach for that. Got to learn something new thanks! :)
 » 4 years ago, # |   0 i couldn't type as fast as um_nik solves & types the problems
 » 4 years ago, # |   0 Editorial is actually unavailable.
•  » » 4 years ago, # ^ |   +3 Please wait until system testing ends.
•  » » » 4 years ago, # ^ |   0 Ended.
•  » » » » 4 years ago, # ^ |   0 It opens for me and some other people I've asked. Doesn't it open for you?
 » 4 years ago, # |   0 That moment when you try to solve E with MST using DSU and realized that its just OEIS .
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 waste of time ..... U will definitely get TLE if u will try it by using MST ... as given complete graph So, max possible edges 10^12(10^12 − 1)/2
•  » » » 4 years ago, # ^ |   0 Yeah i know but i have 90 minute remained so i tried to try my luck
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 No OEIS needed. 36926019
•  » » » 4 years ago, # ^ |   0 thanks for sharing ur solution :)
•  » » » 4 years ago, # ^ |   0 Can you explain your approach for this solution?
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   0 Connect each number only with the next one. The cost is 1 per each 2 numbers as they only differ in the first bit. Now we have to connect each 2 numbers with the next 2 numbers, they'll cost 2 per 4 numbers(2 connected to 2), as you'll definitely find in each group a number that differs only at the second bit with a number from the second group, and so on with all the bits.It gets a bit tricky when n is not a power of 2, because then, some groups will need to be connected to their "next"s, while others won't.
•  » » » » » 4 years ago, # ^ |   0 Thanks mate!
•  » » 4 years ago, # ^ |   +9 Don't worry, everybody who use OEIS write MST too
 » 4 years ago, # | ← Rev. 2 →   0 Why This Code for C Fails Code Please Tell me.Edit: I was doing: Case 1st: Connect 1 with 2 from n-2 elements and connect 2 with n-1 and n. for case 2nd: Create a Binary tree.
 » 4 years ago, # |   +6 CF predictor showing 'Application Error' :(
 » 4 years ago, # |   0 Can this be hacked?I feel it should be `if(taken and *primes.begin()
 » 4 years ago, # | ← Rev. 2 →   +3 Why doesn't Rating Predictor show Round 473 ? This is updated almost everytime after the contest.
•  » » 4 years ago, # ^ |   0 Works perfectly fine for me.
 » 4 years ago, # |   +13 Is there somebody, who mixed up k with m in problem B and got billions wa(((
•  » » 4 years ago, # ^ |   0 Not billions, but yeah got one
•  » » 4 years ago, # ^ |   0 Got one too!!
 » 4 years ago, # | ← Rev. 2 →   +4 Similar problem to problem E:http://codeforces.com/problemset/problem/888/G (Boruvka's algorithm for the MST).
 » 4 years ago, # |   +10 Became Expert!!! :P
 » 4 years ago, # |   0 What's the intuition behind C's solution?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 In bipartite graph, the number of minimum-vertex-cover is equal to the number of maximum-matching. A tree is a bipartite graph, when you regard nodes with depth of different parity as different bipartite parts.Therefore, the answer by "wrong algorithm" is true if and only if the calculated minimum is equal to the number of maximum-matching, and is false otherwise.To explicitly find a case where the calculated minimum is not equal to the number of maximun-matching, you can refer to the Hall's Theorm Hall's Theorm
 » 4 years ago, # |   +5 Hi, I'm a contest contestant: Codeforces Round # 473 (Div. 2)there was a code that was not tested and was sent during the contest; is the problem D, since the problem I sent remained in Pretests passed, but when I sent it after the answer the contest answer gave me correct answerThis is my code during the contest: http://codeforces.com/contest/959/submission/36929338This is my code after the contest: http://codeforces.com/contest/959/submission/36933508both are the same code
 » 4 years ago, # |   +3 Sorry for my poor English! In problem 959C - Mahmoud and Ehab and the wrong algorithm,anyone thinked n = 8 is the smallest case which exist a tree which Mahmoud's algorithm is wrong. They think that theorem might be because the second sample test.In fact, n = 6 is smallest case. Therefore,n = 7 or n = 6 is test hack for C.
 » 4 years ago, # |   0 In problem D, why I change the position of two sentences, the judge results differ?the first one got AC 36938566and the second one got Runtime error 36938574Can someone help me?
 » 4 years ago, # |   0 Can Anyone Help me in E ? The editorial language is too much technical for me to understand it. I got the little approach. But i got doubts in it....
 » 4 years ago, # | ← Rev. 2 →   0 Update: I got it......Problem D;input3 3 18 2judge Output : 3 19 2.My output: 3 19 5.why My output is wrong????
•  » » 4 years ago, # ^ |   0 Because you wan to find the lexicographically minimal array. 2 is smaller than 5, which means your solution is not minimal. Think of it as inserting the smallest prime number that is not yet used by the previous elements.
 » 4 years ago, # |   0 (╯°□°）╯︵ ┻━┻, when your friends up 1000 points in cf predictor(XD) and u.u no rated for you