INOI 2016 Discussion

@shauryaagg

Yes, they did change it. If you have a problem with that, you should email the coordinator. I did.

My solution for Wealth Disparity is working in all the test cases except for this one

Subtask 2

Outcome Details Execution time Memory used

Not correct Execution timed out (wall clock limit exceeded) 0.992 s 896 KiB

It is executing in less than 1 second. So, shouldn’t it work? Also, I think that changing the time limit from 3s to 1s in the re-evaluation is unfair.

EDIT:
I mailed ico@iarcs.org.in regarding this. This is what I was mailed back in return:

“Yes, it was 3 seconds on the iON server and is 1 second on the ICO
server, but this does not matter. We checked your code manually.
Your algorithm is O(n^2) and the problem requires an O(n) solution.
The case where you get time limit exceeded is the one large test case
that is there to check for O(n^2) vs O(n). The server sometimes
reports an inaccurate time when the time limit is reached, but the
verdict in this case is definitely correct.”

I understand what they are trying to say, but if they allowed the cpu time complexity to be less than 3 seconds on the iON server, then shouldn’t they allow it in the re-evaluation as well?

Well here are the qualifiers for ioitc

http://www.iarcs.org.in/inoi/2016/inoi2016/shrdlu.php

INOI 2016, List of qualifiers - IARCS Results. I qualified :smiley:

2 Likes

This is the new link: New Link

Congratulations to all those who mase it.

So when was the camp held last year? And when is it expected to be held this year?

Could anyone share the answer of wealth disparity question.

I don’t get the logic to define a well bracket sequence:

  • i 1 2 3 4 5 6
  • V[i] 4 5 -2 1 1 6
  • B[i] 1 3 4 2 5 6

It says that the items a pos (1 3) is a well bracket sequence. (also if there is an open bracket not closed inside it)
than says (1 3 4 5) is a well bracket sequence, but these are contiguous and not one inside the other.
At this point I have two doubts:
If I find a sequence (1 1 4) can 4 close 1 either 2 or can close only the second 1.
If I find a sequence (1 4 3 2 5) (k=3) is (1 4 2 5) a well bracket sequence?

Excuse me if I put another post, but the comments doesn’t format properly the code and can be very hard to read. (I cannot ask by myself since I have not enough karma)
Ever about brackets problem. My if to recognize if are valid sequence is the follow:

          if ( (pairs[i]&lt pairs[j] && pairs[i+1]&gt pairs[j+1]) ||
             (pairs[i]&gt airs[j] && pairs[i+1] &lt pairs[j+1]) ||
            ( pairs[i+1] &lt pairs[j]) ||
             ( pairs[j+1]&lt pairs[i]))
             {
                sum+=pairs[j+2];
            }

where pairs is an array 3*n contained all the valid pairs of brackets sequence found. Pairs[0] is the position of the open bracket, pairs[1] is the closed bracket, and pairs[2] is the sum of the pair.
Does somebody tell me if I understood it right?

I am approaching the Wealth Disparity via a graph solution. My code is pasing all the testcases except one, which is showing the following error: RE (SIGABRT)(0.540000)

My code is here: WEALTH_DISPARITY

Can anybody please tell me what exactly this error means and why am I getting this error?

I used Rajat’s solution, O(n^3), but I am getting TLE for 2nd sub task. Can anyone please suggest a faster solution ?

Subtask 1 of each problem was 40 pts. I got 140 on pretests (dfs+brute)

1 Like

High 5 anukul. Got 140 on pretest too.

Do they even give TLE? In my epxerience during ZCO and INOI this year, my computer simply stopped responding and then they had to switch me over to another.

It just said I got x/y cases right. Didn’t tell me any reason.

I tried the solution for brackets (the part where I’m storing on the stack) in the Codechef IDE and it passed. Hopefully I’ll get 100.
Also can anyone please award me points so that I can ask questions and comment? I’m new to Codechef and Competitive Programming so it would be appreciated a lot.

I searched and realised getting your answers upvoted gives you enough karma to comment and ask questions. Can anyone kindly upvote this answer or give me karma points? Thanks a lot.

I did plain dfs(node, max_of_subtree). do you think it will result in RE? I used a vector btw, so all elements are on the heap.

dfs will AC , 10^5 recursion easily works without any problem

You used the Recursive variant. Well N can go upto 10^5 and I’m not sure how much the stack can handle (the function call stack and you will call the function N times). Maybe you should do a google search. In my opinion it depends upon the underlying implementation and can vary from platform to platform. You should email them maybe.