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

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**

Idea: SlavicG

We find the day that Alin got the maximum amount of money by iterating through the array. If we have no day when the sum is positive, output 0.

Create a variable max, a variable sum and a variable pos. Set $$$max = 0$$$, $$$sum = 0$$$, $$$pos= 0$$$. Iterate through the array and add $$$arr[I]$$$ to $$$sum$$$. If $$$sum > max$$$ then save $$$i$$$ in the variable $$$pos = i$$$, and set max to the current $$$sum$$$. After you are done iterating print $$$pos$$$.

Link to solution: https://ideone.com/wZWJBW

PROBLEM B.

**Sanda's Homework**

Idea: ssense

The following greedy solutions always works: Sort the array $$$arr$$$, and then iterate until you find the minimum even number. If at the end of the loop it doesn’t exist then we have no answer and the solution is $$$-1$$$. Because we can not create an even number without any even digits. If there is an even element, save it’s index to a variable.Then print the array decreasing order (from $$$n$$$ to $$$1$$$)without the minimum even digit(the element at the saved index). After printing the array, print the minimum even digit so the number will be even.

Link to solution: https://ideone.com/fyDKc2

Problem C:

**Gicu's way Home**

Idea: SlavicG

This problem can be solved using dynamic programming.

The idea is for every element we try $$$k$$$ elements before it to see which one will give us the least cost.

Set an array $$$dp[n+1]$$$ and all the elements are equal to $$$10^9$$$ and set $$$dp[1]$$$ = 0; iterate through the array from $$$2$$$ to $$$n$$$ and for each $$$dp[i] = min(dp[i], dp[j]+abs(arr[i]-arr[j]))$$$ where $$$(i-k \leq j < i)$$$ and $$$j$$$ indicates one of the last $$$k$$$ bus stops. After you are done iterating print $$$dp[n+1]$$$.

Link to solution: https://ideone.com/zllXMy

Problem D:

**Game of GCD**

There are $$$2$$$ cases: If $$$k$$$ is even Bob makes the last move and he can always insert a coprime number with the gcd of the array, so after the insertion the $$$gcd$$$ of the array is $$$1$$$.

Idea: ssense

If $$$k$$$ is odd then Alice makes the last move. Alice wins if we can remove an element from the starting array such that the $$$gcd$$$ of $$$arr$$$ is bigger than 1. To find this out we can use the fundamental theory of arithmetic which states that any integer can be expressed as a product of prime numbers.For each element in the array we find what primes divide it by iterating through all the primes under 100(since it is given that $$$a_i \leq 100$$$). If any prime divides more than $$$n-1$$$ elements Alice wins since if Bob introduces a number Alice can delete that number in the next move. If no prime divides more than $$$n-1$$$ elements then bob wins.

Link to solution: https://ideone.com/nmWCRz

Idea: SlavicG

Another solution for when $$$k$$$ is odd is with prefix and suffix $$$gcd$$$. Iterrate over all $$$a_i$$$ from $$$1$$$ to $$$n$$$ and set $$$prefixgcd[i] = gcd(prefixgcd[i-1],prefixgcd[i])$$$. Then do the same for $$$suffixgcd$$$, but in reverse order: from $$$n$$$ to $$$1$$$ and set every element $$$suffixgcd[i] = gcd(suffixgcd[i+1],suffixgcd[i])$$$. Be careful at $$$prefixgcd_1$$$ and $$$suffixgcd_n$$$, You should just attribute them the value of the element at the index. After that we just iterate over all the array and check if $$$gcd(prefixgcd[i-1], suffixgcd_[i+1]) > 1$$$ ( again, be careful at $$$a_1$$$ and $$$a_n$$$). If this is true for at least one element then the answer is $$$"YES"$$$. But if we can not find such i then the answer is $$$"NO"$$$.

Link to solution: https://ideone.com/R5YyHC

Problem E:

**Strange Pool**

Idea: ssense

We create an array $$$sum$$$ where $$$sum[i]$$$ is the sum of all the elements in array $$$a$$$ with index smaller than one. Set $$$sum[0]$$$ = 0. We have $$$sum[i] = sum[i-1]+a[i-1]$$$. Now we can use binary search to find the smallest sum bigger than $$$b[i]$$$ then print the index where the smallest sum bigger than $$$b[i]$$$ is.

Link to solution: https://ideone.com/1DCK0b

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.

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.

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

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

Around 1400 I guess.

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

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.

ok thanks

I guess, D — 1400, E — 1300.

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

Clean solution for problem E using pbds

SOLUTIONCan 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.

"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

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 sayinsert the value $$$1$$$.because surely when you insert $$$1$$$ the gcd would definitely be $$$1$$$.But he said

a prime number, but didn't mentioned thatall prime numberswill satisfy the condition. But I also think that inserting 1 is a better idea.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 incorrectan 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.I have now corrected it to say coprime number, sorry for the confusion.

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

Yeah, many people misunderstand that part.

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

Very nice contest ! Good job guys !

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

We are planning on publishing more :)