theweirdki9's blog

Google OA | [SWE Summer Intern 2025]
By theweirdki9, history, 5 weeks ago, In English

I had this problem in my Google Summer Intern On campus OA which I was not able to solve even till today.

problem description:-

Prime Tree You are given an undirected Tree T consisting of Nodes N rooted at node 1. You have to assign value to each node of the tree such that: - The assigned value must be prime number less than or equal to 100. - The sum of values assigned to any pair of adjacent nodes must not be a prime number.

Give the Number of valid assignments. (MOD the answer with 1e9+7)

My Approach:- - We know that besides 2 all prime Numbers are odd. and sum of 2 odd Numbers is always even, which means that they can not be prime. - If we take Number '2' out of the question than all permutations are valid. - In the case we consider '2', we know that if the other number be 7. then 2 + 7 = 9 which is not a prime. so there are some finite numbers which on adding with 2 gives None prime AND, some other finite numbers (like 3, 2+3 = 5) which give prime.

NOW, my idea is to place 2 at all nodes one by one (something like rerooting) and place its neighbours to be numbers that yield NON-PRIME.

I don't know if it's right or not, also I couldn't Implement it by myself.

Tags dp, tree
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

You can solve it using DP on tree. Let $$$A$$$ be the set of odd primes which on adding $$$2$$$ again give a prime, and let $$$B$$$ be the set of odd primes which on adding $$$2$$$ become non prime. Let their sizes be $$$a$$$ and $$$b$$$ respectively.

Let $$$dp_{i,k} (1\leq i\leq n, 0\leq k\leq 2)$$$ denote the answer for subtree of $$$i$$$ where:

$$$dp_{i,0}$$$ represents when $$$i$$$ th node is $$$2$$$

$$$dp_{i,1}$$$ represents when $$$i$$$ th node belongs to $$$A$$$

$$$dp_{i,2}$$$ represents when $$$i$$$ th node belogns to $$$B$$$

Then, the transitions are simple:

$$$dp_{v,0} = \sum_{u \in child(v)}dp_{u,0}+dp_{u,2}$$$

$$$dp_{v,1} = a\cdot (\sum_{u \in child(v)}dp_{u,1}+dp_{u,2})$$$

$$$dp_{v,2} = b\cdot (\sum_{u \in child(v)}dp_{u,0}+dp_{u,1}+dp_{u,2})$$$

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

    thanks for the quick reply, this seems correct

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

    I think instead of sum ( ∑ ) it should be multiplication ( ∏ )operation as all the subtrees are totally independent .

    → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it could be solved easily using some combinatorics. Let's divide the solution into two parts first, 2 has not been assigned to any node in the tree and second the tree has 2 assigned to some node. For the first part if $$$p$$$ is the number of primes less than 100 then the number of solutions are $$$n!*{{p-1}\choose{n}}$$$.

Second part can be calculated by taking adjacency into account. For each node fix the current node as 2. The neighboring nodes can be assigned all numbers which pairs with 2 and has pair-wise sum as non-prime (let' say $$$m$$$ is the count of all such primes), then $$$\Sigma{{m\choose{adj}} * adj! * {{p - adj - 1}\choose{n - adj - 1}} * (n - adj - 1)!}$$$ for all nodes.

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

    this was exactly my first thought, but I suck at combinatorics and couldn't do it

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

    The values assigned to the node need not necessarily be distinct right? Why $$$p-1\choose n$$$ then?

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you give me some advice on how to get the Google summer intern OA? I haven't got one

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had got the same question ,tried solving it using combinatorics but couldn't solve it.

→ Reply