### Tima's blog

By Tima, history, 3 years ago, translation, ,

Let's discuss problems. How to solve F,J,M?

•
• +31
•

 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +3 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
•  » » » 3 years ago, # ^ |   0 Thank a lot bro
 » 3 years ago, # |   +5 Where can I find the problems?
•  » » 3 years ago, # ^ |   +3
 » 3 years ago, # | ← Rev. 3 →   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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
 » 3 years ago, # | ← Rev. 3 →   0 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.
•  » » 3 years ago, # ^ |   +6 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 тогда непонятно, что может быть в тесте 2. потому что по сути, из вашего доказательства следует, что наше решение должно быть правильным. Upd. я понял ошибку. спасибо за ответ