sinhashubham95's blog

Invitation to February Easy'18 on Hackerearth
By sinhashubham95, 7 years ago, In English

Hello Codeforces Community!!!

I invite you all to take part in HackerEarth's February Easy contest.The contest will be held on 1st February, 2018 at 22:00 IST.

Problems have been set by me(sinhashubham95) and tested by r3gz3n and harshil.We are grateful to HackerEarth admin r3gz3n for his help.

You will be given 5 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.

This contest is themed on Naruto and dedicated to my friends rajatanand and hjjobs.

Good luck and have fun.

Update 1 : Close to 7 hours left in the contest.

Update 2 : The contest has started. All the best !!

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

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

Can someone explain 'The Great Ninja War' ?

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

In the fourth question, how are we using lazy propagation for p >1 ?

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

    Let's say we are working with the segtree responsible for pth powers. Suppose a particular node is responsible for the sections [L,R] and x is the value by which we want to increase all values of this range. Then this node already has the sum A[L]p + A[L + 1]p...A[R]p. Now we want to update it so as to become (A[L] + x)p + (A[L + 1] + x)p...(A[R] + x)p. If we open the latter expression by binomial theorem and subtract the first expression, we get the value that needs to be added to this node to account for the corresponding update. That value after some rearrangement can be written as

    We can notice that the term within sigma will already be available in same ranges in other segment trees (ie maintained for different powers) Therefore this node can be updated in at max 10 steps. Since there can be log(N) disjoint nodes and 10 segtrees to update our update complexity is around 10 * 10 * log(N)

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

For each problem, theres a well written editorial in the Editorial tab in the problem statement page. For any queries to the solution of the problem, you can refer to that.

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

    Yeah, I referred to the editorial. I can not understand the solution to the third problem. Can you elaborate on the DP states?

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

    I don't understand the significance of using the LCM.

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

      Because we don't need more information. The problem ask us to check the divisibility of the special sum for every digit of the troop number, i.e., only from 1 to 9. We don't need to check the divisibility for numbers higher than these. Thats why we only pass the sum%LCM in the state.

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

        But does 2520 help in checking whether the sum is special or not? What if, the special sum doesn't involve all the numbers from 1..9? For example, if the number is 2024. In this case, the sum will be 264, which is not divisible by 2520, even though the troop is special.

        → Reply