Passed the pretests for me. (same recursion)
I sort of did this, in a very untidy way, but it didnât passâŚ
The cutoff has been 100 for a couple of years now. No idea about this one. P1 was too easy, I think. I would say 140 or 200.
I think system testing might be a problem there, but then again, no one has a better solution right?
For the 2nd problem, I assumed the first case if all v[I]s are negative. For e.g.
6 3
-5 -4 0 -3 -6 -5
1 3 4 2 5 6
My code was printing -5. And for no bracket subsequence, I printed a huge negative quantity.
mbrc was trying to code a O(n^2*k) solution, but apparently couldnât do it in time.
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.