Codeforces Round #566 (Div. 2) Editorial

6 years ago, # ^ |

My intended solution was much harder than tester's solutions

→ Reply

AnandOza

6 years ago, # ^ |

-7

What was your intended solution?

→ Reply

6 years ago, # ^ |

+23

Please read editorial.

→ Reply

komolakanto

6 years ago, # |

+36

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

→ Reply

6 years ago, # ^ |

Difficulty balance. See number of solvers for each problem.

→ Reply

AltAccountWhenTired

6 years ago, # |

← Rev. 3 →

-14

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

code

ll n, f1, f2, f3, c, x1, x2, x3;
    while(cin>>n>>f1>>f2>>f3>>c)
    {
        ll ans=0;
        x1 = solve(5, f1, MOD);
        x2 = solve(5, f2, MOD);
        x3 = solve(5, f3, MOD);
        Matrix x;
        Resize_Matrix(3, 3, x);
        x[0][1]=1;
        x[1][2]=1;
        x[2][0]=x[2][1]=x[2][2]=1;
        --MOD;
        x=Matrix_Exponentiation(x, n-1);
        ++MOD;
        ans=x[0][0]*x1+x[0][1]*x2+x[0][2]*x3;
        ans%=MOD-1;
        ans=powmod(5, ans, MOD);
        ll tmp;
        n-=3;
        if(n%2==0){
            tmp=((n/2)%(MOD-1))*((n+1)%(MOD-1));
        }
        else{
            tmp=((n)%(MOD-1))*(((n+1)/2)%(MOD-1));
        }
        n+=3;
        tmp*=2;
        tmp%=MOD-1;
        tmp=powmod(c, tmp, MOD);
        ans*=tmp;
        ans%=MOD;
        cout<<ans<<endl;
    }

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

→ Reply

6 years ago, # |

Wow a fast editorial

→ Reply

228228227_is_prime

6 years ago, # |

+160

arsijo pls stop creating problems (c)

→ Reply

https://www.youtube.com/watch?v=KNviwfDeRKg&feature=youtu.be

6 years ago, # ^ |

+76

→ Reply

228228227_is_prime

6 years ago, # ^ |

He-he, nice one :)

→ Reply

tribute_to_Ukraine_2022

6 years ago, # ^ |

https://youtu.be/e-ObfcCJsBs

→ Reply

chemthan

6 years ago, # |

Is test case weak or this is correct?

→ Reply

6 years ago, # ^ |

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)

→ Reply

dreamoon_love_AA

6 years ago, # ^ |

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 (>__<)

→ Reply

amankumarkeshu

6 years ago, # |

+62

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

→ Reply

6 years ago, # |

← Rev. 2 →

+142

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}}$$$.

→ Reply

VadymKa

6 years ago, # ^ |

+20

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

→ Reply

monsoon

6 years ago, # ^ |

+100

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$$$.

→ Reply

21August

6 years ago, # ^ |

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

→ Reply

monsoon

6 years ago, # ^ |

+23

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)$$$.

→ Reply

21August

6 years ago, # ^ |

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

→ Reply

izanbf

6 years ago, # ^ |

+26

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

→ Reply

6 years ago, # ^ |

What to do after building recurrence

→ Reply

izanbf

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

izanbf

6 years ago, # ^ |

Search for Linear Recurrences section in this book

→ Reply

hoke_t

5 years ago, # ^ |

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}$$$

→ Reply

Z8N

6 years ago, # ^ |

← Rev. 2 →

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}$$$

→ Reply

shahidul_brur

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Cqt_Iostream

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

Andimeo

6 years ago, # ^ |

-8

\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

→ Reply

stringray

6 years ago, # ^ |

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

→ Reply

abhinav_jain02

6 years ago, # ^ |

Learnt a lot from your solution.

→ Reply

snorlax91

6 years ago, # ^ |

Can you explain why it is P-1?

→ Reply

AryaKnight

6 years ago, # ^ |

Because of Eulers Theorem. https://en.wikipedia.org/wiki/Euler%27s_theorem

