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

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.

3 Likes

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

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

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!

3 Likes

Are you seriously asking this? o.O

9 Likes

i felt that the paper was tough this year

//