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
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. 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:
Idea: mesanu
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$$$.
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"$$$.
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
