McDic's blog

By McDic, history, 4 months 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

»
4 months 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 .

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Wow very fast editorial :D

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Woah. That was fast.

»
4 months ago, # |
  Vote: I like it +71 Vote: I do not like it

C made me sad :[

»
4 months 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?

»
4 months 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?

»
4 months 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?

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

    Difficulty balance. See number of solvers for each problem.

»
4 months 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

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Wow a fast editorial

»
4 months ago, # |
  Vote: I like it +160 Vote: I do not like it

arsijo pls stop creating problems (c)

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

Is test case weak or this is correct?

  • »
    »
    4 months 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)

  • »
    »
    4 months 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 (>__<)

»
4 months ago, # |
  Vote: I like it +62 Vote: I do not like it

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

»
4 months 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}}$$$.

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

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

  • »
    »
    4 months 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$$$.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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)$$$.

        • »
          »
          »
          »
          »
          4 months 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.

        • »
          »
          »
          »
          »
          4 months 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$$$
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What to do after building recurrence

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 months 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}$$$
        • »
          »
          »
          »
          »
          4 months 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}$$$
        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

      • »
        »
        »
        »
        4 months 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

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

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Learnt a lot from your solution.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain why it is P-1?

    • »
      »
      »
      4 months 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).

      • »
        »
        »
        »
        4 months 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$$$.

    • »
      »
      »
      3 months 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

    • »
      »
      »
      2 weeks 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

  • »
    »
    4 months 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?

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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}$$$
»
4 months 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 :(

.*.
***
.*.
...
.*.
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same

  • »
    »
    4 months 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.

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

What was the harder (original) version of B?

  • »
    »
    4 months 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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months 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 *

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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.)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes. Answer should be “NO”.

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

                  Thanks man. I solved it using coloring now.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Sorry for misleading you)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Also holds h,w<=500?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check out Stars Drawing(Hard version).

»
4 months 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.

»
4 months 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?

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

    I used hashing as well, but no DP required.

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for illustration

    • »
      »
      »
      2 weeks 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

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to calculate power of c?

    • »
      »
      »
      4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

  • »
    »
    4 months 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 :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B — why we should "search the end of the "+" shape from the center. (White stars in the picture below.)" Problem description says "There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction." and it is enough to check that center has consecutive non-empty cells. And after we do not need to check this row and column (which contains our center "+"). My logic was : find "*", check if it has at least one consecutive "*", save row and column and then check other rows and columns for "*", if they contains "*" — then "NO", otherwise "YES". So what is wrong with this logic?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because any “*” that isn’t part of the picture will make it a “NO”. There should be no “.” That breaks the continuation of any ray. Once there is a “.” At the end of a Ray, every other box should be empty, that is “.”

»
4 months 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)$$$

»
4 months 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

»
4 months 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. :(

  • »
    »
    4 months 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!

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey, no worries. Awesome explanation. Thanks a ton! :)

»
4 months 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.

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

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see thx.

    • »
      »
      »
      4 months 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.

    • »
      »
      »
      3 months 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.)

      • »
        »
        »
        »
        3 months 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.

»
4 months 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.

  • »
    »
    4 months 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

»
4 months 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?

»
4 months 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.

»
4 months 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."

  • »
    »
    4 months 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

»
4 months 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)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The order doesn't matter, just get as many lyrics as possible in output.

»
4 months 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

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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.

»
4 months 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.

»
4 months 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. :))))

»
4 months 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?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very cool problems! E is a nice problem, even I didn't manage to solve it.

»
4 months ago, # |
Rev. 3   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 a 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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I provided all solutions. Thank you.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

»
4 months 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
»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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

»
4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes you just need to have a clear vision of what you're trying to do, that's why I always try to solve the problem on paper first because otherwise I get really confused at my own code if I try to think of the solution during the process of writing code, makes debugging a lot more painful and time-taking.

        What got me about this task was my lack of knowledge about vector of vectors data structure which was needed for this task, otherwise this task was clean enough.

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How you find transformation matrix.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ok, so u have to use observations to find tranformation matrix.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Very nice and simple approach. I saw your implementation. Can you tell why you have used modp while taking modulo in multiply function instead of mod??

  • »
    »
    4 months 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!

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

Moved to a different post this

»
4 months 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

»
4 months 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

»
4 months 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.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

»
4 months 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).

»
4 months 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://codeforces.com/contest/1182/submission/55465546

»
4 months ago, # |
  Vote: I like it -33 Vote: I do not like it

can anyone tell me why my approach is wrong for Problem C

#include<bits/stdc++.h>

using namespace std;

map<pair<int, int>, stack<string > > mp;
map<pair<int, int>, stack<string > > :: iterator itr;

vector<pair<string, string> > complete, semi;

