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, neckbosov, Livace, demon1999, and gritukan 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**.

**UPD :** Editorial and bonus tasks.

Good luck and Have fun!

**UPD** congratulations to the winners!

Div.1:-

Div.2:-

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

Yeah I really hope!

great......

"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

CF's servers U_U

,so what's the criteria for a contest to be rated set .... Is it the difficulty level or the implementation required to solve it

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.

What do you mean by bad day??

I just mean that sometimes the servers can get too clogged with submissions or can shut down on their side temporarily

how are you theodor?

I missed rated contests...

hope it will be rated

"hope it will be rated" — M_H_H_7 April 2, 2018

maybe i dont have good english, but at least i respect others(unlike you ;) )

finally ,after 7 days from the last rated contest ,we have CF rated Round :) great :|

Good Luck , wish less implementation problems :D

Why was the contest moved? (maybe because of mathmash)

Woooow , Egyptian problem setters , I really proud of you

It is not the first time dude. we are everywhere ^^

Yeah i know ^_^

elmasry tol 3omro ma3rof bgbroto

I Hope It Will Be Rated...........

Short statement. I hope.

Good job !!! I will have two competitons in the one day. Enjoy it !!!!

Wait A and B solution on this channel

https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg/featured

waiting for a syrian contest daniar :P

next week

Yeah! 5 rated contest in the week ! High ratings to everybody! What a sad story...)

I thought your handle is, "I am asshole".

i hope problems will not test our english and interpretation skills rather it will be short and simple.

Now,Is it confirm whether this contest will be rated or not??? And Can we see 7000 participation 3 minutes before the registration.

Good questions

Interesting problem titles

Is anyone else seeing limited submission languages? I can't submit in C++

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.

For which cases answer i -1 in C? Very good problems by the way.

N < 6

how to solve F?

I only needed one extra second to submit D, I hope my code wont pass :(

Just look at the system testing . lightning speed...

My C Code , What's wrong???

In the case of

`n>5`

, you just printed two different correct trees...1 2 2 3 3 4 4 5 5 6 6 7 7 8

What's wrong if I choose 2 5 7 or 2 5 8？

`...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)........I see... Thx!

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.

U have to read condition one more time =)

Why is this WA on test 2 in problem C ?

The first tree is a correct case.

oddCnt= 7 andevenCnt= 1, therefore the answer is 1, which is correct because you can choose the root vertex and all edges will be covered.In the first case, the algorithm will give the correct result — 1

Congratulations on beating the world record on systest start.

It is so strange to see OEIS problem in E :(

Can you post the link?

Sure

Unable to hack solution in the last 3 minutes the page kept loading endlessly :| PS: Internet was stable

Problem F is this right? https://stackoverflow.com/questions/34136955/finding-the-no-of-subset-with-a-given-xor

Yes

Fastest start of System Test ever :o

Because the number of test cases is small, only around 25 — 50 lol

How to solve E?

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

Thanks! More problems using OEIS?

Click on OEIS. Thanks to -Morass-! :)

Thank you very much!

Shit! I added a 0 (n = 1) in the start of the sequence, and couldn't find it on oeis. :/

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!

how do you get formula from oeis?

someone, please answer to this.

What is the O(n^3) solution. I'm not able to get the O(n^3) itself.

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 numbern- 1 to the graph (resulting in graph withnnodes), 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 devidesn. So our final answer is sum of maximum power of 2 that dividesi, foriranging from 1 ton- 1. Now all you need to do is, insted of counting them one by one, count how many of them will have 2^{x}as the maximum divisor. Then just add 2^{x}×countto answer.As = count of numbers in [1,

n] that are divisible by 2^{x}. So number that are divisible by atmost 2^{x}but not 2^{x + 1}, that is just (assume all divisions are integer division).So the answer is .

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

cal(int n){ if n == 1 return 0; return n / 2 + 2 * cal (n — n / 2) ; }

got AC with few line of codes :))

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.

You missed

`#include <bitset>`

.wow!..how does that magically compile on my PC?

Which compiler did you use?

how to solve C?

Painting says that for n <= 5 there no incorrect trees. For n >= 6:

First tree -

1 2

1 3

1 4

4 5

4 6

...

4 n

There incorrect algo gives 3. Correct answer is 2.

Second tree -

1 2

1 3

1 4

... 1 n

There both algos give 1.

n = 5

1-2-3-4-5

incorrect tree, isnt it?

It's correct tree, because there evenCount = 2, oddCount = 3. And answer is 2.

oh, you are right. thx

For n = 5 :incorrect tree :1 — 2

1 — 3

3 — 4

3 — 5

which gives ans = 2 .

But correct tree :1 — 2

1 — 3

1 — 4

1 — 5

which gives ans = 1 .

so why n = 5 gives -1 for incorrect tree ???

"scratch your head" a little bit more

How to solve problem D?

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.

This is so cool! Thanks a lot

That's very similar to my approach, except that I use Python. Is it not possible to solve it in Python? (got TLE #6)

Example:

5 2 4 1 5 10

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

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

i couldn't type as fast as um_nik solves & types the problems

Editorial is actually unavailable.

Please wait until system testing ends.

Ended.

It opens for me and some other people I've asked. Doesn't it open for you?

That moment when you try to solve E with MST using DSU and realized that its just OEIS .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

Yeah i know but i have 90 minute remained so i tried to try my luck

No OEIS needed. 36926019

thanks for sharing ur solution :)

Can you explain your approach for this solution?

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.

Thanks mate!

Don't worry, everybody who use OEIS write MST too

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.

CF predictor showing 'Application Error' :(

Can this be hacked?

I feel it should be

`if(taken and *primes.begin()<a[i])`

but second condition might always be true.Why doesn't Rating Predictor show Round 473 ?

This is updated almost everytime after the contest.

Works perfectly fine for me.

Is there somebody, who mixed up k with m in problem B and got billions wa(((

Not billions, but yeah got one

Got one too!!

Similar problem to problem E:http://codeforces.com/problemset/problem/888/G (Boruvka's algorithm for the MST).

Became Expert!!! :P

What's the intuition behind C's solution?

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

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 answer

This is my code during the contest: http://codeforces.com/contest/959/submission/36929338

This is my code after the contest: http://codeforces.com/contest/959/submission/36933508

both are the same code

Sorry for my poor English! In problem 959C - Махмуд, Эхаб и неправильный алгоритм,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.

In problem D, why I change the position of two sentences, the judge results differ?

the first one got AC 36938566

and the second one got Runtime error 36938574

Can someone help me?

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

Update: I got it......

Problem D;

input

3 3 18 2

judge Output : 3 19 2.

My output: 3 19 5.

why My output is wrong????

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.

(╯°□°）╯︵ ┻━┻, when your friends up 1000 points in cf predictor(XD) and u.u no rated for you