ssense's blog

By ssense, history, 6 weeks ago, In English

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

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

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Around 1400 I guess.

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

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

      • »
        »
        »
        »
        6 weeks 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.

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

    I guess, D — 1400, E — 1300.

»
6 weeks 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 :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Clean solution for problem E using pbds

SOLUTION
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to understand C? I don't understand why we iterate from 2 to n (is it 1 based indexing?) and why do we do we take minimum? because for any bus position we are at, it'll cost us abs(i — j) i being the starting pos and j where we stop. Also, why do we add dp[j] with the absolute difference? I'm not good at dp so sorry for asking such a vague question.

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

    "why do we add dp[j] with the absolute difference"

    This is because the absolute difference between both of them is max(i,j)-min(i,j) you can find max and min of both and do it also,

    We take minimum because the question tells us to find minimum number of bus stops through which we have to go to.

    You can refer to my submission(I use Java) https://codeforces.com/gym/295323/submission/93069356

»
6 weeks 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$$$.

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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.

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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.

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

        Yeah, many people misunderstand that part.

  • »
    »
    6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Very nice contest ! Good job guys !

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

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

    We are planning on publishing more :)