### Sooke's blog

By Sooke, 6 months ago,

1337A - Ichihime and Triangle

Idea: Sooke

Tutorial
Solution by Sooke

1337B - Kana and Dragon Quest game

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander

1336A - Linova and Kingdom

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander

1336B - Xenia and Colorful Gems

Idea: ustze & isaf27

Tutorial
Solution by Sooke

1336C - Kaavi and Magic Spell

Idea: EternalAlexander

Tutorial
Solution by ouuan

1336D - Yui and Mahjong Set

Idea: Sooke

Tutorial
Solution by Sooke
Solution by PinkRabbit

Idea: Sooke

Tutorial
Solution by Sooke
Bonus

1336F - Journey

Idea: EternalAlexander

Tutorial
Solution by EternalAlexander

• +257

 » 6 months ago, # |   +55 Fun fact: 1336A - Linova and Kingdom and 1336C - Kaavi and Magic Spell were prepared for Codeforces Round #564 (Div. 1) but unused for some reason.
•  » » 6 months ago, # ^ |   0 For problem 1336A — Linova and KingdomMy approach is to do dfs and then sort the nodes is decreasing order wrt size of sub tree. If two nodes has same sub tree size, then we will pick the node with smallest depth first.Can you please tell me, why this approach is wrong.
•  » » » 6 months ago, # ^ |   0 It is just wrong logic.
•  » » » » 6 months ago, # ^ |   0 Yeah, understood I found the counter example. Thank you.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 For problem 1337E — Kaavi and Magic SpellMy approach is to use dp with 3 dimensions, for every character I put in A, I am calculating no. of substrings it is forming.Initial state: dp[0][i][i] = 2 (if S[0] == T[i])My state transition: dp[i][st][end] = Summation of (dp[i-1][st+1][end]) if S[i] == T[st] Where st runs from 0 till T.length and end starts from st.And my submission is here https://codeforces.com/contest/1337/submission/77231262My solution is failing at 7th test case, could you please let me know if the approach is correct and where I am going wrong?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +8 sorry I mistook something...just forget what I said
•  » » » 6 months ago, # ^ |   0 forget about the logic.. n^3 dp array won't fit into memory limits
 » 6 months ago, # |   +33 This round has given me confidence.Thanks to the author and the examiners!
 » 6 months ago, # |   0 Is there Chinese solution?
•  » » 6 months ago, # ^ |   +8 You can check luogu, some nice guys have written Chinese editorials there.
•  » » » 6 months ago, # ^ |   0 Thanks.
•  » » 6 months ago, # ^ |   -30 no
 » 6 months ago, # |   +3 Thanks problem-setters for the editorial. I will try to solve C next time
 » 6 months ago, # |   0 will there be any dp solution for 635 div2 'C'?If yes, Please explain.
•  » » 6 months ago, # ^ |   +14 I think you can do it by something like $dp_{i,j}$ -> the answer when $j$ nodes chosen in the subtree of $i$. But the complexity will be $O(nk)$. And you can use the alien trick to optimize it to $O(n\log k)$ or sth, but it seems very stupid.
•  » » 6 months ago, # ^ |   0 Isn't counting how many nodes are there that are under a node u and connected with you is DP. Like this? 76935092
•  » » » 6 months ago, # ^ |   0 This was greedy approach,i think so.
•  » » » » 6 months ago, # ^ |   0 I think greedy was the last step where I used priority_queue. Maybe I am wrong. I face problems with dp and greedy.
•  » » » » » 6 months ago, # ^ |   +6 In this problem, if you have used the fact that you have to color all nodes of subtree of ith node (except the ith node) before coloring the ith node, then you have used a greedy approach.
•  » » » » » » 6 months ago, # ^ |   0 And I did exactly the same.
•  » » 6 months ago, # ^ |   0 manan_shah, probably you can contribute to this.
•  » » » 6 months ago, # ^ |   0 actually my solution is the same as the editorial. 76863601 The cnt is maintaining the no. of nodes in the subtree of a node including that node. Our approach would be to select the leaves, but if the value of k is greater than that, then we need to select other nodes that are at levels above the leaves and contribute to happiness. A crucial observation is that when a node is selected, it would decrease the happiness of all the other which are in the subtree. And as we have selected the nodes in the subtree already, the happiness would increase by the depth(level)-nodes in subree. So we sort the array of level-no. in subtree and select the largest k. I noticed that I could have computed level by dfs also as presented in the editorial. I had the bfs approach in mind first and then I noticed that it isn't the only thing so I had to use dfs.
•  » » » » 6 months ago, # ^ |   0 I dont understand what you said tha "and as we have selected the nodes in the subtree already, the happiness would increase by the depthe nodes in subtree" please can you explain again..
•  » » » » » 6 months ago, # ^ |   0 our main idea is to select the leaves but now if we have more to select, we will pick one level above the leaves. So, which ones should we pick? We pick the ones having maximum happiness. Now if we pick one,we know that it will add happiness by the level of that node, but as we have picked all in its subtree before its picking,we need to subtract the number of nodes in its subtree as while travelling up, the current node won't count. so, finally we just sort all the values(level-no. in subtree)(net happiness which every node would provide) Hope this helped.
•  » » » » » » 6 months ago, # ^ |   0 ohh, now i got the point. thank you so much
•  » » » » 5 months ago, # ^ |   0 What's the use of level[0]=-1000000; in your code?
•  » » 6 months ago, # ^ |   0 Video editorial of 635-Div2-C
 » 6 months ago, # |   +22 I have prepared video editorials, check them out for more insight about the problems.Div2C/Div1ADiv2D/Div1B
•  » » 6 months ago, # ^ |   +20 If possible try to make video editorial for DIV2-E, It would be more helpful if you do so.
•  » » » 6 months ago, # ^ |   +33 This guy explain div2 E in excellent way.
 » 6 months ago, # |   0 is the note of div 2 E right?
•  » » 6 months ago, # ^ |   0 ok i got it i didnt read the input the first string taken is S not t
 » 6 months ago, # |   0 Div2 C and Div2 D were great problems. Thanks to the authors of the round!
•  » » 6 months ago, # ^ |   +4 It could be greater if the authors didn't gave the case 1 1 1 1 1 1000000000 in the sample. Then, a lot of people like us would have assume ans = 1e18 first instead of 9e18. And would have got WA and do debugging. Anyway, C and D was nice. Learned a lot solving these.
•  » » 6 months ago, # ^ |   0 Problem C was harder than Problem D for me. :(
•  » » » 6 months ago, # ^ |   0 it's easier, in D u've used approach from editorial?
 » 6 months ago, # |   0 Thank you for funny legends!!!
 » 6 months ago, # |   +10 Can someone please explain to me why Div.2 C got wrong answer on test 6? https://ideone.com/EhLzvj. My idea is that I create a vector from 1 to all the leaves. I then create another copy of it and increase the sum by the difference between each of the vectors. Can anybody help me and tell me how to get it to be accepted?
