This is the editorial for the Unofficial Div4 Round#1 created by SlavicG and mesanu.
Previously you could only virtually participate, now the contest is open for practice!
Invitation link for the contest: https://codeforces.net/contestInvitation/d477e058f265a72092af5c11074234d720a0fb5f
PROBLEM A:
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.
Idea: mesanu
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:
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:
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: mesanu
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:
Idea: mesanu
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.
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.
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
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$$$.
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.
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.
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 :)
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.