Vovuh's blog

By Vovuh, history, 6 days ago, In English,

1176A - Divide it!

Idea: Vovuh

Tutorial
Solution

1176B - Merge it!

Idea: MikeMirzayanov

Tutorial
Solution

1176C - Lose it!

Idea: Vovuh

Tutorial
Solution

1176D - Recover it!

Idea: MikeMirzayanov

Tutorial
Solution

1176E - Cover it!

Idea: MikeMirzayanov

Tutorial
Solution

1176F - Destroy it!

Idea: BledDest

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

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

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

      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 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        thanks!!

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

        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.

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

      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 :)

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

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

why in that order ?

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

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

        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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you do problem C with DP and binary search? Thanks!

»
5 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F with DP ?? Thanks!

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    55473892

    I guess my submission is clear it has some comments if you did not get the idea I can explain it a little bit more here

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is the graph is bipartite?

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

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

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Can someone tell me why this python code is giving WA while its c++ version is giving correct result: PROBLEM A: ~~~~~ Your code here... t = int(input()) while (t > 0): t = t — 1 n = int(input()) count = 0 while (n % 5 == 0): count = count + 1 n = 4 * n / 5 while (n % 3 == 0): count = count + 1 n = 2 * n / 3 while (n % 2 == 0): count = count + 1 n = n / 2 if (n == 1): print(count) else: print("-1") n = 0 ~~~~~

link: https://codeforces.com/contest/1176/submission/55432686

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why it is not accepting for problem E [](https://codeforces.com/contest/1176/submission/55372927)

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

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

  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

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

why 5 4 3 is not a valid answer for D for below test case-- 3 3 5 2 3 2 4

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

    In problem statement, "if a[i] is a prime number, then one integer p[a[i]] is appended to array b" if a[i]=5 and here 5 is prime number so 5th no. prime number is 11 which must appended in array b.But 11 is not in given array b that's why 5 4 3 is not a valid answer.

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

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.

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

PROBLEM C CAN SOMEBODY TELL ME WHY I M GETTING TIME OUT IN #TC 9.Ii know m algo is not efficient but i m not able to get editorial pls help my solution is 55554895 55554895