### saliii's blog

By saliii, history, 4 years ago,

We were waiting several weeks to setting this contest and hope the problem was good enough.

#### Events

There was a difficulty with 805E - Ice cream coloring/804C - Ice cream coloring. A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this.

For this sentence, Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph. You can find the meaning of "connected subgraph" with connected and subgraph, thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement.

I will write the full editorial in the few next days, now some hints and short solutions exist here.

## Hints

805A - Fake NP

hint1

805B - 3-palindrome

hint1
hint1
hint2
hint1
hint2
hint3
hint4
hint1
hint2
hint3
hint1
hint2

804E - The same permutation

hint1
hint2
hint3

804F - Fake bullions

hint1
hint2
hint3
hint4
hint5
hint6

# Solutions

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

Time Complexity:

Time Complexity:

Memory complexity:

python3
C++

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++

Time Complexity:

Memory complexity:

C++

From: saliii, Writer: saliii

Time Complexity:

Memory complexity:

C++

From: saliii, Writer: amsen

Time Complexity:

Memory complexity:

Java8
C++
C++

As my good friend, Arpa, did, let me share with you a perfect poem of one of our best poet you might know, Molavi:

.......................................................................................بند بگسل، باش آزاد ای پسر ** چند باشی بند سیم و بند زر

O son,  burst thy chains and be free! How long wilt thou be a bondsman to silver and gold?

.......................................................................................گر بریزی بحر را در کوزه‌‌ای ** چند گنجد قسمت یک روزه‌‌ای‌‌

If thou pour the sea into a pitcher,  how much will it hold? One day's store.

..................................................................................... کوزه‌‌ی چشم حریصان پر نشد ** تا صدف قانع نشد پر در نشد

The pitcher,  the eye of the covetous,  never becomes full:  the oyster - shell is not filled with pearls until it is contented.

.............................................................................. هر که را جامه ز عشقی چاک شد ** او ز حرص و عیب کلی پاک شد

He (alone) whose garment is rent by a (mighty) love is purged entirely of covetousness and defect.

• +81

 » 4 years ago, # |   0 Auto comment: topic has been updated by saliii (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 3 →   +6 If we had these types of editorials for future contest as well, could be good. Sometimes all you want is hints :)
•  » » 4 years ago, # ^ |   0 I totally agree, this is what editorials here need.It would be awesome to have hints after every contest, it's really all you might be missing to solve a problem(especially when you're upsolving).Thanks saliii !
•  » » » 4 years ago, # ^ |   0 YW!
 » 4 years ago, # |   +60 We were waiting several weeks to setting this contest and hope the problem was good enough.Why didn't you write full editorial for this several weeks?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +35 we were trying different problems, there is near 4 or 5 really good problems, we don't use them here for different reasons. And we wrote a big part of editorial! To be honest, We started preparing the contest from 4 mouth ago.
 » 4 years ago, # | ← Rev. 2 →   +3 In Div2 E /Div1 C , How to implement what is written in the editorial ??? I realized the hints during the contest but I really could not come up how to implement it efficiently ???
•  » » 4 years ago, # ^ |   +4 Do dfs from any vertex T and keep set of used colors in each vertex. When you come in some vertex try to set colors for each type in way like: int color = 1; while (used_color[v].count(color)) { ++color; } After you set a color for a type do another dfs from this vertex in every other vertex which have same type and insert this color in their used sets. Total complexity is .
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I do not understand Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph in problem. Form a connected subgraph of what graph and in which graph?? ignoring this forms G a forest like structure of cliques.tia
•  » » » 4 years ago, # ^ |   0 Forms connected subgraph in original tree. So all vertices with same type are connected by tree edges. For example 1 to 1,2 to 2 is ok, but 1 to 2 to 1,2 not okay (as 1 and 1,2 should be connected by edge to form connected subtree). It wasn't clear for me too.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 thanks, i looked at your comments below, now clear why graph in your ex is invalid. so G will be a disconnected graph of cliques and hence min col is max size of a clique. am i right?? no i am not right. i'm being stupid.
 » 4 years ago, # | ← Rev. 2 →   +13 nice contest
 » 4 years ago, # |   0 In Div1 C Editorial:The trivial upper-bound should be maximum size of vertices sets.I think this is a trivial lower-bound of the answer, perhaps it is trivial as upper-bound too but in that case is trivial that this is the answer.
