notsoawesome's blog

Doubt in problem C-MP3
By notsoawesome, history, 5 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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If you understood please do tell me.

→ Reply
  • »
    »
    4 years 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.net/contest/1199/submission/120241055

    → Reply
»
4 years 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
→ Reply