•  » » 6 months ago, # ^ |   +3 Well, it is simply wrong logic.
•  » » » 6 months ago, # ^ |   +7 Thank you for your help. I have just understood why it doesn't work.
•  » » 6 months ago, # ^ |   +2 Why am I getting all these downvotes? I just asked a question about a problem that I thought about incorrectly! What is wrong? Do you just see a downvote and say I will go with the flow or what?
•  » » » 6 months ago, # ^ |   -70 Maybe Div.2 C seems too easy.And your idea is totally wrong that seems like you are fake.
•  » » » » 6 months ago, # ^ |   +14 Wait what? What do you mean I am fake? A robot or something? I honestly don’t get it. I am just a kid in college who is currently a trainee at ACM and who is definitely passionate for competitive programming. What is wrong with you!
•  » » » » » 6 months ago, # ^ |   -49 There is an another reason.If you usually chat in codeforces,you will find that the people whose rating is high hardly gets downvotes.But I exactly don't care about thing.
•  » » » » » » 6 months ago, # ^ |   +6 What do u mean ?!?!? He just asked a q.U don't wanna answer just scroll down.
•  » » » » » 6 months ago, # ^ |   0 dude just dont listen to him , he is just another blockhead who had been struggling in his life, don't give shit to these people.
•  » » » » » » 6 months ago, # ^ |   -50 Aren't you?
•  » » » » » » » 6 months ago, # ^ |   +10 No one understands why you said the guy asking his question is fake. Maybe you just like to keep receiving downvotes, I suppose...
•  » » » » » » » » 6 months ago, # ^ |   -44 Because Chinese people in 某谷 always pretend themselves.I 'm sorry for what I say.
•  » » » » » » 6 months ago, # ^ |   0 Yeah, will do. Thanks man
•  » » » » » 6 months ago, # ^ |   +3 Tips: Next time before you decide to retort upon somebody, check his contribution first.
•  » » » » » 6 months ago, # ^ |   +32 "fake" means "strong, but pretending to be weak" among OIers in China.I don't agree with him that you are "fake", I believe you asked the question because you really didn't know why it was wrong.However, I think it's better to find a counter-example by yourself instead of asking here. If you really want to ask here, I suggest you explain why you thought it was correct. Your explanation was not detailed, so I had to read your code, and I just couldn't understand why you thought it was correct.
•  » » » » » » 6 months ago, # ^ |   0 Ohh ok I get it now. I really hope I was actually good. Thankfully though this is the first div 2 contest that I have solved 2 questions in and I was so excited about solving C as well. Due to me solving 2 questions, my rating jumped by 129 points which is awesome! As to my question, your are absolutely right, and I am sorry I didnt provide a detailed enough explanation, it turns out it really was only bad logic. What made me believe that I had something going for me during the contest was that it failed at test 6 so I thought there was just a small thing or case that I forgot and then it would be accepted. Thank you.
•  » » » » 6 months ago, # ^ |   +5 This dude needs english classes for babies.
•  » » » 6 months ago, # ^ |   +10 The whole commenting area would be blown up if everyone having problems like yours sent a comment. If your algorithm is tested wrong and you don't know why, there are many ways to figure out besides sending a comment asking for help. Also, when a link is posted, it is more often an exhibition of another solution with a different thinking to a certain problem that people wanna share, rather than an ask for help. So try to work independently :)
•  » » » » 6 months ago, # ^ |   +13 Yeah, you are right. It's just that this is my first comment on a round and I so a few questions from people asking about their code so I assumed it would be fine. Sorry for the inconvenience.
•  » » » » 9 days ago, # ^ |   -10 kaogu
 » 6 months ago, # |   0 Why in div2 D they are using upper_bound and then decrement z instead of using lower_bound while iterating on z. When I use lower_bound it give wrong answer.
•  » » 6 months ago, # ^ |   +51 And that is why you should read carefully the definition of these functions.
•  » » » 6 months ago, # ^ |   0 Upper_bound gives value which is stricly greater than given value.why we are not checking for both values of z(upper_bound) and z-1?
•  » » » » 6 months ago, # ^ |   0 What do you mean by "checking both values of z and z — 1"?
•  » » » » » 6 months ago, # ^ |   0 let the value of x(from one of the gems) is 50 and we want find upper_bound in following array 2 5 35 52 78 100z=upper_bound() will give the value 52 which sould be taken but we are decrement z which will give the value 35
•  » » » » » » 6 months ago, # ^ |   0 Ah. You misunderstood what z was for. z was actually meant to find the largest element smaller than given value.
•  » » » » » » » 6 months ago, # ^ |   0 z is upper_bound() which is smallest element greater than given valueinfact stricly greater
•  » » » » » » » » 6 months ago, # ^ |   0 Yep, that's why we have to decrement z.
•  » » » » » » » 6 months ago, # ^ |   0 It's easy to prove: no matter what z is, the bigger rx is, the smaller (rx−gy)2 and (rx−bz)2 are; for bz it's similar.This statement is in editorial for the problem xenia and colorful gems (problem D Div-2). I still cant understand how to prove this. Can anyone help me with this?
•  » » 6 months ago, # ^ |   +7 Here's an example. #include #include using namespace std; int main() { set a = {2, 4, 6, 8}; cout << // greater or equal, but no equal element *a.lower_bound(5) << "\n" << // greater or equal, finds equal element *a.lower_bound(6) << "\n" << // strictly greater *a.upper_bound(5) << "\n" << // strictly greater, so ignores equal element *a.upper_bound(6) << "\n"; } Output: 6 6 6 8 Hope this clears things up.
•  » » » 6 months ago, # ^ |   0 Thanks, now i got my mistake.
•  » » » » 6 months ago, # ^ |   0 Could you please explain why z is being decremented?
•  » » » » » 6 months ago, # ^ |   0 Since we want the greatest value less than or equal to (let's call it) v, we find the number just before the least value strictly greater than v. There's some number just before and just after v in the set. (Or there are no numbers before, and that has to be handled separately.) upper_bound and lower_bound both give the number just after, and only are differ in whether they include v itself. The before and after are right next to each other, though, so finding the value just after and decrementing will get the value just before.In the example, suppose we have the set {2, 4, 6, 8} and we want to find the value just before 5. upper_bound gives us a pointer to 6, which is just after. Decrement the pointer, and you end up just before at 4.Now suppose we want to find the value just before 6, where equal to 6 is still ok. upper_bound gives a pointer to 8 because it never gives back the value itself. Decrement the pointer, and you end up at 6.I wish there was a standard function for finding the value before, but there isn't.
•  » » » » » » 6 months ago, # ^ |   0 As per your statement "the greatest value less than or equal to v ", if we get value equal to v we are fine with that but if it becomes less then it violates ours assumption of z being greatest of all.?????
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 If r = {5} g = {5} b = {1,7} we fix g = 5 and look for upper bound from b which is 7 and according to the editorial solution z-- will indicate 1 so red(5) <= green(5) <= blue(1) which is violating the context . Isn't it ?
•  » » » » 6 months ago, # ^ |   0 You have it backwards. That would give the condition red(5) >= green(5) >= blue(1).
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I also had the same doubt. Actually {x,y,z} are different in editorial and implementation. I will be explain using implementation code. You can figure out the difference.Some Definitions-lower_bound() — greater or equal to the element.upper_bound() — strictly greater than the element.These are steps we are doing -1. We are fixing x from vector a.2. We need to find z from vector c such that z>=x hence we use lower_bound.3. We need to find y from vector b such that x>=y hence we first use upper_bound to find element strictly greater than x then decrements it which guarantees that y<=x is followed.So y<=x<=z relation has been followed as mentioned in editorial(note the difference in conventions).
 » 6 months ago, # |   0 can anyone please explain the editorial of problem 1336B — Xenia and Colorful Gems?I am not able to understand it?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -12 sorry!
•  » » » 6 months ago, # ^ |   0 He is talking about 1336B, the Div1B aka Div2D.
•  » » 6 months ago, # ^ |   +7 I used greedy approach ... just sort all three array and take 3 pointer i,j,k and move the pointer which would give lowest value as compared to the ones we would get by moving any other pointer.Here is this link of my submission ... https://codeforces.com/contest/1337/submission/76877219
•  » » » 6 months ago, # ^ |   0 Thanks!
•  » » » 6 months ago, # ^ |   0 can u plz explain ur approach
•  » » » 6 months ago, # ^ |   0 I was trying something quite similar but couldn't implement it. Thanks a lot!!
•  » » » 5 months ago, # ^ |   0 really good solution man
 » 6 months ago, # |   0 Otherwise, if we choose its parent to develop tourism instead of itself, the sum of happiness will be greater.Here is a mistake. Should be "the sum of happiness will be smaller."
•  » » 6 months ago, # ^ |   0 I think so too. Been stuck at that line for a while. Authors please clarify.
•  » » 6 months ago, # ^ |   +7 I think you mixed up "tourism" with "industry"? In the statement, you are asked to choose $k$ cities to develop industry, but here in the lemma, we are choosing cities to develop tourism.
 » 6 months ago, # |   +1 Can anyone please explain Div2-D problem. I understood the core idea that we iterate over any one array and find closest int rest two but why is there 6 possible cases?
