red_coder's blog

By red_coder, 12 years ago, In English

Can anyone pls tell me how to solve this problem

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

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

someone pls help

»
12 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

I know , you are dissatisfied of the bad explanation of editorials in codeforces same as me!

I also know that my comment will get bad rating :(

»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I'm sorry about that,It's my first time to write a formal editorial so maybe I can't do very good...well,which part in the editorial you can't understand?You can point it out and I'll try to make it clear.

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

    dp(j)=(dp(j-1)+pj - 1)*pj What does this formula mean? And after calculated this dp, what should I do to calculate the final result?

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

      I've said that dp(j) means that the sum of all event like event(i,j) where i<j.

      so for dp(j), event(i,j-1)*p(j)=event(i,j),and we add the event(i-1,i),that make this formula working.

      the result is just (sum of p)+(sum of dp)*2

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

        i got your first point n^2= C(n,2)+n. But why u said we have to consider only those pair of O's having no X between them. Suppose we have OXXO then why cant we consider first O and last O as a pair. Next thing which confused me was how via dp u calculated all that stuff.. dp(j)= (dp(j-1)+pj-1)*pj... and one thing more, i asked u to give me some link so that i can contact u if in some trouble and u gave me some weird link of ask.fm. Dont u have any facebook account or any email id. I am too much frustated :(

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

          I think because if pair of O's has one or more X's between the solution will consider each one of O's separately

          for example if we have OXXO then we will consider two events the first is event(1,1) and the second event(4,4)

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

            this problem is becoming my nightmare..... its too confusing

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

              you are not forced to solve this problem. there are hundreds of problems to think about!

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

              I can understand your feeling dude, I'm trying to solve the last round on SGU now but sucked at one problem too...

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

          in "OXXO"...so the answer obviously is 2,right?

          if you consider the first and last one, it will go wrong of course.

          I mean,in a consecutive O's block,the number pair of O *2 +the number of O is equal to n^2...so the pair of O should be in the a O's block with no 'X' in it.so of course there's shouldn't be any 'X' between them.

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

            tell me one thing... if dp(j) contains sum of all event(i,j) then dp(j-1) contains sum of all event(i,j-1) and since event(i,j-1)*pj= event(i,j) then dp(j)=dp(j-1)*pj but according to u dp(j)= (dp(j-1)+pj-1)*pj. why???

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

              for dp(j), you should also consider event(j-1,j),but event(j-1,j-1) is not in dp(j-1).

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

                finally got it.. one thing i must say, man u are a great coder but a very bad teacher :)