Hello everyone!
I want to invite you to participate in another contest at HackerEarth — this time it is India Hacks 2016.
Check out the prizes:
Maybe you already saw an announcement of Qualification Round 1 by shef_2318. In case you missed it — there will be two more qualification rounds.
Qualification Round 2 (link) will take place on January, 10 (check your timezone). Top 1000 participants from this round will qualify for the main contest.
If you like prizes on a picture above and still haven't qualified for the next round, or you would like to take part in an interesting competition against a lot of coders from all over the world, or you want to try yourself on a set of not very hard but still interesting and educative problems — this one is for you!
I am a tester of problemset which you'll face during a contest. There will be 5 problems with partial scoring system (you get points for every test which you passed), and you'll have 3 hours to solve them. Thanks to RomaWhite, Baba, subway, kunal93, harshil for preparing problems and to belowthebelt for providing technical help with contest preparation.
Good luck and have fun! Hope to see you in standings :)
UPD. Contest has ended! Congratulations to anta on being fastest to solve all 5 problems, and to 24 other contestants who also managed to get full score. Best luck in next round to all those who qualified to next round, and for all those who didn't get into top1000 — you'll still have one more chance in Qualification Round 3.
Thanks to everyone for participating! Solutions and editorials are public now; feel free to discuss problems.
India l0l h4x.
For all the effort to make "hacker" mean something like skilled programmer, I can only see it in a memetic way.
How to solve the last problem.
Greedy. You always pick the smallest number which can't be written as a
sumproduct of at most (since the first number is 1) K previous ones and isn't forbidden.Product
at most? why not exactly?
Because the first such number is 1, and see definition of a tuple.
Damnit!
Because you have taken 1 and you can mutiply your number to 1 as many times as you want.
Can we repeat the numbers??
Yes.
How did you implement this?
Both short editorial and codes by setter/tester/contestants are available already.
First of all, it's sufficient to consider K ≤ 20 and all numbers ≤ 5·105. (discovered empirically)
I made a table of which numbers can be created as products of 0..K already used numbers and when choosing x as the next number, updated all entries in the table for multiples of x. Complexity:
.
Let me guess
The limit to get 4*10^4 primes, with the formula number of primes from 1 to n ~ n/log n.
Any other logic?
Nice contest. For my knowledge of programming the tasks were enough good and interesting !
Also, after this contest I realized that I must spend much more time in solving task, instead of inventing them :)
I spend around 1h and 20 minutes in trying to find bug in the second problem and it was wrong way for output ( I wrote maximum area and then minimum ).
Whether bad programmers like me can expect some present like t-shirt for unexpected success and placing in top 50-100 at the final round ?
Who else thinks third problem is harder than last?
Just in case — problems weren't sorted by their difficulty :)
Third has way too much submissions compared to its trickiness. Most probably because of partial scoring.
I was able to get 50pts just with the bruteforce solution
There is no notification regarding people advancing to the next round.
The results of all three qualifier rounds of Algorithms track will be announced on 24th of this month. You can check the status of your selection then. We need to run plagiarism tests etc., before we come up with the final list.