•  » » 6 months ago, # ^ |   0 i need to know too
•  » » » 6 months ago, # ^ |   +14 Imagine the solution : if it is ordered like $r_x \le g_y \le b_z$, then you need to run through the green set, and for every $g_y$ take a red $r_x$ just below $g_y$ and a blue $b_z$ just above.But what if the solution is rather $g_y \le r_x \le b_z$ ? You then need to run through the red set first (the middle one).Etc... You have to try all permutations.
•  » » 6 months ago, # ^ |   0 because there can be 6 possible permutations of x,y,z
 » 6 months ago, # |   0 A bit different solution for 1336D: SpoilerLet $a_1,\,a_2,\,\cdots,\,a_n$ be the initial values. Also let $t_0$ and $s_0$ be the initial number of triplets and straight subsets and let $t_i$ and $s_i$ be the number of triplets and straight subsets after inserting a tile with value $i$. This solution has 3 phases: Finding the values of $a_1,\,a_2,\,a_3$ with at most 4 queries: First we insert tiles in this order: 1, 2, 3. If $t_3 > t_2$, we can find $a_3$. If $t_3 = t_2$ (we can conclude that $a_3 < 2$ and) we can use the equation $s_2 - s_1 = (a_1 + 1)a_3 + a_3a_4 = a_3(a_1 + a_4 + 1)$ to determine whether $a_3 = 0$. Now if $t_1 = t_0$ or $t_2 = t_1$, we insert a tile with value 1. Let $t'_1$ and $s'_1$ be the number of triplets and straight subsets after this insertion. If $t_1 = t_0$, we can find $a_1$ by comparing $t'_1$ and $t_3$. If $t_2 = t_1$, we can use the equation $s'_1 - s_3 = (a_2 + 1)(a_3 + 1)$ to find $a_2$. Finding the values of $a_4,\,a_5,\,\cdots,\,a_{n - 1}$ with $n - 4$ queries: To find the value of $a_i$ ($4 \leq i \leq n - 1$), let $T$ be the current number of triplets. Also let $S'$ be the number of straight subsets before inserting the tile with value $i - 1$. Now we insert a tile with value $i$. If $t_i > T$, we can find $a_i$. If $t_i = T$ (we can conclude that $a_i < 2$ and) we can use the equation $s_{i - 1} - S' = (a_{i - 3} + 1)(a_{i - 2} + 1) + a_i(a_{i - 2} + a_{i + 1} + 1)$ to determine whether $a_i = 0$. Finding the value of $a_n$: Let $S$ be the number of straight subsets before inserting the tile with value $n - 1$. We can use the equation $s_{n - 1} - S = (a_{n - 3} + 1)(a_{n - 2} + 1) + (a_{n - 2} + 1)a_n$ to find $a_n$.
 » 6 months ago, # |   -20 I tried using calculus in Div 2 Problem D(XENIA AND COLORFUL GEMS) but was not able to achieve a good equation has anyone done it with using Maxima and Minima approach , if yes Please explain it :)
•  » » 6 months ago, # ^ |   +1 Wow
•  » » » 6 months ago, # ^ |   0 ?? :) :) Did you do it using Maxima Minima?
•  » » » » 6 months ago, # ^ |   0 no
•  » » 6 months ago, # ^ |   0 I solved it in practice using the concept of minima , i fixed two pointers for sorted r and b then binary searched g to get the best avg value of r's and b's pointer. Incrementing two pointers greedily for minimum distance segment . https://codeforces.com/contest/1337/submission/77064128
•  » » » 6 months ago, # ^ |   0 thanks for sharing it :)
•  » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ |   0 thanks for helping me out
 » 6 months ago, # |   0 This code is of div 2 problem A. Codewhy it didn't got TLE as the range of the numbers is 10^9 and if the variable d=10^9 and and b+c=2 then the loop this code should give TLEI think if loop goes beyond 10^7 or 10^8 it should give TLE
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 When using one simple loop, you can iterate up to 10^9. 10^7 / 10^8 is TLE for python.P.S. If you want, I can send you link to interesting problem, that have idea, that using up to 1.5 * 10^9 in 2 seconds and solution for it.
•  » » » 6 months ago, # ^ |   0 So if i have two nested loops having iterations upto 10^4 (each loop),would it show TLE
•  » » » » 6 months ago, # ^ |   +1 No. 10^8 is ok.
•  » » » 6 months ago, # ^ |   0 ya sure pls send it
•  » » » » 6 months ago, # ^ |   0 cant find endlish version. will try to explain in messages
•  » » » 6 months ago, # ^ |   0 If so then also it should give TLE because t<=1000 so overall worstcase will be 10^12
•  » » » » 6 months ago, # ^ |   0 Ya, point to be noted
•  » » » » » 6 months ago, # ^ |   +1 Well,I got some links which talks about compiler optimization and the way we wrote our code.how many operations per second :: codeforces5*(10^9) operations working in one second :: codeforceshow to estimate if a solution would pass time limit or not :: codeforces
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 The compiler is probably smart enough to optimize that to O(1), as in skipping the loop entirely.
 » 6 months ago, # |   +67 Is there a better explanation for Div1 C ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +144 Let me try. I will explain the same dp but with another indexation and less cases to handle.Informal: Let dp[i][j] ($i\leq j$) be the number of ways to perform $j - i$ operations in such a way that the string we've built so far will be in the position [l..r) of the final string, provided that we did not perform invalid actions. For example, if $T$ is abac then dp[2][5] is the number of ways to build ac* where * is any symbol, counting that if we'll ever finish this as a spell then we add exactly 2 more letters to the beginning. This dp is easy to calculate using dp[i][j - 1], dp[i + 1][j], s[j - i] and probably t[i] and t[j - 1].More formal: Let's change the rules for our game. The new rules follow.We have an infinite sequence of free cells, numbered by $0$, $1$, $2$ etc. Before we start, we put a separator before any of the cells (either before the 0-th cell or between any two consecutive cells). In each turn we delete the first character of $S$ and put it either into the left nearest free cell to the separator (if any), or into the right nearest free cell. We cannot put a character $c$ into the sell $i$ if $i < m$ and $c\neq T_i$. After each turn we can claim our victory if the first $m$ cells are filled (by the letters of $T$, as follows from the rules).I state that the new game is equivalent to the old one. Indeed, putting the separator before the $i$-th cell in the new game corresponds to promising that we will add the character to the front of $A$ exactly $i$ times in the old game. I leave understanding of the relation between victories in these two games as an exercise to the reader.Now it's easy to calculate dp[i][j] which is the number of ways to eventually fill exactly the cells [i, j). The answer to the problem is the sum of dp[0][j] for j from $m$ to $n$. My dp calcuation:for (int i = 0; i <= n; ++i) { dp[i][i] = 1; } for (int len = 1; len <= n; ++len) { char c = s[len - 1]; for (int i = 0; i + len <= n; ++i) { int j = i + len; if (i >= m || t[i] == c) { dp[i][j] += dp[i + 1][j]; } if (j > m || t[j - 1] == c) { dp[i][j] += dp[i][j - 1]; } } } It's not necessary to calculate it in this order; one could also do for i := n..0; for j := i + 1..n.
•  » » » 6 months ago, # ^ |   0 what exactly is l and r ?
•  » » » » 6 months ago, # ^ |   +33 Oops, I meant $i$ and $j$
•  » » » 6 months ago, # ^ |   +7 I've seen that many top contestants used this indexing, but I couldn't understand it before. Thanks for the explanation.
•  » » 6 months ago, # ^ | ← Rev. 5 →   +78 I myself failed to understand the tutorial too. I've read some comments under the announcement blog and have looked through some implementations. Assume that both strings $S$ and $T$ are of equal length, that is $m = n$. If it is not the case, append some special characters to $T$ that say that any character may be there. You have to count number of ways to build string $T$ using the two operations. Let $dp(l, len)$ be the number of ways to build string $T[l, l + len - 1]$ having used first $len$ characters of $S$. When you have a string $T[l, r]$ and you consider the next character, that is $S[r - l + 2]$, you can proceed to states $T[l, r + 1]$ and $T[l - 1, r]$, but only when $T[l - 1] = S[r - l + 2]$ or $T[r + 1] = S[r - l + 2]$ respectively. If $T[i] = ?$, a special character, then it is always true that $T[i] = S[j]$, for any $j$. To get the answer remember that you don't have to use all $\lvert S \rvert$ characters, you may stop after some steps, so you need to sum $dp(1, len)$, for $len \ge \lvert T \rvert$. I assumed that $\lvert S \rvert = \lvert T \rvert$, but you still need to store the initial length of $T$ before appending special characters to calculate the answer. Have a look at my submission 76955112. The hack I use when filling initial $dp$ state is proceeding up to $n + 1$ as without it I don't get correct $dp(n, 1)$ because $dp(n + 1, 0)$ is used.I would like to see the tutorial to be presented in a clearer way so I can understand how exactly our solutions are different.
•  » » » 6 months ago, # ^ |   0 Nice explanation!!
•  » » » 6 months ago, # ^ |   +4 Your approach of filling special character made the problem much easier to understand. Thanks for the explanation.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I implemented like this by handling base cases differently- https://codeforces.com/contest/1337/submission/77173179
•  » » » 6 months ago, # ^ |   0 Thank you so much !!!!
 » 6 months ago, # |   +6 Here is a solution for div2 C (detail explanation with code ) Check Here