map<int, stack<string> > mp1;
int main(){
	int n; cin>>n;
	for(int i=0;i<n;i++){
		string s; cin>>s;
        int last,cnt = 0, len = s.length();
        for(int j = 0;j<len;j++){
        	if(s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u'){
                last = s[j]-'a';
                cnt++;
            }
        }
      //  cout<<cnt<<" "<<last<<"\n";
        if(mp[{cnt, last}].size() > 0){
            complete.push_back({mp[{cnt, last}].top(), s});
            mp[{cnt, last}].pop();
        }
        else{
        	mp[{cnt, last}].push(s);
        }
	}
	
	//cout<<complete.size()<<"\n";
	
	for(itr = mp.begin();itr != mp.end();itr++){
		if(itr->second.size()){
		   if(mp1[itr->first.first].size() > 0){
		   	   semi.push_back({mp1[itr->first.first].top(), itr->second.top()});
		   	   mp1[itr->first.first].pop();
		   	   itr->second.pop();
		   }
		   else{
		   	   mp1[itr->first.first].push(itr->second.top());
		   	   itr->second.pop();
		   }
		}
	}
	
	//cout<<semi.size()<<"\n";
	vector<pair< pair<string, string> , pair<string, string > > > v;
	int semiLength = semi.size(), completeLength = complete.size();
	for(int i=0;i<min(semiLength, completeLength);i++){
		pair<string, string> p = semi[i];
		pair<string, string> p1 = complete.back(); complete.pop_back();
		v.push_back({{p.first, p1.first}, {p.second, p1.second}});
	}
	
	completeLength = complete.size();
	for(int i=1;i<completeLength;i++){
		pair<string ,string> p = complete[i];
		pair<string, string> p1 = complete[i-1];
		v.push_back({{p.first, p1.first}, {p.second, p1.second}});
	}
	
	cout<<v.size()<<"\n";
	for(int i=0;i<v.size();i++){
		cout<<v[i].first.first<<" "<<v[i].first.second<<"\n";
		cout<<v[i].second.first<<" "<<v[i].second.second<<"\n";
	}
	return 0;
}
»
4 months 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
  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months 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!.

»
4 months 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).

»
4 months 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 :(

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

Can anyone explain E to me please?

»
4 months 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

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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!

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

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

»
4 months 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; }
  • »
    »
    4 months 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.

»
4 months 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?

»
4 months 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://codeforces.com/contest/1182/submission/55501256 I am unable to figure out its cause ? Can someone help?

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to find two nodes of "directly reachable"??? And also how to find the furthest directly reachable leaf node from a semitop??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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.

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

How to calculate term by matrix exponentiation?

»
4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been trying to do B, and I think it also matches the editor's solutions, but idk, it is getting runtime errors saying that the index gets out of bounds. it kinda looks like this..

include

include <bits/stdc++.h>

using namespace std;

int main() { int w, h; cin >> h >> w; char arr[h][w]; for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { cin >> arr[i][j]; } } int f = 0; for(int i = 0; i < h; i++) { for(int j = 0; j < w; j++) { if(arr[i][j] == '*' && arr[i][j + 1] == '*' && arr[i + 1][j] == '*' && arr[i — 1][j] == '*' && arr[i][j — 1] == '*') {

int x, y, z;
            z = j;
            while(arr[i][z] == '*' && z < w) {
                arr[i][z + 1] = '.';
                z++;
            }
            z = j;
            while(arr[i][z] == '*' && z >0) {
                arr[i][z - 1] = '.';
                z--;
            }
            x = i;
            while(arr[x][j] == '*' && x < h) {
                arr[x + 1][j] = '.';
                x++;
            }
            x  = i;
            while(arr[x][j] == '*' && x>0) {
                arr[x - 1][j] = '.';
                x--;
            }
            arr[i][j] = '.';
            f++;
            break;
        }
    }
}

for(int i = 0; i < h; i++) {
    for(int j = 0; j < w; j++) {
        if(arr[i][j] == '*' && (arr[i][j + 1] != '*' || arr[i + 1][j] != '*' || arr[i - 1][j] != '*' || arr[i][j - 1] != '*')) {
            cout << "NO";
            return 0;
        }

    }
}
if(f == 1) {
    cout << "YES";
    return 0;

}

cout << "NO";


return 0;

}

»
4 months 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?

  • »
    »
    4 months 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

»
4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial for B is very very good. Thanks for the effort McDic

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how the time complexity of the editorial solution for C is O(nlogn) or O(n)?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was attempting problem B and I got WA in test 9.

My approach is to first scan the whole picture in 3x3 squares for the "centre" pattern:

.*.
***
.*.

If the program detects more than 1 centre, it returns false. Otherwise, it records all the consecutive '*' grids from the centre in 4 directions into a list (with the centre included). Finally, it checks for any '*' grids in the picture but not on the list.

Can anyone point out the errors of my approach/implementation? Thank you very much!

Submission: 55542827

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me how to use and implement C (Beautiful Lyrics) using hashing in c++. I did it without hashing and am getting TLE.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain in C https://codeforces.com/problemset/submission/1182/55726315 why i am getting TLE on test case 5

»
4 months 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.

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

    I will add this testdata, sorry for that issue.

»
4 months 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.

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

    (This is wrong)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it thanks!

      • »
        »
        »
        »
        4 months 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$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can i get the explaination for 1st problem