Hi everyone!
I would like to invite you to participate in February Clash at HackerEarth. The contest is scheduled to start at February 11, 1200 hrs IST. The contest will last for 24 hours so everyone should be able to find some time to comfortably participate.
There will be six tasks in the problemset. Five of them are standard algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the last task is an approximate problem — your score for this task depends on how good your solution is compared to the current best solution.
flatline, pkacprzak, Sokolov, r3gz3n and Abhinav Gupta are the authors of this problemset. All the testing was done by me, akulsareen
I hope that everyone from beginners to experienced contestants will be able to find some problem that challenges and interests them. In case you find all problems too easy there is always the approximate challenge to tackle.
As always, belowthebelt was a great help, and I would like to thank him for taking care of all the technical aspects of contest preparation.
While problem solving is rewarding enough on its own, there will be some added incentive for you to do well.
Top5 of leaderboard will receive some nice prizes:
$100 Amazon gift card + HackerEarth T-shirt
$75 Amazon gift card + HackerEarth T-shirt
$50 Amazon gift card + HackerEarth T-shirt
HackerEarth T-shirt
HackerEarth T-shirt
Good luck to everyone — hope to see you at the top of the leaderboard.
UPD: Contest is now over.
How to solve Sonya and Sticks? In the editorial I can only find the code but not explanation.
The editorial will be written by Sokolov and should be uploaded soon.
Added the editorial. Feel free to discuss it and ask questions.
thanks for detailed explanation.
This link gives a brief explanation of the solution. http://discuss.spoj.com/t/dominoes/2491/2
I couldnt get that explanation
After the contest began I was informed that the problem Sonya and Sticks already existed on SPOJ. I want to apologise to anyone who feels they were affected by my oversight.
I am also sorry that the leaderboard was not functioning properly w.r.t the approximate problem for most of the contest. Something about a minimisation problem with negative scores seemed to break something on the site.
I just read the editorial for tree coprime queries. At the end it mentions "Another solution is to maintain an array P(v,r) which stores the number of nodes on the path from the root to r with values x such that v|x. Updates on which can be handled using a Fenwick Tree". Wont the array P require 10^5*5000 memory?
Note that there are approximately 3000 square free numbers less than 5000. Now you can't store the entire array P in memory, but what you can do is consider the square free numbers in blocks of 300. Memory in that case will be ~120 MB.
What I mean by considering them in blocks is, first you run the algorithm but only store and compute for the first 300 square free numbers, then for the next 300 and so on. But note that this will make the solution 10 times slower, so instead of 300 we can choose the block size to be around 600.
I will update the editorial so it mentions this.
Ok..got it. Also can we linearise the tree using hld and then apply square root decompostion? I saw a solution that linearised the tree using mo's on tree and then used square root decomposition.(instead of mo's with updates.)
Correct me if I am wrong, but I think this solution linearises the tree using HLD, and then uses Square Root Decomposition.
https://www.hackerearth.com/problem/algorithm/little-shino-and-equation/ how to solve this ,i checked some accepted solution they have used extended euclidean algorithm but didn't figure how they r minimizing the number of steps with it or explain any other solution for this problem thank you :)
We can minimize the number of steps using ternary search.
how,can you share your solution with elaboration?
we need to solve the equation ax+by=d where x,y can be negative also and minimise abs(x)+abs(y).Using extended euclidean theorem find any one solution and then write the general solution using that.Then notice that ternary search would be applicable.
I did it without ternary search. I first found the general soln and then to minimize abs(x) + abs(y) I made three cases: a) Both +ve b)x -ve c) y -ve. Both together cant be -ve. THEN i found min of those.https://www.hackerearth.com/submission/7200353/ .can someone tell how to solve sonya and stickz? Couldnt understand from spoj blog.
Tree and Coprime Queries and be solved in
by processing all updates and queries related to the same number offline. Instead of creating 5000 bits , we can keep just 1 bit and process all updates and queries related to this number at once and clear the bit after we are done with everything related to this number. This works pretty fast.
I was asked a few times for a detailed editorial to my problem Largest Windmill from the contest, so I've just uploaded it: https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/largest-windmill/editorial/