McDic's blog

By McDic, history, 5 years ago, In English

Sorry for such difficulty balance. Here is the editorial.

Tutorial is loading...

Solution Code for A

Behind story of B: Original B was harder. None of 2100+ rated testers solved original B, so it got downgraded. Also there was more than 15 pretests before.

Tutorial is loading...
Solution Code for B

Behind story of C: C is created before few days to contest. If there was no current C, the contest would have hell balances.

Tutorial is loading...
Solution Code for C

Behind story of D: Honestly I predicted D as hell hard problem. But other high rated people said it's not that hard.

Tutorial is loading...
Solution Code for D

Behind story of E: I didn't expected such well-known problem. My solution for E is more complicated.

Tutorial is loading...
Solution Code for E

Behind story of F: This problem was located at D originally.

Tutorial is loading...
Solution Code for F
  • Vote: I like it
  • +102
  • Vote: I do not like it

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

what a cute maths in e and f. It looks like i will learn whole maths from codeforces itself and even surpass rng_58 .. LOL.

D is a nice problem .

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

Wow very fast editorial :D

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

Woah. That was fast.

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

C made me sad :[

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

Why my solution for C (id:55462095) wasn't judged when I submit at 01:59:45?

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

McDic "Behind story of E: I didn't expected such well-known problem. My solution for E is more complicated."

what u mean by it. as u were the setter of this problem and u r urself saying i didn't expected?

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

    My intended solution was much harder than tester's solutions

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

Great problems. Fast editorial. Please set more rounds McDic.
Also, what does balance mean?

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

    Difficulty balance. See number of solvers for each problem.

»
5 years ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

Anybody can tell me please, if my code for E is wrong in idea or there is a bug??

code

All ready functions are copied from the net or from old codes. Where "solve" function gives the discrete log. full code

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

Wow a fast editorial

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

arsijo pls stop creating problems (c)

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

Is test case weak or this is correct?

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

    gamegame said this is so slow for some cases. I'm sorry about that. (I put some of countercases that some solutions work too slow for it)

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

    It will get TLE on following case:

    1
    1 10000000 1 1000000000
    

    I feel shame that I using this method to pass problem F in the contest (>__<)

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

Do other people also feel that this contest wasn't balanced.

»
5 years ago, # |
Rev. 2   Vote: I like it +142 Vote: I do not like it

Alternate (easier) solution for E: $$$5$$$ is a primitive root modulo $$$10^9+7$$$. So, for every number $$$x$$$ in $$$(0, 10^9+7)$$$ there exists $$$p$$$ such that $$$5^p\equiv x \pmod {10^9+7}$$$. This is known as Discrete Logarithm and can be calculated quickly with Shanks algorithm.

Now, lets take discrete $$$\log_5$$$ in both sides of the recurrence:
$$$\log_5(f_n) = (2n-6)\log_5(c) + \log_5(f_{n - 1}) + \log_5(f_{n - 2}) + \log_5(f_{n - 3})$$$

If we let $$$F_n = \log_5(f_n)$$$, $$$C = \log_5(c)$$$, and $$$g_n = 2n - 6$$$, then it transforms into:
$$$F_n = g_n C + F_{n - 1} + F_{n - 2} + F_{n - 3}$$$

We can calculate $$$F_n$$$ directly via matrix exponentiation and then calculate $$$f_{n} = 5^{F_{n}}$$$.

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

    This one is much more straightforward and natural in some sense.

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

    Even simpler solution: $$$f_n = c^\alpha f_3^\beta f_2^\gamma f_1^\delta$$$ for some exponents $$$\alpha$$$, $$$\beta$$$, $$$\gamma$$$ and $$$\delta$$$, which according to Fermat's little theorem need to be known modulo $$$P-1$$$ for $$$P=10^9+7$$$. Thus first calculate exponents using fast matrix exponentiation modulo $$$P-1$$$, and then calculate powers using fast exponentiation modulo $$$P$$$.

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

      how to calculate the exponent of C using dp recurence? that was the main problem, the rest are easy.

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

        You have recurrence $$$\alpha_n = \alpha_{n-1} + \alpha_{n-2} + \alpha_{n-3} + 2n-6$$$ which can be rewritten as $$$\alpha_n = \alpha_{n-1} + \alpha_{n-2} + \alpha_{n-3} + 2\varepsilon_{n-1} - 6$$$ and $$$\varepsilon_n = \varepsilon_{n-1} + 1$$$. Then use matrix of size $$$5\times 5$$$ to calculate vector $$$(\alpha_n, \alpha_{n-1}, \alpha_{n-2}, \varepsilon_n, 1)$$$.

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

          OMG thank you very much. I just got stuck at the power of C, now i get it thanks.

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

          You still able to make this easier:

          $$$\alpha_n = \alpha_{n-1} + \alpha_{n-2} + \alpha_{n-3} + 2n - 6$$$

          and

          $$$\alpha_{n-1} = \alpha_{n-2} + \alpha_{n-3} + \alpha_{n-4} + 2(n-1) - 6$$$
          $$$\alpha_{n-1} = \alpha_{n-2} + \alpha_{n-3} + \alpha_{n-4} + 2n - 8$$$

          If we compute the difference:

          $$$\alpha_n - \alpha_{n-1} = \alpha_{n-1} - \alpha_{n-4} + 2$$$

          and we get the following easy recurrence:

          $$$\alpha_n = 2\alpha_{n-1} - \alpha_{n-4} + 2$$$
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What to do after building recurrence

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

              Compute the values for the value of n that you need. You can solve this in O(log n), search about computing values of linear recurrences using matrix exponentiation.

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

                but how to form transformation matrix. any pattern to follow for it.

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

            I think we can do even better, since getting rid of constants is generally helpful. As you said:

            $$$\alpha_n = 2\alpha_{n-1} - \alpha_{n-4} + 2$$$
            $$$\alpha_{n-1} = 2\alpha_{n-2} - \alpha_{n-5} + 2$$$

            If we compute the difference:

            $$$\alpha_n - \alpha_{n-1} = 2\alpha_{n-1} - 2\alpha_{n-2} - \alpha_{n-4} + \alpha_{n-5}$$$

            and, cleaning up, we get the following recurrence:

            $$$\alpha_n = 3\alpha_{n-1} - 2\alpha_{n-2} - \alpha_{n-4} + \alpha_{n-5}$$$
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          For $$$b_n = \alpha_n + n$$$ recurrence takes the same form as for $$$f_1,f_2,f_3$$$.

          $$$b_n = b_{n-1} + b_{n - 2} + b_{n-3}$$$
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Since, $$$2n-6 = 0, 0, 0, 2, 4, 6, 8, 10, 12, ......$$$ then, $$$α_n=α_{n−1}+α_{n−2}+α_{n−3}+ε_n$$$ and $$$ε_n=ε_{n−1}+2$$$, where $$$ε_1=ε_2=ε_3=0$$$ and $$$α_1=α_2=α_3=0$$$

          Update: I got AC with this idea.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Can you explain your matrix please? $$$a_{n - 2}$$$ = 0 * $$$a_n$$$ + 0 * $$$a_{n - 1}$$$ + 1 * $$$a_{n-2}$$$ + 0 * $$$g_n$$$ + ???(5th)

            I wonder what is the fifth elements in this matrix ?

            Edit: Oh,nevermind,just silly me.

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

        \alpha can be translated to, say

        we define theta_n = alpha_n + n we have theta_n = theta_n-1 + theta_n-2 + theta_n-3

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

      cool solution, we don't need to worry about finding primitive roots .

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

      Learnt a lot from your solution.

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

      Can you explain why it is P-1?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      How do you calculate $$$\beta, \gamma, \delta$$$? My original thought was that $$$\beta_n = \beta_{n - 1} + \beta_{n - 2} + \beta_{n - 3}$$$, but this would give the same recurrence for $$$\beta, \gamma, \delta$$$ (and hence they'd all have the same result).

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

        Yes, recurrence is the same, but initial conditions are different: $$$\beta_0 = 0, \beta_1 = 0, \beta_2 = 1$$$, but $$$\gamma_0 = 0, \gamma_1 = 1, \gamma_2 = 0$$$, and $$$\delta_0 = 1, \delta_1 = 0, \delta_2 = 0$$$.

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

      can you please explain the meaning of which according to Fermat's little theorem need to be known modulo P−1. During fast matrix exponentiation, why should we take modulus P-1 instead of P

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

      It's also possible to combine the editorial approach with monsoon's approach, avoiding either prime decomposition or needing to find $$$c$$$'s exponent separately. Define $$$g_x = c^x f_x$$$, then find the exponents modulo $$$P-1$$$ in $$$g_n = g_3^\alpha g_2^\beta g_1^\gamma$$$ using matrix exponentiation, then compute $$$f_n = g_n c^{-n}$$$.

      For those unfamiliar with how to use matrix exponentiation to solve this kind of recurrence relation, I had to learn that too, and I found this tutorial helpful.

      Sample code (Kotlin): 61375355

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

    I'm trying to follow along with this approach but my math is not working out, could you help me find where I'm going wrong?

    Consider the case:

    n = 4, f1 = 1, f2 = 2, f3 = 5, c = 3, and modulo 1e9+7

    log5(f1) = 0

    log5(f2) = 381838282

    log5(f3) = 1

    log5(c) = 884237698

    We get for log5(fn) = (2*884237698+1+381838282+0)%mod = 150313665

    5^150313665 % mod = 200000005 , which isn't the answer (should be 90).

    What did I do wrong?

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

    Why can we calculate $$$F_n$$$ directly via matrix exponentiation? Isn't the $$$g_nC$$$ term still troublesome? Are you transforming $$$g_n$$$ into a recurrence like on monsoon's comment?

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

      We can carry that $$$g_n$$$ term with the matrix. I think it is quite well known approach for doing matrix exponentiation simultaneously for 2 recurrences. For example if you have: $$$f_n = f_{n - 1} + g_{n - 1}$$$ and $$$g_n = f_{n - 1} + 2g_{n - 1}$$$, you can make something like this:

      $$$\begin{bmatrix}1 & 1 \\ 1 & 2 \end{bmatrix} \times \begin{bmatrix}f_{n - 1} \\ g_{n - 1}\end{bmatrix} = \begin{bmatrix}f_n \\ g_n \end{bmatrix}$$$
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I misunderstood the problem statement of B and thought that this example yields a YES :(

.*.
***
.*.
...
.*.
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is no a ray of consecutive non-empty cells from the center of your "+" to the non-empty space at the very bottom of your example.

    Thus, the example violates the All other cells are empty condition.

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

What was the harder (original) version of B?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    The width of the vertical stripes and the length of the horizontal stipes are the same everywhere. For example:

    ..***..

    ..***..

    .*****.

    .*****.

    ..***..

    YES

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

      Can you explain more? I am getting WA at 15.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        There is a mistake in your variable “NoIsland”. You don’t increase it sometimes. Test:

        3 5

        .*.*.

        ..***

        ...*.

        Your output will be YES.

        So, u can find the plus, then u must paint it. Now, u can check, that there is no unpainted *

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

          Good catch. But why answer is YES in above example?

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

            Your program’s output is “YES”. But real answer is “NO”.

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

              Sorry I am talking about the star example you posted above.

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

                Anand asked the original version of task. And this test was for the original version. (There is a simplified version in the round.)

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

                  Oh you mean for this problem answer should be "NO"?

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

                  Yes. Answer should be “NO”.

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

                  Thanks man. I solved it using coloring now.

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

                Sorry for misleading you)

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

      Also holds h,w<=500?

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

        Yes

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

          It seems not so hard...I think it can be solved with h,w<=2000.

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

            Yes, it is real not so hard. But u need more time to solve it.

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

    Check out Stars Drawing(Hard version).

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

Can you please give us your implementation of E, it will be mush easier to understand the solution this way.

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

Am I the only one who solved D using hashes and DP on tree?

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

    I used hashing as well, but no DP required.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you guys tell me what is hashing on trees or send any blog to understand Sharon lessmeaning

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

        Hashing subtrees is similar to hashing strings. To hash a node I just sort the children by their hash, concatenate them in sorted order and concatenate number of children as well. That should represent a unique subtree.

        Though in this problem I believe I forgot to sort the children, so its probably possible to break my code. Doesn't matter since I didn't solve it in contest anyway.

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

      How did you solve with Hashing only, i also had to use DP on tree.

      Sharon can you please illustrate

»
5 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Solution for E in log N * 5 ^ 3: Just count powers of f1, f2, f3 and c in which they appear in fn, so now our modulo will be 1e9 + 6.

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

    How to calculate power of c?

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

      Let Xi = numer of c's in Fi (Xi, Xi + 1, Xi + 2, C, 2) * M = (Xi + 1, Xi + 2, Xi + 3, D, 2) D = C + 2 and calculation of X is standard.

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

McDic maybe problem E is well known problem, because problem 1106F were before it. Why problem E is a 2250-point problem, if problem 1106F is 3000-point problem?

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

    I predicted there would be not so big gap between D and E, that's why I gave E 2250.

    Also I don't used discrete logarithm for my solution.

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

    Lesson from that: Upsolve problems as much as you can — you never know when a familiar problem would pop :)

»
5 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

There is another solution for problem D that finds the answer by rooting the tree at every node.
Suppose you have rooted the tree at node $$$1$$$. Now, for each node $$$u$$$, you have to find whether the subtree rooted at $$$u$$$ is valid or not (valid means if we ignore the rest of the tree, $$$u$$$ can be an answer). This can be done recursively. Let's define a string $$$s(u)$$$ for each $$$u$$$. If $$$u$$$ is leaf, $$$s(u)$$$ = "1" and $$$u$$$ is a valid node. Otherwise, for each child $$$v$$$ of $$$u$$$ if $$$s(v)$$$ is same, then $$$u$$$ is a valid node and $$$s(u) = s(v) + deg(u)$$$ for some $$$v$$$. For each valid node $$$u$$$, we calculate $$$s(u)$$$. We can't actually store the string in $$$s(u)$$$, right? Instead we will be storing the hash value of the string $$$s(u)$$$.

Now if node $$$1$$$ was valid, we can say it can be the root. If it is not, we will root at one of its child $$$v$$$. This way we will root the tree at every possible node. The only information we will be missing for a root $$$v$$$ will be the string for the parent $$$u$$$ (when $$$1$$$ was root) of $$$v$$$. We can calculate this information when going to $$$v$$$ from $$$u$$$ the same way we calculated $$$s(u)$$$. I have used a multiset for this. There might be a way to avoid the multiset, but I didn't feel the need to.

Code: 55462817
Complexity: $$$O(nlogn)$$$

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

It was also possible to cut through the tests of problem D like this: 55463619

»
5 years ago, # |
Rev. 6   Vote: I like it +10 Vote: I do not like it

Alternatively, for E. call $$$p = 10^9 + 7$$$, we need to find $$$f_n \mod p$$$.

Set $$$g_n = n + \log_c f_n$$$. We get the recurrence relation

$$$g_n = g_{n-1}+g_{n-2}+g_{n-3}.$$$

By Matrix Exponentiation, compute $r_1, r_2, r_3 \mod p - 1$ such that $$$g_n = r_1 g_1 + r_2 g_2 + r_3 g_3$$$.

Now, our final answer $$$f_n$$$ will be

$$$f_n = c^{g_n - n} = c^{r_1 g_1 + r_2 g_2 + r_3 g_3 - n} = (c^{g_1})^{r_1} (c^{g_2})^{r_2} (c^{g_3})^{r_3} c^{-n} = c^{r_1 + 2 r_2 + 3 r_3 - n} f_1^{r_1} f_2^{r_2} f_3^{r_3}.$$$

The time complexity will be $O\left(\log(n) + \log(r_1) + \log(r_2) + \log(r_3) + \log(r_1 + 2r_2 + 3r_3 - n)\right)$. Note that $$$r_i$$$ will be exponential in $$$n$$$ but since we are calculating the exponent modulo $$$p$$$ it is effectively $$$O(\log(n) + \log(p - 1))$$$ for all purposes.

Make sure to calculate $$$r_1, r_2, r_3$$$ modulo $$$p - 1$$$ and not modulo $$$p$$$ (because Fermat's Little Theorem). I made this exact mistake during the contest, cost me the entire problem and a possible top 50 rank FML. :(

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

    Could you explain why it is P-1, also can you share any resource if possible? Thanks!

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry for the late reply, I generally don't come online on codeforces.

      So basically note that we need to find $$$x^k \mod p$$$ for some $$$x, k$$$ where $$$p$$$ is a prime. Thus, by Fermat's Little Theorem, we have that $$$x^{p - 1} = 1 \mod p$$$ hence, $$$x^k = x^{k - (p - 1)} \mod p$$$ since we can just $$$x^{p - 1} = 1$$$ to show that it is equal to the RHS. Thus, $$$x^k = x^{k - q(p - 1)}$$$ where $$$q$$$ is any integer, which is equivalent to show that $$$x^k = x^{k \mod p - 1} \mod p$$$ since we can represent $$$k \mod p - 1$$$ is the remainder $$$r$$$ when we divide $$$k$$$ by $$$p - 1$$$ and we can write $$$k = q(p - 1) + r$$$ for some $$$q$$$ by the definition of remainder.

»
5 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Please explain solution for problem D. For ex.  0 can be root. But we can't select root with degree 1 (for example 4) as root.

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

    In this case 0 is the semitop and there is no top.

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

      I see thx.

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

      Same with this picture, but there is no vertex 1 and its subtree. 0 can be the root, but others can't.I think 0 is neither top vertex nor semi-top vertex.

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

      Hello, I apologize for the dumb question, but why doesn't this strategy work for D? Do bfs bottom up starting with a layer of all vertices with degree one. For each layer, check that all vertices in the layer have the same degree. But (only once) if there is just one vertex with different degree, and it has only one leaf descendent, set that leaf aside because it might be the root. Continue until you reach the top of the tree. (And maybe check that one vertex you set aside.)

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

        My first approach is same as your approach, but it might require tricky implementation and tricky case handling. So I changed my strategy.

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

Different way to think about D: suppose that $$$r$$$ is the selected root. For any edge $$$u \rightarrow v$$$ such that $$$u$$$ is closer to $$$r$$$ than $$$v$$$, the subtree below $$$u \rightarrow v$$$ can be described by a sequence of pairs [next branching factor > 1, distance to next branching factor > 1]. That's because anywhere the subtree branches, all children should be isomorphic.

The number of pairs in that representation is limited by $$$log(N)$$$. We can do a standard tree dp and compute the condensed representation (or detect that one doesn't exist) for each of the $$$2N - 2$$$ subtrees of the original tree. The final answer is any root such that each of its child subtrees have the same representation.

My implementation can be found here.

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

    This is one of those solutions that seem so obvious when it's explained. And yet I spent an hour trying to get around the O(N) representation :p

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

Why do we have to iterate over prime divisors in E? Can't we just calculate the power of f1, f2 and f3 contained in fn the same way?

»
5 years ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

My solution to E:

$$$ \log_C F_i= \log_C F_{i-1} + \log_C F_{i-2}+ \log_C F_{i-3} + 2i-6 $$$

We can get $$$\log_C F_n$$$ in $$$O(\log n)$$$ ,then easy to get the result.

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

can someone explain c more vividly? what they mean in "If you want to form a beautiful lyric with 4 words, then the lyric must be one of the things listed below;

Consist of two complete duos. Consist of one semicomplete duo and one complete duo."

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

    if complete duo means same number of vowels + same last vowel
    and semicomplete means same number of vowels only
    Then yeah, it's just like you wrote

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

which is correct order of lyrics in C? give me 4 word(just complete duo semicomplete duo)

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

"the furthest directly reachable leaf node from semitop, and the closest directly reachable leaf node from semitop. It is guaranteed that the top node is one of those two leaves."
I don't understand why one of those have to be the top

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

    McDic It can't be that all leaves are at the same distance from semitop? Or what am I missing?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Directly reachable nodes are the only nodes that you can find from only $$$degree = 2$$$ nodes. If there is only one node in inner tree, then all leaves including top node can be directly reachable leaves.

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

Thank you for an interesting contest! Can you please put some solutions in the editorial? The problems are well explained but it will be a good thing if you'll show the solutions.

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

I don't know why, but i misunderstood the condition of problem A at first :D. It took me a while to realise how simple it is. :))))

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

Actually, I misread problem C the first time, and I'm still wondering how to solve it.

I thought there could be more than two words in a line of a lyric.

Can anyone help me on this modified problem?

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

    Do you need help on your "more than two words" problem , or the C problem ? I'm not even sure how the "more than two words" problem would work, the goal of C is to get as many lyrics as possible, and not as many same vowel words as possible.

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

      The mote than two words problem is what I’m asking

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i did the same thing and find i misunderstood until see this editorial. struggle for it the entire contest. since my misread solution can pass until pretest 16 that i didn't found i misread.

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

      Could you give me some hint about the misread problem? I'm still wondering

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        it was a wrong solution. i just do same approach as editorial but after that two filter, there are some words left with same end of vowel can form pair of 3rd words. but it will broke when i have too many same vowel amount pair and have to break some of pair to form 3rd word pair.

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

C. Beautiful Lyrics: What about the O(N) implementation in the problem C? I did it with an array of maps : map<char,vector<string>>mp[1000002]; so in the i'th position i have a map with all the words that contain i vowels. In that map the kth element (k is a vowel) is a vector with the strings that the last vowel is k. There is my solution:55461952

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

So many approaches for D and E is very nice, it makes problem look natural rather than derived from technique.

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

I provided all solutions. Thank you.

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

    It says you are not allowed to view the page when clicking on solution link

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

      Hmmm.. Why is this happening O_o I will try to solve this issue

»
5 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I used same approach for C, it's failing for testcase 7 and I'm unable to find the bug.

Code

Sorry for the messy code :/

UPD — Found the testcase.

Testcase 1
Testcase 2
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In D we may just find a centroid, and when find the path of two-degrees vertices, the end of this path need to be a root.

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

Why we use only sqrt(n) numbers in problem f?

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

    Divide $$$[a, b]$$$ to $$$sqrt(n)$$$ blocks, and it's possible to search all area using only one block because of properties of modulo operation.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

IN problem E, let power of c in f(n) be g(n). So, g(n) = 2 * n — 6 + g(n — 1) + g(n — 2) + g(n — 3). This could be done through matrix exponentiation.

Let matrix m be = {(1 , 1 , 1 , 2 , -4) , (1 , 0 , 0 , 0 , 0) , (0 , 1 , 0 , 0 , 0) , (0 , 0 , 0 , 1 , 1) , (0 , 0 , 0 , 0 , 1)}

Now {g(n) , g(n — 1) , g(n — 2) , n , 1} = m * {g(n — 1) , g(n — 2) , g(n — 3) , n — 1 , 1}

Similarly we can find powers of f1 , f2 and f3. Is E possible to solve in this manner?

P.S. :- I am asking this question because I am not able to solve this question.

P.S.2 :- Thanks. I solved the question.

»
5 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Sadly, my solution for B didn't make it after the contest because I didn't check that with a test case like:

3 3
.*.
**.
.*.

My function to find the center of the '+' would check for posible centers at i = 2, j = 1, thus checking in the array a position that didn't exist (i + 1, j).

It was easy to solve though, it was just changing if(i == x) return false; for if(i == x - 1); but it's kinda sad, since I usually have a hard time with B problems and this was the first time I got one with pretests passed in a Div 2.

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

Can anyone help me with this tle on problem C: https://mirror.codeforces.com/contest/1182/submission/55471836

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

D can be "solved" without thinking too much. While less than 0.7s has passed pick at random two vertices which have different degrees and are even distant apart, find midpoint of path between them, and call it $$$y$$$. Suppose we root the tree at $$$x$$$. Vertices in subtree containing vertex $$$a$$$ are closer to $$$a$$$, in vertex containing $$$b$$$ are closer to $$$b$$$, all other are equal distance from $$$a$$$ and $$$b$$$, so since $$$a$$$ and $$$b$$$ have different degrees cannot be our sought root. Those vertices form either a subtree or complement of subtree if we have vertex rooted at $$$1$$$, so we can mark all of them as impossible by just adding $$$\pm 1$$$ to one of those vertices or the root and then considering only vertices for which sum of values on the path to root is $$$0$$$ as valid. After that just check all such vertices with basic dfs. To do all this efficiently we need some basic implementional tricks. 55472896

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

I jumped up from rank 3500 to rank 2500 purely because of B hacks and system tests.

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

It says that i'm not allowed to view the requested page when i click to the solution. What is the problem?

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

    If you need the code for a certain problem, just go to Standings and search for code that suits your needs, usually the high-ranked users have the same/better code as/than editorial's.

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

      Yeah, you're right. I already analyzed some solutions on problem C. This problem is not so hard,but there is a lot of stuff to do and it gets a little tricky. That's why i was curious about the editorial.

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

I found a similar solution to E, that worked when I upsolved the problem. Let $$$g_n$$$ denote $$$c^n f_n$$$. Then we have $$$g_n = g_{n-1} g_{n-2} g_{n-3}$$$, and thus for all $$$n, g_n = g_1^{x_n} g_2^{y_n} g_3^{z_n}$$$. Then the recurrence satisfied by $$$x_n, y_n, z_n$$$ is $$$x_n = x_{n-1} + x_{n-2} + x_{n-3}$$$, and same for $$$y, z$$$. Now use matrix exponentiation modulo $$$10^9+6$$$ to find the reduced exponents, and this enables us to find $$$g_n$$$ using the formula above. Then we find $$$c^{-n} g_n$$$ using inverse of $$$c^n$$$, and thus we're done.

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

    How you find transformation matrix.

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

      Consider the following three equations:

      $$$x_n = 1 \cdot x_{n-1} + 1 \cdot x_{n-2} + 1 \cdot x_{n-3}$$$
      $$$x_{n-1} = 1 \cdot x_{n-1} + 0 \cdot x_{n-2} + 0 \cdot x_{n-3}$$$
      $$$x_{n-2} = 0 \cdot x_{n-1} + 1 \cdot x_{n-2} + 0 \cdot x_{n-3}$$$

      This gives the required matrix, upon comparing with the product of a matrix and a vector.

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

    Can you explain why it is 10^9 + 6 and not 10^9 + 7? Also could you share any resource? Thanks!

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

McDic how you came up with the formula for g(x,p).

Can you explain why it will be sum of remaining three.

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

    Because $$$a^p \times a^q = a^{p+q}$$$

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Moved to a different post this

»
5 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

I think problem E can be done by matrix multiplication,and it is easy to think. Let $$$f_n=f_1^{a_{n-3}}\cdot f_2^{b_{n-3}}\cdot f_3^{c_{n-3}}\cdot c^{2d_{n-3}}$$$,then $$$a_1=1,a_2=1,a_3=2,a_n=a_{n-1}+a_{n-2}+a_{n-3}$$$,

$$$b_1=1,b_2=2,b_3=3,b_n=b_{n-1}+b_{n-2}+b_{n-3}$$$,

$$$c_1=1,c_2=2,c_3=4,c_n=c_{n-1}+c_{n-2}+c_{n-3}$$$.

$$$d_1=1,d_2=3,d_3=7,d_n=d_{n-1}+d_{n-2}+d_{n-3}+n$$$

And we can use Fermat's little theorem to modulo them with 1e9+6

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

why i am not able to see solution code. whenever i am clicking on solution page than it show you are not allowed to view requested page

»
5 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

We could solve D by the following observation : if the answer exists and is not the center of the tree, then it must be one of the leaves.

Proof :

Denote : dist(u,v) is distance from node u -> node v

Let two ends of the diameter of the tree is end1, end2, and the length of the diameter is d. Obviously end1, end2 are leaves.

Let k leaves in the tree be L1, L2,..., Lk. Suppose end1 = L1, end2 = L2.

Let the root we are looking for be x. If x is not one of the leaves then all dist(x, Li) must have the same value.

1, if d is odd, there is no such non-leave node u satisfies all dist(u, Li) is equal.

2, if d is even:

a, If k==2 then all L1, L2 and center is the answer, nothing else.

b, If k>=3 then if x is not the center nor leave, then there must be a leave Li (i>=3) such that the path x->Li does not intersect with the diameter. Because dist(x, Li) = dist(x, L1) = dist(x, L2). Then we could easily prove that one of two following inequalities must be true :

b.1) dist(Li, L1) > d.

b.2) dist(Li, L2) > d.

So in this case we find a path which length is larger than the diameter -> contradiction.

Therefore in two cases, if the answer exists then either the center or the leaves must be the answer (q.e.d)

Which nodes should we check ?

1, Both ends of the diameter, which is L1 and L2

2, The center

3, A leave Li such that dist(Li, L1) = dist(Li, L2). Here we can infer that center must exist in the paths from L1 -> Li and from L2 -> Li

3.1) if dist(Li, L1) < d. We will prove that if Li is not the answer, then the answer doesn't exist at all:

