Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

McDic's blog

By McDic, history, 8 months ago, ,

Sorry for such difficulty balance. Here is the editorial.

Solution Code for A

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

Solution Code for B

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

Solution Code for C

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

Solution Code for D

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

Solution Code for E

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

Solution Code for F

• +102

 » 8 months ago, # |   +23 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 .
 » 8 months ago, # |   +7 Wow very fast editorial :D
 » 8 months ago, # |   +6 Woah. That was fast.
 » 8 months ago, # |   +71 C made me sad :[
 » 8 months ago, # |   +3 Why my solution for C (id:55462095) wasn't judged when I submit at 01:59:45?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +9 It says wrong answer on pretest 1
 » 8 months ago, # |   -6 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?
•  » » 8 months ago, # ^ |   +1 My intended solution was much harder than tester's solutions
•  » » » 8 months ago, # ^ |   0 ok.
•  » » » 8 months ago, # ^ |   -7 What was your intended solution?
•  » » » » 8 months ago, # ^ |   +23 Please read editorial.
 » 8 months ago, # |   +36 Great problems. Fast editorial. Please set more rounds McDic. Also, what does balance mean?
•  » » 8 months ago, # ^ |   +5 Difficulty balance. See number of solvers for each problem.
 » 8 months ago, # | ← Rev. 3 →   -14 Anybody can tell me please, if my code for E is wrong in idea or there is a bug?? codell 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<
 » 8 months ago, # |   +7 Wow a fast editorial
 » 8 months ago, # |   +160 arsijo pls stop creating problems (c)
•  » » 8 months ago, # ^ |   +76
•  » » » 8 months ago, # ^ |   +5 He-he, nice one :)
•  » » » » 8 months ago, # ^ |   +6
 » 8 months ago, # |   +5 Is test case weak or this is correct?
•  » » 8 months ago, # ^ |   +6 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)
•  » » 8 months ago, # ^ |   +8 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 (>__<)
 » 8 months ago, # |   +62 Do other people also feel that this contest wasn't balanced.
•  » » 8 months ago, # ^ |   0 Nope
 » 8 months 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}}$.
•  » » 8 months ago, # ^ |   +20 This one is much more straightforward and natural in some sense.
•  » » 8 months 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$.
•  » » » 8 months ago, # ^ |   +8 how to calculate the exponent of C using dp recurence? that was the main problem, the rest are easy.
•  » » » » 8 months 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)$.
•  » » » » » 8 months ago, # ^ |   0 OMG thank you very much. I just got stuck at the power of C, now i get it thanks.
•  » » » » » 8 months 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$
•  » » » » » » 8 months ago, # ^ |   0 What to do after building recurrence
•  » » » » » » » 8 months ago, # ^ |   +3 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.
•  » » » » » » » » 8 months ago, # ^ |   0 but how to form transformation matrix. any pattern to follow for it.
•  » » » » » » » » » 8 months ago, # ^ |   0 Search for Linear Recurrences section in this book
•  » » » » » » 7 months ago, # ^ |   0 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}$
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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}$
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 months ago, # ^ |   -8 \alpha can be translated to, saywe define theta_n = alpha_n + n we have theta_n = theta_n-1 + theta_n-2 + theta_n-3
•  » » » 8 months ago, # ^ |   +3 cool solution, we don't need to worry about finding primitive roots .
•  » » » 8 months ago, # ^ |   0 Learnt a lot from your solution.
•  » » » 8 months ago, # ^ |   0 Can you explain why it is P-1?
•  » » » » 8 months ago, # ^ |   0 Because of Eulers Theorem. https://en.wikipedia.org/wiki/Euler%27s_theorem
•  » » » » » 8 months ago, # ^ |   0 Hey, thanks. Understood it now. :)
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » 8 months ago, # ^ |   +3 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$.
•  » » » 8 months ago, # ^ |   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 P
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 sorry, I didn't know that it is explained below...
•  » » » 5 months ago, # ^ | ← Rev. 5 →   0 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
•  » » 8 months ago, # ^ |   +3 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+7log5(f1) = 0log5(f2) = 381838282log5(f3) = 1log5(c) = 884237698We get for log5(fn) = (2*884237698+1+381838282+0)%mod = 1503136655^150313665 % mod = 200000005 , which isn't the answer (should be 90).What did I do wrong?
•  » » » 8 months ago, # ^ |   +1 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).
•  » » » » 8 months ago, # ^ |   0 Thank you.
•  » » » » » 7 months ago, # ^ |   0 Sharon How did you calculated log5(c) ?
•  » » » » » » 7 months ago, # ^ |   +1
•  » » » » 8 months ago, # ^ |   0 How to calculate fn mod k.can u share Euler's formula
•  » » » » » 8 months 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$
•  » » » » 8 months ago, # ^ |   0 Can you explain why mod-1? (I watched Euler's theorem, but did not understand why mod-1)
•  » » » » » 8 months ago, # ^ |   +4 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$.
•  » » » » » » 8 months ago, # ^ |   0 Thanks)
•  » » 8 months ago, # ^ |   0 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?
•  » » » 8 months ago, # ^ |   +5 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}$
•  » » » » 8 months ago, # ^ |   0 Got it, thanks!
 » 8 months ago, # |   +7 I misunderstood the problem statement of B and thought that this example yields a YES :( .*. *** .*. ... .*. 