→ Reply

atakyn

6 years ago, # ^ |

← Rev. 2 →

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).

→ Reply

monsoon

6 years ago, # ^ |

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$$$.

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

sorry, I didn't know that it is explained below...

→ Reply

Spheniscine

5 years ago, # ^ |

← Rev. 5 →

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

→ Reply

6 years ago, # ^ |

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?

→ Reply

6 years ago, # ^ |

In the end you are doing $$$f_n \equiv 5^{F_n} \pmod{10^9 + 7}$$$. For that to be true, you should calculate $$$F_n$$$ in modulo $$$10^9 + 6$$$ (from Euler's Theorem).

→ Reply

6 years ago, # ^ |

Thank you.

→ Reply

TiredOfLife

5 years ago, # ^ |

Sharon How did you calculated log5(c) ?

→ Reply

https://www.geeksforgeeks.org/discrete-logarithm-find-integer-k-ak-congruent-modulo-b/

5 years ago, # ^ |

→ Reply

6 years ago, # ^ |

How to calculate fn mod k.can u share Euler's formula

→ Reply

6 years ago, # ^ |

+28

How to calculate fn mod k: Explained above.
can u share Euler's formula: Here it is: $$$e^{ix} = \cos x + i \sin x$$$

→ Reply

mrboorger

6 years ago, # ^ |

Can you explain why mod-1? (I watched Euler's theorem, but did not understand why mod-1)

→ Reply

6 years ago, # ^ |

By Euler's Theorem, if $$$p$$$ is prime then $$$a^{\phi{(p)}} \equiv a^{p - 1} \equiv 1 \pmod p$$$. Equivalently, $$$a^{k(p-1) + c} \equiv a^c \pmod p$$$. So, if you want to calculate $$$a^b$$$ in modulo $$$p$$$, then you need to calculate $$$b$$$ in modulo $$$p-1$$$.

→ Reply

mrboorger

6 years ago, # ^ |

Thanks)

→ Reply

rodz

6 years ago, # ^ |

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?

→ Reply

6 years ago, # ^ |

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}$$$

→ Reply

rodz

6 years ago, # ^ |

Got it, thanks!

→ Reply

bodmas

6 years ago, # |

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

.*.
***
.*.
...
.*.

→ Reply

mivael

6 years ago, # ^ |

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.

→ Reply

AnandOza

6 years ago, # |

What was the harder (original) version of B?

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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

..***..

.*****.

..***..

YES

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 3 →

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 *

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

Yes. Answer should be “NO”.

→ Reply

6 years ago, # ^ |

Thanks man. I solved it using coloring now.

→ Reply

6 years ago, # ^ |

Sorry for misleading you)

→ Reply

meaningIess

6 years ago, # ^ |

Also holds h,w<=500?

→ Reply

6 years ago, # ^ |

Yes

→ Reply

meaningIess

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

anupamshah_

6 years ago, # ^ |

Check out Stars Drawing(Hard version).

→ Reply

21August

6 years ago, # |

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

→ Reply

6 years ago, # ^ |

I will provide. Please wait.

→ Reply

lessmeaning

6 years ago, # |

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

→ Reply

6 years ago, # ^ |

I used hashing as well, but no DP required.

→ Reply

MinaToma

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

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.

→ Reply

MinaToma

6 years ago, # ^ |

Thank you for illustration

→ Reply

Lets__go

5 years ago, # ^ |

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

Sharon can you please illustrate

→ Reply

Bohun

6 years ago, # |

← Rev. 2 →

+13

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.

→ Reply

King_of_Snus

6 years ago, # ^ |

How to calculate power of c?

→ Reply

Bohun

6 years ago, # ^ |

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.

→ Reply

dmkz

6 years ago, # |

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?

→ Reply

6 years ago, # ^ |

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.

→ Reply

Lucina

6 years ago, # ^ |

← Rev. 3 →

The first thing that popped up in my mind after reading E is 1106F - Lunar New Year and a Recursive Sequence too. Sad that I can't implement in time. Also, editorial solution for E is little tricky. I like it. Thanks for the problemset. :)

