mohammedehab2002's blog

By mohammedehab2002, 8 months 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, 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:-

  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  

»
8 months 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)

»
8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    CF's servers U_U

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it -6 Vote: I do not like it

          What do you mean by bad day??

          • »
            »
            »
            »
            »
            »
            8 months 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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how are you theodor?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I missed rated contests...

hope it will be rated

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

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

    • »
      »
      »
      8 months 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 ;) )

»
8 months 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 :|

»
8 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Good Luck , wish less implementation problems :D

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Woooow , Egyptian problem setters , I really proud of you

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Short statement. I hope.

»
8 months 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 !!!!

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

waiting for a syrian contest daniar :P

»
8 months 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...)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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.

»
8 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Good questions

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting problem titles

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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.

»
8 months 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.

»
8 months ago, # |
  Vote: I like it +18 Vote: I do not like it

how to solve F?

»
8 months 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 :(

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
8 months 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???

  • »
    »
    8 months 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...

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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).

  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U have to read condition one more time =)

»
8 months 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
  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Congratulations on beating the world record on systest start.

»
8 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
8 months 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

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Fastest start of System Test ever :o

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    8 months 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).

  • »
    »
    8 months 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!
  • »
    »
    8 months 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 .

    • »
      »
      »
      8 months 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

  • »
    »
    8 months 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 :))

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      n = 5

      1-2-3-4-5

      incorrect tree, isnt it?

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "scratch your head" a little bit more

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is so cool! Thanks a lot

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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! :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial is actually unavailable.

»
8 months 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 .

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    No OEIS needed. 36926019

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for sharing ur solution :)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your approach for this solution?

      • »
        »
        »
        »
        8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

CF predictor showing 'Application Error' :(

»
8 months 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.

»
8 months 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.

»
8 months 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(((

»
8 months 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).

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Became Expert!!! :P

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the intuition behind C's solution?

  • »
    »
    8 months 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

»
8 months 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

»
8 months 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.

»
8 months 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?

»
8 months 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....

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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????

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
8 months 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