### ssense's blog

By ssense, history, 7 months ago,

This is the editorial for the Unofficial Div4 Round#1 created by I_Love_YrNameCouldBeHere 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

• +10

 » 7 months ago, # |   -17 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.
•  » » 7 months ago, # ^ |   +10 I can give a counter example2 2 2 5 27By your algorithm this should print YES however the answer is NO.Look like the tests weren't strong enough.
•  » » » 7 months ago, # ^ |   -10 I'm sorry for a minor mistake in my previous comment, actually, I counted all the numbers not divisible by min. https://codeforces.com/gym/295323/submission/93082233
 » 7 months ago, # |   0 What will be the rating of problem D and E on Codeforces?
•  » » 7 months ago, # ^ |   0 Around 1400 I guess.
•  » » » 7 months ago, # ^ |   0 Thanks,So problem D and E are around 1300-1400 on codeforces
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 7 months ago, # ^ |   0 ok thanks
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 I guess, D — 1400, E — 1300.
 » 7 months ago, # |   0 I think D should've been E and vice versa. thanks for the good problemset :)
 » 7 months ago, # |   0 Clean solution for problem E using pbds SOLUTION#include #include #include using namespace __gnu_pbds; using namespace std; #define int long long template using oset =tree, rb_tree_tag,tree_order_statistics_node_update> ; signed main() { int n,m ; cin >> n >> m ; vectora(n),b(m),p(n+1); for(int &x:a) cin >> x ; for(int &x:b) cin >> x ; oset>s ; for(int i=1;i
 » 7 months ago, # |   0 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.
•  » » 7 months ago, # ^ |   0 "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
 » 7 months ago, # |   -8 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$.
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   -8 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.
•  » » » » 7 months ago, # ^ |   0 I have now corrected it to say coprime number, sorry for the confusion.
•  » » » » » 7 months ago, # ^ |   0 I have to say also thank you for the nice contest, especially problem D.
•  » » » » 7 months ago, # ^ |   0 Yeah, many people misunderstand that part.
•  » » 7 months ago, # ^ |   0 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
 » 7 months ago, # |   +1 Very nice contest ! Good job guys !
 » 6 months ago, # |   0 Will there be more such Rounds? It's good for Beginners to Practice.
•  » » 6 months ago, # ^ |   0 We are planning on publishing more :)
 » 5 months ago, # |   0 Thank you so much. I really liked this contest. Hoping for more contests like this :)