### TLE's blog

By TLE, history, 6 months ago, ,

1081A - Definite Game

Idea: yjq_naiive Developer: yjq_naiive

Hint
Solution
Code (yjq_naiive)

1081B - Farewell Party

Idea: yanQval Developer: yanQval

Hint
Solution
Code (yanQval)

1081C - Colorful Bricks

Idea: fjzzq2002 Developer: fjzzq2002

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: fjzzq2002 Developer: fjzzq2002

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Tricky Interactor

Idea: fjzzq2002 Developer: fateice, fjzzq2002

Yet another binary search?

Hint
Solution
Code (fjzzq2002)

1081G - Mergesort Strikes Back

Idea: quailty Developer: fateice, fjzzq2002, yjq_naiive

Hint
Solution
Code (fjzzq2002)

1081H - Palindromic Magic

Idea: fjzzq2002 Developer: fjzzq2002, yjq_naiive

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

 » 6 months 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?
•  » » 6 months ago, # ^ |   0 this one is easier
•  » » 6 months 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?
•  » » » 6 months 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.
•  » » 6 months ago, # ^ |   0 Excuse me? How can I find that problem ?
•  » » » 6 months ago, # ^ |   0 This is a problem used in Sichuan Team Selection Competition(for CNOI) 2017. I don't know anywhere to submit it:(
 » 6 months ago, # |   +10 "and we didn't except anyone to pass."should be *expect
•  » » 6 months ago, # ^ |   +15 Corrected, sorry about that.
 » 6 months 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
•  » » 6 months 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)
•  » » » 6 months ago, # ^ |   +1 Thanks for helping i understand with the help of you answer
•  » » » 5 months 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 months 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 months ago, # ^ |   +1 ok, i understand thanks for helping
•  » » 6 months 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!
•  » » » 6 months 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 ?
•  » » » » 6 months ago, # ^ |   +1 ghoshsai5000 is correct. Person[8] and person[9] should have different hats.
•  » » 6 months 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)
•  » » » 6 months ago, # ^ |   0 Thank you all for helping me :)
•  » » 6 months ago, # ^ |   0 detailed editorial for problem C : https://codeforces.com/blog/entry/63900
 » 6 months 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
•  » » 6 months ago, # ^ |   +135 It's called prim.
 » 6 months 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?
•  » » 6 months 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.
 » 6 months ago, # |   +13 we didn't expect any to pass. That's too realistic.
 » 6 months ago, # |   +24 hints are amazing!
 » 6 months ago, # |   0 sir,,,,problem (B) ,simple input and output same but wrong ans(WA) 1st case ans,Why do it?
•  » » 6 months ago, # ^ |   -10
•  » » » 6 months ago, # ^ |   +23 You output 'possible'. It should be 'Possible', capital P.
•  » » » » 6 months ago, # ^ |   0 thanks. i guess it.
 » 6 months ago, # |   +1 Oh my god! Parity! How could I not have thought about it!
 » 6 months ago, # |   0 Thanks for your fast editorials
 » 6 months ago, # |   0 Does someone have an idea why I got a TLE in problem B? I used the same approach as mentioned in the solution. My submission: https://codeforces.com/contest/1081/submission/47127581
 » 6 months ago, # | ← Rev. 2 →   0 nice problemset..
 » 6 months 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.
•  » » 6 months ago, # ^ |   0 To divide a by b with modulo, you need to multiply a by reverse element of b under modulo m
•  » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1081/submission/47111844 see this submission
 » 6 months 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".
•  » » 6 months ago, # ^ |   +10 I've modified the editorial. Hope that helps.
 » 6 months 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.
•  » » 6 months ago, # ^ |   +1 Try this: 3 2 2 1 2 1 2 1 2 3 47
•  » » » 6 months 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
•  » » » » 6 months 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
•  » » » » » 6 months 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
•  » » 6 months ago, # ^ |   0 Can u please tell the insight behind using mst?
•  » » » 6 months 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.
 » 6 months 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
•  » » 6 months 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.
 » 6 months 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?
 » 6 months 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.
•  » » 6 months ago, # ^ |   +5 literally how I solved it. Beautiful solution.
•  » » 6 months ago, # ^ |   +5 We can also solve it with union-find algorithm instead of bfs.
 » 6 months 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
 » 6 months 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
•  » » 6 months ago, # ^ |   0 use & for a vector parameter, but anyway your solution was incorrect
•  » » » 6 months ago, # ^ |   0 Yes I used the & operator, let me check what is the error. Thank you linjek
 » 6 months ago, # |   0 please any one can explain the solution of problem B. i am advance thankful for it.
 » 6 months ago, # |   0 Can anyone explain me how this code from C calculates the number of combinations to take k from n-1?
 » 2 months 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.
•  » » 2 months 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.
•  » » » 2 months ago, # ^ |   0 Thanks. I got it now