How to solve problem A from Kickstart Round E ?

Here’s the link to the problem statement :

https://code.google.com/codejam/contest/12234486/dashboard#s=p0

My approach :

dp[i] = minimum number of operations to form the first i characters.

My Code:

For each position ‘i’ see if the substring formed by next ‘j’ (for all possible ‘j’) characters is present in the the first ‘i’ characters, and try to append it as many times as possbile, while updating the solution for the higher positions by taking minimum of existing solution and new solutions. Basically, build solutions for smaller lengths, and try to extend them to larger strings in every way possible.

If someone has solved this / can find out where my logic is going wrong, please help me. Thanks.

1 Like

I am not sure If I am getting correctly what you are saying… But I was also thinking in same way may be… And problem with this solution is… clipboard is playing good role here… I mean how can be you so sure to take greedy approach and override clipboard… Remember if something is already on clipboard can be used later… and copying on clipboard is also taking one step… So I think taking greedy approach for copying on clipboard would be wrong… because you may end up copying again and again… Think of an example with alternative repetitive substring like abcxydxyabcexydabcfxyabc… I hope I am making my point clear to indicate your mistake…

1 Like

If you can share your code it will be easier for us to try to break it. Also if you like, I can describe my approach which worked.

EDIT: I guess @vsp4 has found the flaw.

My approach uses dp[i][j][k], which represents the cost of building the string upto the first i characters such that after it is built, the substring S[j..k] is on the clipboard. Additionally there is a dp_{min}[i] which is also the cost of building the string upto the first i characters, but regardless of what ends up on the clipboard. Initially all values are set to +\infty.

If some substring S[j..i] is pasted to extend the string from S[1..j-1] to S[1..i], we can set dp[i][j][i] = dp[j-1][j][i] + 1. Here we face a problem, that at j-1 we could not have possibly known that some substring in S[1..j] will match with S[j..i]. To overcome this, some preprocessing can be done to find the first occurrence of each substring, and only bother about those. I used Z-algorithm on every substring S[i..N] : 1 \le i \le N to generate a table, and from that we can generate another table f where f[i][j] is the starting index of first occurrence of the substring S[i..j].

As I was saying, we can paste some substring S[j..i] to get S[1..i]. Then we find x = f[j][i], y=x+i-j, which are the bounds of the first occurrence of S[j..i]. We can now set dp[i][x][y] = dp[j-1][x][y] + 1.

Alternately, if S[i] is typed and appended to S[i-1], all dp[i][j][k] can be reduced if possible to dp[i-1][j][k]+1, since we add one character but don’t touch the clipboard.

Clearly, dp_{min}[i] = \min\{dp_{min}[i-1]+1, \min\{dp[i][j][k] \text{ for all } j,k \}\}

The last step is to iterate over all subarrays S[j..k] in S[1..i], and reduce each dp[i][j][k] to dp_{min}[i]+1 if they can be reduced, since we can always copy any substring in the current string to the clipboard after it is built.

In the end, dp_{min}[N] will be the answer.
The complexity is \mathcal{O}(|S|^3) for both the main algorithm and the preprocessing.
You can see my code for more details.

2 Likes

I’ll share my code. Yeah, It’d be nice if you could tell me your approach. Thanks.

He is right. Your solution assumes that clipboard would be empty if a new single character is added. However it can be beneficial to paste whats in clipboard again at some later time in just 1 move. Eg: aabaacaadaa -> 9. Your code outputs 11

3 Likes

Yeah, I got it now. Thanks

Why are we looking at only the first occurrence of a substring ? @meooow

Suppose we have a string S=“abcdefdef”, and we are at index 6 with S[6]=“f”. If we copy the substring S[4…6] = “def” to the clipboard, then we will get some cost for dp[6][4][6]. Now skip ahead to index 9. Here we can append S[7…9] = “def” to S[1…6] = “abcdef” to build the string. But at index 6, we didn’t know that S[7…9] will be the same as S[4…6], so we didn’t assign dp[6][7][9].

Now at this point we could do something like at each index assign the dp value for all future matching strings at once, but clearly that will be a hassle and will also increase the complexity. So instead I observed that since S[4…6] = S[7…9] = “def”, dp[6][4][6] and dp[6][7][9] will be the same, so why not just bother with the first occurrence only. I have chosen the first occurrence for convenience, actually you can choose any one occurrence to be sort of the representative of all occurences.