Problem A: https://codeforces.net/problemset/problem/954/A↵
↵
Let's iterate over all characters of the string from left to right (excluding last character). Suppose i is a position of the current element of the string. If si ≠ si + 1, increase answer by 1 and increase i by 2, else just increase i by ↵
1.↵
↵
Problem B: https://codeforces.net/contest/1095/problem/B↵
↵
It is easy to see that we always have to remove either minimum or maximum of the array. So we can sort the array and the answer will be min(an−1−a1,an−a2). We also can do it without sort because two minimal and two maximal elements of the array can be found in linear time.↵
↵
Problem C: https://codeforces.net/contest/961/problem/B↵
↵
Let's iterate over all i from 1 to n and if ti is equal to 1 then add ai to the some variable res and replace ai with 0. Then answer will be equal to , where can be easily calculated with prefix sums for each i.↵
↵
Problem D: https://codeforces.net/problemset/problem/225/B↵
↵
Firstly you should generate all k-bonacci numbers less than n. For k ≤ 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 109 are powers of two only (and 0). So you will have no more then 100 numbers.↵
↵
Then you should use greedy algo. You should substract from n maximal possible k-bonacci numbers. You should repeat this operation while n is not decomposed. And in the end you will have answer.↵
↵
Why all numbers will be different? One of possible proves:↵
↵
F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)↵
↵
F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)↵
↵
You can substract the 2nd equation from the 1st one and you will recieve F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), that equal to 2F(k, n - 1) ≥ F(k, n). This unequation also holds for n ≤ k.↵
↵
Suppose than greedy also constricted 2 equal numbers F(k, x) in decomposition. But then in virtue of unequation we should take number F(k, x + 1) insead these 2 numbers. Сontradiction.↵
↵
But you didn't need prove than greedy algo works, you might believe that it works:)
↵
Let's iterate over all characters of the string from left to right (excluding last character). Suppose i is a position of the current element of the string. If si ≠ si + 1, increase answer by 1 and increase i by 2, else just increase i by ↵
1.↵
↵
Problem B: https://codeforces.net/contest/1095/problem/B↵
↵
It is easy to see that we always have to remove either minimum or maximum of the array. So we can sort the array and the answer will be min(an−1−a1,an−a2). We also can do it without sort because two minimal and two maximal elements of the array can be found in linear time.↵
↵
Problem C: https://codeforces.net/contest/961/problem/B↵
↵
Let's iterate over all i from 1 to n and if ti is equal to 1 then add ai to the some variable res and replace ai with 0. Then answer will be equal to , where can be easily calculated with prefix sums for each i.↵
↵
Problem D: https://codeforces.net/problemset/problem/225/B↵
↵
Firstly you should generate all k-bonacci numbers less than n. For k ≤ 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 109 are powers of two only (and 0). So you will have no more then 100 numbers.↵
↵
Then you should use greedy algo. You should substract from n maximal possible k-bonacci numbers. You should repeat this operation while n is not decomposed. And in the end you will have answer.↵
↵
Why all numbers will be different? One of possible proves:↵
↵
F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)↵
↵
F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)↵
↵
You can substract the 2nd equation from the 1st one and you will recieve F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), that equal to 2F(k, n - 1) ≥ F(k, n). This unequation also holds for n ≤ k.↵
↵
Suppose than greedy also constricted 2 equal numbers F(k, x) in decomposition. But then in virtue of unequation we should take number F(k, x + 1) insead these 2 numbers. Сontradiction.↵
↵
But you didn't need prove than greedy algo works, you might believe that it works:)