•  » » 8 months ago, # ^ |   0 Same
•  » » 8 months ago, # ^ |   +3 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.
 » 8 months ago, # |   +8 What was the harder (original) version of B?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +7 The width of the vertical stripes and the length of the horizontal stipes are the same everywhere. For example:..***....***...*****..*****...***..YES
•  » » » 8 months ago, # ^ |   0 Can you explain more? I am getting WA at 15.
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   0 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 *
•  » » » » » 8 months ago, # ^ |   0 Good catch. But why answer is YES in above example?
•  » » » » » » 8 months ago, # ^ |   0 Your program’s output is “YES”. But real answer is “NO”.
•  » » » » » » » 8 months ago, # ^ |   0 Sorry I am talking about the star example you posted above.
•  » » » » » » » » 8 months ago, # ^ |   0 Anand asked the original version of task. And this test was for the original version. (There is a simplified version in the round.)
•  » » » » » » » » » 8 months ago, # ^ |   0 Oh you mean for this problem answer should be "NO"?
•  » » » » » » » » » 8 months ago, # ^ |   0 Yes. Answer should be “NO”.
•  » » » » » » » » » 8 months ago, # ^ |   +3 Thanks man. I solved it using coloring now.
•  » » » » » » » » 8 months ago, # ^ |   0 Sorry for misleading you)
•  » » » 8 months ago, # ^ |   0 Also holds h,w<=500?
•  » » » » 8 months ago, # ^ |   0 Yes
•  » » » » » 8 months ago, # ^ |   0 It seems not so hard...I think it can be solved with h,w<=2000.
•  » » » » » » 8 months ago, # ^ |   0 Yes, it is real not so hard. But u need more time to solve it.
•  » » 8 months ago, # ^ |   0 Check out Stars Drawing(Hard version).
 » 8 months ago, # |   0 Can you please give us your implementation of E, it will be mush easier to understand the solution this way.
•  » » 8 months ago, # ^ |   0 I will provide. Please wait.
 » 8 months ago, # |   +9 Am I the only one who solved D using hashes and DP on tree?
•  » » 8 months ago, # ^ |   +3 I used hashing as well, but no DP required.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you guys tell me what is hashing on trees or send any blog to understand Sharon lessmeaning
•  » » » » 8 months ago, # ^ |   +3 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.
•  » » » » » 8 months ago, # ^ |   0 Thank you for illustration
•  » » » 5 months ago, # ^ |   0 How did you solve with Hashing only, i also had to use DP on tree. Sharon can you please illustrate
 » 8 months 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.
•  » » 8 months ago, # ^ |   0 How to calculate power of c?
•  » » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   0 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?
•  » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   +9 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. :)
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 8 months ago, # ^ |   +11 Lesson from that: Upsolve problems as much as you can — you never know when a familiar problem would pop :)
 » 8 months ago, # |   0 In Problem B — why we should "search the end of the "+" shape from the center. (White stars in the picture below.)" Problem description says "There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction." and it is enough to check that center has consecutive non-empty cells. And after we do not need to check this row and column (which contains our center "+"). My logic was : find "*", check if it has at least one consecutive "*", save row and column and then check other rows and columns for "*", if they contains "*" — then "NO", otherwise "YES". So what is wrong with this logic?
