SiddharthBora's blog

SPOJ FREQUENT WA
By SiddharthBora, 12 years ago, In English

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.

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

»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I think that your idea is wrong. You better use sqrt-heuristic here.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

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

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Maybe code will speak better than words? http://pastebin.com/XEjuaB7w

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

            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

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

              It is impossible input since numbers must be in non-decreasing order

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it +7 Vote: I do not like it

                Pffff... Sorry, I am blinded... Then solution is really easy and it looks like yours.

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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));

                  → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot knightL. I found the mistake. That was a hard catch.

    → Reply