Wait for system testing. I had used a lot of my time trying to figure out how strong the test data was. And it wasn’t very strong. Keeping fingers crossed!
Looks like 140 to me. 200 would be way to high and problem 2 certainly was tough. (I didn’t even realize there was a DP solution to it). And how did you do the brute force for subtask 1? My brute force gave 3 correct answers and 2 incorrect for subtask 1. I tried possibly every test case I could think of and got the expected output. Also the description was a bit ambiguous. I remember in the explanation that the numbers at index 2, 4, 5, 6 were said to be (don’t remember the exact term). But the indexes 2,6 and 4,5 were not mentioned. So is it to have gaps greater than 2 between the numbers?
6 3
4 5 -2 1 1 6
1 3 4 2 5 6
@animesh_f, how did you try to figure out the test cases? Only the first two test input and output were shown on my system (and both gave correct results in Brackets, subtask 1). They should have displayed the input which gave incorrect results.
@geekpradd My code initially gave the same 3 out of 5. But after I tried it with this test case I found out my mistake. Values 1 2 3 4 1 2 3 4, and bracket sequence 1 2 4 5 1 4 2 5. K=3 N= 8 Expected output is 16.
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
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
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.
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
The subsequence does not have to be contiguous.
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.
Can you explain your P1 solution? It looks like O(n^2) to me. Here’s the DFS solution 3CX73s - Online C++ Compiler & Debugging Tool - Ideone.com
Look at the spreadsheet , the number of 140’s have increased drastically