# Inoi 2017 discussion

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

2 Likes

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.

4 Likes

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

1 Like

Iâ€™m getting 200.
The first one for me was

O(nlogn)

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

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!

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

This will help everyone to know their chances of getting into TC.

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