My code was accepted on all 8 test cases of subtask 1 and 2. First create a tree structure and then find the minimum value of each branch. After this recursively subtract the maximum of a branch from the minimum of the branch to find the largest disparity.
Problem 2 - Brackets
This one was very hard. I bruteforced for the solution. Got all test cases in subtask 1 correct but timed out on subtask 2.
Expecting 140 or 150(I don’t remember how much you get for subtask 1 of Brackets)
How did you do? Honestly I found the questions(Brackets in particular) to be much harder than previous years questions.
It went bad for me. The first one seemed really easy but I could not find out where I was going wrong… Got only 6/8. I didn’t even bother trying the second one cause I knew it was way out of my league. They shouldn’t conduct it this way next year onward… The test cases don’t tell us where we are going wrong, whether TLE or logic error etc. I performed quite badly, no chance this year
Do they even give TLE? In my epxerience during ZCO and INOI this year, my computer simply stopped responding and then they had to switch me over to another.
1.) A code which is compiling and running smoothly in dev c++ flagged an submission error when submitted through the server.
2.) A code which compiled and gave the correct answer in dev c++ showed ‘Fail’ in that corresponding test case (1st test case - Wealth Disparity). One of the attenders has taken 2 photographs showing the difference.
3.) I had to change my computer 3 times to get a satisfactorily fast computer which compiled and ran at normal pace.
Wealth Disparity was pretty straightforward.
The main thing in this problem is that the difference between the weight of an ancestor of a node and the weight of the node must be maximum. This can be solved using DFS by maintaining another variable in the stack which represents the maximum ancestor weight encountered so far in the branch. The answer will be the maximum difference of this value and the weight of the node. This can be done by doing DFS once.
I used a vector of vector of ints to represent the tree as an adjacency list. Then DFS was done and I maintained a variable, difference which is simply the maximum value of the difference of the weight of the node and the maximum weight encountered of the parent node. This value was updated every time during a node visit and the maximum weight encountered in a branch was also updated.
Overall, DFS takes O(V+E) using Adjacency list and since E = V - 1 in a tree, Time complexity is O(2V-1) = O(V) = O(n).
Space Complexity in the adjacency list is also O(V+E) = O(V) = O(n)
For brackets, I tried brute force but got only 3/5 test cases correct in the first subtask. Does anyone have any idea how to get a non brute force solution to Brackets?
Is the cut off going to be 100 as well this time? This is my first time and I was hoping to qualify. Now though, I’m not so sure.
I tried the solution for brackets (the part where I’m storing on the stack) in the Codechef IDE and it passed. Hopefully I’ll get 100.
Also can anyone please award me points so that I can ask questions and comment? I’m new to Codechef and Competitive Programming so it would be appreciated a lot.
I searched and realised getting your answers upvoted gives you enough karma to comment and ask questions. Can anyone kindly upvote this answer or give me karma points? Thanks a lot.
You used the Recursive variant. Well N can go upto 10^5 and I’m not sure how much the stack can handle (the function call stack and you will call the function N times). Maybe you should do a google search. In my opinion it depends upon the underlying implementation and can vary from platform to platform. You should email them maybe.
I don’t think DFS will AC. DFS and Recursion are the same here (Basically you are maintaining a explicit stack instead of using the function call stack that is generated while using recursion)
Sorry. i thought you meant AC as RE. Yes DFS will AC. and so should recursion.
And is a vector stored on the heap? I thought that it is stored on the stack like an array.
Basically the vector header info is allocated on the stack whereas the actual data is stored on the heap. Looks like I won’t have any problems with the memory management.
200 in pretests; not sure about what’s going to happen in the end
About the first problem, is it allowed to let i, j be the same? I didn’t consider that case and got AC but I’m not really sure if it’s going to pass the final tests.
Also is a O(n^3) solution supposed to pass in the second problem? I did the same dp as rajat1603, which takes around 700^3/2 ~ 2e8 operations. Is this fast enough? (It passed the pretests.)
Also ambiguity in the second problem: what will be the answer if all v[i]'s are negative? Is it some negative number or zero (the empty bracket sequence)? I assumed the second one and got AC, but then again idk if it’s going to pass the final tests.
