RishabhKejariwal's blog

By RishabhKejariwal, 5 years ago, In English

Hi everyone,

I would like to invite you to participate in HackerEarth's October Easy'19. The contest will start at 04:00 UTC, October 05, 2019

The problems are prepared by me, slappy , TheOneYouWant , Vivek1998299 and vamaddur and tested by Arpa. I hope you'll find the problemset to be interesting.

You will be given 6 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts) — $75, $50 and $25 Amazon gift cards respectively. In addition, there are T-shirts for the top 10.

Good luck & high ratings!

  • Vote: I like it
  • -10
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Where are the problems?

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Is it April Fool ?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Not sure if anyone else is facing the issues but I am not able to see the problems

I found the question 'Finite or Infinite' very interesting. I wrote an editorial on it here.

»
5 years ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

WTF is this man? You copied the number of chocolates problem from some hair problem and just changed the no. of hair to no. of chocolates. You didn't even bother changing the explanation of the sample from the no. of hair to the no. of chocolates. Even the copied problem statement is wrong since Alice is losing chocolates not Bob.

P.S.: I even have a link to the hair problem that I'm talking of.

EDIT: Now, they've changed the explanation.

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

    Dear Tarun, I ask you not to prejudice and listen to me for a minute.

    The problem created by RishabhKejariwal, he used "hair" in his statement. We have a grammar verification team. They decide the final statement. After they reviewed the statement, they chose to use "chocolate" instead of "hair." Unfortunately, they missed replacing all of the "hair"s to "chocolate"s.

    If you have a link, publish it.

»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Instead of complaining about no problems.
Go claim first prize ($75) for scoring full points in 0s.

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

Can someone please explain any other way to solve 'Absolute tree'? Not able to understand editorial

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

    Solved with square-root decomposition and segment tree. Divide the euler tour of the tree into sqrt size blocks and sort each block. For each block maintain a segment tree where a node [l, r] stores the minimum depth of any node in this range.

    For query of a node i, let the corresponding subtree be represented by subarray [l, r]. For partially intersecting blocks just do sqrt traversals and check if the given condition is satisfied. For fully intersecting blocks as these blocks where sorted previously, calculate two extreme indices j(let them be j1, j2) such that abs(A[i] — A[j]) >= K[i](which can be done with binary search). Now just query in the corresponding segment tree of that particular sqrt block in the range [0, j1] and [j2, sz(block) — 1].

    Complexity — O(n√nlog√n)

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    It is evident that Euler tour will be necessary in order to access subtree of each node. Say we have the Euler tour with us in a list $$$E$$$. Now say for some node $$$u$$$ the subtree is from index $$$l$$$ to $$$r$$$ in $$$E$$$. The following steps will lead to finding the solution for $$$u$$$ :
    1. Maintain a list of pairs $$$V$$$ of form $$$(A[E[idx]], Depth[E[idx]])$$$ for each $$$idx \,\epsilon\,[l,r]$$$.
    2. Sort $$$V$$$. We now have a list of subtree elements of $$$u$$$ sorted on the basis of $$$A$$$ value.
    3. Let $$$x$$$ be the rightmost position in $$$V$$$ where $$$A[x] \,\leq\,A[u]+k$$$ and $$$y$$$ be the leftmost position in $$$V$$$ where $$$A[y] \,\geq\,A[u]+k$$$. This can be done using binary search. So, $$$|A[u] - A[i]|\,\geq\, k \,\,\forall\,\, i\leq x$$$ and $$$|A[u] - A[i]|\,\geq\, k \,\,\forall\,\, i\geq y$$$.
    4. We now just need to find minimum depth $$$\,\forall\,\, i\leq x$$$ and $$$\,\forall\,\, i\geq y$$$. This can be done by creating and prefix min and suffix min array.
    Following the above steps for each node will lead to $$$O(N^{2}log(N))$$$ time complexity. So for optimisation apply $$$SQRT$$$ decomposition by dividing $$$A$$$ into $$$\sqrt{N}$$$ sized blocks, and maintaining data structures mentioned in $$$1 - 4$$$ for each block.
    Now for each subtree from $$$[l,r]$$$ processing can be done in $$$(|r - l|/\sqrt{N})log(\sqrt{N})$$$ and overall $$$O(N\sqrt{N}log(\sqrt{N}))$$$ complexity.
    Clearly this is not the most optimal solution for this problem, but it's different from the editorial as you hope for.

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

      Approaches like : these having quadratic complexity also seem to work, indicating extremely weak test cases.