•  » » 8 months ago, # ^ |   0 Because any “*” that isn’t part of the picture will make it a “NO”. There should be no “.” That breaks the continuation of any ray. Once there is a “.” At the end of a Ray, every other box should be empty, that is “.”
•  » » » 8 months ago, # ^ |   0 Yes, thanks, I understood.
 » 8 months 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)$
 » 8 months ago, # |   0 It was also possible to cut through the tests of problem D like this: 55463619
 » 8 months 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. :(
•  » » 8 months ago, # ^ |   +3 Could you explain why it is P-1, also can you share any resource if possible? Thanks!
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 months ago, # ^ |   0 Hey, no worries. Awesome explanation. Thanks a ton! :)
 » 8 months ago, # | ← Rev. 2 →   +9 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.
•  » » 8 months ago, # ^ |   +5 In this case 0 is the semitop and there is no top.
•  » » » 8 months ago, # ^ |   0 I see thx.
•  » » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ |   0 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.)
•  » » » » 8 months ago, # ^ |   0 My first approach is same as your approach, but it might require tricky implementation and tricky case handling. So I changed my strategy.
 » 8 months 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.
•  » » 8 months 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
 » 8 months ago, # |   +5 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?
 » 8 months 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.
•  » » 8 months ago, # ^ |   0 Why so many downvotes?
 » 8 months ago, # |   0 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."
•  » » 8 months ago, # ^ |   0 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
 » 8 months ago, # |   0 which is correct order of lyrics in C? give me 4 word(just complete duo semicomplete duo)
•  » » 8 months ago, # ^ |   0 The order doesn't matter, just get as many lyrics as possible in output.
 » 8 months ago, # |   0 "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
•  » » 8 months ago, # ^ |   0 McDic It can't be that all leaves are at the same distance from semitop? Or what am I missing?
•  » » » 8 months ago, # ^ | ← Rev. 4 →   0 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.
 » 8 months ago, # |   0 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.
•  » » 8 months ago, # ^ |   0 Sure. Please wait.
 » 8 months ago, # |   0 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. :))))
 » 8 months ago, # |   0 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?
•  » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ |   0 The mote than two words problem is what I’m asking
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 8 months ago, # ^ |   0 Could you give me some hint about the misread problem? I'm still wondering
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   0 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.
 » 8 months ago, # |   0 Very cool problems! E is a nice problem, even I didn't manage to solve it.
 » 8 months ago, # | ← Rev. 3 →   0 C. Beautiful Lyrics: What about the O(N) implementation in the problem C? I did it with a array of maps : map>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
 » 8 months ago, # |   0 So many approaches for D and E is very nice, it makes problem look natural rather than derived from technique.
 » 8 months ago, # |   +6 I provided all solutions. Thank you.
•  » » 8 months ago, # ^ |   0 It says you are not allowed to view the page when clicking on solution link
•  » » » 8 months ago, # ^ |   +3 Hmmm.. Why is this happening O_o I will try to solve this issue
 » 8 months ago, # | ← Rev. 2 →   +3 I used same approach for C, it's failing for testcase 7 and I'm unable to find the bug.CodeSorry for the messy code :/UPD — Found the testcase. Testcase 18 a e i o u u u u Answer — 2 Testcase 24 hela helo helo helu Answer — 1Thanks to ajecc for this testcase
 » 8 months ago, # | ← Rev. 2 →   0 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.
•  » » 8 months ago, # ^ |   0 I also thought the same solution. Did you solve it by finding centroid? Does it work?
•  » » 8 months ago, # ^ |   0 After finding centroid, how do you check whether the condition, nodes with same distance from the root will have same degree?
•  » » » 8 months ago, # ^ |   0 Yes, you may see
 » 8 months ago, # |   0 Why we use only sqrt(n) numbers in problem f?
•  » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # | ← Rev. 3 →   0 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.
 » 8 months 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.
 » 8 months ago, # |   0 Can anyone help me with this tle on problem C: https://codeforces.com/contest/1182/submission/55471836
 » 8 months ago, # |   +9 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
 » 8 months ago, # |   +10 I jumped up from rank 3500 to rank 2500 purely because of B hacks and system tests.
 » 8 months ago, # |   0 It says that i'm not allowed to view the requested page when i click to the solution. What is the problem?
•  » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ |   0 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.
•  » » » » 8 months ago, # ^ |   0 Yes you just need to have a clear vision of what you're trying to do, that's why I always try to solve the problem on paper first because otherwise I get really confused at my own code if I try to think of the solution during the process of writing code, makes debugging a lot more painful and time-taking.What got me about this task was my lack of knowledge about vector of vectors data structure which was needed for this task, otherwise this task was clean enough.
 » 8 months ago, # |   +8 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.
