How was your test experience and your performance?
My center was at IIT Patna and the test experience was just fine after the 1 hour delay. Much better than last year.
Solved the first one by a simple dfs. No idea why it was included in INOI. For the second one I did a brute force specific to the first two test cases. This brought my total score to 150
The experience was a big improvement over ZCO. Despite the 1 hour delay.
I did the same for the first problem and implemented a dynamic solution for the second one.
It passed all the test cases fine.
Fingers crossed for system testing.
What was your complexity for the first problem? I got an NlogN DFS for the first and an N^2 DP for the second.
Same, the first was NlogN due to the sort+search I did.
The second was an N^2 DP.
Solution for the second problem: Observe that only the number of trainings before the i’th training determines the strength and not the order in wich they took place.
Thus,
DP(t,i)=0 if i > n;
DP(t,i) = max( DP(t+1,i+1),DP(t,i+1)+tvals[t]*arr[i])
Here, tvals[t] stores the strength after t trainings, arr[i] stores the XV coefficient for the cities.
The first part of max refers to training in the i’th city while the second part to battling.
Answer is given by DP(0,0);
Overall complexity is O(n^2) after memoization.
The first problem was overall easy, but my code was a little bit bad, as I used sets and comparators for the points.Complexity was O(NlogN)
Expecting 200, but do not know about system testing.
I gave the exam in Kolkata, and the overall environment was good, although, there was a one hour delay.
However, no problems occurred during the exam.
EDIT : I gave the second solution too, but I think it is in the next page or later down in this page.
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).
Since most of you are expecting 200, I dunno if i will be selected with 110 
It was a big improvement compared to previous exam of ZCO 2017 although the delay of an hour was a pain. Solved the first one using DFS in O(N Log N). Used another O(N^2) DP solution to solve the 2nd one but got only 50 marks for it gave AC on 2 subtasks and failed on the last one. There was no further time left for me to debug so that`s it. Fingers Crossed for the final results !
Here is an “ANONYMOUS” poll created by me to find the cut-off marks, please vote it here : https://goo.gl/rrXfyL
Here is the result data : https://goo.gl/A6UXD9
I’m getting 200.
The first one for me was
and it was quite simple. I did DFS.
There is one thing that’s bothering me… I used int instead of long long to store the x and y coordinates. However I remember that the last Subtask had large values for R and C. But I don’t remember the limits. Can someone tell the limits as I’m worried that it will overflow.
The second was N^2 DP.
INOI was quite simple this time, the DP was much simpler than last year. The cutoff most probably might be 200 this time.
I did the second one. Why was the first problem so easy, how to do it?
The experience was good but performance was not.
For the second problem, I used Point class in Java, but any pair will do.
Make a list of all the points and take in a set.
Now, get all the patches using DFS/BFS. Using sets is easier in maintaing which squares were visited.now, for each patch, I calculated fence number as
val = 4*number of elements - sum of outdegrees of each element
and then maximized it over all such patches.
complexity O(N logN) where logN is due to Set operations and N since we process each node at most 2 or 3 times.
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.
How would you guys compare this year’s paper to last year ones ?
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!
Are you seriously asking this? o.O
i felt that the paper was tough this year