INOI 2016 Discussion

Problem 1 - Wealth Disparity

My code was accepted on all 8 test cases of subtask 1 and 2. First create a tree structure and then find the minimum value of each branch. After this recursively subtract the maximum of a branch from the minimum of the branch to find the largest disparity.

Problem 2 - Brackets

This one was very hard. I bruteforced for the solution. Got all test cases in subtask 1 correct but timed out on subtask 2.

Expecting 140 or 150(I don’t remember how much you get for subtask 1 of Brackets)

How did you do? Honestly I found the questions(Brackets in particular) to be much harder than previous years questions.

EDIT: Confirmed score of 140

1 Like

mismanagement at my center caused problems I got a proper pc 2 mins before the end of the exam

It went bad for me. The first one seemed really easy but I could not find out where I was going wrong… Got only 6/8. I didn’t even bother trying the second one cause I knew it was way out of my league. They shouldn’t conduct it this way next year onward… The test cases don’t tell us where we are going wrong, whether TLE or logic error etc. I performed quite badly, no chance this year

Brackets Solution

Dp(l , r) max sub-sequence sum of balanced parenthesis where each index from [l , r]

Dp(l , r) = 0   where   r <= l

otherwise

Dp(l , r) = max(dp(l + 1 , i - 1) + arr[l] + arr[i] + dp(i + 1 , r)) where b[i] = b[l] + k

also

dp(l , r) = max(dp(l , r) , dp(l + 1 , r))

4 Likes

I had a lot of technical difficulties :

1.) A code which is compiling and running smoothly in dev c++ flagged an submission error when submitted through the server.
2.) A code which compiled and gave the correct answer in dev c++ showed ‘Fail’ in that corresponding test case (1st test case - Wealth Disparity). One of the attenders has taken 2 photographs showing the difference.
3.) I had to change my computer 3 times to get a satisfactorily fast computer which compiled and ran at normal pace.

I got 100 in the pretests.

Wealth Disparity was pretty straightforward.
The main thing in this problem is that the difference between the weight of an ancestor of a node and the weight of the node must be maximum. This can be solved using DFS by maintaining another variable in the stack which represents the maximum ancestor weight encountered so far in the branch. The answer will be the maximum difference of this value and the weight of the node. This can be done by doing DFS once.

I used a vector of vector of ints to represent the tree as an adjacency list. Then DFS was done and I maintained a variable, difference which is simply the maximum value of the difference of the weight of the node and the maximum weight encountered of the parent node. This value was updated every time during a node visit and the maximum weight encountered in a branch was also updated.

Overall, DFS takes O(V+E) using Adjacency list and since E = V - 1 in a tree, Time complexity is O(2V-1) = O(V) = O(n).

Space Complexity in the adjacency list is also O(V+E) = O(V) = O(n)

For brackets, I tried brute force but got only 3/5 test cases correct in the first subtask. Does anyone have any idea how to get a non brute force solution to Brackets?

Is the cut off going to be 100 as well this time? This is my first time and I was hoping to qualify. Now though, I’m not so sure.

1 Like

200 in pretests; not sure about what’s going to happen in the end

About the first problem, is it allowed to let i, j be the same? I didn’t consider that case and got AC but I’m not really sure if it’s going to pass the final tests.

Also is a O(n^3) solution supposed to pass in the second problem? I did the same dp as rajat1603, which takes around 700^3/2 ~ 2e8 operations. Is this fast enough? (It passed the pretests.)

Also ambiguity in the second problem: what will be the answer if all v[i]'s are negative? Is it some negative number or zero (the empty bracket sequence)? I assumed the second one and got AC, but then again idk if it’s going to pass the final tests.

Does the cutoff vary from Class to Class or is it the same for everyone?

I’m in Class 9, so is the cutoff going to be less for me than say a student of class 12?

can anyone post the sample inputs for both the questions

@siddharth2000

IIRC the sample input for the first one was-
4 5 10 6 12 2 -1 4 2

1 Like

thanks a lot but do you remember the 2nd question’s sample input as well

I guess the solution to the first problem goes as follows :
For every employee, since he has only one manager, the maximum difference you get with that employee and the previous nodes of the tree is the maximum wealth of one of the managers of the branch and himself. The solution is to maximize this list…

I know, a bad way of representing the solution… But i guess this is it…
And as i said, because of system problems, i was not able to implement this…

There were technical difficulties at my centre.

Only C compiler was available and i use to program in C++. I could have done Question-1 but i was unable to debug because of lack of compiler and the teachers their were also unable to do anything.

Problem 1

For all employee, traverse up the tree and keep checking if the (higher persons wealth - this person’s wealth) > max

Problem 2

The same recursion (cached) as rajat1603

I passed the pretests. Hoping that this will clear the real check.

Also, I do not understand the claimed DFS solution.

Does anyone know when the results should be expected?

It went Bad! (With a capital B) I mean - I solved the first question - got the logic right - but failed on its implementation. As for the second one - I gave it a try, but just wasn’t able to solve it.

Seems that I’ll have to wait till the next year.

PS: Created a poll here - http://goo.gl/J883Ke

Please vote, so that we can find the expected cutoff & upvote this so that everyone can vote too!

2 Likes

This Google spreadsheet is publicly editable. This way, we can get an estimate on the cutoff. Add the codechef username and marks of the person you are sure of. Also check to make sure no duplicates.

Thanks.

3 Likes

Though couldn’t implement it but we could have used stacks for finding the largest possible bracket sequence (push opening brackets and when pushing closing brackets compare it with the most recent open bracket, if matched pop both of them) I think it is O(n) and then kadane’s algo for O(n) which i think makes this problem very easy.
Can anyone confirm if it is correct.

Here’s what I did for WLTHDISP: create pair of salary and boss#. Sort by boss# so that one whose boss is higher up in tree comes first in array.
This way Mr.Hojo is the first one. (1-indexed) after that dp[n] = 0. i=n-1; i>0; i–.
Now while the j=I+1 th term has same boss (I.e. it is at the same height in the tree, j++ and find the max of dp[j]+salary[i]-salary[j] for each iteration.

Earlier I was using Floyd Warshal but realized O(n³) is too much for this data. And by the time I submitted this Sol, timer ran out so could only submit for s.t.1.

please someone post solution for wealth disparity on ideone or pastebin…I got ac on 1st problem and screwed up second problem…and my computer during exam hanged so many times …

I mailed at ico@iarcs.org.in asking when the results would be announced.

“We have just received the exam data from TCS. We have to re-evaluate
all the submissions and check. A realistic estimate is Monday.”

Monday it is then.