Hello everyone!
I would like to invite you to participate in another HackerEarth contest. This time it is HackerEarth July Circuits. It's a long contest that will start on July, 16 21:00 IST (check your timezone). Contest will run for 8 days.
The problemset consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.
I'm a tester of a problemset you'll have to work on — thanks to r3gz3n, pkacprzak, Yury_Bandarchuk, magieNoire.
Tasks should not be very hard for top-level contestants, and I expect them to get full score on classic part of a problemset. However, even if you solved everything — you'll still have to do your best on approximate problem :)
As usually, there will be some nice prizes for those who'll reach top spots, here are prizes for top5 (in case you haven't open contest page) :
- $100 Amazon gift card + HE t-shirt.
- $75 Amazon gift card + HE t-shirt.
- $50 Amazon gift card + HE t-shirt.
- HE t-shirt.
- HE t-shirt.
Upd. Contest has ended, congratulations to winners:
1) mugurelionut
2) ceilks
3) Rox
5) jtnydv25
All solutions are public, solutions by setter and tester are also available now, all editorials have been published.
How to solve Benny and the Universe?
Let's do bruteforce. There 9 variants for first digit, 10/2 variants for second, 10/3 for third etc.
Our bruteforce will find all possible numbers in time 9·5·4·3·25 = 11520 (multyplying by some small constant). Then we sort them and answer queries using two lowerbounds.
You described the solution to Benny and Universal Numbers problem. :P
Oh, sorry.
You are about that problem. https://www.youtube.com/watch?v=UVrN_182CfA
I'll probably never understand why video is so popular.
This 15minute video would require 3 minutes of reading text
Yes, you probably never would. As for me, I can't understand why it has only ~200 views which is like 30 times smaller than codeforces audience.
Benny and the Universe was I guess a variation of the subset sum problem.
Idea:
dp[n][0 <= x < min_element] = minimal number which mod min_element is equal to x we can getSo we can get number t if dp[n][t % x] <= t
Code for details:
https://www.hackerearth.com/submission/4486563/
What I don't understand is this problem can essentially be reduced to : determine if sum S can be made using some number of coins with values V[i]. How can we solve this subset sum problem in O(N*x). Could you please prove why your solution is correct?
Hm, what exactly you want me to prove? We use that if we can get number x we can get x + c * dmin for any c
Thanks , I finally understood it. Great solution. :D
I will try explaining what i implemented. The key point was that the smallest number(satellite id) had to be <= 10000. Using this fact we can create an array where for each index in the array we fill the smallest value that is achievable which gives same remainder on dividing by the smallest number as the index.
For instance let's say we have numbers 5,6,7(as in sample) Our array of 5 elements would look like[5,6,7,13,14] These are the smallest values which on dividing by 5(the smallest number) give the remainder equal to their index.Once we have constructed this array for each query we simply find its remainder on dividing by 5 and compare the value with respective index in array.If its >= the array value we can get it by adding requisite number of fives else we can't achieve that value. So the only task at hand is to create the desired array details of which are mentioned below.
Here is the solution I implemented.
Another similar problem from a CF round.
A really cool approach is mentioned in the link given by Um_nik.
When will we get to see the editorials?