I recently encountered a problem in a contest.It was very similar to edit distance.Only difference was that we are also given cost of each of the operation insert,delete and replace .We have to find minimum cost to convert string1 to string2. This problem is fairly standard and can be solved using dynamic programming in O(n^2) time. The problem statement for Edit Distance can be found here: Problem

But the constraints given in the contest were n<=100000 so larger test cases won't pass in O(n^2). So is there any way to bring the time complexity of the solution?

Hey Codeforces Community,

First of all I beg your pardon as I am not asking something very informative here.

I want to ask why rating of some of the Div2 users(including me) have not changed after the TechnoCup (2017).These is a discussion regarding this here and MikeMirzayanov has replied to it positively : Contest Discussion .

Some DIv2 users have their rating updated but some have not received any change. Is it because I registered during the late registration or some other reason?

Hi everyone,

I recently gave Topcoder SRM(698) for the first time. After solving the problems I wanted to up solve but I could not find the editorials for the contest. I googled it and most of them have directed me to this Link .

But I could not find editorial for the recent contest there and there has no update on this link for the past 4-5 days. So does it take them time to update on this link or I am looking at the wrong place.If so where should I look?

Please help!! Thanks in advance.

Faced this problem in practice area : Problem

It seems like a general DP problem but I could not figure out its solution.I also tried finding its editorial but there seem to be no resource available for this problem.I tried seeing solutions of others but they were impossible to understand until I know what does DP array in their solution represent.

So please help me.Any small hint will also do fine. Thanks in advance. :)

Hello all,

I was doing DP problems in Problemset section of Codeforces, when I came across this question involving prefix function :

Problem

I could do this question in O(n^2) using simple search and KMP but as evident constraints are such that the problem needs to be solved in O(n). I went to see the editorial for the problem but I could not get the approach.

Editorial

I know the principle of prefix function and I know how it is calculated but the approach in the editorial just went above my head. So please elaborate the editorial approach. Any new solution is also welcomed.

Thanks in advance.

Hello All,

I came across this interesting question in which there is an array consisting of n numbers with each number lying between 1 to m. Now it is asked to find the minimum number of swaps necessary to reformat the array such that the array elements with same value come together.

Note: Here Here swap means exchanging position of two adjacent numbers.

Example: If N=4 && M=2 && A[4]=1 2 1 2 => Ans=1

If N=6 && M=4 && A[6]=2 1 4 3 1 2 => Ans=6

Constraints: 1<=N<=10^5 && 1<=M<=16

I have been able to find that this question can be solved using DP+bitmasking but I am facing difficulty in forming the DP structure. So if anybody can help,it will be really grateful.

Thanks

Hello all,

This is my first blog entry on Codeforces. So please forgive me if I am not following any regulation. I recently came across a question.Its statement goes like this:

Given an array A1,A2...AN. We are asked to count the number of contiguous subarrays Ai,Ai+1...Aj such that 1≤i≤j≤N and the largest element of that subarray occurs only once in that subarray.

For example: If N=3 A[3]={1 2 3} => Ans=6 || If N=4 A[4]={2 2 1 2} => Ans=6

Constraint: 1<=N<=10^5 and 1<=A[i]<=10^5

I have the Naive approach which works in O(n^2) but as evident from constraints it would give TLE. So please help to optimize the solution. Thanks.