dgupta0812's blog

[HELP] Beautiful Tree — An interview question
By dgupta0812, history, 4 years ago, In English

[HELP] Beautiful Tree — An interview question

Hey guys !!

Hope you all are in good condition and enjoying the lock down ;)

I recently stumbled on a question of trees and online queries and I'm unable to solve it. So I'm attaching the image containing the question. And, just in case if the image is not clear, I'm writing it in the same manner (or at least trying to) as it is in the attached image. And please don't ask for the link to the question as I don't have one.

You are given a tree with N vertices, rooted at vertex 1 (indexed from 1 to N). Each vertex has a value associated with it. The value of $$$i_{th}$$$ vertex is $$$a_i$$$. Consider $$$f_i$$$ as the $$$a_i$$$ th beautiful number.

A beautiful number is a number whose sum of squares of digits is less than or equal to X. You have to process M queries where each query can be of two types.

Type 1 -> 1 i y : update $$$a-i$$$ to y

Type 2 -> 2 i : output the sum of $$$f_i$$$ for all the nodes in the sub-tree of node i ( including node i). Since the number can be very large compute it modulo 998244353.

CONSTRAINTS :

1 <= N, M, i, $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, y <= 5*$$$10^5$$$

1 <= X <= $$$10^{10}$$$

Time Limit : 1 sec

If anyone got any ideas or know how to solve this questions in the given constraint, please do tell.

Also under what categories such questions fall ?

And it would be great help if anyone can share a bunch of resources from where beginners like me can learn and practice these type of questions.

Thank you.

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

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

answer is given here

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

    Oh I didn't knew it was from codenation.

    BTW Thanks for the link.

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

It seems like a pretty tough question

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

Which interview you have given?

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

    I haven't given any interview. One of the seniors in my college had shared these questions so that we might know what level of competitive programming needed to be done.

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

You can 'flatten' the tree into a one dimensional array using pre-order numbering so that nodes in the same subtree will appear in a consecutive subarray.

Then the problem will become queries of modifying an element and finding a sum of numbers in a subarray which can be solved using segment tree or binary indexed tree

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

    Oh !! I got it now. Thanks man.

    It would be really grateful if you can post some links from where I can learn and practice such questions.

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

Auto comment: topic has been updated by dgupta0812 (previous revision, new revision, compare).

→ Reply