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
My P1 solution was DFS. I couldn’t figure out a better one.
many people got 140 by brute. i don’t think they will give them they may give them chance just because they got brute correct. in that case, cutoff may be 200.
I meant that it doesn’t ever show TLE. My bruteforce solution was for too slow for the subtask 2 and when I submitted it my test computer just stopped responding and then I had to switch to another computer. Also in case of segmentation fault or others it showed ABC.exe is not working or something.
Subtask 1 was n<=10. They would obviously have put it there for a reason. Looks like you think brute was a piece of cake. How much did you score in P2?
1 Like
It will TLE on Subtask 2, then. My dfs (linked above) is linear. As the traversal is depth first, you can just pass the maximum value encountered as an argument.
Why are there two different scores for first three contestants ??? … And Guys Chill ^
I am sorry, I meant to say my solution to P1 wasn’t DFS. It takes time O(n*h) where h is the height of the tree
No, cutoff will be same for all the classes. However, they may change the cutoff slightly so that some younger students can qualify.
Thats O(n^2) bro
“younger students can qualify”? what logic is that?
1 Like
I contacted Dr Madhavan Mukund regarding cutoffs and whether there is any privilege for class 11 and below. Here is the reply:
For the past 2-3 years, the cutoff has been at least one problem fully
correct. We have not so far implemented any special cutoff for class
11 and below, but we are open to considering it if the situation
warrants it.
–
Dr Madhavan Mukund
National Coordinator, Indian Computing Olympiad
Professor, Chennai Mathematical Institute, Chennai, India
(COPIED FROM QUORA :P)
This look about correct? #include <stdio.h>#include <iostream>#include <vector>#include <algorithm> - Pastebin.com O(n^3)