•  » » 6 months ago, # ^ |   0 Is this a sort of blog of yours?
•  » » » 6 months ago, # ^ |   0 Yap!
•  » » 6 months ago, # ^ |   +1 You say that for a node with c children and at level x from root, if we choose as tourism city then it will contribute (c)*(x). But that presumes that all the ancestors are tourism cities as well. What if not all ancestors are tourism cities?
•  » » » 6 months ago, # ^ |   0 There is no meaning of building industry on the ancestors (it wont maximize) Because if a node has c*x happiness (assuming all the ancestor is tourism spot) Then we will first build industry on that not on its ancestor And thats why if a node give c*x additional happiness its ancestor will give less for sure
•  » » 6 months ago, # ^ |   0 In step 4 you said that if a node has c children and it is at a depth of x,then it will give c*x happiness if we select it...select it as what?? Industry or tourism?? if we select it as a tourism city, then i think happiness will be c*(x+1).As depth of a node u means the number of nodes in the path [1,u).u is excluded. So if we include u as a tourism city then the number of tourism city in front of the c children becomes (x+1). So happiness becomes c*(x+1). I am stuck here. Please Help.
•  » » » 6 months ago, # ^ |   0 Suppose Node A has depth x [1,x] x included A has c children and as its tree if we are going to select A we must have build industry in all of its children (remember A is still tourism we have not build anything) A as a tourism spot — c*x ( as all children will pas through x nodes) A as a industry — we have now (c+1) industry and (x-1) tourism spot so (c+1)*(x-1)Remember its tree so we are just thinking about that particular branch and then comparing it with others
•  » » 6 months ago, # ^ |   0 There are a few places where you have mixed tourism and industry and the total contribution by each node towards the total happiness will be (c-x).
•  » » » 6 months ago, # ^ |   0 I may have make it bit blurry . I took (x-1) as remaining tourism spot where taking it x will make it clear
 » 6 months ago, # | ← Rev. 2 →   0 Is there any specific reason for vector/set giving TLE in div1B ? I was trying to optimise my logic but couldn't come up with anything, so randomly changed vectors to arrays and it passed in around (1/15)th of the time limit. Got around 6-7 wrong submissions simply because of using vectors :/ I don't think I have ever gotten TLE before with n being 1e5 and the code running in O(n.logn) with vectors :(
•  » » 6 months ago, # ^ |   +28 Looking at the code i guess you simply forgot to put the "&" when passing vector to functions.
•  » » » 6 months ago, # ^ |   0 Oh damn. I completely ruined the contest because of this silly error. :( Thanks!
 » 6 months ago, # |   +1 Is std::nth_element faster than std::sort?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +14 Yes, it has Linear complexity since it doesn't sort the entire sequence. Rather, places in the nth position the number which should have been in that position if the sequence was sorted. The rest of the elements won't be in any particular order except for the fact that all elements before the nth element won't be greater than the nth element and all the elements after it won't be smaller.
 » 6 months ago, # |   +3 I solved the Div2D 1337D - Xenia and Colorful Gems a bit differently. I created an array $v = r \cup g \cup b$ and sort it with keeping track of from which set they come. Whenever I have found $3$ numbers, I calculate an answer and keep the best one. First, notice some observations. For an $rrrggggbbbb$ portion, it is better to take the latest $1st$ number and the earliest $3rd$ number in a sorted triplet to find the best result. For an $rggggb$ portion, the best $g$ would be the one which is the closest to $(r+b)/2$. One can easily prove this using some mathematical expression. Once we read the first number (and know which set it's coming from), the $5$ cases are possible while iterating over $v$. Consider the array $v$ looks like this in the beginning.$r_0 r_1 r_2 g_0 g_1 g_2 g_3 b_0 g_4 r_3 ...$Cases: We are still reading the $1st$ type of number. If so, just take the latest one ($r_2 g_0 b_0$ is better than $r_0 g_0 b_0$, using observation $1$). A new type of number has been read. This is our $2nd$ number. Once we have found some $2nd$ number, we are looking for a $3rd$ one. If the $2nd$ number keeps repeating, we just take all of them to a temporary array. If the $1st$ type of number comes back instead of $3rd$ or $2nd$, make it the new $2nd$, and turn the old $2nd$ into new $1st$. ($b_0g_4r_3$ is better than $g_3b_0r_3$) Lastly, if we indeed reach a $3rd$ number ($r_2 g_0 g_1 g_2 g_3 b_0$ or $b_0 g_4 r_3$), we need to find the best $2nd$ number from the temporary array using binary search. Say, $r_2 g_1 b_0$ is the best we have found. After finding the result, make the current $2nd (g_1)$ into $1st$ and the $3rd (b_0)$ into $2nd$, waiting for an $r$ to occur and $gbr$ to happen. But wait, is that right? Not really. We indeed want a $gbr$ to occur, but the best $g$, in this case, is not $g_1$, it's $g_3$, the one that's right before the $b_0$ which we declared as the new $2nd$ (or the old $3rd$). It's similar to the Case $1$ described above. Be careful at this part. This eventually goes over all possible triplets, and every time we find a triplet, we find the best middle ($2nd$) number using binary search. My submission: 76948887.
 » 6 months ago, # |   0 Why does finding 3 closest numbers using 3 pointers in the 3 sorted array(moving ahead the pointer with min value) fail in DIV2-D.Can someone please point out a case?
•  » » 6 months ago, # ^ |   0 I'm not 100% sure how are you going to update the pointers, so try this case. 3 2 2 2 1 2 2 3 2 5 2 2 2 2 3 1 2 2 5 2 2 2 2 3 2 5 1 2 All 3 here are actually the same, but I have a feeling that your pointer update process might fail in 1 or 2 cases.
•  » » 6 months ago, # ^ |   0 it will not fail, you just have to adjust according to requirement of min of the sum of squares. Check out my solution 76926016
•  » » » 6 months ago, # ^ |   0 why are you using sum of squares to move the pointers instead of moving the pointer which points to the minimum element?
 » 6 months ago, # |   0 For Div2(C), my logic was to sort nodes ascending according to their degree(no of other nodes they are connected to) and then descending according to their depth. Then choose first k nodes as industry. Why is this approach incorrect ? Can anyone suggest a test case please?
