Here is the link to the the SPOJ problem FREQUENT: https://www.spoj.pl/problems/FREQUENT/ And here is a link to my solution http://ideone.com/7XiVC I used segment trees to solve the problem keeping the left end number/frequency, the right end number/frequency and the maxfreq number/frequency of a segment. But I am receiving a WA. Could anyone tell me the problem.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
I think that your idea is wrong. You better use sqrt-heuristic here.
The sqrt-heuristic(if I understand what it is) would in O(q*sqrt(n)) complexity. Segment Trees should work in O(q*log(n)) complexity. I wonder how the idea would be wrong it actually does give correct answers on the sample cases that I have tried.
Oh, rlly?
There are a lot of things, that you can do via sqrt-heurictic and sqrt-decomposition, but it's impossible (or very difficult) to manage to do it using segment tree.
Your idea is correct. But you mistyped on rows 108-109. At least there are some small mistakes. By the way it is not important which number is the most frequent in whole segment
Is his idea the same as one that we use in finding contigius subsequence with the largest sum that belongs to some segment? If yes, you're wrong...
No, it is not like this. We store for each node of segment tree 5 values: left and right value of segment, their frequences and answer for this segment. With this information we can merge consequent segments in a simple way. Now, if we need to answer query, we select the nodes of segment tree, which cover the interval, and merge them left to right.
If you have to merge these segments: "1 1 1 2 2" and "2 2 3 3 3", what would be the result and how would your merging work?
Maybe code will speak better than words? http://pastebin.com/XEjuaB7w
Isn't the answer 6 for such input? code
16 1
1 1 1 1 2 2 2 3 3 2 2 2 4 4 4 4
1 16
0
It is impossible input since numbers must be in non-decreasing order
Pffff... Sorry, I am blinded... Then solution is really easy and it looks like yours.
can you please tell in this question...
http://www.spoj.com/problems/GSS1/
what should i store at each node ? i have given 11 WA and 4 TLE since last week. can you help me in this ? thanks.
u can store 4 attributes at each node, namely 1- segment sum 2- best sum 3- best prefix 4- best post fix
a[inde].bsum=max(a[2*inde].bsum,max(a[2*inde+1].bsum,(a[2*inde].bpost+a[2*inde+1].bpre))); a[inde].bpre=max(a[2*inde].bpre,(a[2*inde].ss+a[2*inde+1].bpre)); a[inde].bpost=max(a[2*inde+1].bpost,(a[2*inde].bpost+a[2*inde+1].ss));
Thanks a lot knightL. I found the mistake. That was a hard catch.