Sorry for such difficulty balance. Here is the editorial.
Tutorial is loading...
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 BBehind 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 CBehind 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 DBehind story of E: I didn't expected such well-known problem. My solution for E is more complicated.
Tutorial is loading...
Solution Code for EBehind story of F: This problem was located at D originally.
Tutorial is loading...
Solution Code for F
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?
It says wrong answer on pretest 1
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?
My intended solution was much harder than tester's solutions
What was your intended solution?
Please read editorial.
Great problems. Fast editorial. Please set more rounds McDic.
Also, what does balance mean?
Difficulty balance. See number of solvers for each problem.
Anybody can tell me please, if my code for E is wrong in idea or there is a bug??
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)
https://www.youtube.com/watch?v=KNviwfDeRKg&feature=youtu.be
He-he, nice one :)
https://youtu.be/e-ObfcCJsBs
Is test case weak or this is correct?
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)
It will get TLE on following case:
I feel shame that I using this method to pass problem F in the contest (>__<)
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}}$$$.
This one is much more straightforward and natural in some sense.
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$$$.
how to calculate the exponent of C using dp recurence? that was the main problem, the rest are easy.
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)$$$.
OMG thank you very much. I just got stuck at the power of C, now i get it thanks.
You still able to make this easier:
and
If we compute the difference:
and we get the following easy recurrence:
What to do after building recurrence
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.
but how to form transformation matrix. any pattern to follow for it.
Search for Linear Recurrences section in this book
I think we can do even better, since getting rid of constants is generally helpful. As you said:
If we compute the difference:
and, cleaning up, we get the following recurrence:
For $$$b_n = \alpha_n + n$$$ recurrence takes the same form as for $$$f_1,f_2,f_3$$$.
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.
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.
\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
cool solution, we don't need to worry about finding primitive roots .
Learnt a lot from your solution.
Can you explain why it is P-1?
Because of Eulers Theorem. https://en.wikipedia.org/wiki/Euler%27s_theorem
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).
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$$$.
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 Psorry, I didn't know that it is explained below...
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
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?
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).
Thank you.
Sharon How did you calculated log5(c) ?
https://www.geeksforgeeks.org/discrete-logarithm-find-integer-k-ak-congruent-modulo-b/
How to calculate fn mod k.can u share Euler's formula
How to calculate fn mod k
: Explained above.can u share Euler's formula
: Here it is: $$$e^{ix} = \cos x + i \sin x$$$Can you explain why mod-1? (I watched Euler's theorem, but did not understand why mod-1)
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$$$.
Thanks)
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?
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:
Got it, thanks!
I misunderstood the problem statement of B and thought that this example yields a YES :(
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.
What was the harder (original) version of B?
The width of the vertical stripes and the length of the horizontal stipes are the same everywhere. For example:
..***..
..***..
.*****.
.*****.
..***..
YES
Can you explain more? I am getting WA at 15.
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 *
Good catch. But why answer is YES in above example?
Your program’s output is “YES”. But real answer is “NO”.
Sorry I am talking about the star example you posted above.
Anand asked the original version of task. And this test was for the original version. (There is a simplified version in the round.)
Oh you mean for this problem answer should be "NO"?
Yes. Answer should be “NO”.
Thanks man. I solved it using coloring now.
Sorry for misleading you)
Also holds h,w<=500?
Yes
It seems not so hard...I think it can be solved with h,w<=2000.
Yes, it is real not so hard. But u need more time to solve it.
Check out Stars Drawing(Hard version).
Can you please give us your implementation of E, it will be mush easier to understand the solution this way.
I will provide. Please wait.
Am I the only one who solved D using hashes and DP on tree?
I used hashing as well, but no DP required.
Can you guys tell me what is hashing on trees or send any blog to understand Sharon lessmeaning
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.
Thank you for illustration
How did you solve with Hashing only, i also had to use DP on tree.
Sharon can you please illustrate
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.
How to calculate power of c?
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.
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?
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.
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. :)
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://codeforces.me/problemset/submission/1182/55508849
Lesson from that: Upsolve problems as much as you can — you never know when a familiar problem would pop :)
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. :(
Could you explain why it is P-1, also can you share any resource if possible? Thanks!
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.
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.
In this case 0 is the semitop and there is no top.
I see thx.
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.
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.)
My first approach is same as your approach, but it might require tricky implementation and tricky case handling. So I changed my strategy.
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.
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
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.
Why so many downvotes?
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."
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
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
McDic It can't be that all leaves are at the same distance from semitop? Or what am I missing?
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.
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.
Sure. Please wait.
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?
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.
The mote than two words problem is what I’m asking
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.
Could you give me some hint about the misread problem? I'm still wondering
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.
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:55461952So 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.
It says you are not allowed to view the page when clicking on solution link
Hmmm.. Why is this happening O_o I will try to solve this issue
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.
Answer — 2
Answer — 1
Thanks to ajecc for this testcase
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.
I also thought the same solution. Did you solve it by finding centroid? Does it work?
After finding centroid, how do you check whether the condition, nodes with same distance from the root will have same degree?
Yes, you may see
Why we use only sqrt(n) numbers in problem f?
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.
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:
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;
forif(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.me/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?
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.
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.
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.
How you find transformation matrix.
Consider the following three equations:
This gives the required matrix, upon comparing with the product of a matrix and a vector.
Can you explain why it is 10^9 + 6 and not 10^9 + 7? Also could you share any resource? Thanks!
reference: Fermat's little theorem
a^(p-1) = 1 (mod p) when p is a prime number.
McDic how you came up with the formula for g(x,p).
Can you explain why it will be sum of remaining three.
Because $$$a^p \times a^q = a^{p+q}$$$
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.
3.2 is very wrong
Answer should be 9, not -1
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.
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.me/contest/1182/submission/55465546
Aren't they different lyrics?
and
It's actually different beautiful lyrics. No matter which word you use, just maximize the concurrent number of beautiful lyrics.
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.
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.
"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.
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.
A Simple python solution for Problem C. Hope it's useful!
Submission link : 55487269
You can comment below if you have any doubt!.
Please, hide your code using the link.
How to solve 1182 B using dfs (just wondering as it is mentioned in the tags).
I also think but didn't, get it.... Plz explain
please refer to this
debugged E 10 mins after the contest ended For slow typer like me, 2 hrs is not enough :(
Can anyone explain E to me please?
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
Ah yeah, you are right. You are saying about example
1-2-3-4-5, 2-6-7-8
right?
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!
I fixed that part. It will be reflected to the post soon.
I used McDic's approach in problem C but not getting AC. Can anyone help (@McDic)
It's hard to read the code due to the indentations. Please make code pretty and re-ask.
Done
What is the verdict you got? WA? TLE? MLE?
For problem D, why the answer is only exist in the two leaves of the diameter path and the middle of the diameter path?
My code for problem B is giving run time error on test 16. Here is my code :- https://codeforces.me/contest/1182/submission/55501256 I am unable to figure out its cause ? Can someone help?
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.
Can someone plz explain problem C, and its time complexity?
It, possibly, O(n), but it easier to implement it with O(n logn) complexity by using std::map.
How to calculate term by matrix exponentiation?
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.
Please, what are the math/algorithm prerequisites to understand the problem's E solution?
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.
Does Someone have a simpler solution for problem C that does not use Hash-maps or RB trees?
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
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
I'm not sure if this is performance bottleneck, but I don't recommend to use string as key of map.
Thanks for the recommendation, will remember it from now on.
For problem D, this submission is accepted: Incorrect solution. Even though it outputs 6 for this test:
While the correct answer is 1.
I will add this testdata, sorry for that issue.
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.
(This is wrong)
Got it thanks!
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$$$.
Can anyone help me how to come up with the dfs solution in problem B.
There's another approach for D.
If the root node has degree $$$\ge 2$$$, then it must be a centroid. Hence, we can just look at all centroids and see if they work as a root node.
Otherwise, we know that we either don't have a valid root node or the root node has a degree of $$$1$$$ and is a leaf. A naive solution would be to check all leaves, but this can be up to $$$\mathcal{O}(N^2)$$$ if we have a lot of leaves.
Let's root the tree at an arbitrary leaf $$$l$$$. If $$$l$$$ is indeed the desired root node, then we're done, so let's assume that $$$l$$$ is not the desired leaf node. Now, using hashing, you can check for all subtrees of our new rooted node, if that subtree is valid. by valid, I mean that it's symmetrical (symmetrical in the sense that that rooted subtree satisfies problem constraints). Let's look at the first subtree which is NOT symmetrical. Then, we know that our answer belongs to that subtree. Our answer is going to be the node that makes the subtree fail.
161980523
Also, by the way, I explain how the hashing works in one of my blog posts here. It's a very cool algorithm.