Hello Codeforces Community!
I invite you all to take part in HackerEarth's October Easy contest, scheduled on the 1st of October 2017 at 22:00 IST.
Problems have been set by me and tested by paradox1. We are very grateful to HackerEarth admin r3gz3n for his help. :)
You will be given 6 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 5 beginners.
Good luck and have fun! :D
UPD: Contest has started.
UPD: Contest has ended. Editorials are out. Congratulations to the top 5!
1. I_love_Tanya_Romanova
2. chemthan
3. shubhamgoyal__
4. akulsareen
5. Trans
Hoping servers don't crash this time :P
That makes two of us.
Where are the prizes for top 5 beginners announced?
Contest will start in roughly 100 minutes.
Auto comment: topic has been updated by satyaki3794 (previous revision, new revision, compare).
What is the definition of beginner? Contest's description says "(1st year or 2nd year)", but I don't know what does that mean.
May be there is something wrong. My friend Trans took place 5 in the contest, he's new to hackerearth so he just updated his profile.
Yeah, I corrected the list of winners. Thanks for pointing it out. :)
A note on the last problem. Through the course of the contest, I came to know of multiple solutions to it and I am just listing them out.
1. Inclusion-exclusion principle using DSUs, as explained in the editorial and used by the tester(see the tester solution in the editorial)
2. Centroid decomposition with bitmasks to represent the "seen" gift types, used by me (see the author solution in the editorial)
3. DP on trees, using bitwise-OR transform to speed up merging of subtrees, used by akulsareen in his submission
Can you please explain approach 3.
I will give a rough overview of the solution. Let M = 2^m. You run a DFS over the tree. Each DFS call returns a polynomial of degree 2^M-1, in which the coefficient of x^i is the number of vertices v in the subtree of the current vertex u such that the path from u to v has bitmask i (bitmask is used to represent the set of "seen" gift types).
Now, you need to handle the number of paths such that the LCA of the endpoints of those paths is u. Notice that, if you take a path from u having bitmask i and another path from u having bitmask j, the bitmask of the path joining them is i OR j (simply the union of the two sets).
Now, let u have children c1, c2,...., ck. You have a polynomial for each of them. Let the polynomials be P1, P2,...., Pk respectively. You need the polynomial
P1*P2 + (P1+P2)*P3 + (P1+P2+P3)*P4 + ..... + (P1+P2+...P(k-1))*Pk.
There are k polynomial multiplications. The coefficients in the resulting polynomial give the number of paths passing through this vertex u.
Each polynomial multiplication is done in O(M * logM). Overall time complexity is O(N * M * logM).
In question Mancunian and Twin Permutations, Author solution uses persistent segment tree for online solution. Is it solvable by Mo's Sqrt Decomposition(offline solution)? Any suggestions!
Author solution uses persistent segment tree for offline solutionPersistent segment tree is used for online solution , not offline.
You can also use a merge sort tree for online solutions. (Queries are log^2(N) though)
Is it solvable by Mo's Sqrt Decomposition?If you use BIT along with MO's, then yes.
But you can just do a linear traversal if you're using BIT.(As mentioned in the editorial)