### craus's blog

By craus, 8 years ago, translation, ,

Hello!

We're glad to say that at 3.00 PM, October 6 another contest by team Samara SAU Teddy Bears will be held.

This contest was a qualification round for Samara SAU teams. Winners will participate in ACM ICPC 2012-2013. Contest will be easy, a bit easier than our previous contest.

Contest is over. Thanks to coders who participate in it. Now you can start virtual contest (registration by this link), or just solve the problems.

What else:

• Input-output: standard console input-output (like at Codeforces rounds)

• It's not recommended to use %lld for reading and writing 64-bit integers in GNU C++

• +33

 » 8 years ago, # |   +31 Thanks a lot to the following participants for their solutions of problem J: You made my day :D
•  » » 8 years ago, # ^ |   0 Treap?
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Cartesian Tree!Actually, the last one is Splay Tree o_O
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +2 Splay is not too hard, if you understand it. I think i did. Even with complexity analyse. Treap is common only in russia and close contries. Mostly they use AVL or RB, as far as i know. They both have same rotate as Splay. And this is the only hard place to code.
•  » » » 8 years ago, # ^ |   0 Cartesian tree ^_^
 » 8 years ago, # |   0 Can someone explain me why the answer is Constantine in the first sample test in problem H?
•  » » 8 years ago, # ^ |   0 Make sure that you don't miss the word "each" in the statement
 » 8 years ago, # |   +1 I can't understand the sample I/O of problem E. I think the answer is (p + q) / 2,could you please tell me how to get the correct answer?
•  » » 8 years ago, # ^ |   0 Probabilities of choosing the coins before and after the first throw are not equal.
•  » » 8 years ago, # ^ |   +7 It's an application of Bayes' theorem.P(B | A) = P(A |^| B) / P(A) = (1/2 * p * p + 1/2 * q * q)/(1/2 * p + 1/2 * q) P(B) = probability to get heads on the second throw, P(A) — probability to get heads on the first throw. P(A |^| B) — probability to get heads on both throws.So P(B | A) is the probability to get heads on the second throw if we are given that we got heads on the first one.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +1 I see, Thanks a lot! :)
•  » » » 6 years ago, # ^ |   -8 How is getting a head second time after getting head on first throw a dependent event? Pls explain. Shouldn't both be independent events?
 » 7 years ago, # |   0 Could someone give me the editorial for problems of this contest?
 » 6 years ago, # |   0 Pls explain the approach for Problem J — Product Innovation
•  » » 6 years ago, # ^ |   0 Simulation using a linked list.
 » 5 years ago, # |   0 How to solve M
•  » » 4 years ago, # ^ |   +4 Go all vector saving the last occurrence of the value v [i] was in position i, and then for each current position look at it already existed an equal element earlier, if so, create an edge of the current position for this last occurrence. Just make a bfs or dp to find the shortest path.
 » 4 years ago, # |   +3 How to solve problem H? I thought in grundy numbers, but I dont see independent stacks.
 » 2 years ago, # |   0 Why does this submission for problem A TLE Submission ,, is my HashSet causing this TLE?
•  » » 2 years ago, # ^ |   0 Yes
•  » » » 2 years ago, # ^ |   0 How to solve this problem, then any hints?
 » 6 weeks ago, # |   0 Why isn't Grundy working for H? How to approach this one?