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/jDkZE0
Problem D:
There are $$$2$$$ cases: If $$$k$$$ is even Bob makes the last move and he can always insert a prime number such that 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