Proof : If Li is not the answer and Lj (j!= i) is the answer, and because dist(Li, L1) == dist(Li, L2) and dist(Lj, L1) == dist(Lj, L2), then: dist(Li, center) <= d/2 and dist(Lj, center) <= d/2.

Because dist(Li, L1) < d ==> dist(Li, center) < dist(L1, center) = d/2.

==> dist(Lj, Li) <= dist(Lj, center) + dist(Li, center) < dist(Lj, center) + dist(center, L1) == dist(Lj, L1).

==> So Lj could not be the answer (contradiction).

3.2) If dist(Li, L1) == d then we can prove that if the center is not the answer, then the Li is also not the answer.

Proof : Suppose there exist u, v such that dist(u, center) == dist(v, center) and deg(u) != deg(v), then obviously dist(u, Li) == dist(v, Li) (which is easy to prove) and deg(u) != deg(v). So Li will not be the answer.

Overall, we have to check L1, L2, center, and at most ONE special leave Li such that dist(L1, Li) == dist(L2, Li) < d.

The complexity is O(n) or O(nlogn).

55464949

I love this type of problem, it's perfectly balance between mathematic thinking and coding.

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

    3.2 is very wrong

    9
    1 2
    2 3
    2 4
    4 5
    5 6
    5 7
    4 8
    8 9
    

    Answer should be 9, not -1

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

      Thanks for the idea.

      3.2 must be fixed to the following :

      If dist(Li, L1) == d, then when Li is the answer, for all Lj != Li, dist(Lj, Li) == d. So here just root the tree at the center, let the child of the center is V1, V2,...

      We could easily see that if there are two leaves Li, Lj in the subtree of Vi then obviously dist(Li, Lj) < d, so both Li, Lj is not the answer.

      So find the only leave Li inside the subtree of Vj, if the Li is not the answer, then the answer doesn't exist at all.

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

