MikeMirzayanov's blog

2014-2015 CT S02E09: Codeforces Trainings Season 2 Episode 9
By MikeMirzayanov, 10 years ago, translation, In English

Welcome to 2014-2015 CT S02E09: Codeforces Trainings Season 2 Episode 9 - 2006-2007 ACM-ICPC Northeastern European Regional Contest (NEERC 06). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

Good luck!

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

»
10 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

hello everyone!! can you help me??

why in the problem I : Interconnect the answer for the second case is 1.5

input

4 2

1 2

3 4

output

1.5

???

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

    With probability , we'll connect 1-2 or 3-4, leading to the same connectedness. With probability , we'll connect 1 or 2 with 3 or 4. Therefore, the expected time is .

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

      thanks you !! I get a accepted

      I thought who E = 1/3 * ( E ) + 2/3 -> E = 1

      thanks you!!

      I solve this problem with memorization with map<vector,double> are there some best idea??

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

        I used map<hash(vector),double> and another map<hash(vector),vector> to find out which vector it is.

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

          map<hash(vector),double> mean who

          if I have the states

          vector = {1 , 2 , 3} = HASH( ( 1*B^2 + 2*B + 3) % MOD )

          for some B , MOD

          right?

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

            Yes, for example polynomial hash.

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

              thanks you again : ) !!! can you get me your email ??

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

                It is where it's always been.

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

This contest is a duplicate of 2006-2007 ACM-ICPC Northeastern European Regional Contest (NEERC 06)

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

How to solve problem I?

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

    I did it with dynamic programming. First I used disjoint sets (or connected components would work fine) to calculate the sizes of all the connected components of the graph. Then, my recursive dynamic programming state was a sorted list of those sizes (the total number of states is somewhere around the 30th partition number. At each state I did the following sum:

    For each pair of element of my list of sizes, the number of edges I could add is just the product of their sizes — call this p. Since there are n choose 2 total edges in the graph, the probability that I connect these components is p / (n choose 2). So I add to my sum p / (nchoose 2) * (1 + dp(new list with these components combined)).

    However, if I add up the probabilities for all of these combinations, they may not sum to 1 since there's the case when I add in an edge to the same component. For this, just observe the following formula, letting x be the probability that I choose two nodes in the same component: dp(list) = (sum above) + x * (1 + dp(list))

    This can be rewritten as dp(list) = ((sum above) + x) / (1 — x)

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

      You need to link with http://, or it'll be considered an inner (to CF) link.

      It's pretty much just bruteforce — listing all possible states (multisets of component sizes).

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

How to solve C ? I've found solution using matrix multiplication, but size of matrix is too large and, of course, I get TLE on test 9.

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

    You can calc only one row from matrix, all others will be same with shift. O(lg(K)*N^2)

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

Is there any Editorial for this contest

→ Reply