•  » » 6 months ago, # ^ |   0 6 3 1-2 2-3 3-4 4-5 4-6
•  » » » 6 months ago, # ^ |   0 thanks a lot saurav. I appreciate your effort
 » 6 months ago, # |   +12 EternalAlexander could you please simplify the notations of the problem div1 C?
 » 6 months ago, # |   +3 Can Anyone explain the Top-Down Approach for Div.1 (C) 1336C — Kaavi and Magic Spell ???
 » 6 months ago, # |   -8 Everyone seems to be solving 2E/1C in $O$$($$n^2$$) memory while tourist did in O(n) — 76845451. Can someone who understands his approach please explain how it is different from the one discussed in the editorial? •  » » 6 months ago, # ^ | +15  » 6 months ago, # | 0 I am not getting the solution of linova and kingdom can anyone explain me?????  » 6 months ago, # | +5 For Div2 D. I used a simple 3 pointer search similar to this gfg link. My submission - 76926016 •  » » 6 months ago, # ^ | +3 My approach is same with you. I guessed this solution during the contest, but can't proof it until now:( •  » » 6 months ago, # ^ | 0 on what basis u are incrementing i,j,k in while() loop??? plz explain :( cant get this. thank u •  » » » 6 months ago, # ^ | 0 I calculated 3 new sums(tmp1,tmp2,tmp3) by increasing each one of i, j and k. Then increased i, j or k whichever resulted in the smallest tmp value.  » 6 months ago, # | 0 I dont understand the meaning of size(u) in problem C. Please explain me the reason why we subtracted it from the depth of every node?? •  » » 6 months ago, # ^ | 0 to subtract the losses because of converting industry to tourism. This is because there will be no convey from this city.  » 6 months ago, # | 0 [problem:div2c]In this problem first i'm trying to add all the happiness values of all the farthest nodes then second farthest and so on untill i have taken  » 6 months ago, # | 0 Can anyone help with this proofno matter what z is, the bigger x is, the smaller (x−y)^2 and (x−z)^2 are; for z it's similar. Div2/D Problem Xenia and colourful gems  » 6 months ago, # | ← Rev. 2 → 0 Can anyone help me understand the approach div2 E Kaavi and magic spell? What is j represent here? Dp[i] [j] represents what?  » 6 months ago, # | 0 Can anybody explain why my submission 76966044 for Div 2C is getting Runtime error on Testcase 9? My approach is the same, i.e calculate depth — (no. of nodes in it's subtree) for every node and then print the sum of the k largest elements. •  » » 6 months ago, # ^ | 0 I never used python. How does this work with local variables and recursion? Codedef numberOfNodes(s, e): count1[s] = 1 for u in graph[s]: if u == e : continue numberOfNodes(u, s) count1[s] += count1[u] return(count1)  •  » » » 6 months ago, # ^ | 0 If you are asking about the variable count1, I have already initialized it outside the function, on line no. 29 •  » » » » 6 months ago, # ^ | 0 So why do you return it, and copy to treecount?What about example 5 of this tutorial? As I understand it says the local variable is local. •  » » » » » 6 months ago, # ^ | 0 Right, the variable declaration might have been causing some problems in the recursion, so i changed from the recursive approach to an iterative approach and it finally got AC. Thanks a lot  » 6 months ago, # | 0 Why the ans is b,c,c in the first question instead of b,c,d in the first question? •  » » 6 months ago, # ^ | ← Rev. 2 → 0 let a=1,b=1,c=2,d=3 taking sides as b=1,c=2,d=3 . 1 + 2 == 3 . not Correct. the thing is b+c is always greater than c but if you choose third side as d , in some cases b+c will equal d ( because d > c ) •  » » » 6 months ago, # ^ | +1 Means we haveto follow the property x+y>z, x+z>y && y+z>x Right? •  » » » » 6 months ago, # ^ | 0 yes , sum of two sides greater than third •  » » » » » 6 months ago, # ^ | 0 Thank you so much. •  » » 6 months ago, # ^ | +4 By choosing b, c, c, notice that b + c > c and c + c > b. These 2 inequalities works for all positvie b and c, hence it always work.If you did b, c, d, b + c can potentially be less than d. For example, simply consider the input 1 1 1 10. You would print 1 1 10 instead, when you can just build an equilateral triangle with sides 1. •  » » » 6 months ago, # ^ | 0 Thank you so much.  » 6 months ago, # | 0 On 1337D i tried to sort all the three arrays, and for each fixed x, i would ternary search for y, but to make the decisions on this ternary search i would make another ternary search for z. Code . It did pass 22 test cases. It is not easy to find cases to make it fail.  » 6 months ago, # | ← Rev. 2 → 0 Why once upper bound and lower bound is used? Why I can't use lower bound/upper bound twice? can squares return value zero? Can someone please explain? •  » » 6 months ago, # ^ | 0 First lower bound used because you want to have a value which is not less than x(i.e greater than or equal to x).Second,upper_bound (with z--) to have the greatest value which is smaller than x in c,now we can't use lower_bound here because lower_bound will give a value not less than x(the value may be equal to x we don't want that we need strictly greater) for eg. say we have c= 2,3,6,6,6,7 and x=6 now when we use z=lower_bound(....)(which is wrong) z will be equal to 6 and z-- =3 but what we need is z to be 7 and z-- =6 which will minimise the difference. •  » » » 6 months ago, # ^ | 0 Thank you, It was very helpful and well explained. •  » » » 6 months ago, # ^ | 0 What if c = 2,3,7 and x = 6. We want z = 7 but z-- will make it 3 which is less than x? •  » » » » 6 months ago, # ^ | 0 That's why we are trying different possible combinations  » 6 months ago, # | +1 Cant find Tutorial of 1337D Problem (Ps: I am new here can anyone help) •  » » 6 months ago, # ^ | 0 1337D is 1336B - Xenia and Colorful Gems because Div1 and Div2 both use the same problems, but use different names for some fancy reason.  » 6 months ago, # | +15 For div.1 E2 Lemma 3How to proof that the linear space B has exactly m-k bases ? •  » » 6 months ago, # ^ | ← Rev. 3 → +8 First, it is clear that the length of B is m when k=0.Every time we add a new base to A (also, k is increased by 1). B is impossible to be B before, we must remove some bases in B. If we remove more than 2 bases in B, the length of B is minus when k is increased to m!So the length of B has to be m-k.UPD: I found a much easier way to prove it. See it in the new tutorial.  » 6 months ago, # | ← Rev. 3 → 0 I am trying to implement div2C, my code clearly runs in O(nlogn) time, but I keep getting TLE. one of my subbmissions. I have checked many times but couldn't find what is wrong. •  » » 6 months ago, # ^ | 0 still couldn't figure this out, can anyone help here please? •  » » » 6 months ago, # ^ | +1 https://codeforces.com/blog/entry/75996?#comment-605586 this was the error  » 6 months ago, # | 0 i don't know why i am getting WA in div-2 D.I am using 3 pointer technique to minimize the difference between largest and smallest element chosen and then finding the mid element which minimizes the answer. here is link to my code: https://ideone.com/XzeUzs thanks in advance  » 6 months ago, # | ← Rev. 2 → +27 Another solution for 1336C: SpoilerAssume we have n positions number from 0 to n-1.We delete the letters in S and put them in these positions.We can simply see that the operations described in the statement can be changed to these: Put the first letter arbitrarily in the positions. Put other letters either at the front or at the back of the sequence of letters we put in the positions. And the dp is quite obvious now:Let dp[i][j] be the answer when we delete the first i letters in S and the start of the sequence in the positions is j.We can choose to put the i+1 letter either at the front or at the back of the sequence.If the position we put this letter in is between 0 and m-1,we need to make sure this letter equals to the corresponding letter in T.That means:(if the dp is valid)dp[i+1][j-1]+=dp[i][j]$$dp[i+1][j]+=dp[i][j]$Of course,$dp[1][j]=2$ if $j>=m$ or $S[j]==T[j]$.The final answer is $\sum_{i=m}^{n}dp[i][0]$.This solution is easier to think,understand and implement than the editorial.
•  » » 6 months ago, # ^ |   +8 Thanks! Much easier to understand and implement. In case anyone needs the code — 77121142
•  » » » 6 months ago, # ^ |   0 Thanks nikhil! beautifully implemented.
•  » » 6 months ago, # ^ |   0 why is dp[1][j]=2 for j>=m?
 » 6 months ago, # |   +13 Can anyone re-explain E1 to me ? :'(
 » 6 months ago, # |   0 My observations and solution for Div2 C / Div1 A and Div2 D / Div1 B in the Announcement thread:Div2 CDiv2 D
 » 6 months ago, # |   +6 There is another straightforward to think greedy solution using hld for Div1A:Let, $t(u) = \text{number of chosen vertices in subtree of }u$, $l(u) = \text{level of }u\text{ if we root the tree at }1\text{ (in particular }l(1)=0)$.Maintain $f(u) = l(u) - t(u)$ for all free (not chosen) vertices.Initially, $\text{ans}=0$. Then, do this $k$ times: Choose $v = \text{arg}\,\max\limits_{u\text{ is free}}\,f(u)$. $\text{ans} := \text{ans}+f(v)$. To maintain $f(u)$, you need to decrease $f(u)$ by $1\, \forall u \mid u \in \text{path}(1 \rightarrow v)$. (Do this using hld) Complexity: $\mathcal{O}(n + k \log^2 n)$
