Any idea when the results are coming out?
The results are probably gonna be out by Monday i.e,10/12/2018(seeing from previous trends of announcing results ,that is) .
Btw ,did anyone properly notice the time limit for the questions? It was 2 seconds .Even a brute Force approach should have worked in c++ and other languages (Java - twice the time limit and python -4 times I guess),according to using just 10^7 ooperations per seconds .
The results have been probably declared. I received a mail from CodeChef, stating that all students with a score >= 40 have qualified for INOI 2019.
Cheers!
Arnav.
Can somebody please properly explain the approach to solve SINGTOUR? Here’s the part I understand: Sorting vectors of pairs (Upper limit, Index) and (Lower limit, Index).
What I do not understand is the logic behind iterating over i from 0 such that i\lt n and performing this operation at each iteration:
[second represents the index part of the pair]
score[lower_limits[i].second] += n - i - 1;
score[upper_limits[i].second] += i;
Can somebody please explain how this helps in computing the final score? Please note that this is with reference to the solution at https://www.codechef.com/viewsolution/22016797
@aryan_02:
It is based on the observation that, for an interval [l, r], each starting or ending point that lies inside this interval adds 1 to the score of this interval. So, if an interval lies completely inside, it has a starting point and an ending point lying inside [l, r] and hence it adds 2 to the score. For intersecting intervals, either the staring point or the ending point lies inside, and so each intersecting interval adds 1 to the score.
Also, all the intervals lying completely to the left of l or to the right of r add 1 to the score. This means, the score for [l,r] is equal to the number of starting points inside [l, r] (intersecting or lying completely inside) + the number of starting points after r (intervals lying to the right of r) + the number of ending points inside [l, r] (intersecting or lying completely inside) + the number of ending points before l (intervals lying to the left of l).
The first two terms and the last two terms above can be clubbed together which makes the score for [l, r] equal to the number of starting points after l (= n - i - 1, if index of l in lower_limits
is i) + the number of ending points before r (= j, if the index of r in upper_limits
is j).
@lokesh2002 had already made a spreadsheet, which also has the scores for ZIO. Please replace yours with his, as it’s better to have all the scores in one place.
@kristopher
Everyone on ico whatsapp group have this link,and it can be used for all three
Zio/Zco/INOI. why a new one?.
You need to watch Baahubali to understand the code properly.
Damn shouldve known that :o
Well, as far as i heard the first problem, basically it was for each range, count total number of ranges lying totally inside it and number of ranges partially overlapping with it. Both can be solved quite easily using merge sort trees or persistance or any other 2D DataStructure of your choice. That would have made this a blind implementation problem. the intended solution is probably using some binary searches, using which u can determine how many ranges are outside ur boundary and how many are inside. PS: work out the details urself.