akulsareen's blog

February Clash 2017
By akulsareen, history, 7 years ago, In English

Hi everyone!

I would like to invite you to participate in February Clash at HackerEarth. The contest is scheduled to start at February 11, 1200 hrs IST. The contest will last for 24 hours so everyone should be able to find some time to comfortably participate.

There will be six tasks in the problemset. Five of them are standard algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the last task is an approximate problem — your score for this task depends on how good your solution is compared to the current best solution.

flatline, pkacprzak, Sokolov, r3gz3n and Abhinav Gupta are the authors of this problemset. All the testing was done by me, akulsareen

I hope that everyone from beginners to experienced contestants will be able to find some problem that challenges and interests them. In case you find all problems too easy there is always the approximate challenge to tackle.

As always, belowthebelt was a great help, and I would like to thank him for taking care of all the technical aspects of contest preparation.

While problem solving is rewarding enough on its own, there will be some added incentive for you to do well.

Top5 of leaderboard will receive some nice prizes:

  1. $100 Amazon gift card + HackerEarth T-shirt

  2. $75 Amazon gift card + HackerEarth T-shirt

  3. $50 Amazon gift card + HackerEarth T-shirt

  4. HackerEarth T-shirt

  5. HackerEarth T-shirt

Good luck to everyone — hope to see you at the top of the leaderboard.

UPD: Contest is now over.

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

Comments Comments (18)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Sonya and Sticks? In the editorial I can only find the code but not explanation.

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

After the contest began I was informed that the problem Sonya and Sticks already existed on SPOJ. I want to apologise to anyone who feels they were affected by my oversight.

I am also sorry that the leaderboard was not functioning properly w.r.t the approximate problem for most of the contest. Something about a minimisation problem with negative scores seemed to break something on the site.

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

I just read the editorial for tree coprime queries. At the end it mentions "Another solution is to maintain an array P(v,r) which stores the number of nodes on the path from the root to r with values x such that v|x. Updates on which can be handled using a Fenwick Tree". Wont the array P require 10^5*5000 memory?

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

    Note that there are approximately 3000 square free numbers less than 5000. Now you can't store the entire array P in memory, but what you can do is consider the square free numbers in blocks of 300. Memory in that case will be ~120 MB.

    What I mean by considering them in blocks is, first you run the algorithm but only store and compute for the first 300 square free numbers, then for the next 300 and so on. But note that this will make the solution 10 times slower, so instead of 300 we can choose the block size to be around 600.

    I will update the editorial so it mentions this.

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

      Ok..got it. Also can we linearise the tree using hld and then apply square root decompostion? I saw a solution that linearised the tree using mo's on tree and then used square root decomposition.(instead of mo's with updates.)

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

        Correct me if I am wrong, but I think this solution linearises the tree using HLD, and then uses Square Root Decomposition.

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

https://www.hackerearth.com/problem/algorithm/little-shino-and-equation/ how to solve this ,i checked some accepted solution they have used extended euclidean algorithm but didn't figure how they r minimizing the number of steps with it or explain any other solution for this problem thank you :)

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

    We can minimize the number of steps using ternary search.

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

      how,can you share your solution with elaboration?

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

        we need to solve the equation ax+by=d where x,y can be negative also and minimise abs(x)+abs(y).Using extended euclidean theorem find any one solution and then write the general solution using that.Then notice that ternary search would be applicable.

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

          I did it without ternary search. I first found the general soln and then to minimize abs(x) + abs(y) I made three cases: a) Both +ve b)x -ve c) y -ve. Both together cant be -ve. THEN i found min of those.https://www.hackerearth.com/submission/7200353/ .can someone tell how to solve sonya and stickz? Couldnt understand from spoj blog.

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

Tree and Coprime Queries and be solved in by processing all updates and queries related to the same number offline. Instead of creating 5000 bits , we can keep just 1 bit and process all updates and queries related to this number at once and clear the bit after we are done with everything related to this number. This works pretty fast.

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

I was asked a few times for a detailed editorial to my problem Largest Windmill from the contest, so I've just uploaded it: https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/largest-windmill/editorial/

→ Reply