mesanu's blog

By mesanu, history, 4 years ago, In English

This is the editorial for the Unofficial Div4 Round#1 created by SlavicG and mesanu.

Announcement

Previously you could only virtually participate, now the contest is open for practice!

Invitation link for the contest: https://codeforces.com/contestInvitation/d477e058f265a72092af5c11074234d720a0fb5f

PROBLEM A:

Alin and Money

PROBLEM B.

Sanda's Homework

Problem C:

Gicu's way Home

Problem D:

Game of GCD

Problem E:

Strange Pool
  • Vote: I like it
  • +10
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

In problem D, (if k is odd)I found out the minimum divisor(let's say min) (min>1) of the maximum number of the array then counted all the numbers divisible by min. If count is either 1 or n-1 then answer is YES otherwise NO.

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

    I can give a counter example

    2 2 2 5 27

    By your algorithm this should print YES however the answer is NO.

    Look like the tests weren't strong enough.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What will be the rating of problem D and E on Codeforces?

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

    Around 1400 I guess.

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

      Thanks,So problem D and E are around 1300-1400 on codeforces

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

        We thought that D and E would be around 1300-1400 on CF, however in official rounds the problem ratings are calculated based on the people that solved them and their ratings.

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

    I guess, D — 1400, E — 1300.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think D should've been E and vice versa. thanks for the good problemset :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Clean solution for problem E using pbds

SOLUTION
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Editorial of D:

I think you have made a mistake when you said he can always insert a prime number such that the gcd of the array is 1, this is actually not true because lets say your current array is $$$[10]$$$ inserting prime number $$$5$$$ would make the gcd $$$5$$$. I think it should be corrected to say insert the value $$$1$$$. because surely when you insert $$$1$$$ the gcd would definitely be $$$1$$$.

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

    But he said a prime number, but didn't mentioned that all prime numbers will satisfy the condition. But I also think that inserting 1 is a better idea.

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

      This is actually true ! but I wanted to correct the understanding that many people have which is a lot of people always think that the taking gcd with a prime number would yield $$$1$$$ which absolutely incorrect an example would be $$$gcd(7, 14) = 7$$$ or $$$gcd(5,5) = 5$$$. a lot of times people when they hear $$$gcd = 1$$$, they think prime numbers.

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

        I have now corrected it to say coprime number, sorry for the confusion.

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

          I have to say also thank you for the nice contest, especially problem D.

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

        Yeah, many people misunderstand that part.

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

    If the gcd of the array is x then Bob should insert any number coprime with x, doesn't matter if it is prime or not. I said he can insert a prime number because all primes are coprime with other primes. Also 1 works like sazid mentioned

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Very nice contest ! Good job guys !

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be more such Rounds? It's good for Beginners to Practice.

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

    We are planning on publishing more :)

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

nice problem D! i used seive for 100 nums in O(1) then i counted the number of ai divisible by a prime p for each prime then take the max count if >= n-1 then yes, else no and it worked.