Can anyone pls tell me how to solve this problem
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Can anyone pls tell me how to solve this problem
Name |
---|
someone pls help
Have you read the editorial ? Editorial
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 :(
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.
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?
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
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 :(
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)
this problem is becoming my nightmare..... its too confusing
you are not forced to solve this problem. there are hundreds of problems to think about!
I can understand your feeling dude, I'm trying to solve the last round on SGU now but sucked at one problem too...
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.
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???
for dp(j), you should also consider event(j-1,j),but event(j-1,j-1) is not in dp(j-1).
finally got it.. one thing i must say, man u are a great coder but a very bad teacher :)
I'm a student...not a teacher...