•  » » 4 years ago, # ^ |   0 Thanks, edited.
•  » » 4 years ago, # ^ |   0 can you please explain why is the upper bound max of vertices sets?
 » 4 years ago, # | ← Rev. 2 →   0 Okay, I understand why it's not nlogn.
 » 4 years ago, # |   0 Why All of my submissions show skipped? Though all of them are passed in system test.
 » 4 years ago, # |   0 This was my first contest, can anyone help me with Div2 D problem ? I am not able to figure out the logic from hints.Thanks.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 My approach: consider x letters 'a' in a row and a single letter 'b'. Try to figure out the required number of steps to turn this to (many letters b + x letters 'a') for an arbitrary x.For example, x = 3 (x = 2 is given as a problem sample) aaab -> aabba -> abbaba -> bbababa -> bbbbaaba -> bbbbabbaa -> bbbbbbabaa -> bbbbbbbbaaa :)
•  » » » 4 years ago, # ^ |   0 can you pls elaborate more?? i tried but not able to follow.
•  » » » » 4 years ago, # ^ |   +3 Ok :) The fact that can be used to solve this one: should you have x letters 'a' and a single 'b', this will soon turn to a string of y letters 'b' and x letters 'a'. What's the value of y? :) As given in samples, aab will turn to bbbbaa.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 i followed someone's solution sol and what it does is: iterate from right and find answer for index where a's are present and update number of b's right to this. is it not miscounting as in your above ex if we follow this pattern then in 4th step(bbbbaaba) leftmost a has to wait 1 more step to be interchanged. how is it compeseted overall??
•  » » » » » » 4 years ago, # ^ |   +5
•  » » 4 years ago, # ^ |   +5 The end of changes is string s like b....ba.....a, because you can't find substring ab.Okey, let's try to do this string, as we can see when you meet ab it replace with bba, so a and b swap, but if we have aab it became abba, so we can find new ab and after two moves it becames bbbbaa and so on...So, when we find new ab, it will not changes smth after it, just previous string, because of that we can iterate from left to right, count all a, and, when we find b, swap all found a with this b.If you modulate this process, you see, that if you have n a before b you will make 1 + 2 + 4 + ... + 2n - 1 moves or 2n - 1.And we got solution: int counta = 0; int ans = 0; for (char c: s){ if (c == 'a') ++counta; else ans += (2 ^ counta) - 1; } just use precalc or bin_pow with module
 » 4 years ago, # | ← Rev. 2 →   0 Ice coloring: Could someone explain how following given tree topology — colors it correctly? Which part of problem guarantees it?For example not following tree, just processing by tree vertex index, would fail on test 143 that is a custom hack.
•  » » 4 years ago, # ^ |   0 Did you understand why processing by tree vertex index is wrong?
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 I understand why it's wrong. But I don't understand why processing by tree edges is correct.For example 2 31 1 1 2 2 1 21 2 2 3 Would fail when processing by tree edges, but why this input is incorrect?
•  » » » » 4 years ago, # ^ |   +3 Umm, is the input correct? I think the edges should be 1 3, 2 3 due to each icecream being in a connected subgraph.
•  » » » » » 4 years ago, # ^ |   0 Ok, thanks, now I understand that each type of ice cream must form connected subgraph in a tree.
•  » » » » » » 4 years ago, # ^ |   0 I don't know why processing by tree vertex index is wrong though. I think there should always be enough colors to avoid clashes, which means it should work. Hopefully someone clarifies.
 » 4 years ago, # |   0 In 805F — Expected diameter of a tree, may I ask how to get the maximum path of each vertices in a graph? Is it run from a vertex to all vertices in its graph to get that vertex maximum path or is there a better way to do it? Thanks.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Prove me someone if I am wrong, but we can find center(es) of tree and half of diameter + distance to closest center is maximal distance
