Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### TLE's blog

By TLE, history, 21 month(s) ago,

1081A - Определенная игра

Idea: yjq_naiive Developer: yjq_naiive

Hint
Solution
Code (yjq_naiive)

1081B - Прощальная вечеринка

Idea: yanQval Developer: yanQval

Hint
Solution
Code (yanQval)

1081C - Цветные кирпичики

Idea: fjzzq2002 Developer: fjzzq2002

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081D - Максимальное расстояние

Idea: fateice Developer: fateice

Sorry for the weak pretest.

Hint
Solution
Code (fateice)

1081E - Недостающие числа

Idea: fjzzq2002 Developer: fjzzq2002

Hint
Solution
Code1 (fjzzq2002)
Code2 (fjzzq2002)

1081F - Коварный интерактор

Idea: fjzzq2002 Developer: fateice, fjzzq2002

Yet another binary search?

Hint
Solution
Code (fjzzq2002)

1081G - Сортировка слиянием наносит ответный удар

Idea: quailty Developer: fateice, fjzzq2002, yjq_naiive

Hint
Solution
Code (fjzzq2002)

1081H - Палиндромная магия

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

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