BledDest's blog

By BledDest, history, 2 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it  
  • +74
  • Vote: I do not like it  

»
2 months ago, # |
Rev. 2   Vote: I like it +91 Vote: I do not like it

I liked this round. Generally, the idea of educational rounds is very good. That one in particular expanded my horizons. Usually, when you learn MST, you think: "Why should I bother with Prim's or Boruvka's algo? Just learn Kruskal and forget about the rest". Task G reminds us that every algorithm is important and can have its own unique application.

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

    Before this round, I didn't even know about the existence of Boruvka's algorithm.

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

      Neither did I.

      Educational Rounds always teach us about some cool new algorithm or an application of an old algorithm that is not quite popular. :-)

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

    FWIW, you can solve this by starting with Kruskal's algorithm too. If you only look at the highest bit at b = 29, and split your vertex set into two halves V0 and V1 (one with all vertices where bit b is turned on, the other all the vertices where this bit is turned off). It follows that internal edges in either V0 or V1 will have bit b turned off, but edges between the two components will have this bit turned on. Thus, if you were to run Kruskal's algorithm you would first enumerate all internal edges in V0 and V1 before considering edges between the two components. It follows that Kruskal's algorithm would first connect all of V0 into a single tree (V1 respectively), and then find a single connecting edge between the two components.

    This gives you a simple recursive algorithm: Split on the highest order bit b, solve these two halves recursively (only considering bits  < b), and then find the weight of the single connecting edge, i.e. given two sequences of values, find the pair of values with minimal exclusive-or. This last problem can be solved using a very similar recursion.

    Code: 32170476

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey guys! Here are some of my thoughts on the meet-in-the-middle techniques on problem E: http://robezhang.blogspot.com/2017/11/meet-in-middle-technique-on-educational.html Feel free to ask questions and give suggestions!

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why don't you put your implemented codes with the tutorial?I think it will be helpful for many of us :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C can someone explain this part:

" Write down lengths of segments between two consecutive occurrences of this character, from the first occurrence to the start of the string and from the last to the end of the string."

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

    Let k be the maximal length such that there exists segment of length k that doesn't include character c. You can take all the occurrences of character c and check where this segment can fit. Thus maximal distance between those occurrences and ends of the string will get you maximal k.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how the bitmask solution look like for Probelm E?

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

    i think the bitmask is for easy iteration over all possible subsets. Suppose there are n elements then iterate over 0 to 2^n for all possible subset generation.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Look at my codes for the problem F. I wrote a solution using an algorithm Boruvki but unfortunately it got TLE. Even though my realization is not good as author might have expected to see, I think 2 seconds for the problem which has complexity of is (very) tight

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

    Try first sorting numbers. I have no idea why it works, but I also had time limit with same solution and sorting the numbers mad code at least 2x faster.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Doesn't the Boruvka's algorithm work for graphs with distinct edge weights only? In the case of problem G, how is that guaranteed?

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

    It is not guaranteed, hence the warning.

    but we should be careful to avoid adding edges that form cycles in MST

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

      Can you please elaborate how is the repetition avoided ??

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

        The problem is with duplicates. Instead of dealing with just weights of edges, consider the pair (w, i) for each edge, where w is its weight and i is the edge index. Now no two pairs are same as each edge has a different index and you can run Boruvka's algorithm as usual.

        Code

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody elaborate D? for m, 0<=m<=k, pi != i. isn't this a derangement? How can there be nCm ways to do this?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If I understand correctly, the editorial claims that the answer for B is always n — dx — dy. Can someone prove it mathematically? How about an intuitive proof?

Was just trying to figure out how I can come up with such ideas myself in the future. This sounds like a genius idea to me but I am not sure why it works.

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

    You start at (0,0) so if you end up at some (dx,dy) it means you have gone atleast dx in the x axis in the same direction and dy in y axis in the same direction. so it means if you come back dx and dy steps in the respetive directions you will be back at (0,0). For example consider this case 6 LLRRRR

    you are at 0,0 initially now you go l l so you are at (-2,0), then you go r r r r so you are at (2,0) which is 2 places right of the place you need to be(ie (0,0)) so you subtract that from 6 and you get 4 which is the answer. Hope this helps

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve G using prim's algorithm with 2sec time limit? cause i'm getting time limit error and was wondering if it's my coding problem or algorithm with O(ElogV) time complexity.

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

Problem G can be simply solved by trie with 2 keys 0 or 1.

Complexity = O(n * (30 or max(log ai))

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

Why there is a two pointers tag on Problem C?