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
Problem Testers
Please try all problems, Editorials will be available at the end of contest.
GL&HF
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
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).
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 :(
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 :)
Gentle reminder, contest has started !!!!
interesting problems. though i could solve only the first two :|
What was the benefit of having "caterpillar" restriction at last problem?
I originally had thought problem that way, so I missed this part.
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?
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
Thank you :)
Nice solution, I somehow forgot about existence of spanning trees :)
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.
@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.
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.
Sure, I will do that.
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.
WOW, I didn't notice it!
Any Similar Questions as the 4th one?
Codeforces 91C