Блог пользователя vovuh

Автор vovuh, история, 5 лет назад, перевод, По-русски

1176A - Divide it!

Идея: vovuh

Разбор
Решение

1176B - Merge it!

Идея: MikeMirzayanov

Разбор
Решение

1176C - Lose it!

Идея: vovuh

Разбор
Решение

1176D - Recover it!

Идея: MikeMirzayanov

Разбор
Решение

1176E - Cover it!

Идея: MikeMirzayanov

Разбор
Решение

1176F - Destroy it!

Идея: BledDest

Разбор
Решение
Разбор задач Codeforces Round 565 (Div. 3)
  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Problem E was little tricky, learned a lot. Thanks a lot for great contest!!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    can u explain problem E? I haven't understood the tutorial. thanks in advance!!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Maintain a adjacency list, and then arrange the vertices by number of other vertices it is connected to(v[current_vertex].size) in a multiset or priority_queue (descending order). Pop to the priority_queue and mark the vertex as visited and push it in ans_vector. Iterate all the vertices to which it is connected as also mark them true but dont put these vertices in ans. (Because you need to maintain different colour). Do this until all vertices are visited.

      Ex: For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Vertex 2 will have max size(2), push it in ans_vector and also mark 1,2 and 3 as true.

      Now you have an answer vector. If the size if less than equal n/2 print it otherwise print those which not not in ans_vector . This is because the set of vertices which are in ans_vector and which aren't both satisfies the condition of given problem (expect for size one)

      My submission: https://codeforces.com/contest/1176/submission/55381513 Though i was not able to do it in contest.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        thanks!!

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If someone is trying this approach, try this case. You will understand why pure greedy approach won't work.

        1
        9 8
        1 3
        2 3
        3 4
        4 5
        4 6
        9 7
        4 9
        9 8

        Thats why we have to use either the found set or compliment of it.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks a lot for this test case. I was thinking greedy will work

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            What do you exactly mean by greedy here, I just ran a dfs on the graph starting with coloring 1 with 0, its uncolored neighbors with 1 and so on, got ac link , then printing each all colored 0 or1 based on their size

            Am i missing something,

        • »
          »
          »
          »
          »
          13 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          thank you very much for the tc!!!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        please explain the condition when the ans.size() > n/2 if i understood it correctly you want the answer to be all the other remaining vertices. Why is it so?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          This is because the vertices not present in ans vector will also satisfy the given problem statement.

          Consider coloring the vector in answer vector by color 1 and rest by color 2. Now reverse the colors. You can better understand by drawing some examples.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you elaborate this If the size if less than equal n/2 print it otherwise print those which not not in ans_vector . with a test case. Since we are sorting in descending order why there is a need to do so?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Alternately, you can try the approach given in tutorial.

      Use BFS. Since BFS transverses the graph layer-wise, you can 'color' the alternate layers with color 0 and 1.

      Ex:For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Color vertices 1 and 3 with color 0 and 2 with color 1. You would get two answers, the vertices those on even layers and the other on odd. Print the one with minimum size.

      This is a more cool approach :)

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Anyone having solution of E using DSU? or give some idea?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"you can just simulate the process, performing actions from third to first."__

why in that order ?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Every time you perform operations 2 and 3, you multiply the number with 2 or 4. Therefore, each application of 2 and 3 will make the number divisible by 2, thus forcing you to perform operation 1. If you perform 3 and 2 first until you cannot anymore, then the only possible operation you need to perform is 1.

    Of course, you can perform the operations in any order you want (eg. 1, 3, 2, 1, 2, etc) as long as you can still perform one.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why 3*cnt5 not 4*cnt5 in problem A? please answer.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        for each power of 5 you have to do:

        • apply once operation 3 (/5, * 4)

        • apply twice operation 1 (divide twice by 2 since you multiplied with 4 before)

        so 3 operations

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

anyone, please explain the problem D in Graph (dfs and similar) approach. Thanks

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Won't the solution to the problem D have a worst time complexity of O(n^2) ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain problem F I am not able to understand the editorial solution. Thanks in advance.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello. I'm interested. Do someone implement some algorithms and data structures from scratch during competition or they have been implemented? I mean sieve, for example, in task D.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in my opinion,one should be familiar with sieve through practice so that one can easily implement it within a minute during contest.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

why 3*cnt5 not 4*cnt5 in problem A? please answer.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you see. Here's three steps to execute: 1.perform the third operation: n = n * 4 / 5 2.perform the first operation: n = n / 2 3.perform the first operation: n = n / 2 after theses three steps the result you got is the n you type divided by 5. so it's 3 * cnt5.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody explain me problem F, the problem say that "you choose the cards and the exact order they are played", I think that if we have 3 cards 1, 2 ,3, we have to choose card 1, 2 and 3, not 3, 2 ,1 or 1, 3, 2, ... But I read that the solution has sorted the array and chosen maximum if we can, I think in some case, it will wrong, because we have neglected that we have to choose the cards in order they are played. Sorry about bad english

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey! can someone please tell me what is wrong with my code? http://codeforces.com/contest/1176/submission/55369953

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

@MikeMirzayanov Can you please tell me why this approach for problem E fails?

Basically I am greedily selecting vertices if none of their neighbours have been selected. At the end ,if the selected set has more than ceil(n/2) vertices then i print the complementary set

I feel this should work because one of the sets ie the original or the complementary set should have size less than or equal to ceil(n/2) and no two vertices in the original set have edges between them , so they are connected to some vertex in the complementary set (since the graph is connected) . So the complementary set is also a possible answer.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just now realized the mistake in my code. I should have checked for the floor(n/2) instead of ceil of n/2. Thanks anyways

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

For E,I tried "Graph coloring" with G and R such that neighbouring nodes have different colors,through BFS,now count the number of Green and Red,which ever is less than n/2,print that.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

(Maybe my English is poor)

My idea is similar to the tutorial. This codedoes not exceed O(n), isn't it? But it really timed out. Why is this?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is wrong in this solution of problem D( Recover it!)?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Problem E, apparently just finding a bipartite coloring of the graph will suffice. That is what I did and got AC. My submission (in java) is here: https://codeforces.com/contest/1176/submission/58155189

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain problem C? I can't understand the editorial.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

i found my mistake

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1176E — Cover it

Could anybody explain why I am getting TLE my solution https://codeforces.com/contest/1176/submission/92457008

Then there is this solution by a friend of mine and he is getting TLE on case 15. Why? https://codeforces.com/contest/1176/submission/56036460