MikeMirzayanov's blog

By MikeMirzayanov, history, 8 years ago, In English

Welcome to 2016-2017 CT S03E06: Codeforces Trainings Season 3 Episode 6. 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 available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

Visit Codeforces::Gym to find the contest and register.

We are planning to start on October, 12, 2016 13:10 (UTC).

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
  • +43
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve problem I?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    1. We can solve the problem for each connected component independently.

    2. If there is an odd number of vertices in a connected component, there is no answer (otherwise the sum of all degrees in the resulting graph is odd for this component, which is impossible).

    3. Let's find an arbitrary (rooted) spanning tree. Now we can build the answer starting from leaves. For each node, we will do the following: if the number of edges from kids to it is even, we add an edge from this vertex to its parent. Otherwise, we don't do anything. Why does it work? For all vertices, except, possibly, for the root, the answer is correct by design. The sum of all degrees must be even. The sum of all degrees of all vertices except for the root is odd (as the number of such vertices is odd and their degrees are odd). Thus, the degree of the root is also odd.

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

How can I solve problem M ? May be the easiest problem. But I can't it figure out.

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

    Problem M: Idea: Count of reachable numbers less than 10 ^ 9 is small, around 100,000.

    So you can either do a dynamic programming using map<int,bool> dp where dp[i] denotes whether it is a losing state or winning state. A state is winning iff you can reach some losing state.
    DP Using Map
    DP Using Array — since 2, 3, 5, 7 are the possible prime factors of reachable numbers.

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

    I think I have a better solution. Consider the smallest numbers of the form (9^i * 2^i) and (9^j*2^(j-1) which are >= given number n. Take their min and if (9^i * 2^i) is lesser Ollie wins, else Stan wins.

    This works since whenever Ollie wins, steps will be 2*9*2*9*...*2*9 and when Stan wins, steps will be 9*2*9*2*...*2*9.

    So, you can go from right to left in the sequence i.e. start from num=1. Do num*9 and num*2 alternatively till (num < n). If the last step was num*2, Ollie wins, else Stan wins.

    int curr = 1;
    bool flag = 1;
    while (curr < n)
    {
    	if(flag)
    	{
    		curr *= 9;
    		flag = 0;
    	}
    	else
    	{
    		curr *= 2;
    		flag = 1;
    	}
    }
    if (!flag)
    	cout << "Stan wins.\n";
    else
    	cout << "Ollie wins.\n";
    
»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

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

    You can find the probability "No 2 man chose the same color" that probability equals to product of (2 * C — 2 * i) / (2 * C — i) with 1 <= i < M

»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Test data for J is weak. This test: 10 100 9999999...999 (5000 numbers of 9) makes submission from HAT and SkyTeam TLE

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to pass test 3 of problem D ?

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's the problem with this solution for problem H? It gives me WA on test 4.

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

How to solve B?

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

how to solve E ??

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

    Answer doesn't depend on count of ladies.

    Imagine that gentelmens choose colors. Calculate dpi — probability of first i gentelmens to have different colors. Suppose that gentelmens choose from two variants of each color.

    dpi = dpi - 1·pi

    where pi is probability i-th gentelmen to choose new color

    pi = (2·с - 2·(i - 1)) / (2·c - (i - 1))

    Answer is 1 - dpm. We don't need multiply all pi by large m because answer is very small. In my code I calculated i from m - 300000 to m.

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

Problem E was hard to understand for me :(

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

How to solve problem A?