craus's blog

Codeforces Gym: Samara SAU ACM ICPC Quarterfinal Qualification Contest
By craus, 12 years ago, translation, In English

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

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

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

Thanks a lot to the following participants for their solutions of problem J:

You made my day :D

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

    Treap?

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

      Cartesian Tree!

      Actually, the last one is Splay Tree o_O

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

        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.

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

      Cartesian tree ^_^

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

Can someone explain me why the answer is Constantine in the first sample test in problem H?

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

    Make sure that you don't miss the word "each" in the statement

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

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?

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

    Probabilities of choosing the coins before and after the first throw are not equal.

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

    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.

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

      I see, Thanks a lot! :)

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      How is getting a head second time after getting head on first throw a dependent event? Pls explain. Shouldn't both be independent events?

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

Could someone give me the editorial for problems of this contest?

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

Pls explain the approach for Problem J — Product Innovation

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

How to solve M

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

    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.

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

How to solve problem H? I thought in grundy numbers, but I dont see independent stacks.

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

Why does this submission for problem A TLE Submission ,, is my HashSet causing this TLE?

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

Why isn't Grundy working for H? How to approach this one?

→ Reply