INOI 2016 Discussion

general
,
101

@warhawk_123, my solution - http://pastebin.com/S0BPGgRF

I just wish I had thought of this during the test. I manually tested in on the test cases and it passed all with the longest one taking about 0.45 seconds.

The tester code is half baked just to get the stuff done in C# - http://pastebin.com/3uknCA5N

102

can someone share their O(n) soln for Wealth Disparity, since my soln timed out only in the 2_10 input which was supposed to be a worst case input

103

Hereā€™s my solution. I know its very messy but I was only focused on getting it right during the exam - http://pastebin.com/zPwvGp1e

104

@archit129 cool manā€¦!! wow your pointer skills are way better than meā€¦

105

@shauryaagg

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

106

Change what?

107

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 [email protected] 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?

108

doesnt matter , n^2 will not even work with 10 seconds and O(n) will work with even in 1 second

109

There was an answer before this answer which @shauryaagg has now deleted

110

thanks archit

111

Well here are the qualifiers for ioitc

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

112

http://www.iarcs.org.in/inoi/2016/inoi2016/results_inoi2016.php Results. I qualified :smiley:

2 Likes
113

Hereā€™s mine, http://ideone.com/3CX73s

114

This is the new link: New Link

Congratulations to all those who mase it.

115

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

116

In the month of May

117

last year it was from 1st to 9th may

1 Like
118

Could anyone share the answer of wealth disparity question.

119

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?

120

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?