I did a check like this. Let lmax = 0. Now change lmax only if the given subsequence sum is greather than lmax so I guess it will also prefer the no bracket sequence. I got accepted for all test cases but I had not thought of this scenario. Also I was printing 0 for no correct bracket sequence too
I guess the solution to the first problem goes as follows :
For every employee, since he has only one manager, the maximum difference you get with that employee and the previous nodes of the tree is the maximum wealth of one of the managers of the branch and himself. The solution is to maximize this listā¦
I know, a bad way of representing the solutionā¦ But i guess this is itā¦
And as i said, because of system problems, i was not able to implement thisā¦
There were technical difficulties at my centre.
Only C compiler was available and i use to program in C++. I could have done Question-1 but i was unable to debug because of lack of compiler and the teachers their were also unable to do anything.
can someone interpolate the cut-off through polls a facebook ?
i think it should be zero in case answer is going negative as an empty bracket sequence is always considered as balanced
Problem 1
For all employee, traverse up the tree and keep checking if the (higher persons wealth - this personās wealth) > max
Problem 2
The same recursion (cached) as rajat1603
I passed the pretests. Hoping that this will clear the real check.
Also, I do not understand the claimed DFS solution.
Does anyone know when the results should be expected?
It went Bad! (With a capital B) I mean - I solved the first question - got the logic right - but failed on its implementation. As for the second one - I gave it a try, but just wasnāt able to solve it.
Seems that Iāll have to wait till the next year. 
PS: Created a poll here - http://goo.gl/J883Ke
Please vote, so that we can find the expected cutoff & upvote this so that everyone can vote too!
2 Likes
Could someone write this in a more detailed manner? I canāt understand this solution at all. My code timed out in subtask 2, probably because I think it ran in O(n!) time
Abey matlab Global Variable ā¦ Matlab har bracket se bahar
Yes I thought that too and passed the pretests, but shouldnāt that be mentioned in the statement? It was very confusing imoā¦
Well, 2 1 K+1 K+2 was DEFINED to be a balanced bracket sequence in the question. How can we just assume that an empty bracket sequence is balanced when itās not been specifically defined? It should have been mentioned in the question, itās not that stray a case to think about while framing the question.
Add everyone you know: Spreadsheet
This Google spreadsheet is publicly editable. This way, we can get an estimate on the cutoff. Add the codechef username and marks of the person you are sure of. Also check to make sure no duplicates.
Thanks.
3 Likes
If b[i] is a closing bracket, i cannot be part of any valid subsequence of b[i ā¦ j] so dp[i][j]= dp[i+1][j]. Otherwise iterate over all values of k such that k is the closing bracket of i and k<i<=j. If i is matched with k, we get v[i]+v[k] points for this and dp[i+1][k-1]+dp[k+1][j] points for the remaining sequence, so dp[i][j]= max(dp[i][j], v[i]+v[k]+dp[i+1][k-1]+dp[k+1][j]). Also thereās a possibility that i is not matched with anyone, so dp[i][j]= max(dp[i+1][j], dp[i][j]).
1 Like
Though couldnāt implement it but we could have used stacks for finding the largest possible bracket sequence (push opening brackets and when pushing closing brackets compare it with the most recent open bracket, if matched pop both of them) I think it is O(n) and then kadaneās algo for O(n) which i think makes this problem very easy.
Can anyone confirm if it is correct.
The subsequence does not have to be contiguous.
Hereās what I did for WLTHDISP: create pair of salary and boss#. Sort by boss# so that one whose boss is higher up in tree comes first in array.
This way Mr.Hojo is the first one. (1-indexed) after that dp[n] = 0. i=n-1; i>0; iā.
Now while the j=I+1 th term has same boss (I.e. it is at the same height in the tree, j++ and find the max of dp[j]+salary[i]-salary[j] for each iteration.
Earlier I was using Floyd Warshal but realized O(nĀ³) is too much for this data. And by the time I submitted this Sol, timer ran out so could only submit for s.t.1.
So many people scoring 200 and 140 ā¦ Cut off -> 140 probably
1 Like
donāt think so. they want to increase competition in the camp. they may take 35 people by making 100 cut-off.