altruist's blog

By altruist, history, 4 years ago, translation,

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.

• +119

 » 4 years ago, # |   0 Can someone provide more explanation about solving Div-2 E?
•  » » 4 years ago, # ^ |   +11 i think this one clarify everything :)
 » 4 years ago, # |   +12 Problem C can be done in O(N*M) using dynamic programming.http://codeforces.com/contest/761/submission/24322743
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 can you please explain me your approach ? thanks in advance .
•  » » » 13 months ago, # ^ |   0 It's quite similar to this problem. At state i, you just want to know minimal cost to have 1 digit (or 1 lowercase or 1 special character) as well as minimal cost to have 2 (1 digit & 1 lowercase, 1 digit & 1 special character, 1 lowercase & 1 special character) and finally, minimal cost to have all of three characters. Because at the state i, you can't conclude anything, you have to store all of them to conduct the answer at final state.Check my solution. It's same ideal with Arkin, i think.
 » 4 years ago, # |   +1 Can anyone explain me DP approach of problem C ?
•  » » 4 years ago, # ^ |   +5 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 years ago, # ^ |   0 Got it Thanks
 » 4 years ago, # |   0 Can someone explain to me why is [l - ai;r - ai] in problem D ?
•  » » 4 years ago, # ^ |   0 It's interval for Ci, not for Bi, fixed now, thank you.
 » 3 years ago, # |   0 Im getting TLE for C. The authors solution is O(n^3 * m). I feel my solution is O(8 * n * m). What am i doing wrong. My dp code