15.07.2021

Wrote 2 Educational contests Codeforces: one virtual and one online.

Problem D confused me. The task was to find the length of maximal subsequence with lcm ≤ m. I tried to think about different approaches. DP? I can’t come up with states. Factorization? No ideas how to fit it in TL. Much time spent. But stop, what if we count the longest subsequence for each lcm ≤ m? If we have some subsequence, what numbers can we put in order to not change the lcm? We can put x: lcm % x == 0. So if we have x, we can put it in x, 2*x, 3*x, … Wow, so easy. I even didn’t believe that it is all that I need. Wrote. WA. WTH? Yes, it is O(nlogn) according to harmonic series, but can I guarantee that all x are different (if they are all equal it can be O(n²))? No, so I need to map it. AC.

Conclusion: DON’T FORGET THAT SOMETIMES YOU NEED THE UNIQUENESS OF NUMBERS, BUT IT IS NOT GUARANTEED!

This task was easier than the previous one, but I didn’t solve it on contest. I tried some greedy ideas, but they didn’t worked. The task is to find lexicographically smallest string that is concatenation of given strings. The solution is to use comparator: a < b < = > a+b < b + a. This is transitive relation, so we can use it to sort it. That’s all!

Conclusion: THERE IS A TYPE OF TASKS WITH SOLUTION BASED ON SPECIAL COMPARATOR

Tasks A, B, C from ECR 111 got AC in 40 minutes. Well done. C was interesting. Used ideas of finding closest larger/smaller number with stack and fixing right bound of “good” subarray. Ideas came up into my mind quickly enough. Nice! May be it is a smell of a progress?

Read D, E. E is interesting, but D is submitted by more contestants. So let’s think about D. I’m too lazy here to describe my thoughts, especially since I did not manage to pass it. So I will leave chat with my teammate. In russian.