•  » » 6 months ago, # ^ |   +4 how is that straightforward
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 $f(u)$ means how much I can gain from choosing $u$... this is the first thought that crosses mind.
•  » » » » 6 months ago, # ^ |   0 Trying to put tourism spots at nodes with maximum size subtrees first comes to mind first (which is incorrect, but can be fixed).
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Since we would choose all nodes in a subtree of node u before u itself, we would better use number of all nodes in that subtree in the first place. Instead of adding them one by one.
•  » » 6 months ago, # ^ |   0 Hey I have been trying to come up with solution div2c for a while. But even after reading editorial and some comments I could not understand the observations. May be I am thinking in a differnet away that is not close to the actual solution or I am lost. Can you please helpe understading some initial obersavtion made by others not actual soution. May be I am not on right path.
 » 6 months ago, # |   0 A question regarding 1336A - Linova and Kingdom tutorial: why are you saying that std::nth_element in STL implies an $O(n)$ solution? As far as I understand, std::nth_element works in $O(nlogn)$ time
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 In the page you mentioned, are you reading the correct footnote? Overloads 2 and 4 take an execution policy as an additional parameter, while overloads 1 and 3 are "Linear in std::distance(first, last) on average" according to your page.For more details, see https://en.wikipedia.org/wiki/Quickselect.
•  » » » 6 months ago, # ^ |   0 Thank you, indeed, I misread the footnotes :)Then it's $O(n)$ on average and $O(nlogn)$ in the worst case, right?
•  » » » 6 months ago, # ^ |   0 I reacted to the claim that the solution is $O(n)$, which is not the case, since big-O notation marks the upper bound of the function (time complexity), and not the average.With $1 <= k < n$ the solution complexity is still bound by $O(nlogn)$Similarly, you can't say that quicksort is bound by $O(n)$ — that's its average performance, but in the worst case it's bound by $O(nlogn)$Sorry for being pedantic, just wanted to point it out.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   +8 You correctly state the average and worst-case complexities, and I agree with you that when someone says "a solution runs in O(something)", the implicit assumption is that they're talking about worst-case complexity. So the post should have said "O(n) average time" to avoid this confusion. Your concern is perfectly justified, in my opinion.I also want to point out your previous comment is absolutely correct too. Big-Oh notation can be used to denote an asymptotic upper bound to any function, and in particular you can use it to bound the average-case complexity as well as the worst-case complexity, and so "O(n) on average" is a technically correct use of big-Oh notation.Either way, nth_element could have been implemented with the Median of medians algorithm to guarantee worst-case O(n) complexity. In practice, the STL implementations we use rely on a variant of Introselect that combines Quickselect and Heapselect. Wikipedia seems to claim that the original Introselect combined Quickselect and the Median of medians algorithm for optimal worst-case complexity, but I can't confirm that.
 » 6 months ago, # |   0 I didn't understand the solution of 1336B — Xenia and Colorful Gems, ** z--; ** ans = min(ans, sq(x - *y) + sq(*y - *z) + sq(*z - x)); why z-- needed? can't we achieve the functionality? using, if (z == b.end() ) z--; 
•  » » 6 months ago, # ^ |   0 Because You need the element which is strictly greater than x which is z than z-- which implies greatest element which is smaller than x in c
•  » » » 6 months ago, # ^ |   0 then why not y++? because here now y is strictly less than x.
 » 6 months ago, # |   +2 i did not understood the editorial for problem C, it is not written well,to clarify my doubts sizu is the size of the subtree of u and depu is its depth ,consider for the last node of the tree with 5 nodes its sizu will be 1 and depu will be greater than 1 , now the author is saying the total happiness will be increased by sizu−depu: here sizu−depu=1-x ,x>1 (sizu−depu) will be a negative value,now how can negative value increase the happiness ???
 » 6 months ago, # | ← Rev. 4 →   0 In 1336B - Xenia and Colorful Gems . Why the idea of choosing nearest element (Binary search) instead of lower bound fails in Test case 48? How is that approach incorrect? My submission 77012000 . I am using a give function to print closest element corresponding to k in some array. Edit: It passed now.
 » 6 months ago, # |   0 Can anyone tell me the bug in my code for Div2C? Here's the link. I followed the same solution which is mentioned in the tutorial. I sorted the nodes according to the children count and if the children count is equal for two nodes, then I chose the node with greater depth to develop the industry.
•  » » 6 months ago, # ^ |   0 Try using unsigned long long everywhere.
•  » » 6 months ago, # ^ |   +8 The problem is: const long MAX = 9e18 -> const long long MAX = 9e18.
 » 6 months ago, # |   +101 The solution to E2 is very interesting, but the tutorial is a little bit hard to understand for me at the beginning. Here are some suggestions:(1) It would be better to use "Walsh-Hadamard transform" instead of "FWT" here, because fast or not does not matter here. (It's not affordable to explicitly compute it anyway.)(2) Similar to (1), I feel that "XOR convolution" is a little bit distracting here, because we only care about one term anyway. It made me feel that "we do Fast Walsh-Hadamard transform because we want to do XOR convolution fast", but this is not true.(3) The proof of lemma 4 doesn't really make sense. "The $i$-th number of $F^c$ only depends on $popcount(i)$, it certainly still holds after Fast Walsh-Hadamard Transform." is true because the the property here is "popcount". If you replace "popcount" with something else it will be false. The formula you listed below should be the actual proof for this lemma.If I'm going to explain this solution I will try to rephrase it as follows. The main purpose of doing Hadamard transform is to move the analysis from linear subspace $A$, which has high dimension ($k$), to another linear subspace $B=\{y:\forall x\in A, \langle x,y \rangle=0 \pmod 2\},$ which has low dimension ($m-k$). Hadamard transform provides a linear transformation between $[x\in A]$ and $[y\in B]$: $[x\in A]=\frac{1}{|B|}\sum_y (-1)^{\langle x,y\rangle}[y\in B]$. Therefore if we want to count how many vectors in $A$ satisfy some properties, we can enumerate every $y\in B$ and calculate its "contribution" instead. Formally, let $F_c$ be the set of all vectors which have $c$ 1s. Then we have $\sum_{x\in F_c} [x\in A]=\frac{1}{|B|}\sum_{y} (\sum_{x\in F_c}(-1)^{\langle x,y\rangle })[y\in B]$. If we simply enumerate every $c\in[m],y\in B$ and calculate the contribution of $y$ in $F_c$ by some combinatorial methods, we have a $O(m^2\cdot 2^{m-k})$ algorithm already. By observing that the coefficient only depends on the number of $1$s in $y$, this can be squeezed to $O(2^{m-k}+m^3)$ as in the tutorial.
 » 6 months ago, # |   0 Really clean editorial and I like it a lot. One small comment to add for Div2C. I thought of the lemma during the contest but did not end up solving the problem.For someone who wonders "why does sorting according to siz_u — dep_u and selecting the first N — K cities to develop tourism ensure that the selected cities stay connected?", it is because the siz_u — dep_u property makes it such that a child node is selected iff its parent node is selected.
 » 6 months ago, # |   +1 Elegant problems and short, concise statements. Thank you for this fine contest!
 » 6 months ago, # | ← Rev. 2 →   0 Video tutorial Div1C/Div2E 1336C - Kaavi and Magic Spell here
 » 6 months ago, # | ← Rev. 2 →   0 Someone please explain Div 2 C briefly.
•  » » 6 months ago, # ^ |   0 since the capital city is at node 1 we have to place industries in such a manner that total sum of tourism cities is maximum for each of the industry greedy thoughtyou should place all the industries as far as possible from the root. proofsuppose you have some node u with distance d which is tourist city but you are placing an industry on some node with distance d-1 or smaller on the path from 1 to u then you can always achieve better answer for placing the industry at node u so that the answer can be increased. hence you will place all the industries as far as possible from the root node problematic situation which may occur to disturb our greedy solution suppose there are two cities u, v which are at same distance d and no other city is more distant from node 1 other than these two cities and both these are non leaf solution to above situation you will prefer to make industry on node which has lesser number of children. since u, v are non leaf nodes that means their children should already have been made industry and making node u or v an industry will decrease the solution by number of children of that node as all the nodes which are in subtree of node u or node v will have one less tourist node each in their path to root.hope it's clear now
•  » » » 6 months ago, # ^ |   0 It is not the node as far as possible from root. Given node u 2 away from root and having 3 children. And node v 3 away from root but with one child only. Then you have to choose v before u, because it contributes more.
•  » » » » 6 months ago, # ^ |   +3 that is what i have said in third and fourth spoiler correct me if I am wrong
 » 6 months ago, # |   0 solution for div 2 d is very elegant
»
6 months ago, # |
Rev. 2   +9

I am trying to write an easier explanation for Div2E/Div1C.
Our target is to build a string of length $n$, which is initially empty.

1 2 3 ..... n

$dp_{i,j}$ is a state where we have already filled up all the positions in the range $[i+1,j-1]$.

1 2 3 ..... i i+1 ..... j-1 j ..... n
* ***** *

Now we will either add the next character at the beginning (at index $i$) if it is equal to $T[i]$ or we will add the next character at the end (at index $j$) if it is equal to $T[j]$. The first option will take us to the state $dp_{i-1,j}$ and the second option will take us to the state $dp_{i,j+1}$.
Our answer is $dp_{1,1}+dp_{2,2}+dp_{3,3}+.....+dp_{n,n}$.
Here is my submission.

•  » » 6 months ago, # ^ |   0 what if it's not equal to both T[i] and T[j].
•  » » » 6 months ago, # ^ |   0 Then, you can't go to any of the two possible new states.So answer for the current state $dp_{i,j}$ will be $0$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I think it should rather be Our target is to build a string of length m, which is initially empty. or did i miss something?
•  » » » 5 months ago, # ^ |   0 It's $n$. Because we will use all the characters from the string $S$.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   0 Thank's i Got it
 » 6 months ago, # | ← Rev. 2 →   0 For div2 C. When I submitted this solution. I got the Wrong answer at test case 7.But when I submitted this solution it got accepted.The only difference between these two starts from line number 34 in the wrong answer I declared the array res as vector int and for the right one, I declared it using pair of vector int.So Why one is got accepted and the other one got rejected ?
