yamih23436's blog

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

By yamih23436, history, 3 years ago, In English

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 .

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

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply