### TLE's blog

By TLE, history, 5 years ago,

1081A - Definite Game

Idea: sunset Developer: sunset

Hint
Solution
Code (yjq_naiive)

1081B - Farewell Party

Idea: yanQval Developer: yanQval

Hint
Solution
Code (yanQval)

1081C - Colorful Bricks

Idea: TLE Developer: TLE

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081D - Maximum Distance

Idea: fateice Developer: fateice

Sorry for the weak pretest.

Hint
Solution
Code (fateice)

1081E - Missing Numbers

Idea: TLE Developer: TLE

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Tricky Interactor

Idea: TLE Developer: fateice, TLE

Yet another binary search?

Hint
Solution
Code (fjzzq2002)

1081G - Mergesort Strikes Back

Idea: quailty Developer: fateice, TLE, sunset

Hint
Solution
Code (fjzzq2002)

1081H - Palindromic Magic

Idea: TLE Developer: TLE, sunset

This problem is quite educational and we didn't expect anyone to pass. :P

Hint
Solution
Code (yjq_naiive)

Hope you enjoyed the round! See you next time!

• +154

| Write comment?
 » 5 years ago, # |   +41 Bonus for H: pick a as some non-empty substring of A and b as some non-empty substring of B. Concatenating them, he will get string ab. How many different palindromic strings can he get?
•  » » 5 years ago, # ^ |   0 this one is easier
•  » » 5 years ago, # ^ |   0 What I have so far:It seems we are basically looking for string p and s such that ((AR contains s and B contains ps) or (AR contains ps and B contains s)) and p is palindromic (possibly empty). To prevent double counting AR should not contain xs or B should not contain xs, where x is the last character of p.There are still some details to work out, but it feels like it should be possible to count these strings by creating a suffix tree containing AR and B to iterate over common substrings s, and by creating a palindromic tree to count the number of different p for each of them (by starting at the longest palindromes ending before the suffix leaves of the current node in the suffix tree and then calculating the number of ancestors of these nodes in the palindromic tree).Is this also the approach you had in mind or am I overcomplicating things?
•  » » » 5 years ago, # ^ |   +10 I think you approach is correct. There is also some approach using SAM or SA but I think there are many details whatever approach you use.
•  » » 5 years ago, # ^ |   0 Excuse me? How can I find that problem ?
•  » » » 5 years ago, # ^ |   0 This is a problem used in Sichuan Team Selection Competition(for CNOI) 2017. I don't know anywhere to submit it:(
 » 5 years ago, # |   +10 "and we didn't except anyone to pass."should be *expect
•  » » 5 years ago, # ^ |   +15 Corrected, sorry about that.
 » 5 years ago, # | ← Rev. 4 →   +1 What is the meaning of this line in Problem B :"It's clear that the number of people having the same bi should be a multiple of bi".and in Problem C i am not able to figure out how multiplying (m-1)with f[i-1][j-1] works please help me
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Here is my editorial on Problem C. It may be helpful to you :)And to explain the DP solution provided — f(i, j) is the number of ways of colouring i bricks with j bricks having a different colour to it's neighbour. There are two options for the i-th brick. Case 1 — It is the same colour as the (i — 1)th brick. In that case, f(i, j) += f(i — 1, j)Case 2 — It is a different colour. Then the number of bricks with different colour increases from j to j + 1. And there are (m — 1) ways to colour this brick. So, f(i, j + 1) += (m — 1)f(i — 1, j)
•  » » » 5 years ago, # ^ |   +1 Thanks for helping i understand with the help of you answer
•  » » » 5 years ago, # ^ |   0 i don't understand how there are (m-1) way to colour this brick ? i mean there are j colour you used left side then you can use (M — j) colour we can select for f(n-1,k-1)
•  » » » » 5 years ago, # ^ |   0 Brick #x should not have the same colour as Brick#(x — 1) and Brick#(x + 1).It can have the same colour as Brick#(x — 2), Brick #(x — 3), etc.
•  » » » » » 5 years ago, # ^ |   +1 ok, i understand thanks for helping
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I also confused with the editorial so I'm writing this so anyone can help me to clear the idea.let's say you have 10 people and the input:107 7 7 7 7 7 8 8 9 9person[0] = There are 7 people with different hat other than meperson[1] = There are 7 people with different hat other than meperson[2] = There are 7 people with different hat other than meperson[3] = There are 7 people with different hat other than meperson[4] = There are 7 people with different hat other than meperson[5] = There are 7 people with different hat other than meperson[6] = There are 8 people with different hat other than meperson[7] = There are 8 people with different hat other than meperson[8] = There are 9 people with different hat other than meperson[9] = There are 9 people with different hat other than meStep: The easiest thing to realize is maybe person 8 & 9 is wearing the same hat, because they belong to the same group (a group that consists of people whom the hat is different with 9 people) Our current answer:X X X X X X X X 1 1(X = don't know yet, but can be assured that it's not 1) Then, we can help person 7 & 6 to know their hat since they also belong to the same group, Our current answer:X X X X X X 2 2 1 1 (Observe that person 7 & 6 using different hat, not 1, not X) For the final step, we can do the same thing except we can't. Person 0 told us that there are 7 people which differs than him but if we mark all the X into 3, then there will be only 4 (person 6-9). But we can divide X into P/Q part such that P = number of people which told you they know A people with different hats, and Q = N — A, in this case, P = 6, Q = 3 so X will be divided into 2 parts Our current answer:3 3 3 4 4 4 2 2 1 1The editorial state that P must be divisible by Q because if it's not it'll add more difference than what's needed, (6/3 -> 3 Red 3 Blue, 2 different hats | 7/3 -> 3 Red 3 Blue 1 Green, 3 different hats) (CMIIW). It's not a mathematical proof but it's based on my intuition, I welcome any suggestions!
•  » » » 5 years ago, # ^ |   0 I have a doubt. If person[8] and person[9] have 9 people with different hats, shouldn't they have different hats. X X X X X X X X 1 2 Please correct me if I am wrong. I didn't understand this part. If they both have hat 1, won't there be only 8 people with different hats to them and not 9 ?
•  » » » » 5 years ago, # ^ |   +1 ghoshsai5000 is correct. Person[8] and person[9] should have different hats.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 For problem B, considering a color of hats that b people are wearing, these b people will have this same b. Therefore, the people having this b must be a multiple of b (because every kind of such hats will contribute b such persons)
 » 5 years ago, # | ← Rev. 2 →   -16 In problem D there is also a very simple solution with Dijkstra. We just have to find the maximum answer for 1 vertex and claim that it will be the same for everyone. Evidence: If from the first peak there is the worst way to some other one. Now let's iterate over everything except the other vertex. If one of them is better than the first one to this bad one, then why couldn’t we come first to this one, and then to the bad one? Then we will find a way shorter.__ My code:https://codeforces.com/contest/1081/submission/47122453
•  » » 5 years ago, # ^ |   +135 It's called prim.
 » 5 years ago, # |   0 Wow, I just realized that my E (47122728) isn't necessarily right (still got AC).I just did greedy. At every even indexed position i, pick the smallest x such that the pref-sum[i+1] is a perfect square, and pref_sum[i] is a perfect square (assuming pref_sum[i] = x + pref_sum[i-1]).To do this, we just keep one variable t, such that we put x = t^2 — sum[i-1] for the smallest t that works.Now my mistake was thinking that all squares were at most 10^13, instead of all deltas being at most 10^13. If that holds, we can just keep trying t's until one works, since t never decreases in the algorithm, and when t^2 > 10^13, we can output FAIL. To check for working just binary search from a vector of squares or something.Is there any input that hacks this?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 For sure all squares are at most 1013. Let , because t2i2 - t2i - 12 ≤ t2i2 - (t2i - 1)2 = 2ti - 1 ≤ x2i, therefore t2i ≤ 105.
 » 5 years ago, # |   +13 we didn't expect any to pass. That's too realistic.
 » 5 years ago, # |   +24 hints are amazing!
 » 5 years ago, # |   0 sir,,,,problem (B) ,simple input and output same but wrong ans(WA) 1st case ans,Why do it?
•  » » 5 years ago, # ^ |   -10
•  » » » 5 years ago, # ^ |   +23 You output 'possible'. It should be 'Possible', capital P.
 » 5 years ago, # |   +1 Oh my god! Parity! How could I not have thought about it!
 » 5 years ago, # |   0 I have used the same approach but my answer is comming wrong . I have calculated (n-1)Ck*m*(m-1)^k, yet it is giving wrong ans with n=123, m= 45, k= 67. Here is link to my code Ideone.com.Please tell me where I am wrong!!Thanks in advance.
•  » » 5 years ago, # ^ |   0 To divide a by b with modulo, you need to multiply a by reverse element of b under modulo m
•  » » 5 years ago, # ^ |   0 https://codeforces.com/contest/1081/submission/47111844 see this submission
 » 5 years ago, # |   0 Can someone please explain problem B..?? i am having trouble understanding the language of the editorial, specially this line "It's clear that the number of people having the same bi should be a multiple of bi".
•  » » 5 years ago, # ^ |   +10 I've modified the editorial. Hope that helps.
 » 5 years ago, # |   0 in problem(D) does it matter whether we use prims or kruskal for making mst, my solution failing on test 18 ,lots of people failed on 18th please help me if you know something about that.
•  » » 5 years ago, # ^ |   +1 Try this: 3 2 2 1 2 1 2 1 2 3 47
•  » » » 5 years ago, # ^ |   0 bro it gives 1 1 which is right isn't . my code is https://codeforces.com/contest/1081/submission/47174196(kruskal) https://codeforces.com/contest/1081/submission/47170933(prims) after finding the mst i consider all the edges which have special vertex on both sides using recusion
•  » » » » 5 years ago, # ^ |   0 You need build mst which contains all special vertex, but not for all tree. Edges with 1 and mb 0 special vertex can also be there. Test 18 checks that
•  » » » » » 5 years ago, # ^ |   0 thanks brother, i didn't use the technique described in editorial, problem was after obtaining the mst a method was required to consider all the edges which have special vertices on both sides(at any distance), i was leaving a case in that, now it is accepted:D
•  » » 5 years ago, # ^ |   0 Can u please tell the insight behind using mst?
•  » » » 5 years ago, # ^ |   0 since there exist multiple paths between two vertices and the cost of EACH path is the maximum of all edges in individual path and the distance between two vertices is minimum of all path's cost. as for distance we are looking for minimum cost path for that purpose it is always good to select ONLY those set of vertices which are good enough to make the graph connected(tree) because from there if you add any more edge that will increase the number of paths between two vertices with heavier edges being introduced they(extra edges after mst) will never effect the distance between the vertices since their(extra edges) weight is more than previous ones(edges in the tree). so wee need to build a mst first and then find a way to account all the edges(having both side special tree) in the tree.
 » 5 years ago, # |   0 I don't understand how does the rfact[] work in Code2 of the Problems C. Can anyone tell me why we can do that instead of using divison. I have just learned programming for 2 months, so please don't laugh at me :)) Thanks for any helping
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 you can also find inverse like in this submission https://codeforces.com/contest/1081/submission/47111844. It uses euclidean theorem.....google it.
 » 5 years ago, # |   0 Can anyone explain D..specifically why mst is being used and where do we get the intuition to use it in this problem?
 » 5 years ago, # | ← Rev. 2 →   +15 In D we can just binary search on answer. For fixed cost we can run bfs from any special vertex on graph G' where G' is exactly the same graph but with removed(disabled) edges with edge_cost > cost and check whether we can visit every special vertex. It's possible to check this condition by running bfs from any special vertex on G'.In this binary search we have to find the smallest possible value that satisfies the condition above.
•  » » 5 years ago, # ^ |   +5 literally how I solved it. Beautiful solution.
•  » » 5 years ago, # ^ |   +5 We can also solve it with union-find algorithm instead of bfs.
 » 5 years ago, # |   0 What am I missing in my code for problem D? WA on TC 7. Plz Help. https://codeforces.com/contest/1081/submission/47271236
 » 5 years ago, # |   0 I am getting TLE for the code (47303815). I have used Kruskal along with disjoint set. Link to code: https://codeforces.com/contest/1081/submission/47303815
•  » » 5 years ago, # ^ |   0 use & for a vector parameter, but anyway your solution was incorrect
•  » » » 5 years ago, # ^ |   0 Yes I used the & operator, let me check what is the error. Thank you linjek
 » 5 years ago, # |   0 Can anyone explain me how this code from C calculates the number of combinations to take k from n-1?
 » 5 years ago, # |   -10 I didn't understand the second solution for problem C. I understood we are taking all the possible combinations for the k bricks which satisfy the condition. Then I didn't understand that how the term m * (m — 1) ^ k is handling all the possible cases.
•  » » 5 years ago, # ^ |   0 These k bricks must be taking a color different from its left neighbor, so each of them has $m-1$ ways of choosing their colors. Also we have $m$ colors for the first brick.
•  » » » 5 years ago, # ^ |   0 Thanks. I got it now
 » 4 years ago, # |   0 A lot of fun, i solved problem C by the mix of 2 solutions that editorial promoted.Check my submission
 » 4 years ago, # |   +1 could someone please explain question C Problem C I am confused with the statement . Please help Thanks and regards
•  » » 4 years ago, # ^ |   +1 There must be exactly K bricks whose color differs from its left neighbour.Eg: RR B BB G GG .In this case K will be 2
 » 5 months ago, # |   0 anyone explain the implementation of D not able to understand