Inoi 2017 discussion

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.

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.


Since most of you are expecting 200, I dunno if i will be selected with 110 :frowning:

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 :
Here is the result data :

1 Like

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.

1 Like

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, 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.

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!


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.



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