altruist's blog

By altruist, history, 4 weeks ago, translation, In English,

I'm extremely sorry for late publication.

Tutorial is loading...

Complexity: O(1).
Author of the idea: Vladik.
Worked on the problem: Vladik.

Tutorial is loading...

Complexity: O(n2).
Author of the idea: MikeMirzayanov.
Worked on the problem: fcspartakm.

Tutorial is loading...

Complexity: O(n3 * m).
Author of the idea: altruist.
Worked on the problem: Vladik.

Tutorial is loading...

Complexity: O(n).
Author of the idea: altruist.
Worked on the problem: altruist.

Tutorial is loading...

Complexity: O(n).
Author of the idea: MikeMirzayanov.
Worked on the problem: altruist.

Tutorial is loading...

Complexity: O(d * (N * M + K)), where d — alphabet power.
Author of the idea: Vladik.
Worked on the problem: Vladik.

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide more explanation about solving Div-2 E?

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem C can be done in O(N*M) using dynamic programming.

http://codeforces.com/contest/761/submission/24322743

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain me DP approach of problem C ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    A simpler approach for problem C would be to store the least index for each type (special,alpha,numeric) in each string if exists. you will have a matrix A[n][3]. now you need to find three indexes i,j,k such that A[i][0] + A[j][1] + A[k][2] is minimum. now simply use three nested for loops one inside another and check for the minimum while ensuring i != j != k, which takes O(N*M + N^3) time. Further optimized solution would be to pick the first minimum, second minimum, third minimum from each column and use the three for loops as mentioned above which will reduce the run time to O(N*M + 3^3) = O(N*M).

    Hope this helped you, Link to my code

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me why is [l - ai;r - ai] in problem D ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's interval for Ci, not for Bi, fixed now, thank you.