Over the past year, I've been reading a lot of papers on chatbots - from ELIZA to neural conversational models, and everything in between. I'm writing a review paper that summarizes the recent developments in the chatbot space, and I want to make sure I'm not missing any of the important papers. What papers do you think I must cover?
In the jth round, the ith element of array assumes the value:
A_i + i + (j-1) - NifN-i < j
A_i + i + (j-1) otherwise.
Do the math, folks!
These values can be calculated as you loop through the array from the last element to the first element. Also, a set can be used to get the greatest/least element in logarithmic time. Notice that you need not keep track of the (j-1) in the above expression. Just add (j-1) to the answer when printing it.
Indian National Olympiad in Informatics (INOI) is round 2 out of 3 (i.e. intermediate) for selection into Indian IOI team. See the discussion replies for solution one hint at a time (credits: Arpan Bhattacharya)
It's pretty easy to get what the problem is asking for, so I'll not waste your time trying to break it down! So, straight to the solution, one hint at a time...
Hint 0000: There's a really elegant dynamic programming solution to this problem. Try coming up with a DP state.
Hint 0001: How about DP(left, right) = the maximum sum among all well-bracketed subsequences, of the sequence starting at the index left and ending at the index right?
Hint 0010: Among all the subsequences in the Values array, such that the corresponding bracket subsequence in the B Array is a well-bracketed sequence, you need to find the maximum sum. So, the answer = DP(1, N).
Hint 0011: In every well-bracketed sequence, each pair of matched brackets 'hugs' another well-bracketed sequence.
Hint 0100: So basically, every well-bracketed sequence is a sequence of one or more matched bracket pairs, of nesting depth one, with (possible empty) well-bracketed mini-sequences between them.
Hint 0101: Doesn't that remind you of good old recursion? Read the next five hints for a piecewise recursive function description.