•  » » 8 months ago, # ^ |   0 How you find transformation matrix.
•  » » » 8 months ago, # ^ |   +8 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.
•  » » » » 8 months ago, # ^ |   0 ok, so u have to use observations to find tranformation matrix.
•  » » » » 8 months ago, # ^ |   0 Very nice and simple approach. I saw your implementation. Can you tell why you have used modp while taking modulo in multiply function instead of mod??
•  » » 8 months ago, # ^ |   0 Can you explain why it is 10^9 + 6 and not 10^9 + 7? Also could you share any resource? Thanks!
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 reference: Fermat's little theorema^(p-1) = 1 (mod p) when p is a prime number.
•  » » » » 8 months ago, # ^ |   0 Hey, thanks. Makes it all more clear now. :)
 » 8 months ago, # |   0 McDic how you came up with the formula for g(x,p).Can you explain why it will be sum of remaining three.
•  » » 8 months ago, # ^ |   0 Because $a^p \times a^q = a^{p+q}$
 » 8 months ago, # | ← Rev. 2 →   0 Moved to a different post this
 » 8 months 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
 » 8 months ago, # |   +1 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
•  » » 8 months ago, # ^ |   0 I am also facing the same problem.
•  » » 8 months ago, # ^ |   +10 3.2 is very wrong 9 1 2 2 3 2 4 4 5 5 6 5 7 4 8 8 9 Answer should be 9, not -1
•  » » » 8 months ago, # ^ |   0 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.
 » 8 months ago, # |   0 Auto comment: topic has been updated by McDic (previous revision, new revision, compare).
 » 8 months ago, # |   0 Why binary search approach on prob C giving WA on test case 16? soln link -:https://codeforces.com/contest/1182/submission/55465546
 » 8 months ago, # |   -33 can anyone tell me why my approach is wrong for Problem C #include using namespace std; map, stack > mp; map, stack > :: iterator itr; vector > complete, semi; map > mp1; int main(){ int n; cin>>n; for(int i=0;i>s; int last,cnt = 0, len = s.length(); for(int j = 0;j 0){ complete.push_back({mp[{cnt, last}].top(), s}); mp[{cnt, last}].pop(); } else{ mp[{cnt, last}].push(s); } } //cout<second.size()){ if(mp1[itr->first.first].size() > 0){ semi.push_back({mp1[itr->first.first].top(), itr->second.top()}); mp1[itr->first.first].pop(); itr->second.pop(); } else{ mp1[itr->first.first].push(itr->second.top()); itr->second.pop(); } } } //cout< , pair > > v; int semiLength = semi.size(), completeLength = complete.size(); for(int i=0;i p = semi[i]; pair p1 = complete.back(); complete.pop_back(); v.push_back({{p.first, p1.first}, {p.second, p1.second}}); } completeLength = complete.size(); for(int i=1;i p = complete[i]; pair p1 = complete[i-1]; v.push_back({{p.first, p1.first}, {p.second, p1.second}}); } cout<
 » 8 months ago, # |   0 Aren't they different lyrics? 1. same differ same sameand 2. same same differ same
•  » » 8 months ago, # ^ |   0 It's actually different beautiful lyrics. No matter which word you use, just maximize the concurrent number of beautiful lyrics.
•  » » 8 months ago, # ^ |   0 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.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you explain how to implement and use hashing in this question using c++. I did it without hashing and am getting TLE. Here is my submissionhttps://codeforces.com/contest/1182/submission/55566266
 » 8 months ago, # |   +3 For DCan 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.
•  » » 8 months ago, # ^ |   +2 "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.
 » 8 months ago, # |   0 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.
 » 8 months ago, # | ← Rev. 2 →   -22 A Simple python solution for Problem C. Hope it's useful!Submission link : 55487269You can comment below if you have any doubt!.
•  » » 8 months ago, # ^ |   +5 Please, hide your code using the link.
 » 8 months ago, # |   0 How to solve 1182 B using dfs (just wondering as it is mentioned in the tags).
•  » » 8 months ago, # ^ |   0 I also think but didn't, get it.... Plz explain
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I guess you could use flood-fill to count no of islands and count how many islands are + shape. Like that.
•  » » 8 months ago, # ^ |   0 please refer to this
 » 8 months ago, # |   0 debugged E 10 mins after the contest ended For slow typer like me, 2 hrs is not enough :(
 » 8 months ago, # | ← Rev. 2 →   0 Can anyone explain E to me please?
 » 8 months ago, # |   0 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