→ Reply

jdh

6 years ago, # ^ |

← Rev. 2 →

For question E, I don't use discrete logarithm or prime factor decomposition. But during the contest, I forgot to do modulo MOD-1 when calculating the power of matrix which is used for the exponent.

Lesson learnt now. I remember better little Fermat theorem from now on.

My solution: https://mirror.codeforces.com/problemset/submission/1182/55508849

→ Reply

kocko

6 years ago, # ^ |

+11

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

→ Reply

solaimanope

6 years ago, # |

← Rev. 2 →

+17

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)$$$

→ Reply

camille

6 years ago, # |

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

→ Reply

islingr

6 years ago, # |

← Rev. 6 →

+10

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. :(

→ Reply

snorlax91

6 years ago, # ^ |

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

→ Reply

islingr

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

EndRay

6 years ago, # |

← Rev. 2 →

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

EndRay

6 years ago, # ^ |

I see thx.

→ Reply

Cqt_Iostream

6 years ago, # ^ |

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.

→ Reply

erickjohnross

5 years ago, # ^ |

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.)

→ Reply

5 years ago, # ^ |

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

→ Reply

saketh

6 years ago, # |

+21

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.

→ Reply

komolakanto

6 years ago, # ^ |

+11

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

→ Reply

Pankin

6 years ago, # |

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?

→ Reply

AH_ljq

6 years ago, # |

← Rev. 2 →

-43

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.

→ Reply

intruder_p

6 years ago, # ^ |

Why so many downvotes?

→ Reply

best1234567

6 years ago, # |

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."

→ Reply

komolakanto

6 years ago, # ^ |

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

→ Reply

best1234567

6 years ago, # |

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

→ Reply

AaronSwartz

6 years ago, # |

"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

→ Reply

AaronSwartz

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

← Rev. 4 →

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.

→ Reply

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

Sure. Please wait.

→ Reply

6 years ago, # |

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. :))))

→ Reply

6 years ago, # |

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?

→ Reply

Scofield11

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

HanaYukii

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

HanaYukii

6 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

Leonardo16

6 years ago, # |

← Rev. 4 →

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

→ Reply

soul_voyage

6 years ago, # |

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

→ Reply

6 years ago, # |

I provided all solutions. Thank you.

→ Reply

madhav_1999

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

dush1729

6 years ago, # |

← Rev. 2 →

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

8
a
e
i
o
u
u
u
u

Answer — 2

Testcase 2

4
hela
helo
helo
helu

Answer — 1

Thanks to ajecc for this testcase

→ Reply

kirillbogatiy

6 years ago, # |

← Rev. 2 →

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.

→ Reply

suvro_coder

6 years ago, # ^ |

I also thought the same solution. Did you solve it by finding centroid? Does it work?

→ Reply

suvro_coder

6 years ago, # ^ |

After finding centroid, how do you check whether the condition, nodes with same distance from the root will have same degree?

→ Reply

kirillbogatiy

6 years ago, # ^ |

Yes, you may see

→ Reply

spaceout

6 years ago, # |

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

→ Reply

6 years ago, # ^ |

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.

→ Reply

nikesh04

6 years ago, # |

← Rev. 3 →

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.

→ Reply

_Shush

6 years ago, # |

← Rev. 2 →

+13

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.

→ Reply

10Queue

6 years ago, # |

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

→ Reply

tribute_to_Ukraine_2022

6 years ago, # |

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

→ Reply

Scofield11

6 years ago, # |

+10

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

→ Reply

6 years ago, # |

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

→ Reply

Scofield11

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

nor

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

How you find transformation matrix.

→ Reply

nor

6 years ago, # ^ |

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.

→ Reply

snorlax91

6 years ago, # ^ |

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

→ Reply

marmot0814

6 years ago, # ^ |

← Rev. 3 →

reference: Fermat's little theorem

a^(p-1) = 1 (mod p) when p is a prime number.

→ Reply

6 years ago, # |

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

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

→ Reply

6 years ago, # ^ |

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

