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

Автор ILoveVanshita, история, 3 года назад, По-английски

NOTE — This problen is not the from any ongoing contest. You are given an array of N integers. X[i] is the number of distinct values that occur to the left of index i and not on or to the right of index i. Y[i] is the number of distinct values that occur to the right of index i and not on or to the left of index i. Determine the absolute difference of X[i] , Y[i] for every index 1 <= i <= N. ****Constraint**** 1<=T<=10 1<=N<=2*10^5 -10^9<=Ai<=10^9

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

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

You can't just say

This problen is not the from any ongoing contest

without stating where you got it from. That's extremely sus.

However, I think this is from Ode 2 Code Round 2, which has already ended, so I think it's safe to put a solution here. I won't until someone else confirms it though.

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

    So,if the contest has already ended,then I think you can share your solution.

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

      Put a link to the contest and proof that it has ended, otherwise I cannot let myself post the solution knowing that you may be cheating.

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

    Yeah, I can confirm this is from Ode 2 code only.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Seems to work on my tests, but I don't have ways to verify it) ~~~~~

Spoiler

~~~~~

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

    Although you have added comments in your code but can you plz elaborate your thought process what you have done.

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

      To solve this problem we need to 1) calculate values in array X, 2) calculate values in array Y, 3) get answer by counting absolute differens between |X[i] — Y[i]|.

      Actually method of calculating values in array X and Y is almost the same (you can see that in code, for X we just start from the beginning and for Y from the end). So the only thing we need to understand is how to calculate array X.

      What is the value of the first element X[0]? Obviously it is 0, as there are no items before element at 0 position. And what is the answer for X[1]? If there no elements equal to arr[0] in range [1, n) X[1] = 1, otherwise X[1] = 0. So basicly to find out X[i] we need to know the value of X[i-1] and how many times arr[i] occurs in range (i, n).

      One of the way to do it is using MAP. (if constraints would allow, we actually could use simple array, where at some index j we will keep how many times j occurs in arr (for example if we have arr = [1,2,2,5,4,5,3,5], our array that count how many times each element occurs would be [0, 1, 2, 1, 1, 3]), but we cannot create such big array (10^9) as we will get TimeLimit or MemoryLimit, so we will use map.) Now for some position i we know if element arr[i-1] will occur later in the array. If it will, we don't need to do anything, but if is won't X[i] = X[i-1] + 1. Thats it! I wrote a little bit overcomplicated code, adding easier version with some comments.

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

I thinks maintaining 2 map ( 1 for the left part (initially empty) and other for the right-part (initially contains all elements)) and when you iterate from left to right you have to increase the left[a[i]]++ and right[a[i]]-- ( and when right[a[i]]==0 then just erase it from the right map). and just take the difference between the size of these two map and just print it for each indexes.

I think this will work if i am not wrong.

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

Anyone got test link for round 3?