Problem F is interesting because it need DP and Greedy at same time. Problem G is just brute force to build a prepared data table. So not very funny. Problem a little bit complex to implement. Nothing special for other problems.
G. Short Task
Solution
Build a prepared data table before handle any input. We calculate the sum of factor for all numbers between 1 to $10^7$. And scanning all numbers to get the minimum number of each query.
Code
F. Education
Looks like knapsack problem or DP problem. But if solve as knapsack problem or dp only. Then will get trouble on the remain money after upgrade position. So this problem also need greedy strategy. If need upgrade position, then upgrade as soon as possible. And then, it become a easy problem.
E. Permutation by Sum
Solution
Let's define $len=r-l+1$, which means the length between $l$ and $r$. The minimum sum can be constructed is $\sum_{i=1}^{len}i$. The maximum sum is $\sum_{i=n-len+1}^{n}i$. All the $s$ between min and max sum can be constructed.
We start from the minimum one. At beginning we put 1 to $len$ into $l$ to $r$.
Base on this one, we check the value one by one. For each value, we try to change it to the largest possible value.
After the change, if the sum still less than s. Then we update our result.
Otherwise this value is the last value who is needed to be changed. So change it to some sensible number. And after that, the sum $s$
Code
D. Corrupted Array
Solution
It's very clear that: $b_{n+1}$ is the sum of $a$. So $b_{n+1}$ must be the maximum value in $b$ or the second maximum value ($x$ take the maximum value). So just need try these two.
Code
Be careful on Arrays.sort() in Java. Refer to this page, should use Long rather than long in java.
C. A-B Palindrome
Solution
Match the palindrome first. And we can determine some of 0 and 1.
After that, the '?' is also match palindrome. Then we change ? to the one which is larger between $a$ and $b$.
Only thing need to be careful is: if the length is odd, then we need some special logic for it.
Code
B. Almost Rectangle
Solution
Find 2 pairs of x and y coordinates directly. If get same x/y from the two poinsts, then +1 for that directly. If it more than $n$ then change it to 0.
Code
A. Spy Detected!
Solution
Find the number that appears only once. Output index.
Code
