06.07.2021
Today was Day 3 of Umnik’s intensive. I solved 4 tasks on contest — A, F, I, N. And 1 task was upsolved — O.
I rate myself low today as I were not efficient. In the first part of contest I missed 2 easy tasks — N and F. F was very easy but I was afraid of formula in this problem.
In every step you should find and delete first i with d[i] < k and then recalculate this d[i]. But if you look calmly at this equation, you will see, that you can iterate through i and recalculate this equation step by step in O(n).
Problem N also seemed to be difficult because you have 10⁵ restrictions of this type:
But, thinking for a couple of minutes you can understand, that operation & is very useful: you get 1 only in case of all arguments being equal to 1. This is the only thing you should know to solve this problem. O(n*30) time. Easy.
Conclusion. IF YOU SEE OPERATION & IN PROBLEM — IT CAN BE VERY EASY, AS & HAS VERY CONVENIENT PROPERTY
Task A was solved at 5 minutes before the end of the contest. But I made a submission at 1:15 from the start. I got WA 9. The idea was good, but is should be improved. The task is: you have function f[X] = {d1, d2, …, dk} where di — divisors of X. If you apply f to vector of numbers, it will apply it for every number. You should apply this operation k ≤ 10¹⁸ times. What are first 10⁵ elements of resulting sequence?
The case X = 1 is trivial. Result is always 1. Case when X is prime also trivial. The result is always 1, 1, …, 1, X. But when X is not prime you can try to apply it straightforwardly. So let’s emulate this operation straight by definition of f. For every divisor of f remember all its divisors to be able to do f. How many times will you do it? Let’s see the worst example. The worst is the slowest. It is, for exampe, X = 4.
k = 1: X = {1, 2, 4}
k = 2: X ={1, 1, 2, 1, 2, 4} + 3 to length
k = 3: X ={1, 1, 1, 2, 1, 1, 2, 1, 2, 4} + 4 to length
…
k = c: +=X = {1, 1, 1 …} + (c + 1) to length
So, when length of X will be 10⁵? Not more than through √(10⁵) iterations. Okay, but we need to make k iterations. In my first submission I forgot about it and just emulate f while length of X < 10⁵ and then print the result. Yes, I am not very clever. Next idea is to continue emulation while X consists of only prime numbers. I cannot make any estimation, but I believe it is also about O(√(10⁵)) iterations. So when I stopped with X only with primes and ones, I should look what is happening next. For example:
1 1 2 1 1 3 ->
1 1 1 2 1 1 1 3 -> position of 2 shifted by 1, 3 — by 2
1 1 1 1 2 1 1 1 1 3 -> position of 2 shifted by 2, 3 — by 4
… -> position of 2 shifted by k, 3 — by 2k, etc
So I just need to apply some shifts in O(10⁵) and that is all. AC (through a lot of stupid WAs)
Next 2 problems are DP. The first one is I. You have string s with size ≤ 2000, t with size ≤ 500, for every number of possible deletions of symbols of s find maximal number of non-overlapping substrings equal to t that can be found in s after deletion. Straightforward dp[i ≤ n][j ≤ m][number of deletions] is 2000*500*2000 with O(1) transitions is TL.
So I came up with dp[i≤n][j≤n] — minimal number of deletions, where j is number of letters of all current fixed occurrences of t. Transitions are also O(1).
The second DP problem O was upsolved. You have an array of integers. Divide them on any number of groups, in each group find max — min and sum it. Find the maximum sum. n ≤ 10⁶. So it should be about linear complexity. I came up with dp[n — prefix][2 — whether I chose maximum][2 — whether I chose minimum], so dp[0][0] — started new group, chose nothing, dp[1][1] I chose max and min, so I can start next group. Got AC. Cool DP. Non trivial.
