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.
My solution for Wealth Disparity is working in all the test cases except for this one
Subtask 2
Outcome Details Execution time Memory used
Not correct Execution timed out (wall clock limit exceeded) 0.992 s 896 KiB
It is executing in less than 1 second. So, shouldnât it work? Also, I think that changing the time limit from 3s to 1s in the re-evaluation is unfair.
EDIT:
I mailed ico@iarcs.org.in regarding this. This is what I was mailed back in return:
âYes, it was 3 seconds on the iON server and is 1 second on the ICO
server, but this does not matter. We checked your code manually.
Your algorithm is O(n^2) and the problem requires an O(n) solution.
The case where you get time limit exceeded is the one large test case
that is there to check for O(n^2) vs O(n). The server sometimes
reports an inaccurate time when the time limit is reached, but the
verdict in this case is definitely correct.â
I understand what they are trying to say, but if they allowed the cpu time complexity to be less than 3 seconds on the iON server, then shouldnât they allow it in the re-evaluation as well?
So when was the camp held last year? And when is it expected to be held this year?
Could anyone share the answer of wealth disparity question.
I donât get the logic to define a well bracket sequence:
- i 1 2 3 4 5 6
- V[i] 4 5 -2 1 1 6
- B[i] 1 3 4 2 5 6
It says that the items a pos (1 3) is a well bracket sequence. (also if there is an open bracket not closed inside it)
than says (1 3 4 5) is a well bracket sequence, but these are contiguous and not one inside the other.
At this point I have two doubts:
If I find a sequence (1 1 4) can 4 close 1 either 2 or can close only the second 1.
If I find a sequence (1 4 3 2 5) (k=3) is (1 4 2 5) a well bracket sequence?
Excuse me if I put another post, but the comments doesnât format properly the code and can be very hard to read. (I cannot ask by myself since I have not enough karma)
Ever about brackets problem. My if to recognize if are valid sequence is the follow:
if ( (pairs[i]< pairs[j] && pairs[i+1]> pairs[j+1]) ||
(pairs[i]> airs[j] && pairs[i+1] < pairs[j+1]) ||
( pairs[i+1] < pairs[j]) ||
( pairs[j+1]< pairs[i]))
{
sum+=pairs[j+2];
}
where pairs is an array 3*n contained all the valid pairs of brackets sequence found. Pairs[0] is the position of the open bracket, pairs[1] is the closed bracket, and pairs[2] is the sum of the pair.
Does somebody tell me if I understood it right?