likecs's blog

Invitation to Mathemagic 2017- 24 Hour contest
By likecs, 8 years ago, In English

Love solving Mathematical problems. Then get ready for some action ahead.

Computer Science Association, BITS PILANI, Pilani Campus presents you their flagship contest, "Mathemagic 2017". It is being organised as a part of our technical fest, Apogee.

Contest Link : https://www.hackerrank.com/mathemagic-bits

Start Time : 17:00 IST, 23rd March' 2017

Prizes to be Won:

First Place: INR 3000, Second Place: INR 2000, Third Place: INR 1000.

The contest consists of 10 problems of varying difficulty similar to ones available at Project Euler and Ad Infinitum contests. The problems have been set such that even beginners can attempt a few problems and even the best coders find tough job ahead at the hard ones. Although Mathematical insights and tricks would help you find the logic in the problem, programming will be your way out for the full solution. There will be 4 "TEXT" based problems where the input is provided in the question, similar to the format in Project Euler. Rest 6 problems will be programming based. The editorials of all the problems with the Setter's code will be uploaded immediately after the contest so that you may benefit from it.

The problems have been set by me. I would like to thank -Morass- for testing the problems and providing valuable feedback as well. I would also like to thank ujzwt4it and CSA juniors for their feedback as well.

To register for the contest, you just need a Hackerrank handle and then just click on the link mentioned above for registering for the contest.

I hope you enjoy the contest and Happy Coding :)

UPDATE 1: Scoring & Type Distribution will be as follows:

  • 1: Easy 20 points (Text)

  • 2: Easy 30 points (Text)

  • 3: Medium 60 points (Programming)

  • 4: Medium 60 points (Text)

  • 5: Medium 80 points (Programming)

  • 6: Hard 100 points (Text)

  • 7: Hard 120 points (Programming)

  • 8: Advanced 150 points (Programming)

  • 9: Advanced 180 points (Programming)

  • 10: Advanced 200 points (Programming)

UPDATE2 : Contest is over and editorials are out. Winners will be announced soon after plagiarism check is over.

UPDATE3: The winners of the contest are :

  1. uwi

  2. jtnydv25

  3. bayleef

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

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

time is intersecting with round 406.

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

    Contest time: Mar 23 2017, 03:30 pm GST to Mar 24 2017, 03:30 pm GST So, you have one day to solve problems and round 406 is 2 hours.

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

      Not saying i wont have any time just saying it does intersect.

      And by the way time is really important in contest's ,maybe someone solved all the problems in the first 2 hours?

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

        This is unrated contest and I'm participating for myself to learn something new and practice but not for getting prize or high place in standings.

        I don't know, maybe you want prize, that's your opinion.

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

          The funny thing is that i wont participate.

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

            I don't know, maybe you want prize, that's your opinion.

            that's your opinion part contains not participating also.

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

              Why don't you try get a prize, who knows maybe you do good? you should have hope but that is my opinion.

              Lets not continue.

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

    Hi Salitanloo,

    I took your point into consideration. The contest had been made a bit longer than usual so that everyone could participate in it, irrespective of time zone. As far as your point is concerned about someone solving solving all the problems in 2 hours and getting an edge over other in overall time taken, I would like to get an vote from the community here for their opinion on these 2 options:

    1. The time starts at the start of contest, i.e. same for everyone, so people who start late are at a disadvantage.
    2. The timer start when one views the first challenge of the contest, provision is there in Hackerrank for this.

    Please share your opinion of the above 2 points and the timer can be adjusted accordingly.

    Happy coding :)

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

      Definitely not 2.
      Option 2 will just encourage people to cheat which will ruin everyone's experience.

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

        Thanks for your opinion and seeing the number of upvotes you got, the final rules for tie-breaking are as follows:

        1. A participant’s score depends on the number of test cases a participant’s code submission successfully passes. The strength of each test case in the problem will vary.

        2. Participants are ranked by score. If two or more participants achieve the same score, then the tie is broken by the total time taken for submitting the last correct code submission, where time is calculated from the start of the contest, (1700 hrs IST).

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

          There will be just 1 test case for "TEXT" problems, yes?

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

            Yes, the text based will have 1 test case only, that too provided in the problem itself. Sample test case explaining the problem will also be given along with solution, but you do not need to write anything about sample test case output in while submitting your answer.

            → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Contest starts in 45 minutes.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Contest starts in 5 minutes.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Contest has started. Questions are live now.

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

