বুঝতে পারছি এটাতে সেগমেন্ট ট্রি ব্যবহার করতে হবে এবং ফ্রিকোয়েন্সি বা cout এর একটা অ্যারে থাকবে। এরপরে আটকে যাচ্ছি।

সমস্যার লিঙ্ক

asked 03 Apr '18, 09:39

Shaeekh's gravatar image

Shaeekh
868

edited 03 Apr '18, 13:11

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
73618


You can solve this problem using segment tree. If you don't know about segment tree, you may learn it from here or search on google.

Let node[] is an array which stores the information of each node of the segment tree. Each node will store five information in the range which it covers:

  1. left most value in the range(let it be lVal)
  2. right most value in the range(let it be rVal)
  3. frequency of left most value(let it be lCnt)
  4. frequency of right most value(let it be rCnt)
  5. maximum frequency of value in the range(let it be mxCnt)

First the tree building part: When you build the tree, for the leaf node(i.e. node which covers a single index of array), the left most and right most both value will be the value of that index and all the remaining three information(i.e. 3rd, 4th and 5th information above) will be 1.

When you are at any other node which is not a leaf, you have to merge the left and right node to store the information at this node: Let you are at node cur and L is the left node and R is the right node of this node. Then,

  • node[cur].lVal = node[L].lVal
  • node[cur].rVal = node[R].lVal
  • node[cur].lCnt = node[L].lCnt
  • node[cur].rCnt = node[R].lCnt
  • node[cur].mxCnt = max(node[L].mxCnt, node[R].mxCnt)

Now check whether node[L]rVal and node[R].lVal is equal or not. If node[L].rVal equals to node[R].lVal then:

  • node[cur].mxCnt = max(node[cur].mxCnt, node[L].rCnt+node[R].lCnt)
  • if node[L].lVal equals to node[L].rVal, then add node[R].lCnt to node[cur].lCnt
  • if node[R].lVal equals to node[R].rVal, then add node[L].rCnt to node[cur].rCnt

Now the query part:

  • If you are at any node which is outside the range that we are query for then: return -1

  • If you are at such node whose range is fully inside the range that we are query for, then: return node[cur].mxCnt

  • Otherwise recursively find the answer for the node L and node R then merge them to find the actual answer for this node as follows:

Let qL and qR be the answer for the node L and R, respectively. Our answer is(for now) maximum of these two values, i.e. ans = max(qL, qR)

Now, check whether node[L].rVal equals to node[R].lVal or not. If node[L].rVal equals to node[R].lVal then:
ans = max(ans, frequency of node[L].rVal + frequency of node[R].lVal)

Finally, if you are stuck to implement the solution, here is my accepted solution in c++.

permanent link

answered 04 Apr '18, 09:55

shahidul_brur's gravatar image

shahidul_brur
313

edited 04 Apr '18, 10:08

1

@shahidul_brur, প্রশ্ন/উত্তর অবশ্যই বাংলায় হতে হবে। সময় করে উত্তরটি বাংলায় রূপান্তর করে দিন।

(04 Apr '18, 14:13) Mosharraf Hosain ♦
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×131
×54
×36
×18
×14

question asked: 03 Apr '18, 09:39

question was seen: 668 times

last updated: 04 Apr '18, 17:53