Tima's blog

Grand Prix of Bashkortostan
By Tima, history, 9 years ago, translation, In English

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

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can I find the problems?

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      тогда непонятно, что может быть в тесте 2. потому что по сути, из вашего доказательства следует, что наше решение должно быть правильным. Upd. я понял ошибку. спасибо за ответ

      → Reply