•  » » 6 months ago, # ^ |   0 the extra 0th element added to your vector res has created problems I have initalized res vector without space and I have replaced res[i] = with res.push_back() your edited and accepted solution
•  » » » 6 months ago, # ^ |   0 Thank You very much got it now .
 » 6 months ago, # |   0 someone please tell me that why we have added z==c.begin() condition in solve method in Div2. D in editorial I mean upper_bound is returning the smallest index which has greater value than the key searched so suppose if the min value of vector c is greater than the key the result will be c.begin() why would we do continue in this case (can't we form a triplet with value from vector c as c.begin() ) what's wrong with doing that
 » 6 months ago, # | ← Rev. 2 →   0 Why is this solution in Python giving Runtime Error on Case 9 76970117
 » 6 months ago, # |   0 can any one tell me why i am not getting this error wrong answer 2nd numbers differ — expected: '1999999996000000002', found: '1999999996000000000'https://codeforces.com/contest/1337/submission/77100823
 » 6 months ago, # |   0 Can anyone please explain { DIV2 : E. Kaavi and Magic Spell }. I am not getting it from the editorial. Not even the intuition.
•  » » 6 months ago, # ^ |   +5 I tried to explain it briefly here
 » 6 months ago, # | ← Rev. 3 →   +3 Nice round :) Thank you ^^btw, you don't have to actually hold the dp matrix in div1C, as the update only use the next location for each update, you can update it from left to right.Here is a very short solution: codeconst int MOD = 998244353; string s, t; in >> s >> t; vector dp(t.size() + 1, 1); int res = 0; for (int i = 0; i < s.size(); i++) { for (int j = 0; j <= t.size(); j++) { int cur = 0; if (j >= t.size() || s[i] == t[j]) cur += dp[min(j + 1, (int) t.size())]; if (j + i >= t.size() || t[j + i] == s[i]) cur += dp[j]; dp[j] = cur % MOD; } if (i + 1 >= t.size()) res = (res + dp[0]) % MOD; } out << res; 
•  » » 6 months ago, # ^ |   0 It's really short. I didn't fully understand the solution from the editorial though.I was able to solve it using O(n) space too. But I had to store two rows since my current state calculates answer using the values from the previous row.
 » 6 months ago, # |   +13 How to solve the bonus part of E2? :(
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 +1, is it somehow related to this? rabfill's comment claiming $O(2^{2m/5}m)$ complexity though I didn't get his approach.
 » 6 months ago, # |   0 In Div1 E in this part "build linear basis A with given numbers", what do you mean exactly? Build a set with minimum number of elements of the input such that all the elements are linear combination of those?
•  » » 6 months ago, # ^ |   0 consider each number as a zero-one vector in $\mathbb{F}_2^m$, then find a basis of this vector space. Then, each given number can be written as the xor of a subset of this basis.
•  » » » 6 months ago, # ^ |   0 In that case a base could be { (1,0,...,0,0) , (0,1,...,0,0) , ... , (0,0,...,0,1) }, right?I don't understand why $ans_i = p_i \cdot 2^{n-k}$.Do you know a post where i can learn this?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +15 "In that case a base could be { (1,0,...,0,0) , (0,1,...,0,0) , ... , (0,0,...,0,1) }, right?"No, that's a basis of $F_2^m$, but we want a basis of the subspaced spanned by the given vectors. As for why $ans_i=p_i\cdot2^{n-k}$: let $V$ be the set of input vectors, and let $A\subset V$ be a basis of the subspace spanned by $V$. First we look at linear combinations of $V\setminus A$, then we consider linear combinations of $A$ to get a desired popcount. Choose any linear combination of $V\setminus A$, there are $2^{n-k}$ of these, and suppose the xor sum is $x\in span(V)$. Each $x$ that we get this way can be expressed uniquely as a linear combination of vectors in the basis $A$. Now consider one of the $p_i$ linear combinations of vectors in $A$ such that the resulting popcount is $i$, and suppose the xor sum of this linear combination is $y$. There is a unique way to use the basis vectors to go from $x$ to $y$, ie. writing $y-x$ as a linear combination of the basis. This gives a bijection that shows $ans_i=p_i\cdot2^{n-k}$."Do you know a post where i can learn this?"This is linear algebra with a bit of combinatorics.
•  » » » » » 6 months ago, # ^ |   0 I don't get one moment.. Suppose we get any linear combination from $V \setminus A$ which have xor sum $y$. Then we get any subset $X$ from $A$ that have popcount equal to $i$ and xor sum -- to $x$. How come that we're always able to express $y - x$ as linear combination of vectors from $A \setminus X$?
•  » » » » » » 6 months ago, # ^ |   0 Oh, seems that otherwise we've couldn't express $y$ as linear combination of vectors from $A$. Cause linear combination of $x$ is also unique
•  » » » » » 6 months ago, # ^ |   0 Can you elaborate more on the part where you say "This gives a bijection that shows ans_i = p_i * 2^(n-k)."?
•  » » » » » » 5 months ago, # ^ |   0 Every linear combination of $V$ is the sum of a linear combination of $A$ and a linear combination of $V\setminus A$. One way to get a linear combination of $V$ with popcount $i$ is to choose a linear combination $x$ of $V\setminus A$ and a linear combination $y$ of $A$ with popcount $i$. Once we fix $x$ and $y$, we can put $x$ as the linear combination of $V\setminus A$, and $y-x$ as the linear combination of $A$. The number of ways to choose $x$ and $y$ are $2^{n-k}$ and $p_i$ respectively.
•  » » » » » 5 months ago, # ^ |   0 I have the same doubt as Ahmed_Salama, how can we say that the answer is $2^{n-k}.p_i$ Also can you please elaborate the bijection part? What exactly are we bijecting and on to what? And how does this relate to answer?
 » 6 months ago, # |   0 Can anyone please help?Problem Div2 D : I have coded solution as per editorial, verified the data types of ans, vector. I am getting correct answer for the sample test on my machine, but on submitting I'm getting a different output. wrong answer 2nd numbers differ - expected: '1999999996000000002', found: '2147483647'submission 77118100
•  » » 6 months ago, # ^ |   +16 Ok found the mistake. Was setting LONG_MAX to a long long. Still confused why I got correct output locally(on my machine), \$ g++ --version Apple LLVM version 10.0.1 (clang-1001.0.46.4) 
•  » » » 6 months ago, # ^ |   +8 LONG_MAX could be defined differently. You could define your own infinities to avoid this.
•  » » » » 6 months ago, # ^ |   0 Ok. Wasn't aware. Thanks a lot for clearing my doubt.
 » 6 months ago, # |   0 Can someone please tell me why am I getting WA on test case 6 on div2 C . My logic is to find the depth and the no. of children of each and every node. Find depth[i]-children[i] for all nodes and return the sum of the top k values Here's the code https://codeforces.com/contest/1337/submission/77153692
 » 6 months ago, # |   0 Can anyone suggest more good problems like DIV2 'C'(1336A)
 » 6 months ago, # |   0 Heres My Solution to Problem 1336C Memoized Solution I couldnt come up with dp solution can any body tell why with memoized solution its giving TLE? :)
 » 6 months ago, # |   0 SolutionWhy my code is not working for Div1 A, I have chosen all the leaf nodes then for the remaining k I have chosen nodes from that branch which had maximum happiness initially.Please help
 » 6 months ago, # |   0 I don't Understand Div 2 problem D can someone explain to me what's wrong in my idea Idea: First, assume the solution is of the form x<=y<=z fix x and found y by lower_bound(b.begin(),b.end(),x) then found z by lower_bound(c.begin(),c.end(),*y)