•  » » 4 years ago, # ^ |   0 As I finding and try to learning from the provided solution, finding the diameter for each vertices in graph needed 3 times doing the dfs, the first one is finding the farthest vertex from a vertex (V), the second is calculate the diameter of the vertex from vertex V and also finding the farthest vertex again, and the third is to calculate the diameter from the other farthest vertex from second dfs. Is my understanding true? Thank you :)
•  » » » 4 years ago, # ^ |   0 In editorial, there is a code with 3 dfs! but I think we can do it by a simple dp_up down in 2 dfs maybe!
•  » » » » 4 years ago, # ^ |   0 Ok. Thanks! :D
 » 4 years ago, # | ← Rev. 2 →   0 804E — The same permutation Hint 1: Should be 4*k + 2 instead of 4*k + 4.
 » 4 years ago, # |   0 Ok. Obviously stupid question, but still I don't know how to prove that: sum sz_i = n => sum min(sz_u, sz_v) log(max(sz_u, sz_y))=n sqrt(n) log(n)? I suppose, we should prove that sum min(sz_u, sz_u) <= n sqrt(n)... Thank you
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 .
•  » » 4 years ago, # ^ |   0 Imagine you have a graph where each vertex represents one of the components and has weight equal to the size of that component. Your task is to draw n-1 edges weight of each is equal to minimum among vertexes it connects in order to maximize the total weight of edges. It's obvious that the worst case happens when you form a clique of x heaviest vertexes (such that (x — 1)x = 2n since multuedges aren't allowed). That gives you that each vertex has no more than sqrt(n) edges. That's it :)
•  » » 4 years ago, # ^ |   +28 As I didn't see anybody explaining the simple solution I decided to do so.Well it's not exactly what you ask but I think you will understand my solution better (and it works in ). First you must be able to solve the problem for two trees in O(szu + szv) time. In the editorial there is a . If you do the one described in the editorial your solution will simply run in time.So now lets solve the other part of the problem. Lets consider 2 case:1) For a query (u, v), . For such queries we simply run the or O(szu + szv) solution. The overall complexity for such queries then will be or .2) For a query (u, v), . Lets assume that szv ≤ szu. How many trees u such that exist? Well you can simply prove that they are at most , because . Then we can precompute for every "heavy" tree u answer with every other tree v. For a fixed tree u this precompute will have complexity O(N) or depending how you solve the problem for 2 trees. Then this part will be done in time (or ) and will take memory.So then the whole solution will take or and memory.Here is my Accepted code: 26851219PS: You can see a constant B which I use as . Idk why during the contest I thought . It's actually about 315.
•  » » » 4 years ago, # ^ |   +8 Separating big and small components is useful for analysis but in code you can just solve for each query separately and reuse the answer in case of duplicate queries
•  » » » » 4 years ago, # ^ |   0 Oh nice. I actually thought about that during the contest but that the complexity seemed O(N * Q) to me. Now when I thought for a bit it actually is easily provable that the complexity will be . Thanks for sharing :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 How do you solve two trees without log? You do still need to sort verticies with farthest distance from them, right? (And then two pointers)
•  » » » » 4 years ago, # ^ |   0 Read your code and got it, thx.
•  » » » » 4 years ago, # ^ |   +3 We will use the following observations:1) If we have a tree the furthest vertex away from any vertex u will be one of the two ends of any diameter of this tree. You can easily prove this. Let's define d(u) to be the maxiaml distance from vertex u to any other vertex in its tree. Using this observation we can find d(u) for every u in by preforming a couple of DFSes (first we find a diameter of the tree and the we do one DFS from both its ends).2) When we add the edge between the two trees we will have dimeter equal to max(diamT(u), diamT(v), d(u) + d(v) + 1). Let's define D = max(diamT(u), diamT(v)). Obviously we can solve the problem independently for one of the trees. By this I mean we pick one of the trees and then for every​ vertex of the other tree we get the expected diameter if we have chosen it as one of the ends of the edge we will add. Then we if that vertex is u we need to find the count of vertices v such that D > d(u) + d(v) + 1 because for them it is optimal to save our previous diameter. This inequality equivalent to D - d(u) - 1 > d(v). From right we have a constant. How can we find the number of vertices v satisfying the inequality? We can use partail sums. Same goes for the case when D ≤ d(u) + d(v) + 1 but there we do partial sums of d(v). You can reffer to my code.
 » 4 years ago, # |   0 805D-Minimum Number Of Steps what is wrong with this solution somebody help me.
•  » » 4 years ago, # ^ |   +3 take mod for : 1) no_b += no_b ; 2)no_b++
•  » » 4 years ago, # ^ |   0 You get overflow in no_b
 » 4 years ago, # |   0 Auto comment: topic has been updated by saliii (previous revision, new revision, compare).
 » 4 years ago, # |   0 For Div1 C / Div2 E, would it be possible to get input data used for #17 ?
 » 4 years ago, # |   -8 Hi, here is one question, for 804C Ice cream coloring. Will this algorithm work? During inputting tree T, record every pair of ice creams in every set of T's vertex as an edge of G. For example, if there are k ice creams in the set of a T's vertex, then we add k(k - 1) / 2 edges for G during its input(eliminating duplicates). After the construction of G, run a traditional colouring algorithm for it. Such solution doesn't use T as a tree and there is no dfs. But wrong at test case 3. I wondered what is wrong for the whole day:(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 There might be O(n^2) edges on G, that doesn't fit memory/time. Edit: also, iirc coloring a general graph is np-complete (might be wrong).
