### I_love_Tanya_Romanova's blog

By I_love_Tanya_Romanova, 3 years ago, ,

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) :

1. $100 Amazon gift card + HE t-shirt. 2.$75 Amazon gift card + HE t-shirt.
3. \$50 Amazon gift card + HE t-shirt.
4. HE t-shirt.
5. HE t-shirt.

Upd. Contest has ended, congratulations to winners:

1) mugurelionut

2) ceilks

3) rox

4) Sudhanshu Sindhu

5) jtnydv25

All solutions are public, solutions by setter and tester are also available now, all editorials have been published.

• +12

 » 3 years ago, # |   0 How to solve Benny and the Universe?
•  » » 3 years ago, # ^ |   +6 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.
•  » » » 3 years ago, # ^ |   0 You described the solution to Benny and Universal Numbers problem. :P
•  » » » » 3 years ago, # ^ |   +3 Oh, sorry.You are about that problem. https://www.youtube.com/watch?v=UVrN_182CfA
•  » » » » » 3 years ago, # ^ |   +7 I'll probably never understand why video is so popular.This 15minute video would require 3 minutes of reading text
•  » » » » » » 3 years ago, # ^ |   -19 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.
•  » » » 3 years ago, # ^ |   0 Benny and the Universe was I guess a variation of the subset sum problem.
•  » » 3 years ago, # ^ |   +3 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] <= tCode for details:https://www.hackerearth.com/submission/4486563/
•  » » » 3 years ago, # ^ |   0 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?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 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
•  » » » » » 3 years ago, # ^ |   0 Thanks , I finally understood it. Great solution. :D
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 3 years ago, # |   0 When will we get to see the editorials?