Beautiful Tree — An interview question

help
, , ,
1

Beautiful Tree — An interview question

Hey guys !!

Hope you all are in good condition and enjoying the lock down :wink:

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.

1 Like
2

Do a Euler tour on tree and to answer the range queries and point update you can use segment tree.

3

They ask range data structures in interviews? Damn :no_mouth:

1 Like
4

:flushed: Interview questions are tougher than expected. Even linked list and binary tree questions are tough(atleast for me). They are all standard but tough.

3 Likes
5

This was the question asked in the recent codenation test .

1 Like
6

Assume you can get i^{th} beautiful number in O(1) time, then the question becomes easy.
Just flatten the tree with DFS (euler tour) and perform point updates and answer range sum queries, which can be done with fenwick or segment tree.
How to find the i^{th} beautiful number in O(1), we can just preprocess the f array and calculate all vaues upto 5*10^5.

    using pii = pair<int, int>;
    const int N = 5e5 + 10;
    const int mod = 998244353;
    vector<int> f;
    void beautiful() {
        f.resize(N);
        queue<pii> q;
        q.push({0, 0});
        int sz = 0;
        while (sz < N) {
            pii v = q.front(); q.pop();
            f[sz++] = v.first;
            for (int i = 0; i < 10; i++) {
                int num = v.first, sum = v.second;
                if (i == 0 && num == 0) continue;
                sum += i * i, num = (num * 10 + i) % mod;
                if (sum <= x) q.push({num, sum});
            }
        }
    }
2 Likes
7

Check this: Codenation Interview Question — Help Needed - Codeforces

1 Like
8

I think you might be stuck on the beautiful number part…but if you would have solved the lucky number problems(numbers containing 4 and 7) on codeforces then finding the beautiful number has the same algorithm(generating all numbers using brute force)…
If it was the update/query part then you should practice problems on dfs tour…you can find many problems on cc/cf under this tag…

2 Likes