•  » » 4 years ago, # ^ |   0 me too have same problem. can't figure out what's the use of input tree T.
•  » » » 4 years ago, # ^ |   0 check this comment for detail.
 » 4 years ago, # |   0 I wasn't able to get participate on this contest , but i really appreciated the problemset . Its the first time i'm able to build a solution for a D problem :D
 » 4 years ago, # |   0 Auto comment: topic has been updated by saliii (previous revision, new revision, compare).
 » 4 years ago, # |   0 I am getting TLE on test 25 for Div2 F/Div1 D. Can anyone tell what the problem is I can't seem to find it thanks in advance. Code : http://codeforces.com/contest/804/submission/26910532
 » 4 years ago, # |   0 Auto comment: topic has been updated by saliii (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone plzz explain me why my solution is wrong?? http://codeforces.com/contest/805/submission/26964381 actually it gives correct answer for test case#13 on my machine..
•  » » 4 years ago, # ^ |   +5 The calculation of xb*(a[xa]-1) overflows if int is 32-bit.
•  » » » 4 years ago, # ^ |   0 Thanks for the help.
 » 4 years ago, # |   0 A bit simpler solution for the problem 804E (DIV1E).
 » 4 years ago, # |   0 I want to ask some questions about Div1 F.I can't understand the last part that is calculating the ans knowing mincnt[i] and maxcnt[i].For every j(j+bigger+1<=A), your code adds C(upper,j)*C(bigger,b-1-j) to the ans.But j is the number of mxs that are bigger or equal to mx[j] while the problem said "if there are no more than a - 1 gangs with power strictly more than p".Then there may be some situations you do not calculate such as many mxs are equal then your j if not about the number of strictly more than p,but is about mxs that are bigger or equal.Can someone help me?Am I right?
•  » » 4 years ago, # ^ |   0 right, fixed.
 » 4 years ago, # |   0 I have a question about Div1.F.Look at this case: 5 2 2 01011 00011 11000 00100 00110 10 1110100101 1 1 7 1001000 4 1001 10 0110001100 As the whole graph is an SCC ,the mn and mx are: mn[1]=6,mx[1]=10 mn[2]=1,mx[2]=1 mn[3]=2,mx[3]=7 mn[4]=2,mx[4]=4 mn[5]=4,mx[5]=10 if we set the score as follow: score[1]=6 score[2]=1 score[3]=4 score[4]=4 score[5]=4 then we can choose any 2 gangs from gang 1,3,4,5, so the answer should be 6.But the std code gives 4.I wonder if i understood the problem incorrectly.Thanks!
 » 3 years ago, # |   0 In the question A (fake np) the answer in the second example (which is 3) is different from the answer that is tested during compiling the program on the website , why did the author do such a thing??
•  » » 3 years ago, # ^ |   0 both 2 and 3 are right answers
•  » » » 22 months ago, # ^ |   0 what should be the answer if l and r given is 26 and 27?.... acc. to me it should be 3 ..correct me If I m wrong?
•  » » » » 22 months ago, # ^ |   0 2,3,9,13,26 and 27 are correct answers
•  » » » » » 22 months ago, # ^ |   0 but 27=3x3x3...and 26=2x13....so 3 occurs most times...so only 3 would not be the answer
•  » » » » » » 22 months ago, # ^ |   0 dude3 is written only once
•  » » » » » » » 22 months ago, # ^ |   0 oh...I got it..thanku
 » 3 years ago, # |   0 I think in solution of problem C, there was a kind of mistake (python) (int(input())-1)//2 just '/' instead of "//" maybe
•  » » 3 years ago, # ^ |   0 all is right, '//' means integer dividing
•  » » » 3 years ago, # ^ |   0 oh, ok , sorry
 » 2 years ago, # |   0 The question is about the fires example of 805F problem. How is it possible that the answer for {1,3} and {3,1} is different?
 » 23 months ago, # |   0 In problem 805A, how to do this Find the maximum number,which occurs maximum number of times in the segment.
•  » » 23 months ago, # ^ |   0 Can someone post solution for this problem
 » 22 months ago, # |   0 what would be the answer in question A ...if l and r given is 26 and 27... answer should not be equal to 3 instead of 2...correct me if I m wrong !!
•  » » 21 month(s) ago, # ^ |   0 if there are multiple answers, print any of them
 » 13 months ago, # |   0 Am I only one who doesn't understand div1C/div2E problem statement???