ZCO 2019 Discussion

I had hell of a time figuring out the way to undo sorting. I finally kept 1 ordered map where keys were elements and values were all 0. And seperately stored the original order in a vector. I then printed 2*(N-i-1) for each i.

1 Like

@kayak your code is difficult to understand since it is uncommented. Just post your logic

@bdyutish How did you undo the sorting?

@jagoshom I kept a map of pairs as keys and the original indexes as values.You calculate the ans for the sorted vector and assign the answers to an array in the original location using the map.

I just hope the cutoff is 15.

Can anyone tell me the solution for the first problem? Some where saying using mergesort…

Please post your solution for the first problem if anyone solved it fully. code not needed. thanks.

1 Like

Here’s my code for problem 1.

The logic is pretty simple.
Construct two arrays of pair of integers, L and R.
In the first position of each element l of L we put in the value l we receive and in the second position, we put in the index. Create a similar array for R.

Now sort the array L in decreasing order, and R in increasing order.

The score of the i-th person would be the sum of the positions of its corresponding l in L and its corresponding r in R.

For example, if n = 3, and the l and r values are

(10, 20), (13, 15), (14, 16)

The L and R would be, after sorting,

L: (14, 2), (13, 1), (10, 0)
R: (15, 1), (16, 2), (20, 0)

Now, \text{score}[0] = 2 + 2 = 4, \text{score}[1] = 0 + 1, \text{score}[2] = 1 + 0.

Though sadly I was getting WA in the test itself, I have no idea why. My logic is sound.

So, I just wrote a quick brute-force solution and got 15. :confused:

2 Likes

Can grp admin pls upload the link to the ICO WhatsApp grp? Also @kristopher , people are uploading their marks in both the spread sheets. Pls copy the data till now, and delete one, else analysis is going to get pretty messed up.

Is there any chance the cutoff goes down to 15?

When are the results released?Like, any idea?

Please share the logic for the second one.

Can someone who has got 100pts in the first question share their logic.

@mg21 it is most probably not going to be 15 since almost anyone could get 15

For the second DP problem there are few basic observations.

  1. We always put an integer because it will always increase the answer.

  2. The answer can either be the maximum length of UpDown subsegment already present+1 ( put any integer at last in the subsegment) or it can be combination of 2 subsegments which are just separated by 1 element which doesn’t obey the property. We can make the “bad” element “good” by inserting an integer beside it.

Let dp1[i] = maximum length of UpDown subsegment ending at index i

Let dp2[i] = maximum length of UpDown subsegment starting at index i

Now all that is left is to go through each index and find maximum value of dp1[i]+dp2[i] .
We can calculate DP and do this in O(n) with very small constant factor.

P.S. I may have missed some details and it is left as an exercise for the reader :stuck_out_tongue:

2 Likes

Is there any 11th student here who is interested in making a WhatsApp group to prepare for next year’s ZCO?

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.

1 Like

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

1 Like

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