dyps's blog

[HackerRank] 101 Hack 23rd Edition
By dyps, 10 years ago, In English

Hello Coders,

The 23rd edition of 101 Hack is here. This time we have 5 interesting challenges lined up for you.
The contest commences on 27th March 2015 at 16:30 UTC, and will run for 2 hours. You can sign up for the contest here.

The problem statements will be available in English, Russian and Chinese.

Top 10 on leaderboard get cool HackerRank T Shirts

Problem Setters

PraveenDhinwa

Problem Testers

wanbo

Please try all problems, Editorials will be available at the end of contest.

GL&HF

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

»
10 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Btw if somebody is thinking that this is continuous third round of devu, then he is wrong. Please note the difference of "too" in the handle :P

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Btw characters of problems will be Chihiro from animated film Spirited Away (referred as magical girl in the problem statement, I think one of scenes of the movie will reflect in your mind after reading first problem statement :) ) and Devu (Devendra Agarwal (devu).

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

    This movie got some award and all, but I saw the movie once several years ago and didn't really find it interesting. Maybe I didn't understand the film :(

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

      xorfire, I really loved this movie =D I am not a regular movie and anime viewer, so my knowledge of movies is too less to comment, but I found this movie quite good :)

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gentle reminder, contest has started !!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

interesting problems. though i could solve only the first two :|

→ Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

What was the benefit of having "caterpillar" restriction at last problem?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I originally had thought problem that way, so I missed this part.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

In the 4-th problem my initial solution was the following: for each edge find some cycle and say that its sum is 0. Then do gauss elimination modulo 2. It got wrong answer on some cases.

Fortunately, it passed then I consider up to 10 cycles for each edge and add them all to the matrix.

Do anyone know, what the difference is?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Consider case of square divide to 4 squares by 4 edges. (http://ts3.mm.bing.net/th?id=HN.608048807035012494&pid=15.1&H=206&W=160) In bad case you may add only cycles consisting of 2 squares, so their xor will never be one square(If i'm not mistaken).

    In the second case you're probably just lucky.

    One of correct approaches is to get some some spanning forest and add edges consisting of 1 edge not from forest ant path from forest

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

      Thank you :)

      Nice solution, I somehow forgot about existence of spanning trees :)

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

      In fact the problem D can be done in O(m). Let basic cycles be generated by what riadwaw says. Each basic cycle contain at least one edge which don't occur in other basic cycle. So they all are independent to other basic cycles. We can just check the xor of all basic cycle whether contain all edges to know whether all edges set independent to all basic cycles or not.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it -21 Vote: I do not like it

        @dreamoon_love_AA: true, I came up with this solution last day, I did not want to change constraints for passing this solution only as it would have made problem harder.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I don't care the limit of constraint during contest.(In fact, I don't like people be constraint by the limit of constraint.) But I think you can add this method to editorial. It can make people think more.

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

        Um. The all edges set is independent of all basic cycles iff all degrees in the graph are even; that is due to the fact all elements of cycle space are exactly the Eulerian subgraphs.

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any Similar Questions as the 4th one?

→ Reply