notsoawesome's blog

By notsoawesome, history, 2 years ago, In English

Hello everyone, with the help of you guys and helpful blogs, I am able to solve A and B pretty much every time, and most of the time C too(Div >=2 of course).

Here is the problem->Contest #576 Div2 C-MP3

And here is my code->here

For those of you who don't want to see code, here is what I did

-made vector of distinct intensities(which is sorted)

-maintained a freq map for frequency of those intensities

-while the condition of the bits is not satisfied, greedily removed the digits from left and right using two pointers

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

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

If you understood please do tell me.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you had same problem, the algorithm is sub-optimal with the greedy approach, If the hints are not enough, the logic is to find the exact no. of distinct bits needed to be in the disk, and then we just traverse that consecutive bits and find the minimum(if the maximum sum of consecutive bits = x then ans=n-x)

    https://codeforces.com/contest/1199/submission/120241055

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

same problem, please help

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Stupid question, now I have revisited and also a couple of people have the same doubt, good to see that.

I believe now I have solved similar reactions from you :)

Coming to the doubt, the above method is good except that greedy approach. now that I have mentioned that there is error in the logic you can think accordingly

Hint 1
Hint 2
Hint 3
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For those who are stuck with the 2 pointer approach, Consider this testcase :
13 I
1 1 1 1 2 3 3 4 4 4 5 5 5

Suppose the value of I is tuned in a way such that we have to remove 2 distinct values from either side of the array. If we take the 2 pointer approach, then it will remove the 4's and 5's from the right side = removing 6 elements. Whereas the optimal answer is removing 1's and 2's from the left side = removing 5 elements.