There were technical difficulties at my centre.
Only C compiler was available and i use to program in C++. I could have done Question-1 but i was unable to debug because of lack of compiler and the teachers their were also unable to do anything.
Problem 1
For all employee, traverse up the tree and keep checking if the (higher persons wealth - this person’s wealth) > max
Problem 2
The same recursion (cached) as rajat1603
I passed the pretests. Hoping that this will clear the real check.
Also, I do not understand the claimed DFS solution.
Does anyone know when the results should be expected?
It went Bad! (With a capital B) I mean - I solved the first question - got the logic right - but failed on its implementation. As for the second one - I gave it a try, but just wasn’t able to solve it.
Seems that I’ll have to wait till the next year. 
PS: Created a poll here - http://goo.gl/J883Ke
Please vote, so that we can find the expected cutoff & upvote this so that everyone can vote too!
2 Likes
Add everyone you know: Spreadsheet
This Google spreadsheet is publicly editable. This way, we can get an estimate on the cutoff. Add the codechef username and marks of the person you are sure of. Also check to make sure no duplicates.
Thanks.
3 Likes
Though couldn’t implement it but we could have used stacks for finding the largest possible bracket sequence (push opening brackets and when pushing closing brackets compare it with the most recent open bracket, if matched pop both of them) I think it is O(n) and then kadane’s algo for O(n) which i think makes this problem very easy.
Can anyone confirm if it is correct.
Here’s what I did for WLTHDISP: create pair of salary and boss#. Sort by boss# so that one whose boss is higher up in tree comes first in array.
This way Mr.Hojo is the first one. (1-indexed) after that dp[n] = 0. i=n-1; i>0; i–.
Now while the j=I+1 th term has same boss (I.e. it is at the same height in the tree, j++ and find the max of dp[j]+salary[i]-salary[j] for each iteration.
Earlier I was using Floyd Warshal but realized O(n³) is too much for this data. And by the time I submitted this Sol, timer ran out so could only submit for s.t.1.
please someone post solution for wealth disparity on ideone or pastebin…I got ac on 1st problem and screwed up second problem…and my computer during exam hanged so many times …
I mailed at ico@iarcs.org.in asking when the results would be announced.
“We have just received the exam data from TCS. We have to re-evaluate
all the submissions and check. A realistic estimate is Monday.”
Monday it is then.
Any information regarding the cutoff? They get a basic idea of the cutoff from the exam data I think right?
If too many people are getting 100 and above and if they want to restrict the camp participation to some number, say 30, will they operate a differential cut-off for different classes?
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.
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
@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;
}
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
can someone share their O(n) soln for Wealth Disparity, since my soln timed out only in the 2_10 input which was supposed to be a worst case input
Yes, they did change it. If you have a problem with that, you should email the coordinator. I did.