Auto comment: topic has been updated by McDic (previous revision, new revision, compare).

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

Why binary search approach on prob C giving WA on test case 16? soln link -:https://mirror.codeforces.com/contest/1182/submission/55465546

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

Aren't they different lyrics?

1. same differ
   same same

and

2. same same
   differ same
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's actually different beautiful lyrics. No matter which word you use, just maximize the concurrent number of beautiful lyrics.

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

    They are different but you cannot reuse the words. So you can only use the word as many number of times as it is given.

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

For D

Can someone tell why this approach won't work.

We start with leaf nodes delete them, decreasing there parents degree by 1.Now we check if all parents have same degree(Note while checking we check according to degree of original tree) if this doesn't satisfy we return -1 else we continue this process.

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

    "We start with leaf nodes" — I'm guessing you are considering all those nodes with degree 1 as leaf node. In the case, where the only possible root of the tree itself is having degree 1 (see the attached photo), you'll consider that node also as a leaf node, and go on traversing to its parent. So you'll have to handle that case as well.

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

In F how do we handle the case when q is larger than the interval size (i.e. sqrt(b-a+1)). Aren't we ignoring those values according to the tutorial.

»
5 years ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

A Simple python solution for Problem C. Hope it's useful!

Submission link : 55487269

You can comment below if you have any doubt!.

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

