### Tima's blog

By Tima, history, 4 years ago, translation, , Let's discuss problems. How to solve F,J,M? Comments (10)
 » Who can explain problem D ? We solved it with binary_search, and for any step of binary_search we just check if it fits the given size or not, but we get Wrong Answer on test 2.
•  » » Binary search do not work in this problem. Say for 1,1,100,100 and w=103 you can choose l=2, but for l=3 it won't fit
•  » » » Thank a lot bro
 » Where can I find the problems?
•  » »
 » 4 years ago, # | ← Rev. 3 →   Div. 2. How to solve O, Q? We haven't understand problem statement of 'O' or it's test cases #1 and #2: input "1" and "2" haven't any neighbour digits. In 'Q' we substituted every longest possible jump from one dot (marsh in beginning of string) to another with a dot, and repeated until string become '.' (means 'OK'): while( s/^ \. .{0,$j} \././x ){$count ++} (.{min,max} is greedy and tries to match as much as possible any chars, and if following dot \. mismatch then .{min,max} backtracks until \. match, otherwise substitution fails), but had WA #2.
•  » » 4 years ago, # ^ | ← Rev. 2 →   O can be solved in O(1) by precalculations (only 512 answers) or O(n) finding solution directly. cycling from 1 to 2500000 and count how much acceptable integer founded. In C++ checking int would look like this: while(i!=0) { if(abs(i%10 - ((i/10)%10))!=1 && i/10!=0) return false; i/=10; } return true; Q is simple DP with checking for traps. dp[i] = min {dp[i-j], ..., dp[i-1]}+1
 » 4 years ago, # | ← Rev. 3 →   Can somebody explain me problem N(div2)? I would like to see a solution to this problem with proof? We computed the sum of an arithmetic progression and compared it with given x. And we considered that x must be not greater than sum. But we got WA2.
•  » » Notice that a + b and a - b have the same parity. Let S = 1 + 2 + .. + n, then x and S should give the same remainder mod 2. And x must be not greater that n, because |a - b| ≤ max(a, b) for any positive integers a, b.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   тогда непонятно, что может быть в тесте 2. потому что по сути, из вашего доказательства следует, что наше решение должно быть правильным. Upd. я понял ошибку. спасибо за ответ