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 .

Wow very fast editorial :D

Woah. That was fast.

C made me sad :[

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

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?

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

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

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

Wow a fast editorial

arsijo pls stop creating problems (c)

Is test case weak or this is correct?

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

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

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

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

What was the harder (original) version of B?

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

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

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.

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?

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

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

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

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

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

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.

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.

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?

My solution to E:

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

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

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

"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

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.

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

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?

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

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

I provided all solutions. Thank you.

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.

8
a
e
i
o
u
u
u
u

4
hela
helo
helo
helu

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.

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

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.

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.

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

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

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

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

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.

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

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

Moved to a different post this

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

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

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.

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

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

Aren't they different lyrics?

1. same differ
   same same

and

2. same same
   differ same