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

Interesting Problem : Find the number of subarrays in an array which surely contains a majority element ?

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

This problem is from https://acm.hdu.edu.cn/ I don't have the exact link to the problem though. ![ ](codeforces)

I tried many approaches , either they are in efficient or way too complicated .

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

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

I don't have the exact link to the problem though. ![ ](

How come? Could you add a bigger screenshot, so it would be clear where its from — to be sure it's not ongoing contest?

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

My approach is also linear, but I am not sure how to explain it.my approach was to work on individual element as subarray sum need to be > 0 , to be X as majority element, so assign X as +1 and rest element will contribute -1.so we could make consecutive blocks of 0 and >0 and apply running sum , before this we have to push all identical element in vector array storing their index.
But I guess this is your question
https://dmoj.ca/problem/dmopc20c2p5/editorial

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

This problem's link is: https://acm.hdu.edu.cn/showproblem.php?pid=7020

→ Ответить