→ Reply

The_Blitz

6 years ago, # |

← Rev. 2 →

Moved to a different post this

→ Reply

G.E.M.

6 years ago, # |

← Rev. 2 →

+12

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

→ Reply

seven_triple

6 years ago, # |

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

→ Reply

tRuNgSeO

6 years ago, # |

← Rev. 4 →

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.

→ Reply

thecodinglizard

6 years ago, # ^ |

+10

3.2 is very wrong

Answer should be 9, not -1

→ Reply

tRuNgSeO

6 years ago, # ^ |

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.

→ Reply

6 years ago, # |

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

→ Reply

killer_khan

6 years ago, # |

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

→ Reply

intra_code

6 years ago, # |

Aren't they different lyrics?

1. same differ
   same same

and

2. same same
   differ same

→ Reply

6 years ago, # ^ |

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

→ Reply

sh_m

6 years ago, # ^ |

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.

→ Reply

Pj18

6 years ago, # |

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.

→ Reply

rawnix

6 years ago, # ^ |

"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.

→ Reply

sh_m

6 years ago, # |

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.

→ Reply

strangerBoy

6 years ago, # |

← Rev. 2 →

-22

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

Submission link : 55487269

You can comment below if you have any doubt!.

→ Reply

armoking

6 years ago, # ^ |

Please, hide your code using the link.

→ Reply

_yUGGa_

6 years ago, # |

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

→ Reply

codeanna

6 years ago, # ^ |

I also think but didn't, get it.... Plz explain

→ Reply

youssefbou62

6 years ago, # ^ |

please refer to this

→ Reply

retired.old.cake

6 years ago, # |

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

→ Reply

Pankin

6 years ago, # |

← Rev. 2 →

Can anyone explain E to me please?

→ Reply

Wechselhau

6 years ago, # |

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

→ Reply

6 years ago, # ^ |

← Rev. 4 →

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

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

right?

→ Reply

Wechselhau

6 years ago, # ^ |

← Rev. 2 →

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!

→ Reply

6 years ago, # ^ |

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

→ Reply

babu1998

6 years ago, # |

← Rev. 3 →

-29

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;
}

→ Reply

6 years ago, # ^ |

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

→ Reply

babu1998

6 years ago, # ^ |

Done

→ Reply

6 years ago, # ^ |

What is the verdict you got? WA? TLE? MLE?

→ Reply

ACKING

6 years ago, # |

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

→ Reply

RAI

6 years ago, # |

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?

→ Reply

abhinav_jain02

6 years ago, # |

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.

→ Reply

Induber

6 years ago, # |

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

→ Reply

armoking

6 years ago, # ^ |

← Rev. 3 →

Separate all words into groups by property (quantity of vowels, last vowel).
For each group connect maximum numbers of pair words and put this pairs in the first set.
Now regroup all remaining words in groups by their quantity of vowels.
look at the point 2
While size of second set lower then size of first set — get 1 pair of words from first and put it in the second.
Print ans.

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

→ Reply

mrboorger

6 years ago, # |

← Rev. 3 →

How to calculate term by matrix exponentiation?

→ Reply

aditya_sheth

6 years ago, # |

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.

→ Reply

youssefbou62

6 years ago, # |

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

→ Reply

vsriram1012

6 years ago, # ^ |

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.

→ Reply

Noob27999

6 years ago, # |

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

→ Reply

errorgorn

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

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

My Approch

store features(no. if vowels and last vowel ) of each word in a map from string to pair<no of vowel,last vowel>
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)
now we can just iterate through the sorted array to form good lyrics

code my code

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

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

→ Reply

mohamedeltair

6 years ago, # |

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

While the correct answer is 1.

→ Reply

5 years ago, # ^ |

I will add this testdata, sorry for that issue.

→ Reply

persistent_try

5 years ago, # |

← Rev. 2 →

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.

→ Reply

5 years ago, # ^ |

← Rev. 4 →

(This is wrong)

→ Reply

persistent_try

5 years ago, # ^ |

Got it thanks!

→ Reply