With just an hour into contest uwi is leading with 6 problems solved.

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

Any comments about the quality of problemset & testcases, clarity of question etc is welcomed.

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

    That reminds me Ad Infinitum in its best years. Great job, likecs!

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

      I had the same impression as you.

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

I liked most of the questions, but there were some minor things that I didn't like.

Array Shuffling — with current limits (and knowing it's a math contest) I thought that the simple cycle finding will timeout. I got to the multiplicative order in the following way:

Notice that the permutation is (i->2*i if i<n) and (2*(i-n)+1 if i>=n). We know that 2n-1->2n-1, so we omit it and we get permutation i->(2i mod 2n-1) for all i.

I believe that the question would be better with either lower limits (t*n ~ 5*10^7 seemed to be too long) or higher limits (my solution works in O(sqrt(n)) for a single testcase).

Degree-Diameter on Trees — I believe there is an easier way of finding the final formulas, without using progressions. I really liked this problem until I found out that the final progression needs division by L-2 (I didn't know the trick with summation). Was the non-prime modulus really necessary?

Complicated Calculations — I got to the final formula but didn't know how to calculate n!. Again, the (in my opinion) unnecessarily high constraints spoil a good math task with a complicated implementation. If I wanted to require a nice (but still not trivial) implementation trick, I would ask for the result modulo a smaller prime.

GCD rules again — again I think the math part was beautiful (and I was shocked after I got to the end) but I didn't know how to implement it due to high constraints.

Overall, I think that some problems were too complicated on the programming side. I would understand that if there was a passing solution that didn't solve the math part, but I can't see any. Lowering the constraints (or asking to solve input locally) seems reasonable to me.

I wish the contest was longer. I didn't have enough time yesterday and maybe I would come up with implementation of these described. The remaining problems seem nice too, I wish I had more time to try them.

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

    Thank you for the reply.

    Degree-Diameter on Trees: You can refer to the editorial for finding Geometric summation modulo any number here. There are many other approaches also to do the same, but the above one is the simplest one, I guess.

    GCD rules again: Yes, earlier the constraints were lower. But after doing project euler seriously for some days, i found out this thread on problem 10 which used me to increase the constraints as well. Though, some solutions used this technique, some still used hard coded values for ranges and got the code accepted.

    I will keep in mind regarding too many tasks requiring complicated codes in the future. Also, regarding time limits, I had set the time limit for every problem atleast 6-7 times than my intended solution, so that no fast input I/O or mod optimisations were required.

    Just, the second last problem, Coloring Distorted Matrix had a strict time limit according to me, as my solution passed in 1.2 sec and overall time limit was 4 sec, when the code required FFT. So, bad implementations of FFT failed and people tried ways to make it faster or doing naive multiplication for small cases. For this, I asked hackerrank team regarding increase of time limits, but there was bottleneck of 4 sec. Lowering the constraints, I felt it might allow some brute solutions with optimisations to pass.

    Lastly, regarding adding more problems with heavy implementations to be computed locally had the issues with corner cases being directly visible and no plagiarism check can be done on them. So, "TEXT" based problems, though some having some nice ideas were kept for lower weightage.

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

      Degree-Diameter on Trees — Thanks for the link. That's a nice trick indeed. Now I understand why you wanted to include this complication. I have skipped the task after seeing division modulo non-prime number. That's a pity I didn't think more about that.

      I can't view the project euler thread. From what I remember, these were unlocked only after solving a task. The editorial also contains this link, you might want to change that.

      After looking at the scoreboard now, I see I have forgotten that there is partial scoring on hackerrank. I think that the nice versus complicated issue can be solved by stating explicitly that I can get e.g. 50% for solving the lower constraint version (but still high enough that I need the math part). Most of my dissatisfaction comes from the fact that I solved some nice math problems but got 0 points for them. I would be happy with 50% for lower constraint version and I can only blame myself for forgetting about the partial scoring.

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

        I have uploaded the image of the thread from project euler in the editorial section.

        → Reply