•  » » 8 months ago, # ^ | ← Rev. 4 →   +8 Ah yeah, you are right. You are saying about example1-2-3-4-5, 2-6-7-8right?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +5 yes, something like thati 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 commentsbtw,thanks for your nice problems!especially D, i like it a lot!
•  » » » » 8 months ago, # ^ |   +8 I fixed that part. It will be reflected to the post soon.
 » 8 months 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 #include #include #include #include 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<"; 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< 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< 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<= 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<
•  » » 8 months ago, # ^ |   0 It's hard to read the code due to the indentations. Please make code pretty and re-ask.
•  » » » 8 months ago, # ^ |   0 Done
•  » » » » 8 months ago, # ^ |   0 What is the verdict you got? WA? TLE? MLE?
•  » » » » » 8 months ago, # ^ |   0 I got WA for test case 12
 » 8 months ago, # |   0 For problem D, why the answer is only exist in the two leaves of the diameter path and the middle of the diameter path?
 » 8 months ago, # |   0 My code for problem B is giving run time error on test 16. Here is my code :- https://codeforces.com/contest/1182/submission/55501256 I am unable to figure out its cause ? Can someone help?
 » 8 months ago, # |   0 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.
 » 8 months ago, # |   0 How to find two nodes of "directly reachable"??? And also how to find the furthest directly reachable leaf node from a semitop??
 » 8 months ago, # |   0 Can someone plz explain problem C, and its time complexity?
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 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.
 » 8 months ago, # | ← Rev. 3 →   0 How to calculate term by matrix exponentiation?
 » 8 months ago, # |   0 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.
 » 8 months ago, # |   0 Please, what are the math/algorithm prerequisites to understand the problem's E solution?
•  » » 8 months ago, # ^ |   0 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.
»
8 months ago, # |
0

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

include <bits/stdc++.h>

using namespace std;

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

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

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

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

}

cout << "NO";

return 0;

}

 » 8 months ago, # |   0 Does Someone have a simpler solution for problem C that does not use Hash-maps or RB trees?
•  » » 8 months ago, # ^ |   0 here: 55450645I 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
 » 8 months ago, # |   0 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 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I'm not sure if this is performance bottleneck, but I don't recommend to use string as key of map.
•  » » » 8 months ago, # ^ |   0 Thanks for the recommendation, will remember it from now on.
 » 8 months ago, # |   0 Editorial for B is very very good. Thanks for the effort McDic
 » 8 months ago, # |   0 Can someone please explain how the time complexity of the editorial solution for C is O(nlogn) or O(n)?
 » 8 months ago, # |   0 I was attempting problem B and I got WA in test 9.My approach is to first scan the whole picture in 3x3 squares for the "centre" pattern: .*. *** .*. If the program detects more than 1 centre, it returns false. Otherwise, it records all the consecutive '*' grids from the centre in 4 directions into a list (with the centre included). Finally, it checks for any '*' grids in the picture but not on the list.Can anyone point out the errors of my approach/implementation? Thank you very much!Submission: 55542827
 » 8 months ago, # |   0 Can anyone explain me how to use and implement C (Beautiful Lyrics) using hashing in c++. I did it without hashing and am getting TLE.
 » 8 months ago, # |   0 can anyone explain in C https://codeforces.com/problemset/submission/1182/55726315 why i am getting TLE on test case 5
 » 8 months ago, # |   0 For problem D, this submission is accepted: Incorrect solution. Even though it outputs 6 for this test: 14 12 10 10 8 8 6 6 4 4 2 2 1 2 3 3 5 5 7 7 9 9 11 10 14 9 13 While the correct answer is 1.
•  » » 8 months ago, # ^ |   +8 I will add this testdata, sorry for that issue.
 » 8 months ago, # | ← Rev. 2 →   0 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.
•  » » 8 months ago, # ^ | ← Rev. 4 →   0 (This is wrong)
•  » » » 8 months ago, # ^ |   0 Got it thanks!
•  » » » » 8 months ago, # ^ | ← Rev. 5 →   0 I'm sorry for wrong formula. I wrote correct formula again.Let $\frac{p}{q}x \pi = Q\pi + R$ ($0 \le R \lt \pi$)Then $2px = 2qQ + \frac{2qR}{\pi}$So we are going to find the closest remainder to $q$, since $0 \le \frac{2qR}{\pi} \lt 2q$.
 » 5 months ago, # |   0 can i get the explaination for 1st problem
 » 4 months ago, # |   0 Can anyone help me how to come up with the dfs solution in problem B.