I did not give last year, but since I have solved them, I would give the following ratings
out of 10;
Last year:
1 >> 3
2 >> 8
This year
1 >> 5
2 >> 7
This is how I feel when comparing to all the questions from the last 10 years.
The expected solution for FENCE was O(n * log n). You should use maps/sets or sort rows/cols to figure out what the edges are efficiently. Basic STL knowledge was required for 100 points.
TRAINING was a classical knapsack type dynamic programming problem. The first state you can come up with is something like dp[i][x] = Max XP you can get if you have strength x after visiting the first i gyms. Then you observe that the strength can be determined by remembering the number of times you’ve trained, so you don’t need to explicitly store it. This makes it O(n^2).
Note that the test data you all received is not the final one. All codes will be re-evaluated before deciding the cut-offs. Best of luck to everyone!
3 Likes
i felt that the paper was tough this year
I am expecting atleast a 100(150 if my solution for Training passes). Training was rather easy too but I didnt solve for the third subtask. After solving the second I went to the Fences problem which at first glance I thought was tough. But after a quick analysis I figured that it was a simple DFS(or BFS, though implementing BFS was a lot more messy) problem, though the solution needed a smart implementation of maps… I didnt realise it at first so I was moving forward with a “double” sorted cultivated coordinates vector(sorted for the y coordinate and then for the x so that they were all in order) and finding if the surrounding cells were cultivated or not and therefore finding out the number of fences required for each cell, It was a very very crude solution and I was facing faults all the time. Then I implemented with Maps(had to read up the documentation again :3) which passed all the local subtasks. After that I had very little time to code the third subtask of Training and debug it which I had formulated on paper… And also, for Fences I submitted the final solution during the final last minutes at which time the web page just “hanged” :3
Everyone, please put your Name and score in this sheet .
This will help everyone to know their chances of getting into TC.
Please share this link as much as possible.
Thanks
8 Likes
Can anyone post the solution code for both the problems??
Since about 34 are getting 200, I don’t think I have a chance with 110. Do many solutions get rejected after rechecking by organisers every year ? @animesh_f
1 Like
Can anyone open a spreadsheet online, so that we can put up our marks there and estimate the cut-off.I don’t know how, otherwise I would have done it myself.(Cut-off might be 140 – just saying).
1 Like
No, I do not think that the cut-off will be full marks.110-140 seems good, although the problems were not that difficult.
I hope I get selected.
And no, int won’t exceed, as x,y coordinates were between 0-10^5 range.
Also no chances of stack overflow with recursive DFS?
Actually I did the first in one hour and the second using top down in one hour. The last hour was spent doing bottom up which was giving SEG FAULT because I initialized the array on the stack. So I didn’t check the first that properly.
I also did the second problem using top-down.That should not give stack overflow. However, in the second problem, I really do not know as in Java at least, it would have given so.I do not know the stack size in C++, but Java, it is less than 10^4.And I never tried recursive dfs, because I always do the iterative one and it has become kind of a habbit in graph algorithms.Still , hope for the best.
Are you seriously asking this? o.O
9 Likes
@sampritipanda The solution for 50 points (when you store the strength explicitly) is very similar to knapsack DP. Converting it to 100 is just an easy observation 
Maybe TL for problem 2 subtask 1 was somewhat weak. My code that was getting accepted actually took around 2.4-2.5 seconds offline on max test(randomly generated). That or the PCs provided were much slower than codechef.
@nibnalin, TLs were pretty generous. We did not want to force people into making constant optimizations. This isn’t long challenge xD
2 Likes
How much did you score?
Are the codes that we actually submitted going to be reevaluated or the ones that we had to store in the desktop.If it is the latter case, I think I may have left the public before class declaration, which is not allowed in codechef.Eclipse generates public classes by default, so when I submit, I explicitly remove it.But when I saved It , there is a small chance that I may have forgotten to remove it, although the rest of the code is same.Although I think I have removed it, please check it nonetheless once before reevaluation, if that code is going to be checked.roll number is zco31038.
I can see only abt 15