skpro19's blog

Let's discuss HackerEarth December 2017 Circuits here.
By skpro19, history, 7 years ago, In English

Let's discuss the hackerearth december circuits here.

The link to the competition is this.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the 4th question?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you mean splitting of array. if yes.

    i solved it by maintaining inversions of all prefix and of all suffix. Then for each element i m finding how many greater elements are there to the right side. so answer for each k is prefix[i] + suffix[i+1] + no.of element greater to right.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Can you share your code?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        The solution is much more simple based on a simple observation. Consider the given example — 3 5 2 7 6

        It has 3 inversions. Now when 3 gets shifted at back, how many inversions get added? The number of integers greater than 3 i.e 5,7 and 6 add 1 inversion each. And how many inversions get lost? The number of integers smaller than 3 i.e 2 leads to loss of 1 inversion.

        So for each integer shifted, number of inversion increases by number of integers greater than that integer, and decreases by number of integers smaller than that.

        Here is the code

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can create a new array by appending array A to it self A=A+A and now just you need to find inversions in every subarray of size n this can be done using sliding window of Len N and binary indexed tree .

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasn't the contest a bit on the tougher side?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It was, and its due to my problems. I'm sincerely apologetic for this, and I shall be more careful about the difficulties next time.

    On the other hand, I hope all of you'll read the editorials and the pre-required knowledge links attached to them, and it shall definitely be profit for you'll.

    Thank You and Sorry again

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will do. Thanks man.

      Some suggestions: 1.There were too little example test cases in the question. 2. The problems difficulty was out of sync

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Two arrays problem was nice.

      → Reply