Yep thats N^2 , I did that too and didn’t bother with optimising cause it passed … It would work for 10^5 for most cases but one 
For a randomly generated tree, the height is usually proportional to lg(n)
but they will have worst case inputs as well…
so it should be “past 4-5 years” now 
Actually Agnishom it would be log_k(N) where , K is the lowest number of children per node … lg(N) is only applicable to binary trees … And trust me manual testing mein they would only consider the WORST CASE (you should’ve read the instructions, ) (even I should’ve ) dude move on !!!
I just went through the testdata. The testdata is big so it appears that this is the final testdata for evaluation.
Wealth Disparity has two testdatas, my solution passes all in the first one, the second one uses absolute difference, apparently some students looked for maximum absolute difference between the wealth of a manager and a subordinate causing the answers to be different. So if you are one of them, then you are safe.
However, I timed the time taken for my solution to produce the solution and it is taking my computer maximum 0.127 seconds for the last testcase. Even if the grader is significantly weak, since there is 3 second time limit, maybe O(n^2) would pass. [Not sure, I’m creating the O(n^2) solution to test whether it would pass or not]. So the number of students getting >=100 may be higher than what we were expecting with O(n).
EDIT: O(n^2) [Actually O(n*h) where h is the height of the tree] passed on all testcases under 3 seconds except in one. And this one was a worst case input. The file is 2_10.in [The 10th input] and it took the DFS O(n) solution 0.155 seconds in this one. And the O(n^2) solution… well it took 1 minute 43.476 seconds [I was surprised… Infact I ran it twice and this was the best time]. So for 100 you need O(n). All the other test cases are comparatively weak but this one is mammoth.
And I’m giving the real time elapsed output provided by the linux time command. The time will vary but I ran it on a quad core i7. So other testcases may fail under O(n^2) as well depending on the hardware of the grader.
Does anyone have any idea about the limit for the stack size to cause an overflow (is it included in the 512 MB)? I am getting a segmentation fault in test case 2_10 for wealth disparity.
You were right
Got a mail “INOI 2016 Evaluation” My score is 140 confirmed. Now I just hope I will make it.
What was the splitting of the first task?
Wasn’t it 40% and 60% for the two subtasks respectively?
If not, I’ve got 130
How do you get 130? o.O
@Agnishom, it was 30. It’s in the problem description For 30% of the marks, 1 <= N <= 500.
I got 100. Sure of not making it. Brackets test cases were same and in Wealth DIsparity only new testcases were added to Subtask 2. All the best to those who scored >=140. All the best for the camp :D.
Edit: Also Time LImit for Wealth Disparity is 1 second not 3 [Check the Evaluation] . Apparently they increased the limits to make sure only O(n) passes. Let’s see what the cutoff is.
can anyone post solution for brackets on ideone or pastebin???
Here is my solution to Brackets:
/*31001, Agnishom Chattopadhyay, Brackets*/
#include <iostream>
#include <algorithm>
int V[701], B[701], cache[701][701], N, k;
int coolSum(int start, int end){
//std::cout << "coolSum Call" << start << " " << end << std::endl;
if (cache[start][end] != -123456789)
return cache[start][end];
if (start >= end){
cache[start][end] = 0;
return cache[start][end];
}
if ((start == 0) || (end == 0)){
cache[start][end] = 0;
return cache[start][end];
}
if (B[end] <= k){
cache[start][end] = coolSum(start,end-1); //An open bracket at the end contributes nothing
return cache[start][end];
}
int maxTemp = -999999999;
if (B[end] > k){
for (int iii=start; iii < end; iii++)
if (B[iii]==B[end]-k)
maxTemp = std::max(maxTemp, V[iii]+V[end]+coolSum(iii+1,end-1)+coolSum(start,iii-1));
maxTemp = std::max(maxTemp,coolSum(start, end-1));
cache[start][end] = maxTemp;
return maxTemp;
}
}
int main(){
std::cin >> N >> k;
for (int iii=1; iii<=N; iii++)
std::cin >> V[iii];
for (int iii=1; iii<=N; iii++)
std::cin >> B[iii];
for (int iii=0; iii< 701; iii++)
for (int jjj=0; jjj < 701; jjj++)
cache[iii][jjj] = -123456789;
std::cout << coolSum(1,N);
return 0;
}
iii, jjj
nice loop variable names there _ /\ _
3 Likes
That TCS Ion platform was crap.That dev cpp ide was constantly crashing that’s why I was even unable to run code on machine and debug it…They should use simple codeblocks or any other text editor with compiler suite …there’s no need of TCS Ion crap
1 Like