I_love_Tanya_Romanova's blog

Invitation to HackerEarth JulyCircuits Contest
By I_love_Tanya_Romanova, 8 years ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Benny and the Universe?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You described the solution to Benny and Universal Numbers problem. :P

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Oh, sorry.

        You are about that problem. https://www.youtube.com/watch?v=UVrN_182CfA

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          I'll probably never understand why video is so popular.

          This 15minute video would require 3 minutes of reading text

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -19 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Benny and the Universe was I guess a variation of the subset sum problem.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Idea:
    dp[n][0 <= x < min_element] = minimal number which mod min_element is equal to x we can get
    So we can get number t if dp[n][t % x] <= t

    Code for details:
    https://www.hackerearth.com/submission/4486563/

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks , I finally understood it. Great solution. :D

          → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will we get to see the editorials?

→ Reply