Блог пользователя mohammedehab2002

Автор mohammedehab2002, 7 лет назад, По-английски

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
  • Проголосовать: нравится
  • +367
  • Проголосовать: не нравится

»
7 лет назад, # |
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)

»
7 лет назад, # |
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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    CF's servers U_U

    • »
      »
      »
      7 лет назад, # ^ |
      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится -6 Проголосовать: не нравится

          What do you mean by bad day??

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

I missed rated contests...

hope it will be rated

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Good Luck , wish less implementation problems :D

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Woooow , Egyptian problem setters , I really proud of you

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

waiting for a syrian contest Daniar :P

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Good questions

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Interesting problem titles

»
7 лет назад, # |
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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

how to solve F?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 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???

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 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).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    U have to read condition one more time =)

»
7 лет назад, # |
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
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Congratulations on beating the world record on systest start.

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Fastest start of System Test ever :o

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится
    1. Write brute force code(O(n^3)) to generate answer for n=2 to 20.
    2. Search sequence on OEIS.
    3. Profit!
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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 .

    • »
      »
      »
      7 лет назад, # ^ |
      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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    got AC with few line of codes :))

»
7 лет назад, # |
  Проголосовать: нравится 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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve C?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem D?

  • »
    »
    7 лет назад, # ^ |
    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    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.

    • »
      »
      »
      7 лет назад, # ^ |
      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! :)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Editorial is actually unavailable.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    No OEIS needed. 36926019

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain your approach for this solution?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

CF predictor showing 'Application Error' :(

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can this be hacked?

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Became Expert!!! :P

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the intuition behind C's solution?

  • »
    »
    7 лет назад, # ^ |
    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

»
7 лет назад, # |
  Проголосовать: нравится +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 answer

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

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

both are the same code

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 лет назад, # |
  Проголосовать: нравится 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....

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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