Блог пользователя kingofnumbers

help is needed
Автор kingofnumbers, 12 лет назад, По-английски

Hi,

I got problem and can't solve it:

given an array consist of N integers A1,A2,A3...An

for each element i from 1 to n you should increase all elements j by (1) such that j<i and A[j]>=A[i]

example: the array is:

4 2 1 3

i=1 :

nothing before 1 so thing will happen here

i=2 :

A[i]=2 so we need to increase all element before i and bigger or equal than A[i] by 1

so the array become:

5 2 1 3

i=3 :

A[i]=1

increase all element before i and bigger ort equal than A[i] by 1

the array become:

6 3 1 3

finally when i=4 :

the array become:

7 4 1 3

so print the new array to the output

N=10^5

sorry for my English.

thanks in advance.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

There is a modified O(nlgn) merge-sort algorithm which is used to calculate inversions. You can modify that easily and solve your problem ;)

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Where is this algorithm?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Algorithm for number of inversions. Modify it yourself :)

      1- Merge sort array A and create a copy (array B)

      2- Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.

      2a. accumulate the number of inversions to counter variable num_inversions.

      2b. remove A[1] from array A and also from its corresponding position in array B

      3- Rerun from step 2 until there are no more elements in A.

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        please, can you show me how to apply this algorithm on array A= 4 2 1 3

        to make a better understand

        thanks alot

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sure!

          1. A = {4,2,1,3} and B = {1,2,3,4}
          2. A[1] = 4 and the position of 4 in second array is 4th! So inversion += 3(position in sorted array minus one)
          3. Remove 4 from both array and now you have {2,1,3} and {1,2,3} and you should do the second step until A become empty.
          4. Now you have 4 inversions.
          → Ответить
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            I applied this algorithm and got the output 7 3 1 3 instead of 7 4 1 3

            actually finding inversions in not useful in this problem.

            thank you anyway.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I told you so! :) Directly applying this algorithm is not useful! You should modify that!

              Also you can use divide&conquer solution.

              → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am still waiting for a good idea.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Amir.bh said everything... Ok, once again.

    1. Compress numbers in array
    2. for (int i = n-1; i >= 0; i--) {
    ans += fenwickSum(0, a[i]); // sum on [0, a[i]]
    fenwickInc(a[i]); // increment tree[a[i]]
}
    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    I have very ugly solution.
    to solve this problem you need data structure with operations
    1) Find(X) — find object at position X
    2) MoveUp(X) — move all objects from position j >= X to positions j + 1.
    It's like for (i = maxN - 1; i >= X; i--) a[i + 1] = a[i];
    **upd:** for lists there must be a[i + 1].insertAllElementsFrom(a[i]);
    to implement this data structure one can use Cartesian Tree or Rope. now algorithm is straight-forward S — described structure where each cell with index from 0 to 2 * n contains an empty list of integers.

    for each i
   S.MoveUp(a[i]); S.Find(a[i]).clear(); S.Find(a[i]).Add(i);
for (each pos in S)
{
  List = S.Find(pos);
  for (each x in List)
    ans[x] = pos
}
    → Ответить