Mafia2's blog

By Mafia2, history, 4 weeks ago, In English

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The contest was ODE 2 CODE ,on visiting the site again it says you cannot attend this test as it has already ended.And I don't know how to add screenshot so that I can give you proof.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Now it has been 3 days to post this question and there are so many great coders at this community, so plz anyone can tell me how to solve this question?

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Spoiler

~~~~~

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got test link for round 3?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For each ai, find it's contribution to X[i] and Y[i]. Something like : for ai, all i > last occurence of ai, it will contribute in X. Similarly for Y