•  » » 6 months ago, # ^ |   0 Try this: 1 1 2 1 1 2 3 5 
•  » » » 4 months ago, # ^ |   0 I've also used the same approach.My code passes your test case. But fails System Case. For all possible 6 combinations of arrays r,g,b I've used finding x<=y<=z Approach. Please Help!Code
 » 6 months ago, # |   0 How to approach problem C. sizu−depu, how do we get to know about this? observation & intuition?
 » 6 months ago, # | ← Rev. 3 →   0 Can anyone help me why I am getting wrong answer for the test case 6 for this submission https://codeforces.com/contest/1337/submission/77191116. The problem is https://codeforces.com/contest/1337/problem/C (linova and Kingdom)
 » 6 months ago, # |   +8 Hey Guys, If you want a solution for Div.2 B — Kana and Dragon Quest GamePlease check out this video!https://youtu.be/DGo4IU143nQ
 » 6 months ago, # |   0 I use a Max heap in which I I store (-subtreesize,depth of node) and when all subtree nodes are marked ,I add parent(root) of that subtree to priority queue and Mark all the popped nodes from priority queue which are my industries still I am getting wrong answer.https://codeforces.com/contest/1337/submission/77251353
 » 6 months ago, # |   0 Given two integer arrays as input. Your function will return YES if any two of the numbers in the first array adds up to any of the number in second array. Time Complexity required O(n). EXAMPLE:1 A=[-1,8,3] B=[3,7,2] OUTPUT: YES as(-1+3=2, presend in array B) also (-1+8=7, present in array B)EXAMPLE:2 A=[9,6,12] B=[1,2,3] OUTPUT: NO can some help me out in this(similar to two sum)
 » 6 months ago, # |   0 plz explain the logic i problem D
 » 6 months ago, # |   0 Can someone please explain Magic Spells ? Ashishgup I liked your code on this. Can you just tell, what is dp[i][j] in your solution ?Thanks
 » 6 months ago, # |   0 Can anyone explain the time complexity for the 1336B problem?
 » 6 months ago, # |   0 I did same but I was getting Runtime Error which must be due to recursion limit as it will be exceeded if we have all 10^6 nodes connected in a sequence.. So I tried to increase the limit to 10^6 but for that, I got memory limit exceeded error. Then I tried to set it to 10^5, but for this one also I got Runtime error.Can anyone suggest what should I have done?
 » 6 months ago, # | ← Rev. 5 →   +18 I think I am missing something for Division 2 Problem C: Linova and Kingdom. I have the following problem with the author's solution:When calculating increase in happiness, when we choose a certain node $u$ to develop into a tourism city, then the loss is $dep_u$, this is correct: since all the parent nodes are already taken by the lemma that the author proved at the beginning. But when we calculate the gain, it is, at that moment, equal to $size_u$. But when we color some predecessor of $u$ in subsequent (later) steps, then this gain value changes, because some nodes in the sub-tree of $u$ no longer remain as an industry city. EternalAlexander, or anyone, please point out where am I wrong. Thanks!
•  » » 6 months ago, # ^ |   +18 You can see that, when you colour node $u$ all its predecessors are already coloured in previous steps. Because for all predecessors of $u$ the $size-dep$ is greater than $u$.
•  » » » 6 months ago, # ^ |   +18 OK, sorting takes the predecessors first in a branch. But out of all the possibilities over all branches, how does sorting ensure that it takes the best possible node? Because the number $size_u - depth_u$ doesn't really make sense to me, because it loses its significance when we take a child of $u$, it's value completely changes. So why do we store these numbers in an array and sort them. I think this needs some kind of proof??
•  » » » » 6 months ago, # ^ |   +18 We have proved that, in the optimal way, when you take node $u$, all its predecessors are already taken, otherwise you should take the predecessor first.So before we take node $u$, all the nodes in its subtree are definately not taken. So in the optimal way, when you take node $u$ the change to the answer is $size_u - depth_u$.
•  » » » » » 6 months ago, # ^ |   +18 Yes you have proven that, but how do you prove that out of all possible nodes in a given depth (all the nodes in previous depths are already taken), the optimal node is the node with the maximum value of $size_u - depth_u$? Because this number doesn't mean anything after a few steps. So why do we store it? And sort them?
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +18 Ok, I'll try another way to explain.Here $k$ denotes to $n-k$, i.e. the number of tourism cities.Let $f_u$ be $size_u - depth_u$.First, the optimal answer is no less than the greatest $k$ of $f_u$. Because that's the answer when you take the first $k$ nodes.Second, the answer can not be greater than that:If there exists a way to make the answer greater, assume that the nodes you've taken are $u_1, u_2 \cdots u_k$, the sum in this way will be $f_{u_1} + f_{u_2} + \cdots + f_{u_k}$, because for any node taken, all its predecessors are taken, and you can calculate the answer in this way. And you can see this is no greater than the sum of the $k$ greatest $f_u$.
•  » » » » » » 6 months ago, # ^ |   +18 The main idea is: In the optimal way, when you take node $u$, all its predecessors are already taken. If the nodes you take satisfy the condition above, assume the nodes you take are $u_1,u_2 \cdots u_k$, the answer is $size_{u_1} - depth_{u_1} + \cdots + size_{u_k} - depth_{u_k}$. If you take the greatest $k$ of $size_u - depth_u$, the nodes you take satisfy the condition above.
•  » » » » » » » 6 months ago, # ^ |   +18 OK I got it, thanks a lot!!! When you sum those values, the change in $f_u$ of parent due to child node gets added to the answer, and sorting ensures that the conditions $1$ and $2$ are always fulfilled, so it is optimal to take the best $k$. Thanks a lot, really!
•  » » » » » » » » 6 months ago, # ^ |   +18 Yes that's exactly what I meant :D
 » 6 months ago, # |   0 can someone please give solution for 1336C - Kaavi and Magic Spell with proper explaination. I can't understand the editorial.
 » 6 months ago, # |   0 Div2.C Linova and Kingdom is giving Runtime Error on test 9 on several solutions. Can anyone who faced the similar issue clarify what correction they made?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 It's called integer overflow. So use long long as your 'ans' data type to accumulate the sum !
 » 6 months ago, # |   0 Can someone explain problem 1336A like I am a 6 year old please ?
 » 5 months ago, # |   0 In 1336B-Xenia and Colorful gems, why the value of ans is set to 9e18? I kept ans as unsigned long long, and set ans = -1, thinking it would set maximum value to ans. It didn't give correct output. But setting 9e18 gave. Can anyone help me telling why? TIA.
 » 5 months ago, # |   0 Why b,c,d can't give correct ans for problem A. https://codeforces.com/contest/1337/submission/81934213
•  » » 5 months ago, # ^ |   0 Input: $a = 1,~b = 1,~c = 1,~d=1e9$. By condition we should have $(b + c) \geq d \to (1 + 1) \geq 1e9$. It's false.
 » 5 months ago, # |   0 Does anyone know more problems like 1336C — Kaavi and Magic Spell ?
 » 4 months ago, # |   0 For Div2D/Div1B My Approach is very similar to Editorial's. Its failing System Tests.We assume the solution is of the form x<=y<=z. Then Fix x and find y by lower_bound(b.begin(),b.end(),x). Then find z by lower_bound(c.begin(),c.end(),*y)We do this for all 6 Possible Combinations of Arrays r,g,b.CodePlease Help!
 » 3 months ago, # |   0 #include #define ll long long int #define inf 1000000000000 #define mod 998244353 #define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define for0(i, n) for (int i = 0; i < n; i++) #define tc(t) int t; cin >> t; while (t--) #define all(v) v.begin(),v.end() #define maxpq priority_queue #define minpq priority_queue, greater > #define vll vector #define vi vector #define pb push_back #define fi first #define se second #define pii pair #define pll pair #define mii map #define mll map #define ps(x,y) fixed< dp; int n; int steps = 0; ll ways(string a, int ind) { if (ind == n) { if (a.substr(0, t.size()) == t) return dp[a] = 1; else return dp[a] = 0; } if (dp.count(a)) return dp[a]; ll ans = 0; if (ind >= t.size()) { if (a.substr(0, t.size()) == t) ans+= 1; } steps++; ans += ways(a + s[ind], ind + 1) + ways(s[ind] + a, ind + 1); return dp[a] = ans % mod; } int main() { IOS #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif string a; cin >> s >> t; n = s.size(); a = s[0]; ll ans = ways(a, 1) % mod; cout << ans * 2 << endl; //cout << steps<< endl; } can anyone help me to optimize this ?? showing TLE on testcase 7... `
 » 3 months ago, # |   0 1336B — Xenia and Colorful Gems auto y = lower_bound(b.begin(), b.end(), x); auto z = upper_bound(c.begin(), c.end(), x);why is z-- but not z = lower_bound(c.begin(), c.end(), x)?
 » 3 days ago, # |   +24 There was a huge mistake in the tutorial of 1336F - Journey. I have fixed it now. Thanks sys. for pointing out!
•  » » 3 days ago, # ^ |   +20 :)