How to solve 1182 B using dfs (just wondering as it is mentioned in the tags).

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

debugged E 10 mins after the contest ended For slow typer like me, 2 hrs is not enough :(

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain E to me please?

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

Lawali's solution. Find the diameter path and validate for two leaves of the diameter path. If no valid vertex found(i.e. top is not in the diameter path), then the semitop should be the middle of the diameter path. Now validate for the semitop and any directly reachable leaf from semitop. If any valid vertex found, print it. Otherwise print −1.

I think you should check the nearest directly reachable leaf

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    Ah yeah, you are right. You are saying about example

    1-2-3-4-5, 2-6-7-8

    right?

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

      yes, something like that

      i hope that the solution will be fixed soon, it is not a big problem but can cause serious misunderstanding and many people may not look through the comments

      btw,thanks for your nice problems!especially D, i like it a lot!

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

        I fixed that part. It will be reflected to the post soon.

»
5 years ago, # |
Rev. 3   Vote: I like it -29 Vote: I do not like it

I used McDic's approach in problem C but not getting AC. Can anyone help (@McDic)



/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog. Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include <iostream> #include<string> #include<map> #include<vector> #include<utility> using namespace std; typedef pair < string, string > strduo; bool isVowel(char str) { if (str == 'a' || str == 'e' || str == 'i' || str == 'o' || str == 'u') { return true; } else return false; } int countvowels(string str) { int cntr = 0; for (int i = 0; i < str.length(); i++) { if (isVowel(str[i])) { cntr++; } } return cntr; } char lastVowel(string str) { for (int i = str.length() - 1; i >= 0; i--) { if (isVowel(str[i])) return str[i]; } } int main() { int n; cin >> n; map < int, map < char, vector < string >>> mp; for (int i = 0; i < n; i++) { string x; cin >> x; char d = lastVowel(x); char count = countvowels(x); mp[count][d].push_back(x); } /*for(auto x:mp) { cout<<x.first<<":"; for(auto h:x.second) { / cout<<h.first<<"->"; for(auto it=h.second.begin();it!=h.second.end();it++) cout<<*it<<" "; } cout<<"\n"; }*/ vector < strduo > completeduo; vector < strduo > semicompleteduo; // complete duos for (auto & x: mp) { for (auto & h: x.second) { while (h.second.size() >= 2) { string str1 = h.second.back(); h.second.pop_back(); string str2 = h.second.back(); h.second.pop_back(); // cout<<str1<<" "<<str2<<"\n"; completeduo.push_back(make_pair(str1, str2)); } } vector < string > remains; for (auto & h: x.second) { while (h.second.size() > 0) { remains.push_back(h.second.back()); h.second.pop_back(); } } while (remains.size() >= 2) { string str1 = remains.back(); remains.pop_back(); string str2 = remains.back(); remains.pop_back(); semicompleteduo.push_back(make_pair(str1, str2)); } } //semi complete duos // /*cout<<"Complete duos are\n"; for(auto it=completeduo.begin();it!=completeduo.end();it++) {auto h=*it; cout<<h.first<<" "<<h.second<<"\n";} cout<<"\n"; cout<<"Semi-Complete duos are\n"; for(auto it=semicompleteduo.begin();it!=semicompleteduo.end();it++) {auto h=*it; cout<<h.first<<" "<<h.second<<"\n";}*/ vector < strduo > final; while (semicompleteduo.size() > 0 && completeduo.size() > 0) { auto x = semicompleteduo.back(); semicompleteduo.pop_back(); auto y = completeduo.back(); completeduo.pop_back(); final.push_back(make_pair(x.first, y.first)); final.push_back(make_pair(x.second, y.second)); //cout<<x.first<<" "<<y.first<<"\n"<<x.second<<" "<<y.second<<"\n"; } while (completeduo.size() >= 2) { auto x = completeduo.back(); completeduo.pop_back(); auto y = completeduo.back(); completeduo.pop_back(); final.push_back(make_pair(x.first, y.first)); final.push_back(make_pair(x.second, y.second)); //cout<<x.first<<" "<<y.first<<"\n"<<x.second<<" "<<y.second<<"\n"; } cout << final.size() / 2 << "\n"; for (auto it = final.begin(); it != final.end(); it++) { auto x = * it; cout << x.first << " " << x.second << "\n"; } return 0; }
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's hard to read the code due to the indentations. Please make code pretty and re-ask.

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

For problem D, why the answer is only exist in the two leaves of the diameter path and the middle of the diameter path?

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

My code for problem B is giving run time error on test 16. Here is my code :- https://mirror.codeforces.com/contest/1182/submission/55501256 I am unable to figure out its cause ? Can someone help?

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

Can someone please explain how to find semitop in McDic's solution in the editorial? It says :"Then you can find the semitop by collapsing each level from leaf nodes of inner tree. " I keep collapsing each level untill what ? How do i know i have reached the semitop ? Because I can never know which leaf in the inner tree will end up on the semitop.

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

Can someone plz explain problem C, and its time complexity?

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    1. Separate all words into groups by property (quantity of vowels, last vowel).
    2. For each group connect maximum numbers of pair words and put this pairs in the first set.
    3. Now regroup all remaining words in groups by their quantity of vowels.
    4. look at the point 2
    5. While size of second set lower then size of first set — get 1 pair of words from first and put it in the second.
    6. Print ans.

    It, possibly, O(n), but it easier to implement it with O(n logn) complexity by using std::map.

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

How to calculate term by matrix exponentiation?

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

My approach for D: find the centroid of tree. If the tree is good, the centroid will lie on the path between top node and semi-top node. Then, I can travel to the topmost leaf node and check if this node satisfies or not.

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

Please, what are the math/algorithm prerequisites to understand the problem's E solution?

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

    You might have to learn Matrix multiplication, Modular Matrix Exponentiation (which is very similar to Modular Exponentitaion) and Fermat's little theorem for this problem.

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

Does Someone have a simpler solution for problem C that does not use Hash-maps or RB trees?

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

    here: 55450645

    I sorted each word so that all the complete words would be adjacent and you can linearly scan the sorted vector later and find the semi-complete words

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

Can someone explain why my approach is giving TLE. Acc to me it should have o(nlogn) complexity.

My Approch

  1. store features(no. if vowels and last vowel ) of each word in a map from string to pair<no of vowel,last vowel>

  2. sort the input vector of string based on its features(first in increasing order of no of vowel and in case of tie in increasing order of last vowel)

  3. now we can just iterate through the sorted array to form good lyrics

code my code

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'm not sure if this is performance bottleneck, but I don't recommend to use string as key of map.

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

      Thanks for the recommendation, will remember it from now on.

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

For problem D, this submission is accepted: Incorrect solution. Even though it outputs 6 for this test:

14
12 10
10 8
8 6
6 4
4 2
2 1
2 3
3 5
5 7
7 9
9 11
10 14
9 13

While the correct answer is 1.

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

    I will add this testdata, sorry for that issue.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem f: How to get to this conclusion? $$${2px \bmod 2q}$$$

I could only get to this form $$${2px \equiv q \bmod \pi}$$$ I am not able to get to required form.

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    (This is wrong)

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

      Got it thanks!

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

        I'm sorry for wrong formula. I wrote correct formula again.

        Let $$$\frac{p}{q}x \pi = Q\pi + R$$$ ($$$0 \le R \lt \pi$$$)

        Then $$$2px = 2qQ + \frac{2qR}{\pi}$$$

        So we are going to find the closest remainder to $$$q$$$, since $$$0 \le \frac{2qR}{\pi} \lt 2q$$$.

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

Can anyone help me how to come up with the dfs solution in problem B.

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

There's another approach for D.

If the root node has degree $$$\ge 2$$$, then it must be a centroid. Hence, we can just look at all centroids and see if they work as a root node.

Otherwise, we know that we either don't have a valid root node or the root node has a degree of $$$1$$$ and is a leaf. A naive solution would be to check all leaves, but this can be up to $$$\mathcal{O}(N^2)$$$ if we have a lot of leaves.

Let's root the tree at an arbitrary leaf $$$l$$$. If $$$l$$$ is indeed the desired root node, then we're done, so let's assume that $$$l$$$ is not the desired leaf node. Now, using hashing, you can check for all subtrees of our new rooted node, if that subtree is valid. by valid, I mean that it's symmetrical (symmetrical in the sense that that rooted subtree satisfies problem constraints). Let's look at the first subtree which is NOT symmetrical. Then, we know that our answer belongs to that subtree. Our answer is going to be the node that makes the subtree fail.

161980523

Also, by the way, I explain how the hashing works in one of my blog posts here. It's a very cool algorithm.