mohammedehab2002's blog

Codeforces round #473 (Div. 2)
By mohammedehab2002, 6 years ago, In English

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.

UPD : Editorial and bonus tasks.

Good luck and Have fun!

UPD congratulations to the winners!

Div.1:-

  1. Um_nik
  2. dotorya
  3. kmjp
  4. natsugiri
  5. Lewin

Div.2:-

  1. StopBullying
  2. taeyeon_ss
  3. Tsuare
  4. readers2
  5. ajinkya1p3
  • Vote: I like it
  • +367
  • Vote: I do not like it

Comments Comments (102)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

"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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    CF's servers U_U

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it -16 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like 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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          What do you mean by bad day??

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

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

            → Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I missed rated contests...

hope it will be rated

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Good Luck , wish less implementation problems :D

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Woooow , Egyptian problem setters , I really proud of you

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Wait A and B solution on this channel

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

→ Reply
»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

waiting for a syrian contest Daniar :P

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

Good questions

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting problem titles

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

how to solve F?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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???

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    In the case of n>5, you just printed two different correct trees...

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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？

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U have to read condition one more time =)

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In the first case, the algorithm will give the correct result — 1

    → Reply
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Congratulations on beating the world record on systest start.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Fastest start of System Test ever :o

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    1. Write brute force code(O(n^3)) to generate answer for n=2 to 20.
    2. Search sequence on OEIS.
    3. Profit!
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    got AC with few line of codes :))

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "scratch your head" a little bit more

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    1. Generate primes up to x (I used x = 10^7);
    2. 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].
    3. 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].
    4. 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 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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial is actually unavailable.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That moment when you try to solve E with MST using DSU and realized that its just OEIS .

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    No OEIS needed. 36926019

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your approach for this solution?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

CF predictor showing 'Application Error' :(

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can this be hacked?

I feel it should be if(taken and *primes.begin()<a[i]) but second condition might always be true.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Why doesn't Rating Predictor show Round 473 ?
This is updated almost everytime after the contest.

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Became Expert!!! :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intuition behind C's solution?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply