### FieryPhoenix's blog

By FieryPhoenix, 14 months ago,

1348A - Phoenix and Balance

Tutorial
Solution

1348B - Phoenix and Beauty

Tutorial
Solution

1348C — Phoenix and Distribution

Tutorial
Solution

1348D - Phoenix and Science

Tutorial
Solution

1348E - Phoenix and Berries

Tutorial
Solution

1348F - Phoenix and Memory

Tutorial
Solution 1
Solution 2

• +533

 » 13 months ago, # |   +185 Wow! I didn't expect the editorial published so fast.
•  » » 13 months ago, # ^ |   +8 Yeah, I also didn't expected this fast Editorial! XD
•  » » 13 months ago, # ^ | ← Rev. 2 →   -10 Maybe there's a problem in your expectation, think positive
 » 13 months ago, # |   +25 Thanks for the fast editorial!
•  » » 13 months ago, # ^ |   +23 Video solutions:
•  » » » 13 months ago, # ^ |   +9 Berries pls
•  » » » 13 months ago, # ^ |   +1 Thanks
•  » » » 13 months ago, # ^ |   0 thanks
•  » » » » 13 months ago, # ^ |   0 Hello, i didn't understand why we insert n-s at last and sort it.Can you explain?
•  » » » 13 months ago, # ^ |   0 nice editorial ✔ @striver_79
•  » » » 13 months ago, # ^ |   0 Thanks for making a youtube channel for this.
•  » » » 13 months ago, # ^ |   0 Awesome and please explain E and F.
•  » » » 13 months ago, # ^ |   +3 Thx!
•  » » » 13 months ago, # ^ |   0 thanks
•  » » » 13 months ago, # ^ |   0 Your content is very helpful. Thanks!
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Keep posting such video please. Your explanations are great...striver_79But one question...Does breaking down to cases means constructively thinking? I mean if it constructive do I need to always break down into cases? "You said how to solve such problems?" Shall I assume that somehow you got the feeling that the problem was constructive? Sorry if I asked silly questions. Again thank you for your efforts...
 » 13 months ago, # |   0 Editorial so early -.-
 » 13 months ago, # |   +63 Wow, it was very good contest. Fast editorial, cool tasks with short conditions. Thanks!
 » 13 months ago, # |   +40 Damn I feel so stupid after seeing the solution for B Nice problems man!
•  » » 13 months ago, # ^ |   +10 Can anyone recommend practice problems for constructive I really suck at it
•  » » » 13 months ago, # ^ |   -346 I suck at them too. Hate constructive. Downvote the author for making so bad B
•  » » » » 13 months ago, # ^ |   +112 Nahh B isn't bad We just suck XD
•  » » » » 13 months ago, # ^ |   +52 Perhaps that mindset is one of the reasons you are hardstuck Specialist. Never blame the problem, only blame yourself for not practicing enough. With this mindset, improving quickly suddenly becomes much easier for anything you do :)
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Can u pls explain why we go upto n*k.. I did it that way but not getting how its working
•  » » » » » » 13 months ago, # ^ | ← Rev. 3 →   +5 We need to print at least n numbers. Printing k of the numbers (if all unique) or c unique numbers and k - c "1"s (or any other digit) (where c is the number of unique elements) will guarantee that you print all numbers in the input, which is required in the output whatsoever be the insertions you make. The primary goal of constructive problems is to come up with something simple that does the job. You could go all in and actually calculate the sum of first k numbers and then go about trying to solve the problem, but that just makes life a lot lot harder.
•  » » » » » » » 13 months ago, # ^ |   0 Sire, I've a doubt in part B. When we store element in set, elements are reordered. So when we output the elements, order may be different than what is in the original array. Since we want to preserve the order, how will it work? Thanks.
•  » » » » » » » » 13 months ago, # ^ |   0 I am a java coder, I used LinkedHashSet to store elements up to k distinct elements and it worked because it maintains the order of elements.
•  » » » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 The ordering of elements in the set made from the input array $a$ don't play any role once you establish the necessary periodicity of $k$ and print $n$ times, although, it can be done this way too.
•  » » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 I'll try to prove how printing the set (of size $k$) $n$ times will end up printing all necessary elements preserving their ordering.Firstly, any case where $c$ (count of distinct elements) is greater than $k$ is not possible.Secondly, if c == k, simply printing the entire set of elements $n$ times does the work of maintaining the ordering of actual elements as the identity s [k + i] = s [i] holds true. ProofLet the input array be a of size $n$ with exactly k distinct elements (as we are proving for the case c == k right now).Let $s$ denote the set of elements of $a$ (Remember that, here, size of set is $k$).$a = [a_1, a_2, a_3,...,a_n]$$s = [s_1, s_2, s_3,...,s_k]$Yes, the ordering of elements has changed when put in the set. But that doesn't play any role when you print the set $n$ times. Let's see how.Print the set twice. It'll look like this:$s = [s_1, s_2, s_3,...,s_k, s_1, s_2, s_3,...,s_k]$Notice that, $s [k + 1]$ is indeed the same as $s [1]$. It follows for all other positions $i$ in the set i.e. taking any subarray of size $k$ will yield you the same sum.Now, how do all input elements end up getting printed irrespective of their ordering in the set when you print this set of period $k$ $n$ times?$a [1]$ belongs somewhere in the set at some position $s [i]$. When we print the set once, this $a [1]$ ends up getting printed. Now, when we print the set for the second time, $a [2]$ which is in some position $s [j]$ in the set, will end up getting printed. Notice that $a [1]$ was already printed and now we print $a [2]$. Using similar arguments, all $n$ elements of $a$ get printed by printing the set $n$ times. As the set also follows the above mentioned periodicity property, every subarray has the same sum too!Notice how the problem author gave us a clue in the question. He/She/They mentioned that it will not take more than $10^4$ size to print the expected array. Upper bound for $n$ and $k$ is $10^2$. Max value of n*k is indeed not more than max expected size.Thirdly, if c < k, we can simply add k - c "1"s, like mentioned in the editorial, to make the array periodic with period $k$ and same sum for every subarray. Then, the above proof holds for this condition too.Cheers! GL for your next contests.
•  » » » » » » » » » 13 months ago, # ^ |   0 Thanks a lot, picture-perfect!
•  » » » » » » » » 13 months ago, # ^ |   0 you don't need to preserve order. you have set n times: [][][]<- denote set 3 times. let say you need 413 as subsequence. because in each set you have each unique element, you can remove everything from first [] except 4, from second [] remove everything except 1, from last [] remove everything except 3. And, by definition resulting is subsequence, subsequence it's anything you can get by removing elements.
•  » » » » » » 13 months ago, # ^ |   0 As you need to printk numbers n times to make sure the chronological order... So k numbers n times written is total = (n*k)
•  » » » » » » 13 months ago, # ^ |   0 You can think it like this :Suppose k=3 and the sequence is 4 3 4 2 So, you need to make a new sequence with period 3 basically.You can make a set with distinct elements from the original sequence and of length 3, like (2,3,4). Now, you just replace every element with this small sequence. You'll get - 2 3 4* 2 3* 4 2 3 4* 2* 3 4 (* represents the elements in the original sequence)
•  » » » » » » » 13 months ago, # ^ |   0 really nice . Thankyou
•  » » » » » 13 months ago, # ^ |   -143 Even if I practice for lifetime I can't do shit constructive problems
•  » » » » 13 months ago, # ^ |   +1 No, It was a great problem Just needed to think in another way :/
•  » » » » 13 months ago, # ^ |   +7 Why downvote author try to do it.
•  » » » » 13 months ago, # ^ |   +15 Instead of blaming the author, you should focus on practising more.
•  » » » » » 13 months ago, # ^ |   -128 Stop giving advice when you become just become specialist first time. No one asked for it.
•  » » » » » » 13 months ago, # ^ |   +14 Now you are criticising me instead of practising more. That's the reason for your fall. And yes, I become an expert first time with my own potential. And I didn't blame anyone when I was falling. I was seeing my mistakes and was improving them. You should try this too.
•  » » » » » » » 13 months ago, # ^ |   -112 WTF retard. You are not expert you are barely specialist. And no one cares for advice unless you are candidate master or above. SO pls gtfo
•  » » » » » » » » 13 months ago, # ^ |   +17 You too are not eligible to decide the quality of the question, so better you Fuck Off and start practicing.
•  » » » » » » » » 13 months ago, # ^ |   +18 Please, respect others at least.
•  » » » » » » 13 months ago, # ^ |   +17 are you shit!!!...... suraj_gupta is right..... and i am watching your every comment.... why giving so much hate ....... you were not able to solve problem during contest then it is your problem not of Author.... Around 10000 peoples had solved it... nd you are accussing author for your fault....
•  » » » » » » 13 months ago, # ^ |   0 The worst people are those who have not very high rating,looking down upon those who have lower rating,but diligent guys
•  » » » » 13 months ago, # ^ |   +3 seriously you want to blame him for doing so bad in the contest yourself. That's ridiculous.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +1 In the last contest by dreammoon, the problem div2 C was excellent read its tutorial. It is more like a general way to solve any constructive algo. problem that will help surely. https://codeforces.com/contest/1330/problem/C
•  » » 13 months ago, # ^ |   0 Constructing is so hard for me. I haven't been used to it.And I have to admit that I am too scared to solve it LOL.
•  » » » 9 months ago, # ^ |   0 the same to me
 » 13 months ago, # |   +4 A very good editorial indeed and how come you guys publish it so fast..?
•  » » 13 months ago, # ^ |   +247 Secret: I prepare it beforehand :)
•  » » » 13 months ago, # ^ |   +3 Very Good explanation and comments were great at C problem :D Thanks a lot <3
•  » » » 13 months ago, # ^ |   -161 Thanks for ruining ratings with bad problems
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   +5 You seem to be really asking for trouble, don't ya? Go and watch me on Demon Slayer, you'll learn a thing or two about persistence girl.- Inosuke Hashihabara, Demon Slayer Corps.
•  » » » » » 13 months ago, # ^ |   -19 I saw demon slayer but left after 3 episodes it's boring
•  » » » » » » 13 months ago, # ^ |   +2 You left before my entry, of course, it must have been boring.
•  » » » » » » » 13 months ago, # ^ |   0 OH Fuck, ok i might consider it watching again
•  » » » » » » » » 13 months ago, # ^ |   0 さようなら
•  » » » 13 months ago, # ^ |   0 Nice man.
•  » » » 13 months ago, # ^ |   0 Thanks for your problems! Really good!
 » 13 months ago, # |   0 Thanks for the super, duper fast editorial!!!
 » 13 months ago, # |   +3 Bruhhhh, this is magic! Great contest and the fastest editorial ever....
 » 13 months ago, # | ← Rev. 3 →   +32 In addition:In problem C we can reduce the time complexity to O(N) by using array int charCount[26]; (due to the small alphabet size) instead of explicit std::sort.p.s. thanks for the fast editorial.
•  » » 13 months ago, # ^ |   +7 If Anyone needs further information check Count Sort
 » 13 months ago, # |   +6 Video Editorials for today's C and DCDEnjoy watching!
 » 13 months ago, # |   +13 Very nice contest! Problem statements were succinct and the editorial was published so quickly! :)
 » 13 months ago, # |   -81 is it rated ?
•  » » 13 months ago, # ^ |   -30 Yes,See the second line of the announcement.
•  » » 13 months ago, # ^ |   +14 I am just finding your reply's for downvote them xd)):
 » 13 months ago, # |   +25 I think there is an error in solution C.It should be return instead of continue;
•  » » 13 months ago, # ^ |   +1 Thanks, fixed
 » 13 months ago, # |   +28 Can anyone think of a counterexample for this solution to E?Sum up all the red berries and make as many baskets as possible. There are $r$ (at most $k-1$) unused.Sum up all the blue berries and make as many baskets as possible. There are $b$ (at most $k-1$) unused.This is already almost optimal: there are at most $2k-2$ unused berries. We can get at most $1$ basket out of these. Said basket only exists under the following conditions: There are at least $k$ leftover berries. For some shrub, we can take $x$ red berries and $y$ blue berries so that $x <= r$, $y <= b$, and $x + y = k$. If the inequalities are not satisfied, we won't be able to make all the complete color-based baskets. Checking this takes an $O(nk)$ double loop. This way, we leave as few berries unused as possible.My code fails on test case 10, and I think it's a problem with the algorithm and not my code. Here's Haskell: 78739086. Here's C++: 78744165
•  » » 13 months ago, # ^ |   +31 Test: 2 6 17 1 9 3 Your answer : 4Correct answer : 5
•  » » » 13 months ago, # ^ |   0 Thanks!
•  » » 13 months ago, # ^ |   +19 You are almost correct, but you miss some cases.You might have to find more than one shrub, where the red berries add up to x, and the blue ones add up to y. You are only checking the case where it's a single shrub.
•  » » » 13 months ago, # ^ |   0 But we can take both kind of berries from one shrub only, isn't it or did i not get you correctly ?
•  » » » » 13 months ago, # ^ |   0 You can only put berries from one shrub into a single bucket (if they're of different colors) but you can use multiple buckets.For example, in the example above, you can take 5 red, 1 blue from the first shrub, and 3 red 3 blue from the second shrub. The remaining 18 red berries can go into 3 buckets, for a total of 5.
•  » » » » » 13 months ago, # ^ |   0 I still dont get it. you aren't using the r and b remaining berries after grouping all the red and blue berries separately.
 » 13 months ago, # |   0 Thanks to give editorial as early as possible.
 » 13 months ago, # |   +7 I think it would be nice to comment my approach to E and the way i thought about it.Lets say we have some vectors in a plane, lets define a modular plane as a plane such that if we are in $[x, y]$ then $0 \le x,y < k$, also if the condition doesn't holds then we go to $[x\space mod\space k, y\space mod\space k]$(a positive modular), we want to see if we are able to choose some of vectors to reach $[x, y]$ such that $x + y < k$, starting at $[r, c]$. Also each vector is labeled with a number $i$, we cant choose two vectors with the same label, there are $n$ labels at most.We know that a vector $x$ coordinate plus its $y$ coordinate is equal to $k$(each vector means how many reds we chose and how many blues we chose from a $i$th shrub). The problem is not easier, but it can help you understand the logic behind the problem and the solution, at least it helped me. Also if you start from $[r, c]$, you cant reach $[x, y]$ such that $(x+y) \ne (r+c) _{mod \space k}$.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 What is r and c and what does x and y represent?
•  » » » 13 months ago, # ^ |   0 $r$ is number of reds modul $k$ and $c$ is number of blues modul $k$, $[x,y]$ is coordinate of a dot or a vector(coordinates of a vector is the coordinates of the endpoint of the vector when its moved to region)
 » 13 months ago, # |   +9 Woah editorial published very fast! Thanks FieryPhoenix for the contest <3
 » 13 months ago, # |   +26 I didn't expect C to be that simple. Nice problems!
 » 13 months ago, # |   +1 Can anyone explain mass increase from x to 2*x part from D ?
•  » » 13 months ago, # ^ |   +18 There are $x$ bacteria. If you split none, mass total will increase by $x$ that night. If you split all, mass total will increase by $2x$ that night. So, the mass increase will be between $x$ and $2x$ inclusive depending on how you split.
•  » » » 13 months ago, # ^ |   -9 Can we prove that it is possible to acquire all the values in the range $[x,2x]$?
•  » » 13 months ago, # ^ |   +12 Let's say there's x bacteria of mass m. Total mass: x * m At night, it's mass (single bacteria) becomes m + 1. Now, consider if it split before the mass increase. Now, there are 2 * x bacteria of mass m / 2. At night, the total mass becomes (for one bacteria): m / 2 + 1. The total increase: Final mass - Initial mass: 2 * x * (m / 2 + 1) - x*m = 2 * x. This is only if all x bacteria split. If none split, total increase will be x (as every bacteria mass increases by 1). So, increase will be in the range $[x,2x]$
•  » » » 13 months ago, # ^ |   0 Thanks. That was easy to understand.
 » 13 months ago, # |   +19 You make good problems.
 » 13 months ago, # |   +3 I like the format giving solution along side with tutorial is really helpful.otherwise sometimes get stuck with tutorials only.
 » 13 months ago, # |   0 I am not sure I completely understand problem C. In second test case, isn't it better to distribute baacb into ab and abc resulting in min(max(a1,a2)) as ab instead of the given optimal solution abbc which is more than ab.
•  » » 13 months ago, # ^ |   0 then max(a1,a2) will be abc not ab
•  » » » 13 months ago, # ^ |   0 Oh, my bad. Thanks:)
 » 13 months ago, # |   +23 It is really great that you prepared editorial 6 days ago && published score distribution day before round. Huge thanks for this! (and problems were good as well too)!
 » 13 months ago, # |   0 Wow!!! editorial + code with comments, very helpful :)
 » 13 months ago, # | ← Rev. 2 →   +9 I couldn't solve a single question today. I was totally blank. But I, cherished the time I used to read each beautiful problem. And, now this well written editorial and code with comments! Best contest experience I have had till now ! Kudos to the author for his time and efforts !!
•  » » 13 months ago, # ^ |   +8 Great to hear, thank you!
 » 13 months ago, # |   +8 Could someone please help me understand why the following claim is true for problem E? The author states "Note that if we know that there are j extra red berries, we can also easily calculate how many extra blue berries there are." How would we calculate the number of extra blueberries from the the number of extra redberries?
•  » » 13 months ago, # ^ |   +48 If there are $t$ total berries and $r$ extra red berries, there will be $(t-r)$ $mod$ $k$ extra blue berries. This is because all the other red berries are already filled in some baskets, and if there are many extra blue berries they can fill their own baskets too.
•  » » » 13 months ago, # ^ |   +3 I get it now. Thank you!
 » 13 months ago, # |   0 I had to give contest on m2.codeforces.com......codeforces was running very slow.
 » 13 months ago, # |   0 In Div2-B, why is no solution possible if there are more than k distinct integers?
•  » » 13 months ago, # ^ |   0 if there are more than K distinct integers, then there will be at least two subarrays whose sum will be different and they can't be made equal by inserting any numbers from 1 to n
•  » » » 13 months ago, # ^ |   0 Suppose, n = 2, k = 1 & array = {1,2} why the answer is -1? According to the statement answer can be m = 2, array = {1,2}.
•  » » » » 13 months ago, # ^ |   0 your answer {1,2} has two subarrays of length 1 , {1},{2} , and their sums are 1 and 2 and since they don't satisfy the condition given in the problem , it is incorrect.and since {1,2} can't be made periodic with period 1 , answer will be -1below elManco has explained why the answer must be periodic with period k
•  » » » » » 13 months ago, # ^ |   0 Jo3kerR Thank you! I missed that part, sum of every subarray must be equal.
•  » » 13 months ago, # ^ |   +13 You want to make an array such that every subarray of length $k$ has the same sum.Let $s$ be the sum of the first $k$ elements of array $a$. You can tell that $a[k+1] = a[1]$ so that the subarray from $1$ to $k$ and the subarray from $2$ to $k+1$ have the same sum $s$.With the same idea, you can see that the array must have a period of $k$. Thus, once you choose the first $k$ elements, you can only repeat them. That's why you can have at most $k$ distinct numbers.
•  » » 13 months ago, # ^ |   +3 The period has to be k so you can't put more than k distinct integers in one period.
 » 13 months ago, # |   0 can anyone explain what does max(a1,a2,..,ak) means in problem C ?
•  » » 13 months ago, # ^ |   0 The largest lexicographically among the strings $a_1, a_2, \ldots, a_k$.
•  » » 13 months ago, # ^ |   0 The maximum among all these strings a1, a2, ..., ak
 » 13 months ago, # |   0 Author does everything to satisfy participants. Thanks for such a pleasant contest.
 » 13 months ago, # |   0 I told you You guys awesome! Then I again tell it <3. This editorial published as fast as need. Thanks!
 » 13 months ago, # |   0 Can someone pls explain the solution of the problem D
 » 13 months ago, # |   +4 To minimize the length of sequence $a$, we will start building our sequence with $1,2,…,2^x$ such that the total sum $s$ is less than or equal to $n$. If the total sum is $n$, we are done. Otherwise, we insert $n−s$ into our sequence and sort. This gives a valid sequence of minimal length.I don't understand this. Is the sequence just $1,2,2^2,…,2^x$ such that $1+2+2^2+...+2^x <= n$?Also, if you can simply insert $n-s$, then does the case of $-1$ never arise?
•  » » 13 months ago, # ^ |   0 Yes. Because they are the increase in mass. So the sum must be s <= n
•  » » 13 months ago, # ^ |   +9 You can see that we can just wait without splitting to gain every possible integer.
•  » » » 13 months ago, # ^ |   0 OK, thanks. Still no idea how someone is supposed to come up with this during the contest.
•  » » » » 13 months ago, # ^ |   +3 You don't need to use exactly this approach. You could get intermediate value in various ways. First approachFor example, you could at some point decrease number and check is it still possible. To make clear this approach: 1, 2, 4, 8, 16 = 31 > 20 1, 1, 2, 4, 8 = 16 < 20, now you know it should start with 1, 2 1, 2, 3, 6, 12 = 24 > 20, need lower 1, 2, 2, 4, 8 = 17 < 20, now you know it should start with 1, 2, 3 1, 2, 3, 5, 10 = 21 > 20 1, 2, 3, 4, 8 = 18 < 20, now you know it should start with 1, 2, 3, 5 1, 2, 3, 5, 9 = 20 done. It's binary descent. If you always generate all next terms, it works in $O(log^2(n))$ in terms of the task. In this way you get lexicographically smallest sequence. It's very easy to write using recursion. My approachMy solution was much simpler in understanding, but harder to write. First I get 1, 2, 4, 8, 16 = 31 > 20 then I reduce all equal ones in the end at once while I can 1, 2, 4, 8, 8 = 23 > 20 then do the same, now it's 8, 8 1, 2, 4, 7, 7 = 21 > 0 now, last step, I reduce by one from first of equal, to last of equal. 1, 2, 4, 6, 7 = 20 done Example of normal step: 1, 2, 4, 8, 16, 16, 16, 16 <- from this 1, 2, 4, 8, 8, 8, 8, 8 <- to this 1, 2, 4, 8, 11, 11, 11, 11 <- or to this, depends how much we need to go down I'm unsure if it even happens to have so long tail, but I don't care.Example of last step: 1, 2, 4, 8, 11, 11, 11, 11, 11 <- from this 1, 2, 4, 8, 10, 10, 11, 11, 11 <- from to this Last step proof: if you can't reduce all equal ones in the end, it means that number of them is greater than difference with goal, it means you can reduce them one by one and get goal.I made this solution in $O(log^2(n))$ in terms of the task. The only reason why it wasn't $O(log(n))$, because I was lazy, so I was filling tail of similar numbers after each change. Code: 78742069
•  » » » » » 13 months ago, # ^ |   0 Thanks, I will try to understand your approach. By binary descent, I suppose you mean binary search? Or is it different? (Couldn't find anything about binary descent).
•  » » » » » » 13 months ago, # ^ |   0 And, here is code for "First approach", legit binary: 79004119 Similar approach but using fact that lowest the first, highest the most, so you will find lowest on next step very soon: 79006127 Completely same but with loops: 79005752 this one should be most understandable.
•  » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Ah... about binary descent... It's called so when you have some tree of decisions and you descent to some leaf. You can represent all outcomes here as tree like that. Why I said binary? Because either you have binary tree or you can do binary search. Sorry, looks like it's my own name of it :(
•  » » 13 months ago, # ^ |   0 And impossible case doesn't exist.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +8 I had a bit different approach. If it was possible to split all bacteria, we will split them.Now how to check this, Consider there were K bacteria and W total mass at some stage, if W + 2*K >=n than we can directly reach n in n-W splits. Else if W + 4*K >=n than we can do it using 2 splits minimum and for every other case we split all of them. Link to my submission
•  » » » 13 months ago, # ^ |   0 I don't mean to be rude, but I can't understand what you are saying. Either the grammar in sentence is incorrect or some words are accidentally deleted.I can't understand your statement: Consider there were K bacteria and W total mass at some stage, than the if W + 2*K >=n than we can directly reach it in one split.
•  » » 13 months ago, # ^ |   0 Yes, but make $x$ as big as possible.Yes. It is always possible to find a sequence. Easy proof: if you never split your first cell, then after $n-1$ nights the cell has weight $n$. (Obviously that is not the shortest sequence)
 » 13 months ago, # |   0 Editorial is good.
 » 13 months ago, # | ← Rev. 2 →   +8 hey guys .. how did you solve problem A ... look over my solution 78745046 dp Solution lol
•  » » 13 months ago, # ^ |   +1 My solution: SolutionYou can divide items into two piles as follows: first stack: $2^1, 2^2, \ldots, 2^{\frac{n}{2}-1}, 2^n$, second stack: others. This split minimizes the sum difference. This is easy to prove because if one of the piles contains $2^n$, even if the other contains all the others it would have a smaller amount (because: $2^n = 2^1 + 2^2 + \ldots + 2^{n-1} + 1$). However, stacks must contain the same number of elements, so it is prudent to add minimal elements to a larger stack ($2^1, 2^2, \ldots, 2^{\frac{n}{2}-1}$).And code: 78663445
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +8 i think this is the optimal solution good job
•  » » 13 months ago, # ^ | ← Rev. 3 →   +9 cin >> n; cout << 2*((1<<(n/2))-1) << '\n'; 
•  » » » 13 months ago, # ^ |   +8 this is very funny solution great job .... i think no one solve it using dp there is much easier solution
•  » » 13 months ago, # ^ |   0 I summed the first n/2 powers of 2cin >> n; int ans = 0; int p = 1;for (int i = 0; i < n/2; i++) { p *= 2; ans += p; }
 » 13 months ago, # |   0 Judging by the fact that D is rated higher than C despite having a very simple solution with Div2B-ish implementation, (some of) your testers seem to have had similarly over-complicated approaches as me — that makes me feel a little less stupid! Thanks, testers!
•  » » 13 months ago, # ^ |   0 Also thanks to Fiery of course, very nice problems!
 » 13 months ago, # |   0 The editorial has been published very fast, just after the contest. Wow!! The problems were cool..........
 » 13 months ago, # | ← Rev. 3 →   +4  otherwise, we insert n-s into our sequence and sort what does this mean? how do we know that resultant sequence is even possible?
•  » » 13 months ago, # ^ |   +11 We have a sequence $1, 2, \cdots, 2^x$. Note that $n-s$ does not exceed $2^{x+1}$. So, inserting $n-s$ and sorting cannot break the condition: $a_i \le a_{i+1} \le 2a_i$.
•  » » » 13 months ago, # ^ |   +3 got it. thanks for clarifying
 » 13 months ago, # |   +3 B and D were beautiful! :)
 » 13 months ago, # |   0 In the solution of Problem Cif remaining letters aren't the same, we append remaining letters to answerI don't understand why does it works :(
•  » » 13 months ago, # ^ |   +7 Consider aaabbbc split into 3. We're gonna put all 3 as into each split, so our remaining string is bbbc.Dividing evenly gives ab ab abc which won't work. It's easy to tell that ab ab abc isn't as good as a ab abbc because the only thing we care about is that abbc < abc.So we take it to the extreme and throw everything into one, with abbbc as our answer, so that we push that c behind as many lexicographically-lesser characters as possible.
•  » » » 13 months ago, # ^ |   0 Thanks man I thought abbc > abc Now I get it
 » 13 months ago, # |   0 someone please explain why one of the test case of DIV.2 b is failing in the codeforces judge while it is running correctly in my local ide the link is:-https://codeforces.com/contest/1348/submission/78736417
•  » » 13 months ago, # ^ |   0 Try debugging it using random print statements on codeforces custom test.There maybe an initialisation error.
 » 13 months ago, # | ← Rev. 2 →   +6 First time reading the kind of solution in Div2E. Can someone explain in a possibly detailed manner? I don't get how you can derive the number of extra blue berries from the extra red berries.
 » 13 months ago, # |   0 Anyone have tips for number 1, for some reason I just kept on getting 6 for the answer?
 » 13 months ago, # |   0 Nice, E seems to have no testes against n^4 solution//
•  » » 13 months ago, # ^ |   0 There are only $O(nk)$ total reachable states so optimized $n^4$ solutions are not actually $n^4$.
•  » » » 13 months ago, # ^ |   0 lol, yes, sry
 » 13 months ago, # |   0 can anyone help me with the observation of problem C? how can i minimize the maximum lexicographical string?? thanks in advance.
 » 13 months ago, # |   0 Please, help me to identify why this solution fails the test for problem B: https://codeforces.com/contest/1348/submission/78729556
 » 13 months ago, # |   0 I knew I was stupid after I saw the solution to B. But the solution to C was a facepalm. And to think, I thought the contest was hard. The questions are excellent and well made; they just require us to get a click....Just 'a click'
•  » » 13 months ago, # ^ |   0 educational round 86 — B had the same approach and facepalm worthy solution
 » 13 months ago, # |   +3 Kudos to FieryPhoenix for very interesting problems!
 » 13 months ago, # | ← Rev. 2 →   0 FieryPhoenix Problem: 13348B , My_submission:78741637 For the input : 4 2 (n, k), 2 1 1 2 (n distinct number) My output was : 5 (array length), 1 2 1 2 1 (output array). But it shows wrong. Why?
•  » » 13 months ago, # ^ |   +1 look the given array is 2 1 1 2 but in your output there is no sub-sequence of that array.. there should be sub-sequence as 2 1 1 2 in the output array.. you can't delete anything from the given array..you can just add numbers in between them.. like the given array is 2 1 1 2 the answer could be : 1 2 1 2 1 2 look at the answer array — you can choose a sub-sequence which is the given array (2 1 1 2) . so,your answer must contain the given array as a sub-sequence. I hope you got it.
•  » » » 13 months ago, # ^ |   0 PC_S Thanks. I was confused.
 » 13 months ago, # | ← Rev. 2 →   0 How to think for problem like C . I mean seeing min of max() made me think it is binary search over something. Then I thought it being dp .How do we proceed ahead rejecting this ideas and think of case based solution ?
•  » » 13 months ago, # ^ |   0 Put aside ideas that doesn't give any approaches for some time span. You have to have some heuristic how long you may think about idea. Revisit ideas.Personaly, it was obvious that each string has to have letters in sorted order. Because, otherwise we could sort them and string would be smaller. Then I stucked for some time. First good observation for me was: let say string s is answer, then if there some string s' in the list for which some prefix is less than prefix of same length of s, then we can reduce length of s moving letters to s'. Carefully thinking about 'when can we do that', brought me to hypothesis that it's possible only when answer is single letter. Carefullly thinking 'why always single letter' (it's not true) and comparing to samples got me to right list of cases.
 » 13 months ago, # |   +12 My O(N) greedy passed for E: https://codeforces.com/contest/1348/submission/78740802My logic was this: The final baskets can be divided into two categories: those that are homogenous (i.e have only red or only blue berries) and those that are heterogenous (i.e can have both red and blue berries). The heterogenous baskets are obviously from the same shrub.Now, we will run two different greedy solutions. In the first solution, we will prioritise making heterogenous baskets. That is, for each i, add (a[i] + b[i])/k to the answer and then leave the remainder for homogenous baskets. With the remainder, I have just prioritised making homogenous A baskets and then made whatever homogenous B baskets are possible at the end. In the second solution, we will prioritise making homogenous baskets. That is, add (sum of a[i])/k + (sum of b[i])/k to the final answer. Then, find an i such that min(a[i], remainder of a) + min(b[i], remainder of b) >= k. If you find such an i, add 1 to the answer. Otherwise leave as is.Finally, take the max from both solutions and output it.
•  » » 13 months ago, # ^ |   +19 Hacked
•  » » » 13 months ago, # ^ |   0 I think this should fail too: 78774283the testcases don't seem good...
•  » » » » 13 months ago, # ^ |   +39 Hacked. Admittedly, making tests for problem E was very hard because random tests were ineffective, so many of the tests were added through stress testing. As you can imagine, it is very hard to stress against every possible greedy...
•  » » » » » 13 months ago, # ^ | ← Rev. 3 →   0 yes i see, i just hope no one passed system tests with stuff like this: 78775314I don't know how complicated it is to find a hack for this one...
•  » » » » » » 13 months ago, # ^ |   +19 Hacked by generating about $100,000$ random cases with $n,k,a,b$ in $\{1,...,11\}$.It's really hard to find a counter-example for such multi-greedy solutions. In $100,000$ random cases, usually only $1$ or $2$ that program failed. :(
•  » » » » » 13 months ago, # ^ |   0 Yep I understand. Great problems though, thanks for the contest.
 » 13 months ago, # | ← Rev. 2 →   +1 I used a simpler approach with D,Observations — Number of partitions + 1 will always increase each night so I have to create minimum array possible that sum up to n, which is in increasing order and each element is less than it's max possible at that point which is simple as 2^i as ith night (0 indexed) now keep maximum possible element fulfilling those condition. and for actual solution number of partitions each night just take adjacent difference between elements. My sol — 78714792
•  » » 13 months ago, # ^ | ← Rev. 4 →   0 Hey! Can you please explain this part (if condition) in your code? lf = df-x if lf
•  » » » 13 months ago, # ^ |   0 This is the case when we will select maximum possible value for that position i(value = 1< ans = [1, 2, 3, 3] , sol = [1, 1, 0]
 » 13 months ago, # |   0 I am unable to understand div2 C .Can anybody explain it. Thanks in Advance
•  » » 13 months ago, # ^ |   0 Editorial is very clear.
 » 13 months ago, # | ← Rev. 2 →   0 Hello!. Can someone tell me why this solution is wrong for E. It fails on test 73I commented the code so is easy to understand.What I am trying to do is a dp(i, r) = {maximun number of full_boxes from i to n-1, maximum number of unused blue berries}.So in each state I try all possible values from [0, k-1] of red berries that I want not to merge with the same shrub (then this one will be merged with r). At the end the answer should be dp[0][0].first + dp[0][0].second / k
 » 13 months ago, # | ← Rev. 2 →   0 Can anyone please explain why the greedy strategy mentioned in problem D works(i.e to take summation till 2powerx and repeat same for n-s) by working I mean proof that it is optimal
 » 13 months ago, # |   0 There is a typo in problem D. The complexity should be O(nlogn).
•  » » 13 months ago, # ^ |   +16 $n \log n$? $n$ goes up to $10^9$.
•  » » » 13 months ago, # ^ |   0 Oh, I didn't read carefully, and thought n is the length of inc. Since the length of inc is O(logn), the complexity is O(lognlog(logn))?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +3 If you sort using insertion (since we are only adding at most one number), the complexity is still $O(logn)$ I believe.
•  » » » » » 13 months ago, # ^ |   0 I see. Insertion here means insertion sort. Thanks for clarification.
•  » » » » » » 13 months ago, # ^ |   0 insertion sort isn't nlogn for array of n size? logn(log(logn)) isn't right why?
•  » » » » » » » 13 months ago, # ^ |   0 Insertion sort has complexity O(N^2) in general. But here we construct a sorted array in O(N) and insert (at most) one more value at the end. A single insertion operation is O(N) with respect to the size of the array. And since the size of the array is O(log(N)) with respect to the original n from problem statement, so is the time complexity.
•  » » » » » » » » 13 months ago, # ^ |   0 In the solution given we are using sort(inc.begin(),inc.end()) and this sort uses quick sort right? quick sort takes nlogn for size n, so our array length is log(N);so time complex -> log(N)*log(log(N))isn't this right??
•  » » » » » » » » » 13 months ago, # ^ |   0 Sorry, I did not read the code, only the tutorial text.Yes, you are right: if we use the STL function, then that is the right complexity. And if we use insertion, as suggested in the tutorial (but not implemented in the code), then the complexity is linear. These are 2 independent statements, not conflicting with each other.
•  » » » » » » » » » 13 months ago, # ^ |   0 yeah now I get what you meant. thanks for your time.
 » 13 months ago, # |   0 For problem E, What is the memoisation approach, if any?
•  » » 13 months ago, # ^ |   0 This is my solution 78781631, pretty much the same as the editorial solution except it's memoisation. Be aware this approach TLE'd for me, so I had to optimize a bit.
•  » » 13 months ago, # ^ |   0 My solution is a bit different than the one explained in the official editorial.
•  » » » 13 months ago, # ^ |   0 can you explain why there is no need of memoising the variable 'g' in your code in the dp array?
•  » » » » 13 months ago, # ^ |   +1 ExplanationFor a given value of x and r, the value of g will always come out to be same.In other words:If we know the number of red berries that are being passed on to the X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub — Number of red berries R passed onto (X + 1)th shrub) % K
•  » » » » » 13 months ago, # ^ |   0 I think your codes complexity is O(NK), am I correct? btw thanx for the response, it helped a lot!
•  » » » » » » 13 months ago, # ^ |   0 No, it's O(N.K^2)
•  » » » » » » » 13 months ago, # ^ |   0 But your DP array is of size O(NK)? could you please explain how?
•  » » » » » » » » 13 months ago, # ^ |   0 Oh I got it! thanks for the response!
•  » » » » » » » » 13 months ago, # ^ |   0 There's a loop inside each function call f(i, 1, min(a[x] + 1, k)) { }
 » 13 months ago, # |   0 My submission for problem B is always wa,I'm really disappointed,can anyone help me?https://paste.ubuntu.com/p/9Xftz94CM7/
•  » » 13 months ago, # ^ |   0
•  » » 13 months ago, # ^ |   0 OK,I use the char,which caused non-digits
 » 13 months ago, # |   0 Why does D have a binary search tag, is there a way to solve this using binary search? Anyone?
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 Here is a link to my submission: 78773066 I have solved it using binary search. SpoilerSuppose at any instance, we have N no of bacteria adding up to a sum S, Then it is clear we can reach the states, with sum = [S+N, S+2*N] from the current instant/stage. This is already explained in the editorial. We can binary search over this range, at every stage, to find the biggest next state which leads us closest to the destination 'n' and appropriately update the result.
•  » » » 13 months ago, # ^ |   0 Awesome technique!I think sum = [N+S, N+2*S], should rather be sum = [N+S, 2*N+S] .Thanks a lot though!
•  » » » » 13 months ago, # ^ |   0 Assume a state, of sum 3 and no of bacteria 2, then we can can reach the states which have sum in the range [5-7], i.e, [3+2, 3+2*2]
•  » » » » » 13 months ago, # ^ |   0 That's right, tho you have written 2*sum rather than 2*no. of bacteria. Was just mentioning to correct it :)
•  » » » » » » 13 months ago, # ^ |   0 Whoops! apologies for overlooking it twice!! Thanks
•  » » » 11 months ago, # ^ |   0 This uses the same principle but I am finding the value greedily. Although I have to mention that during contest it would require more thought.
 » 13 months ago, # |   +10 It was a nice set of problems! However, I think that the time limit for problem E was too strict. I understand that a O(nk^2) recursive solution may not be fast enough, but I saw some iterative O(nk^2) solutions getting TLE (including mine).
•  » » 13 months ago, # ^ |   +16 Yes, I also got TLE on test 33. When I try to use as least as 'long long' as possible, I got AC
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +8 Oh, I can't believe it, 1934ms AC after changing that. Thank you!
 » 13 months ago, # |   0 [problem:b]1≤ai≤n i didn't notice this statement, well what did it cost me, MY SLEEP.
 » 13 months ago, # |   +6 No offence to problem authors problems were quite elegant but in general I have observed too many constructive algorithm based problem these days. Why the problem setters are focusing on it so much is there any specific reason to include lots of constructive problems in the contest. Or constructive problems are intutive to be prepared. or some other reason exists for this please share your thoughts
•  » » 13 months ago, # ^ |   +21 No offense taken :) . I am not sure about other problem setters but personally, I did not specifically intend to have many constructive problems. But, the problems in my round covered a diverse range of topics: strings, math, dp and more. The constructive part just happened to come with the problems.I think constructive algorithms are very closely associated with logical thinking, so learning to solve them increases your problem solving skills. Personally, I quite like constructive problems because they allow you to be more creative (for the most part).
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 yeah I agree with you problems were really amazing. Even B was very elegant though I solved it too late. But I liked solving B.now I am upsolving other problems.
 » 13 months ago, # |   0 How we can solve to minimize the length of beautiful array (problem B) if we want to. (In the question ,it was told that we don't need to minimize the length).
 » 13 months ago, # |   +2 The solution for 1348C — Pheonix and Distribution will fail for the case where k = n. This is because there is no check for n == k in the part below. if (s[k]!=s[n-1]){ for (int i=k;i
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 The value at the end of the string $s[n]$ is defined, and is in fact '\0'. So, this works out.See http://www.cplusplus.com/reference/string/string/operator[]/ for more technical details.
 » 13 months ago, # |   0 I didn't get the dp logic for div2 E , can anyone please explain it to me...TYSM :)
 » 13 months ago, # |   0 Problem E: Has tag greedy. First line in tutorial: No Obvious Greedy Solution. Is it that complex to implement greedy in it?
•  » » 13 months ago, # ^ |   +24 There shouldn't be any greedy solutions since the special case where the first shrub has only $x$ red berries, the second shrub has only $K-x$ blue berries, and the remaining shrubs have exactly $K$ berries (of either color) is a knapsack variant.
•  » » 13 months ago, # ^ |   +5 The greedy tag might be because some ppl might have used a greedy observation to optimize their DP solution.
 » 13 months ago, # |   0 1348B : Phoenix and Beauty consider an example — 1 3 2 here n=3 , k=2 now there are total 3 distinct numbers but we can get a beautiful array : 1 3 2 2 . maybe i am wrong, if so explain where i failed to understand.
•  » » 13 months ago, # ^ |   0 i got it. how silly to ask!
 » 13 months ago, # |   0 I'm surprised to see the solution of D. I tried to solve D many times but didn't. After seeing this Editorial it seems fun to me.Thanks for the nice problems :).
 » 13 months ago, # |   +22 A different approach for D (binary search):Claim: If answer is 'd' then you can always find the answer by splitting all bateria till d — 3 days, then on d-2, d-1 you split only m, k bacteria. One can find m, k using binary search. Here is the proof:(for image 1: note 1st row represent no. of day, 2nd row represents what is the mass after that night night in case all bacterias have been splitted before, 3rd row represent no. of bacteria available to be splitted for next day.) Here is my submission (Had to upsolve, because in the contest I got confused with the proof for the whole time). Time complexity is O(log(n)) per test case. FieryPhoenix what do you think about this approach.Obviously the editorial solution is much more creative and definitely elegant :). (but I was nowhere near thinking like that).
•  » » 13 months ago, # ^ |   +5 You can find $m$ and $k$ in constant time too.
 » 13 months ago, # |   0 Can some one please help me figure out what is wrong with my solution of 1348B? would be great help thanks https://codeforces.com/contest/1348/submission/78743946Test: #4, time: 234 ms., memory: 160 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWERChecker Logwrong answer Integer element b[199] equals to -1, violates the range [1, 18] (test case 8)
 » 13 months ago, # |   0 Like the idea of problem B. (maybe the hardest B problem I have ever met in a div2 conteset)Thanks for such a high quality contest and the fast turorial! :)
 » 13 months ago, # |   0 Great solution of problem F!!!
 » 13 months ago, # |   -7 Problem B was the cutest.
 » 13 months ago, # | ← Rev. 4 →   +16 Share a Solution in $O(nk)$ of problem E.
•  » » 13 months ago, # ^ |   +21 Could you explain how does it work?
•  » » » 13 months ago, # ^ |   +11 First if we pick r red berries and b blue berries from a shrub and use them to fill exactly i baskets ($(r+b)MODk=0$).Then if $r \geq k$ or $b \geq k$,we can pick k red berries or k blue berries just because they are the same color.So we just need to pick r red and b blue from the same bushes and use them to fill one basket $((r+b)=k)$.And others can be picked just because they are the same color.dp[i][j] means considering the first i shrubs if we can pick x red berries (x%k=j) ,y blue berries to fill exactly some baskets((y+x)%k=0).we can use dp[i][j] to update dp[i+1][c] as follow: If we pick no berries from the $(i+1)_{th}$ shrub,then dp[i+1][j]=dp[i][j] else we must pick exactly k berries from the $(i+1)_{th}$ shrub.Let's suppose we pick "a" red and "k-a" blue.The following condition must be satisfied : 0
 » 13 months ago, # |   0 For A we can see a pattern:2->2, 4-> 2+4, 6->2+4+8... So answer is pow(2,n/2+1)-2
 » 13 months ago, # |   +3 Problems were good. still i was not able to solve even 2 problems.
 » 13 months ago, # |   0 completely outdone by B. :( , great question though :)
 » 13 months ago, # |   0 Nice Contest and Editorial. Thanks Phoenix!But could someone please help me out with E. I can't really understand what is "_leaving extra berries_" in the editorial? :p
 » 13 months ago, # |   0 thankyou soo much for nice editorial and line to line explanation of solution.this is very usefull. hoping for such more editorials and nice solutions like this time in upcoming contests.
 » 13 months ago, # |   0 for (int i=0;i<(n-k+k-1)/k;i++)cout<
•  » » 13 months ago, # ^ |   0 for(int i=0;i<(n-k + (k-1) )/k;i++) cout< 0) cout << s[n-1];By adding (k-1) to n-k, we can skip judging the case that weather (n-k)%k == 0 or not
•  » » » 13 months ago, # ^ |   0 Thank you ,initially i was amazed by this but now i got it, sorry the vote has been done by mistake now iam not able to upvote ,THanks for helping I really appreciate
 » 13 months ago, # |   +9 In problem F there is another way to find which friends to swap. When we construct answer greedily for friend i we always take interval with minimal b. So what are intervals with which we can swap i? There is only one possible interval. Interval with second minimal b (if exists). submission
 » 13 months ago, # |   -8 Nice and simple explanation. Thanks!!
 » 13 months ago, # | ← Rev. 2 →   -11 one of the fastest editorials ever.
 » 13 months ago, # |   0 Solution for D was really elegant!
 » 13 months ago, # |   0 In problem F, why do greedy algorithm for an arbitrary valid ordering work?
•  » » 13 months ago, # ^ |   +29 First we should place friend 1 to somewhere, valid intervals have form [1; x]. Imagine we don't chose one with minimal x, then we should use that interval in future, but then we can swap those two intervals, so solution with using minimal x always exists. For placing friend 2 we can think of intervals with form [1; x] as [2; x] and don't lose anything, and so on. Sorry English.
•  » » » 13 months ago, # ^ |   0 I got it, thanks!
 » 13 months ago, # |   -8 Thank you very much!
 » 13 months ago, # |   +8 Can someone explain the O(nk) solution for E ?
 » 13 months ago, # |   0 The output to my solution in problem D for the test case (t=1, n=8) is giving wrong answer. As per my code the answer should be [0 1 2] but the codeforces compiler is giving the wrong output [0 1] to my code. Someone please look into my code: https://codeforces.com/contest/1348/submission/78825160
 » 13 months ago, # |   0 Can anyone explain me the binary search solution for Problem-D ???
 » 13 months ago, # |   0 can anyone explain me why my solution got TLE for 2nd question though i printed n*k which is less than 10^4 letters output.My submission:78696875
 » 13 months ago, # |   0 In problem D for n=11,by the algorithm described in the tutorial,the answer is coming out to be 3 1 2 0. Can someone help?
 » 13 months ago, # |   +57 More solutions for F:(When I refer to the "length" of an interval below, I mean the number of unmatched points on it)First, any interval of length one can be matched greedily. This reduces the problem size by one. Repeating this until no more intervals of length one are left is actually pretty tricky to implement efficiently. Here are two ways: On every interval, keep two "sentries" at uniformly random distinct positions. This is impossible once the interval has length one, in which case we add it to a queue of length-one intervals. When we find an interval of length one, we match it and shrink all intervals containing that position. This may require relocating "sentries" at this position, which can be done in $O(log{n})$ per sentry using a Fenwick tree. Since each sentry is expected to have $O(\log{n})$ relocations, this solution has an expected runtime of $O(n\log^2{n})$. For each interval, we store it in a bucket based on the leftmost point it contains that hasn't been matched. We sweep from left to right and match length-one intervals we find. We only need to check the interval in the bucket whose right endpoint is closest. If we do find a length-one interval, all other intervals in the bucket get merged into the next bucket. We also need to take a step backward because a new length-one interval may have been created. We can store the unmatched points in a doubly-linked list to do this efficiently. This solution is $O(n\log^2{n})$ if buckets are merged small-to-large, or $O(n\log{n})$ if join-based trees or meldable heaps are used. Now all intervals have length at least two. Suppose there are at least two valid orderings. Observe if the greedy algorithm for finding a solution ever has two active intervals with the same right endpoint, taking either will be optimal, so we will get two different solutions. It turns out this must happen if all intervals have length at least two. There must always be two adjacent (by ID) points such that swapping their intervals creates another solution. Code:
 » 13 months ago, # |   +1 Can someone explain the following approach to D problem ? pigbrain's solutionthis one gives a different answer for the test cases. Thank you.
 » 13 months ago, # | ← Rev. 2 →   +8 For F problem another greedy initial matching is following: Sort by $b_i$ in increasing order. Within groups of same $b_i$ sort by $a_i$ in increasing order. Now, iterate over this order and for interval $i$ pick smallest not used value in the interval. I don't know how to prove it shortly. So, perhaps it's wrong.During this iteration, let say smallest not matched value is $v$. If you also check for any used values (matched) within interval $(a_i, v)$ that can be also matched with $v$ -> this is solution. this pair is exactly what values you may swap. You do this check with segment tree.Or, at least, it passed tests: 78850901 (code is ugly, just for hacks)
 » 13 months ago, # |   0 can someone for problem E explain how this TC's correct answer is 4?  4 8 11 5 1 4 1 4 1 6
 » 13 months ago, # |   +5 For E, doesn't O(nk^2) time out? Or can CodeForces computers handle ~1.25*10^9 operations in 2 seconds? I thought that modern computers can only handle at most 10^7 ish operations a second. This was my first contest so I'm not really familiar with the website. :P
•  » » 13 months ago, # ^ |   +17 O(nk^2) is not around 1e9, it's something like 1e8 and well to be honest it's a bit around the edge for 2 seconds, but generally when you see 500, just remember you can usually run it in n^3 if you code tidily.
•  » » » 13 months ago, # ^ |   +5 Oh lol, just realized it's 1e8 can't count. Thanks for the advice though.
•  » » 13 months ago, # ^ |   +12 Have you ever heard about CPU clock speed? It's measured in Hz. Hertz — is basically something in second. It can be anything. But regarding to clock speed, it is cycles per second.CPU perform single operation in several cycles, and at the same time, several operations during same cycle. Because of parallelism. It's not that kind of parallelism everyone talking about most of the time, like multiple cores / threads. It's other parallelism: processor split operations into micro operations... In short, all I want to say, that you can't tell time spent on operation. Modern CPUs are very complex.Instead, lets say in optimistic maner CPU perform single operation in single cycle. This means if CPU is 3GHz, then it does $3*10^9$ operations per second. I said it's optimistic, but it can be wrong, just because number 1 cycle per operation is arbitrary chosen. You could say 0.5 cycles for operation, it's twice faster. But anyway, it's good approximation of order of magnitude. It's not $10^7$ or $10^8$. It's around $10^9$ because of GHz. Note that some operations are slow, like: sqrt, sin, cos... So, it doesn't work for them the same.In short, thinking about second as approximately $10^9$ operations is enough. You can verify by running code. Just keep in mind that compiller can throw off any code that it may predict result, or if result is not used. So, at least print result of computation, and don't make super simple computations. It's applied to native binaries like produced by C++, C, Pascal, Go, Rust... C#, Java — a bit slower, because they use Virtual Machine pypy is even slower (as far as I remember $10^7$) python is around (as far as I remember $10^6$)
•  » » » 13 months ago, # ^ |   0 Thank you! I didn't know about that before. CodeForces doesn't give extra time to Java, right? Do you know the Hz of the CPU for CodeForces?
•  » » » » 13 months ago, # ^ |   0 I don't know. It doesn't add for python and pypy for sure.
 » 13 months ago, # | ← Rev. 2 →   -7 Given that the feedback on this tutorial is high, I don't really care if I get negatives for my message. Honestly, the tutorial for E is just terrible. There are many claims without a single proof.I didn't understand the tutorial after reading it for two hours though I got some clue. I tried to implement the same thing as described in the solution to see what's going on. If you change the condition from $(a_i - l)~mod~k + b_i$ to $(a_i - l)~mod~k + b_i~mod~k$, you'll get a wrong answer.Where that condition comes from? Why do we need to take the $mod$ of $a_i - l$ but not of $b_i$?
•  » » 13 months ago, # ^ |   +38 Insulting my explanation wasn't called for, please consider asking nicely in the future. Nevertheless, your question is valid so I will try my best to explain.Why we don't mod $b_i$:Consider the case: 2 3 0 2 2 3 The optimal solution will have one basket contain $2$ blue berries from the first shrub and $1$ blue berry from the second shrub, and the second basket will contain $3$ of the remaining berries from the second shrub.After processing the first shrub, only $dp[1][0]$ will be true. When transitioning to the second shrub, one optimal solution leaves $0$ extra red berries and groups the $2$ red berries in the second shrub with a blue berry. So, we want to check if $l=0$ is possible for $i=2$. A correct solution would return true.Look at the condition. $(2-0)$ $mod$ $3$ $+3$ is greater than or equal to $3$, but $(2-0)$ $mod$ $3$ $+(3$ $mod$ $3$ $)$ is not. Why? Because for $l=0$ we can actually group the $2$ remaining red berries with a blue berry when $(b_i \ge 1)$, but after modding it doesn't work. Why we mod $a_i - l$:Consider the case: 2 3 0 2 4 0 If we don't mod $a_i-l$, solution will print $2$. Why? Because for the second shrub it will say it is allowed for $l=0$ when it obviously doesn't work. The $4$ red berries cannot be grouped with blue berries to make some number of full baskets. After leaving $l$ berries for valid $l$, all the remaining red berries must be put away.
•  » » » 13 months ago, # ^ |   0 hi, excuse me, could you please answer my question too? thank you in advance :)for problem E explain how this TC's correct answer is 4? i can only see 3..... 4 811 51 41 41 6
•  » » » » 13 months ago, # ^ |   +5 x c y means take x berries of color c from basket y 1. (6 b 4, 2 b 3) 2. (2 b 3, 4 b 2, 2 b 1) 3. (1 r 4, 1 r 3, 1 r 2, 5 r 1) 4. (6 r 1, 2 b 1)
•  » » 13 months ago, # ^ |   +32 Here's another way of thinking about E:Suppose we know the number of red berries in heterogeneous baskets modulo $k$. This determines the number of blue berries in heterogeneous baskets modulo $k$. Since the number of red berries in homogeneous baskets is a multiple of $k$, it also determines the number of red berries not in any baskets (we can safely assume this to be less than $k$ since otherwise we can form another basket). Similarly, we can determine the number of blue berries not in any basket, and thus deduce the number of baskets.To compute the possible numbers of red berries in heterogeneous baskets modulo $k$, it suffices to look at each shrub separately and determine the possible numbers of red berries modulo $k$ in heterogeneous baskets for that shrub. If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous. Now we have two cases. If there are no heterogeneous baskets, the number of red berries in those baskets is obviously zero. If there is one heterogeneous basket, let $x$ be the number of red berries in it and $k-x$ be the number of blue berries in it. Clearly, $0\leq x\leq a_i$ and $0\leq k-x\leq b_i$. Rearranging, we get $\max(0,k-b_i)\leq x\leq \min(a_i,k)$. These correspond to the transitions for our DP.Code: 78841831Bonus: This implementation is actually $O(nk+k^2)$. (Hint: consider the maximum consecutive sequence of trues in each row).
•  » » » 13 months ago, # ^ |   0 "If there is more than one heterogeneous basket for one shrub, we can rearrange the berries to leave at most one heterogeneous."Thank you.
 » 13 months ago, # |   0 Since some time now, i am seeing a strange pattern in some of cf questions. strangely tough ad hoc which seems just too forced. logics which appear to have been put just to make a question tough more than interesting and learning based . of course some problems are really beautiful and you get to learn, but many like this contest's D are straight out from the first category i mentioned. ofc i may be wrong, just wanted to voice my view.
 » 13 months ago, # |   0 in problem D, if n=13 output is 1,2,2 but if we follow this approach ,then it goes as, 1->3->7->11 could someone explain it to me? Thx in advance.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 your sequence is right upto 7 that is 1 -> 3 -> 7 but after that only two of them broken down to 4 and you only increased those 4 by 1 You should also increase those bacterium which do not have broken down, so the left 2 bacterium will also get increased by 2 hence total increase will be 6, thus after 7 , 7 + 6 = 13 will come if you still have doubt feel free to ask
•  » » » 13 months ago, # ^ |   0 ok, i get it now..thx
 » 13 months ago, # |   0 (//if sum is not N, we insert and sort) In problem D what is meant by this line in Editorial? Does that (for loop) is performing insertion sort below that line?
 » 13 months ago, # | ← Rev. 8 →   +10 My solution for Problem "E. Phoenix and Berries" 78860291Let, DP[X][R]= Number of baskets that can be completely filled using the shrubs indexed from X to N — 1 (0 based indexing), given that we have R number of red berries to start with.Note that for every shrub, if:- the total number of berries a[X] + b[X] (both red and blue) in a shrub is greater than or equal to K, and there are both red and blue berries in the shrub. Then, we'll fill one basket completely, with these K berries and pass on the remaining berries to the next shrub. There can be at most K - 1 different ways in which we fill a basket containing both red and blue berries from the same shrub.For example if the Xth shrub contains 2 red berries and 10 blue berries and K = 4, then the possible combinations are:- RED BLUE 1 3 2 2 (All the combinations with either zero red berries or zero blue berries will be taken care of in the last part)Whenever, the count of any of these passed on red and blue berries becomes greater than or equal to K, we immediately fill a basket with it and pass on the remaining (R % K, B % K) berries to the next shrub.Important observation:It can be observed that if we know the number of red berries that are being passed on to the X + 1th shrub, we also know the exact number of blue berries that are being passed along with those red berries. Therefore we do not need to keep track of number of blue berries passed, i.e, we do not need to consider B as another dimension in states of DP.Number of blue berries passed = (Sum of total number of berries in each shrub starting from 1st shrub ending at Xth shrub — Number of red berries R passed onto (X + 1)th shrub) % KIf we receive R red berries and B blue berries from the Xth shrub (passed onto the X + 1th shrub), and the total number of berries in the X + 1th shrub is greater than or equal to K, i.e., a[X] + b[X] >= K, then we fill exactly 1 basket with these K berries. After selecting a total of K berries (all possible different combinations of red and blue), from X + 1th shrub, we'll add the remaining red and blue berries to R and B and find mod K.The number of red berries R and blue berries B is always stored as R % K and B % K, because if we have at least K red berries or/and K blue berries, we can completely fill (R / K) + (B / K) baskets.Another CaseIf the number of berries in a shrub is less than K, then we cannot fill a basket completely, using berries, entirely from this particular shrub, therefore we'll have to add the number of red and blue berries in this shrub to R and B respectively, fill R / K and B / K baskets completely, and pass on R % K and B % K red and blue berries respectively, to the next shrub.We solve the above case even when a[X] + b[X] >= K, to consider the combination :- RED BLUE 0 K K 0 and pass on the remaining red and blue berries to the next shrub. :)We have to find DP[0][0] long long dp(int x, int r, int g) // r red berries and g blue berries { if(x == n) //terminating condition return 0; if(DP[x][r] != -1) //value already found before return DP[x][r]; DP[x][r] = 0; int rem_r, rem_g; if(a[x] + b[x] >= k) { // considering all possible combinations of red and blue berries to completely fill a basket for(int i = 1; i < min(a[x] + 1, k); i++) { if(i <= a[x] && (k - i) <= b[x]) { rem_r = r + a[x] - i; rem_g = g + b[x] - (k - i); DP[x][r] = max(DP[x][r], 1 + (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k)); } } } // passing onto the next shrub, the total red and blue berries from this shrub along with the previous red and blue berries passed onto this shrub rem_r = r + a[x]; rem_g = g + b[x]; DP[x][r] = max(DP[x][r], (rem_r / k) + (rem_g / k) + dp(x + 1, rem_r % k, rem_g % k)); return DP[x][r]; } 
•  » » 13 months ago, # ^ |   0 your explanation is good but one point i am missing is you said that if in a shrub a[x]+b[x]>=k then we will fill one basket from it and pass the remaining to next shrub , why? why can't i fill more than one basket from the same shrub(of type in which basket is filled with red and blue berries) if i have the chance , why i am filling only 1 basket and passing to next shrub?
 » 13 months ago, # | ← Rev. 3 →   0 I really apreciate your editorial and your effort! If you don't mind, i'm still having some troubles with problem E, it's a little bit hard to digest these operations. I've read carefully the editorial and all the comments and i'm still having troubles with these parts of the code : "if ((a[i]-k)%K+b[i]>=K) dp[i][j]|=dp[i-1][(j-k+K)%K]; (especially the dp[i — 1][(j — k + k) % k] part)"dp[i][j]=dp[i-1][(j-a[i]%K+K)%K];If somebody can give me an explanation with some examples i would be really grateful.
•  » » 13 months ago, # ^ |   +19 I rewrote some of the variables in the code. Sorry for making it confusing with $k$ and $K$. Essentially, once we determine we can leave $l$ extra red berries from the $i$-th shrub, we also have to check whether the state from the previous layer that we want to transition from is true. For some $l$, if we want to see if we can achieve $dp[i][j]$, we have to check if $dp[i-1][j-l]$ is true. But, $j-l$ might be negative, and since we only care about the value modulo $k$, we force it to be positive by adding $k$ then modding.The second line of the code corresponds to leaving $a[i]$ modulo $k$ berries. We can always achieve this by creating full baskets containing only red berries until there aren't enough. The logic of transitioning from the previous dp layer is the same as I described above.Hope this makes sense!
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 author, I didn't understand the Editorial solution you provided( the last (t-j)/k part ) for the E problem. How when we subtract (TotalBerries-ExtraBerries) we get the max solution. I'm really confused, can you please help me.
•  » » » 13 months ago, # ^ |   0 why is it not possible to leave l red berries if (a[i]-l)%k + b[i] < k. Wouldn't it be possible to combine the (a[i]-l) % k red berries with the j-l red berries already there ?
 » 13 months ago, # |   0 How is time limit handled on codeforces? Mu solution for problem C had T*N complexity, while solution in editorial had T*N*logN which would not make it in 2 seconds for big enough test set (for example if input would 900 test with string of length 10000 + 100 tests for edge cases). I saw such solution in room, but wasn't quick enough to hack it (with program that would generate 1000 * 10000 test set) and it passed (even though I'm pretty sure that it would take more than 2 seconds). So my question is: is time limit in problem for 1 test, or complete test set? And to add: are there some limitations for hacking (for example time limit for program that is generating input, or number of characters for directly passing input)? Thanks.
 » 13 months ago, # |   +8 Detail explanation for div2 C if anyone need here
 » 13 months ago, # | ← Rev. 3 →   +12 My solution for the problem E is greedy and it gave me accepted. To know how it works you can go to this blog: https://codeforces.com/blog/entry/76862
 » 13 months ago, # |   +11 The matching is unique iff contracting the edges (merging nodes connected by edges from our perfect matching into one node) in the perfect matching creates a DAG. Can you please explain why this is true (or give an appropriate theorem/lemma name)?
•  » » 13 months ago, # ^ |   +27 Thanks for asking, I added the following explanation to the editorial:Consider a simpler graph, with only nodes representing positions. We draw a directed edge from node $i$ to node $j$ if the friend currently assigned at position $i$ (from our greedy) can also be assigned to position $j$. So, if there exists any cycle, we can shift the friends around the cycle to create another valid ordering. If the perfect matching is unique, our graph has to be a DAG.Now, returning back to the bipartite graph, we see that it is essentially the same. By contracting edges, all position nodes are equivalent to the friend node that is assigned to them (from the greedy). So, following an edge from the left side (position) to the right side (friend) puts us back on the left side (position), and this graph corresponds to the simpler version I explained above.Please let me know if anything is still unclear.
•  » » » 13 months ago, # ^ |   0 Now it is clear, thank you.
 » 13 months ago, # |   0 can someone please explain o(nk) soln for Phoenix and Berries??
•  » » 13 months ago, # ^ |   +19 Consider solution $2$ from the editorial. It is clear that valid $l$ form a contiguous interval, so we can apply prefix sums on each layer to quickly query whether there exists a "true" in some interval.
•  » » 13 months ago, # ^ | ← Rev. 2 →   +19 Some of comments describe it enough, but I'll try to do my best. Horrible wall of textFirst, let's say "problem is tough, let's try solve easier version". Easier version: we don't have shrubs-baskets. So, basket either full of red berries or full of blue berries. In this case, it doesn't matter how many shrubs, and where is one berry and where is another berry. All we need to know how much berries we have. Let $C_r$ — the number of red berries, and $C_b$ — number of blue berries, and $C$ — the number of all berries. Then, maximum filled baskets is $\left\lfloor \frac{C_r}{k}\right\rfloor + \left\lfloor \frac{C_b}{k}\right\rfloor = \left\lfloor \frac{C_r}{k}\right\rfloor + \left\lfloor \frac{C-C_r}{k}\right\rfloor$Notice, that maximum potentially unused berries is $2*(k-1)$ which is at most 1 basket! So, if unused berries is less than $k$, then we are reached theoretical maximum, because it's equal to case when we can fill basket by any $k$ berries.Now, we introduce shrub-basket — one that may take any $k$ berries from single shrub. I'll call shrub-baskets only those with different berries. Otherwise, you can replace it with full of red berries, or full of blue berries.We don't know how many shrub-baskets we need, and when. Suppose we know, what then? It will look like magic, but ideas how to come to it is about thinking in the way: how those remaining berries behave if you pick one shrub-basket. Then two... Can sometimes two shrub-basket be replaced by one + full of red?Let $S_r$ be the number of red berries in shrub-baskets, and $S_b$ be the number of blue berries in shrub-baskets. Also let $S_r = k\cdot N_r + R_r$ be representation of whole part $(N_r)$ plus remainder $(R_r)$. Similarly $S_b = k\cdot N_b + R_b$. And let $N$ be number of shrub-baskets. This means $S_r + S_b = k\cdot N$. Now $S_r + S_b = k \cdot N_r + k \cdot N_b + R_r + R_b = k(N_r + N_b) + R_r + R_b = k\cdot N$For remainders to be from zero to $k$ there are two cases: $R_r = 0, R_b = 0, N = N_r + N_b \\ R_r \neq 0, R_b = k - R_r, N = N_r + N_b + 1$I'll use following property:$\left\lfloor x-1 \right\rfloor = \left\lfloor x\right\rfloor-1$ Which is same as: $\left\lfloor \frac{x-k}{k} \right\rfloor = \left\lfloor \frac{x}{k}-1 \right\rfloor \\ \left\lfloor \frac{C_r-S_r}{k}\right\rfloor + \left\lfloor \frac{C_b-S_b}{k}\right\rfloor +\frac{S_r+S_b}{k} = \left\lfloor \frac{C_r-k\cdot N_r-R_r}{k}\right\rfloor + \left\lfloor \frac{C_b-k\cdot N_b - R_b}{k}\right\rfloor + N \\ = \left\lfloor \frac{C_r-R_r}{k}\right\rfloor - N_r + \left\lfloor \frac{C_b - R_b}{k}\right\rfloor - N_b + N$And we have two cases: $R_r = 0, R_b = 0, \left\lfloor \frac{C_r}{k}\right\rfloor - N_r + \left\lfloor \frac{C_b}{k}\right\rfloor - N_b + N = \left\lfloor \frac{C_r}{k}\right\rfloor + \left\lfloor \frac{C_b}{k}\right\rfloor \\ R_r \neq 0, R_b = k - R_r, \left\lfloor \frac{C_r-R_r}{k}\right\rfloor - N_r + \left\lfloor \frac{C_b-k+R_r}{k}\right\rfloor - N_b + N \\ = \left\lfloor \frac{C_r-R_r}{k}\right\rfloor + \left\lfloor \frac{C_b+R_r}{k}\right\rfloor - N_b - N_r - 1 + N$In both cases we have: $\left\lfloor \frac{C_r-R_r}{k}\right\rfloor + \left\lfloor \frac{C_b+R_r}{k}\right\rfloor$So, the only thing we want to know, is it possible to get $R_r$ or not. let boolean dp[n][r] be true if and only if it is possible to get remainder r berries in shrub-baskets after first n shrubs. Then, obviously if dp[n][r] is true then dp[n+1][(r+j) mod k] is also true if we can make basket with $j$ red berries and $k-j$ blue berries. We can do it if: $j \leq a_n,\;\;\; k-j \leq b_n \\ k - b_n \leq j \leq a_n$Take in account $0 \leq j \leq k-1$ And corresponding range is $max(k - b_n, 0) + r \leq j \leq min(a_n, k-1) + r$This is $O(nk^2)$ solution if you iterate across all $j$. Here is idea to optimize it. First, realize that you set booleans to true many times. What if you would store number instead, and increment it instead of setting it to 1. Then, all non-zero $dp[n][r]$ numbers represent possible remainder, and zero — impossible. How it helps? Increment by one is not a solution. Idea is that any array you can represent as first element + difference between its elements: 1 2 0 5 3 4 same as 1 +1 -1 +5 -2 +1 Increment of single value of differences array is corresponding to increment of all the values after corresponding element:  +2 +2 +2 1 2 0 7 5 6 same as 1 +1 -1 +7 -2 +1 ^ changed only this difference. Increment arbirtary range: +2 +2 -2 1 2 0 7 5 4 same as 1 +1 -1 +7 -2 -1 ^ ^ decrement after range ^ increment start of range So, idea is: for dp[n] use array of sums to check is it possible to make remainder r, and for dp[n+1] calculate differences. when differences are made, convert it into sums and move to next iteration. Also, don't forget to check that range is not empty, and split it in halves if it overflow $k$.Finally, source: 78997658 Bonus: proof we need at most one shrub-basket per shrubI'll use "charging argument" (google if you don't know). Suppose we have optimal solution. This means we know which berry we will put into which basket. Consider any shrub-basket (those which has berries of different color, blue berry in particular). If there is another shrub-basket of same shrub, then it has red berry. If we swap blue berry from our basket with red berry from other basket then number of full baskets doesn't change so it is still optimal solution. But in this way we increase amount of red berries in our basket. If we keep going, eventually we may stuck in two cases: no blue berries in our basket left, this means our basket is no longer shrub-basket in my terms; or there is no second shrub-basket of same shrub. So, either we already have single shrub-basket for this shrub, or we decreased number of shrub-baskets. This means, for each shrub, if number of shrub-baskets is greater than one then we can make it to be exactly one. It means, after this operations we have at most one shrub-basket for shrub. And during this operations we don't loose optimality. If initial solution was optimal, then new one is also optimal. It means, that one shrub-basket for shrub is always enough.
•  » » » 13 months ago, # ^ |   +8 I had idea to use only k/x of those with range starting with x. It would be $O(n+k^2log(k))$ if it work. 79024430 It passed tests but obviously it's wrong so I hacked it.
•  » » » 13 months ago, # ^ |   +8 Looks like I'm finally made legit solution for 1348E - Phoenix and Berries in $O(n + k^2)$ time and $O(k)$ memory. Just for fun I was trying to find solution where n can be bigger, and looks I did it. Code: 79055234 Idea of optimization is pretty simple, we want fast check is shrub useful or not. What do I mean by useful? Well, if processing of it does something, then it is useful. Now, just from definition of does something it means that after processing shrub we have more possible remainders. So, task is: determine fast will it increase. We don't care at all how much. So we can ask opposite: when is it useless? Yet again, say "problem is tough, we need something simpler". When it doesn't change if range is exactly one value? (in other words, if we can fill shrub-basket only in single way). If nothing changed, it means that infinite concatenation of our array of booleans after shift by number of red berries picked did overlap completely, and maybe better for understading: their bitwise OR looks same as initial infinite array. This means that it's shift by whole number of periods of our infinite boolean array. And you may find it in linear time. Back to "tough version". We have range of shifts then. So, we need to find is there any value among those shifts that is not whole number of periods of our infinite array. It's done in constant time. So, in the end, we process only those shrubs which will increase number of possible remainders, and in worst case we increase from 0 to k one by one which is k times. Each processing still takes $O(k)$ so in total with reading of shrubs becomes $O(n+k^2)$. (:
•  » » 13 months ago, # ^ |   +8 also look here https://codeforces.com/blog/entry/76555?#comment-614560
•  » » » 13 months ago, # ^ |   0 thanks