1
$\begingroup$

I am new to algorithms so sorry to ask simple question

I am working on a problem which is about array of integers, my solution is right but not good enough, because I have time exceeded exception on codeforces. I think solution where solution's time < O(n^2) would be right.

enter image description here

My solution:

int n;
cin >> n;

int currentScore = n;
int credits[n];
int grades[n];
for (int i = 0; i < n; i++) {
    cin >> credits[i];
    for (int j = 0; j < i; j++) {
        if (credits[i] <= credits[j]) {
            currentScore--;
        }
    }
    grades[i] = currentScore;
    currentScore = n;
}

for (int i = 0; i < n; i++) {
    cout << grades[i] << endl;
}

return 0;
$\endgroup$
  • 1
    $\begingroup$ For the record: Your solution is O(n^2), and the O(n) is not a requirement, but just your guess. A wrong guess, I think $\endgroup$ – gnasher729 Oct 9 '18 at 7:47
  • $\begingroup$ Yea my solution is O(n^2) and as we know it is not good enough, I thought O(n) solution would be right, I'm not sure about it $\endgroup$ – Nika Kurashvili Oct 9 '18 at 7:50
1
$\begingroup$

A basic approach would be as follows.

Given input $a_1,a_2,\ldots$ we build an array of pairs $A=(1,a_1),(2,a_2),\ldots$.

Now, in $O(n\log n)$ time, we can sort it according to the second component of each pair.

When $A$ is sorted in such way, it's easy to compute the score and modify $A$ so that it becomes of the form $A=(i,{\sf score}_i),(j,{\sf score}_j),\ldots$. This should cost $O(n)$.

Now, we can sort $A$ once more, according to the first component of each pair, so that we have $A=(1,{\sf score}_1),(2,{\sf score}_2),\ldots$. This costs $O(n\log n)$.

Finally, we print the scores.

$\endgroup$
  • $\begingroup$ I sorted A according to the second component and after that I think it's not easy to compute score, I doubt how it's even possible, if you know how could you help me little more please. $\endgroup$ – Nika Kurashvili Oct 9 '18 at 18:32
1
$\begingroup$

Create a binary tree containing the points, either each node also containing the number of elements in each sub tree . For each candidate, determine the number of candidates arriving earlier, and having same or higher score using the tree, then add the candidates score to the tree.

Should work in O(n log n). I doubt O(n) is possible.

PS chi’s answer is a lot easier, and you probably have a library for the sorting, which is the hard part.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.