TLE's blog

By TLE, history, 3 years ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +154
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this one is easier

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excuse me? How can I find that problem ?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is a problem used in Sichuan Team Selection Competition(for CNOI) 2017. I don't know anywhere to submit it:(

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

"and we didn't except anyone to pass."

should be *expect

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Corrected, sorry about that.

»
3 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for helping i understand with the help of you answer

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          ok, i understand thanks for helping

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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:

    10

    7 7 7 7 7 7 8 8 9 9

    person[0] = There are 7 people with different hat other than me

    person[1] = There are 7 people with different hat other than me

    person[2] = There are 7 people with different hat other than me

    person[3] = There are 7 people with different hat other than me

    person[4] = There are 7 people with different hat other than me

    person[5] = There are 7 people with different hat other than me

    person[6] = There are 8 people with different hat other than me

    person[7] = There are 8 people with different hat other than me

    person[8] = There are 9 people with different hat other than me

    person[9] = There are 9 people with different hat other than me

    Step:

    • 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 1

    The 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!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    detailed editorial for problem C : https://codeforces.com/blog/entry/63900

»
3 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    For sure all squares are at most 1013. Let , because t2i2 - t2i - 12 ≤ t2i2 - (t2i - 1)2 = 2ti - 1 ≤ x2i, therefore t2i ≤ 105.

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

we didn't expect any to pass. That's too realistic.

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

hints are amazing!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sir,,,,problem (B) ,simple input and output same but wrong ans(WA) 1st case ans,Why do it?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Oh my god! Parity! How could I not have thought about it!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your fast editorials

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nice problemset..

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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".

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I've modified the editorial. Hope that helps.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try this: 3 2 2 1 2 1 2 1 2 3 47

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u please tell the insight behind using mst?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain D..specifically why mst is being used and where do we get the intuition to use it in this problem?

»
3 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    literally how I solved it. Beautiful solution.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    We can also solve it with union-find algorithm instead of bfs.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What am I missing in my code for problem D? WA on TC 7. Plz Help. https://codeforces.com/contest/1081/submission/47271236

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use & for a vector parameter, but anyway your solution was incorrect

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I used the & operator, let me check what is the error. Thank you linjek

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please any one can explain the solution of problem B. i am advance thankful for it.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me how this code from C calculates the number of combinations to take k from n-1?

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A lot of fun, i solved problem C by the mix of 2 solutions that editorial promoted.

Check my submission

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

could someone please explain question C Problem C I am confused with the statement . Please help Thanks and regards

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      23 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi @AkshayAnand, Can you clarify your above statement,Ia am still not able to understand the question!! Thanks in advance!!

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Just Think in a way that dp[I][j] tells number of ways to make first I bricks coloured such that it has j different adjacent colours.

        now lets think for a ith index,when we are at ith index then there are two possibilities

        1-> ith index brick colour is same as its left adjacent colour(I-1 index). if it is a case then we will take the answer of the previous index dp[I-1][j] where j is different adjacent colours.

        2->ith index brick colour is not same as its left adjacent colour(I-1 index).then just think that if we have a different colour in previous index and we have total of m colours then ith index can have (m-1) colours. so we will firstly take dp[I-1[j-1] and for each way we have (m-1) different colour that's why dp[I-1][j-1]*(m-1)

        Base Case will be dp[I][0] as we have k=0 then for every index we can have only single brick colour for whole bricks. thus dp[I][0] = m.

        Final Transition: dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(m-1)