### ssense's blog

By ssense, history, 6 weeks ago,

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

• +10

 » 6 weeks 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.
•  » » 6 weeks 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.
•  » » » 6 weeks 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
 » 6 weeks ago, # |   0 What will be the rating of problem D and E on Codeforces?
•  » » 6 weeks ago, # ^ |   0 Around 1400 I guess.
•  » » » 6 weeks ago, # ^ |   0 Thanks,So problem D and E are around 1300-1400 on codeforces
•  » » » » 6 weeks 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.
•  » » » » » 6 weeks ago, # ^ |   0 ok thanks
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I guess, D — 1400, E — 1300.
 » 6 weeks ago, # |   0 I think D should've been E and vice versa. thanks for the good problemset :)
 » 6 weeks 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
 » 6 weeks 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.
•  » » 6 weeks 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
 » 6 weeks 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$.
•  » » 6 weeks 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.
•  » » » 6 weeks 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.
•  » » » » 6 weeks ago, # ^ |   0 I have now corrected it to say coprime number, sorry for the confusion.
•  » » » » » 6 weeks ago, # ^ |   0 I have to say also thank you for the nice contest, especially problem D.
•  » » » » 6 weeks ago, # ^ |   0 Yeah, many people misunderstand that part.
•  » » 6 weeks 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
 » 6 weeks ago, # |   +1 Very nice contest ! Good job guys !
 » 10 days ago, # |   0 Will there be more such Rounds? It's good for Beginners to Practice.
•  » » 10 days ago, # ^ |   0 We are planning on publishing more :)