🌍 Tree of Space — Hackathon Problem Statement

Difficulty: Hard | Category: Trees, Data Structures, Concurrency This is the actual Juspay Hackathon problem (Part A & Part B), reconstructed with full constraints, edge cases, and test cases.

📖 Background

You are given a world map modeled as a Generic Balanced M-ary Tree with N nodes. Each node represents a geographic region. You must build a lock management system on this tree that supports three operations: Lock, Unlock, and UpgradeLock.

The tree is given in level-order (BFS order) — the root is the first node, followed by its children left to right, then their children left to right, and so on. Each internal node has at most M children.

📥 Input Format

N M Q
node_1 node_2 node_3 ... node_N
type_1 node_name_1 uid_1
type_2 node_name_2 uid_2
...
type_Q node_name_Q uid_Q

Line 1: Three integers N (nodes), M (max children per node), Q (queries)
Line 2: N space-separated unique strings — node names in level-order (BFS)
Next Q lines: Each query has:
- type : 1 = Lock, 2 = Unlock, 3 = UpgradeLock
- node_name : Name of the target node (guaranteed to exist)
- uid : Integer user ID

📤 Output Format

For each of the Q queries, print true or false on a new line.

🔒 Part A — Lock and Unlock

Operations

1. Lock(X, uid) → type `1`

Lock node X for user uid, granting exclusive access to the entire subtree rooted at X.

Returns true if ALL of the following hold:

Node X is not already locked (by any user)
No ancestor of X is locked (by any user)
No descendant of X is locked (by any user)

Returns false otherwise.

If successful, node X is marked as locked by uid.

2. Unlock(X, uid) → type `2`

Unlock node X that was locked by uid.

Returns true if ALL of the following hold:

Node X is currently locked
Node X is locked by the same uid making the request

Returns false otherwise.

If successful, node X is unlocked and is now available for future operations.

🌲 Tree Structure Visualization

For the example: N=7, M=2, nodes = [World, Asia, Africa, China, India, SouthAfrica, Egypt]

             World          ← Level 0 (index 1)
           /       \
        Asia       Africa   ← Level 1 (index 2, 3)
       /    \     /     \
    China  India SouthAfrica Egypt  ← Level 2 (index 4,5,6,7)

M-ary Index Formula (1-based):

Parent of node at index i: (i - 2) / M + 1
Children of node at index i: M*(i-1)+2 to M*(i-1)+M+1

🧪 Test Cases — Part A

Test Case A-1 (Basic Lock/Unlock)

Input:
7 2 6
World Asia Africa China India SouthAfrica Egypt
1 China 9
1 Asia 2
2 China 9
1 Asia 2
1 World 3
1 Egypt 4

Expected Output:
true
false
true
true
false
true

Explanation:

#	Operation	Result	Reason
1	Lock(China, 9)	`true`	China is free, no locked ancestors/descendants
2	Lock(Asia, 2)	`false`	China (descendant of Asia) is locked
3	Unlock(China, 9)	`true`	China is locked by uid 9 — same uid
4	Lock(Asia, 2)	`true`	Now no locked ancestors/descendants
5	Lock(World, 3)	`false`	Asia (descendant of World) is locked
6	Lock(Egypt, 4)	`true`	Egypt is free; Africa (ancestor) is not locked (Asia is locked under World, but Egypt is under Africa)

Test Case A-2 (Ancestor Check)

Input:
7 2 5
World Asia Africa China India SouthAfrica Egypt
1 World 1
1 China 2
1 Asia 3
2 World 1
1 Asia 3

Expected Output:
true
false
false
true
true

Explanation:

#	Operation	Result	Reason
1	Lock(World, 1)	`true`	Root is free
2	Lock(China, 2)	`false`	World (ancestor of China) is locked
3	Lock(Asia, 3)	`false`	World (ancestor of Asia) is locked
4	Unlock(World, 1)	`true`	World is locked by uid=1
5	Lock(Asia, 3)	`true`	World is now free

Test Case A-3 (Already Locked Node)

Input:
3 2 4
World China India
1 World 5
1 World 5
2 World 7
2 World 5

Expected Output:
true
false
false
true

Explanation:

#	Operation	Result	Reason
1	Lock(World, 5)	`true`	World is free
2	Lock(World, 5)	`false`	World is already locked
3	Unlock(World, 7)	`false`	World is locked by uid=5, not uid=7
4	Unlock(World, 5)	`true`	Correct uid

Test Case A-4 (Sibling Nodes — No Conflict)

Input:
7 2 4
World Asia Africa China India SouthAfrica Egypt
1 China 1
1 India 2
1 SouthAfrica 3
1 Egypt 4

Expected Output:
true
true
true
true

Explanation:
All four nodes are leaf siblings (or under separate branches). None are ancestors/descendants of each other, so all locks succeed independently.

Test Case A-5 (Interleaved Lock/Unlock)

Input:
10 3 8
Root A B C D E F G H I
1 D 1
1 E 2
2 D 1
1 A 3
1 E 2
2 E 2
1 A 3
2 A 3

Expected Output:
true
true
true
false
false
true
true
true

Tree structure for N=10, M=3:

Root / | \ A B C /|\ D E F

Explanation:

#	Operation	Result	Reason
1	Lock(D, 1)	`true`	D is free
2	Lock(E, 2)	`true`	E is free, D is sibling
3	Unlock(D, 1)	`true`	D locked by uid=1
4	Lock(A, 3)	`false`	E (descendant) is still locked
5	Lock(E, 2)	`false`	E is already locked
6	Unlock(E, 2)	`true`	E locked by uid=2
7	Lock(A, 3)	`true`	No locked ancestors or descendants
8	Unlock(A, 3)	`true`	A locked by uid=3

Test Case A-6 (Edge — Single Node Tree)

Input:
1 2 3
Root
1 Root 42
2 Root 42
2 Root 42

Expected Output:
true
true
false

⬆️ Part B — Upgrade Lock

New Operation

3. UpgradeLock(X, uid) → type `3`

Consolidates multiple fine-grained descendant locks into a single lock on an ancestor node X.

Returns true if ALL of the following hold:

Node X is not currently locked
No ancestor of X is locked (by any user)
X has at least one locked descendant
ALL locked descendants of X are locked by exactly the same uid — if even one is locked by a different user, the upgrade fails

If successful:

All locked descendants of X are automatically unlocked
Node X is locked by uid

Key insight: The ancestor check in Upgrade can be implicitly guaranteed if you can confirm that at least one descendant got locked successfully (because a lock can only succeed if no ancestor is locked). However, an explicit ancestor check is safer.

🧪 Test Cases — Part B

Test Case B-1 (Official Example)

Input:
7 2 5
World Asia Africa China India SouthAfrica Egypt
1 China 9
1 India 9
3 Asia 9
2 India 9
2 Asia 9

Expected Output:
true
true
true
false
true

Explanation:

#	Operation	Result	Reason
1	Lock(China, 9)	`true`	China is free
2	Lock(India, 9)	`true`	India is free, sibling of China
3	Upgrade(Asia, 9)	`true`	Asia is unlocked, descendants [China, India] both locked by uid=9. Asia gets locked; China and India are unlocked.
4	Unlock(India, 9)	`false`	India was unlocked during Upgrade
5	Unlock(Asia, 9)	`true`	Asia is now locked by uid=9

Test Case B-2 (Upgrade Fails — Mixed UIDs)

Input:
7 2 4
World Asia Africa China India SouthAfrica Egypt
1 China 1
1 India 2
3 Asia 1
3 Asia 2

Expected Output:
true
true
false
false

Explanation:

#	Operation	Result	Reason
1	Lock(China, 1)	`true`	Free
2	Lock(India, 2)	`true`	Free, sibling
3	Upgrade(Asia, 1)	`false`	India is locked by uid=2, not uid=1. Mixed UIDs → fails
4	Upgrade(Asia, 2)	`false`	China is locked by uid=1, not uid=2. Still mixed → fails

Test Case B-3 (Official Example 2)

Input:
3 2 2
World China India
3 India 1
1 World 9

Expected Output:
false
true

Explanation:

#	Operation	Result	Reason
1	Upgrade(India, 1)	`false`	India is a leaf node — it has no descendants, so there are zero locked descendants. Upgrade requires at least one.
2	Lock(World, 9)	`true`	World is free

Test Case B-4 (Upgrade then attempt to lock upgraded ancestor's ancestor)

Input:
7 2 5
World Asia Africa China India SouthAfrica Egypt
1 China 5
1 India 5
3 Asia 5
1 World 5
2 Asia 5

Expected Output:
true
true
true
false
true

Explanation:

#	Operation	Result	Reason
1	Lock(China, 5)	`true`
2	Lock(India, 5)	`true`
3	Upgrade(Asia, 5)	`true`	Asia is now locked; China, India freed
4	Lock(World, 5)	`false`	Asia (descendant of World) is now locked
5	Unlock(Asia, 5)	`true`

Test Case B-5 (Upgrade with Locked Ancestor → Fails)

Input:
7 2 5
World Asia Africa China India SouthAfrica Egypt
1 World 1
1 China 1
3 Asia 1
2 World 1
3 Asia 1

Expected Output:
true
false
false
true
false

Explanation:

#	Operation	Result	Reason
1	Lock(World, 1)	`true`	Root locked
2	Lock(China, 1)	`false`	World (ancestor) is locked
3	Upgrade(Asia, 1)	`false`	No locked descendants (China lock failed)
4	Unlock(World, 1)	`true`
5	Upgrade(Asia, 1)	`false`	Still no locked descendants

Test Case B-6 (Chained Upgrade & Descendant Checks)

Input:
7 2 4
World Asia Africa China India SouthAfrica Egypt
1 China 3
1 Asia 3
3 Asia 3
3 World 3

Expected Output:
true
false
true
true

Explanation:

#	Operation	Result	Reason
1	Lock(China, 3)	`true`	China is free, no locked ancestors/descendants.
2	Lock(Asia, 3)	`false`	Normal Lock fails because descendant China is locked.
3	Upgrade(Asia, 3)	`true`	Asia is unlocked; only descendant China is locked (by uid=3). Asia gets locked; China unlocked.
4	Upgrade(World, 3)	`true`	World is unlocked; descendant Asia is locked (by uid=3). World gets locked; Asia unlocked.

Test Case B-6b (Upgrade on Already-Locked Node Fails)

Input:
7 2 3
World Asia Africa China India SouthAfrica Egypt
1 Asia 3
3 Asia 3
3 World 3

Expected Output:
true
false
true

Explanation:

#	Operation	Result	Reason
1	Lock(Asia, 3)	`true`	Asia is free. Asia gets locked by uid=3.
2	Upgrade(Asia, 3)	`false`	Asia is already locked — Upgrade requires the target node to be unlocked.
3	Upgrade(World, 3)	`true`	World is unlocked; only descendant Asia is locked (by uid=3). World gets locked; Asia unlocked.

Test Case B-7 (Large M-ary, complex scenario)

Input:
10 3 7
Root A B C D E F G H I
1 D 7
1 E 7
1 F 7
3 A 7
1 B 9
2 Root 7
1 Root 7

Expected Output:
true
true
true
true
true
false
false

Tree: N=10, M=3 → Root has children [A,B,C], A has children [D,E,F], B has children [G,H,I]

         Root
       /  |  \
      A   B   C
    / | \ /|\
   D  E  F G H I

Explanation:

#	Operation	Result	Reason
1	Lock(D, 7)	`true`	D is free
2	Lock(E, 7)	`true`	Sibling of D
3	Lock(F, 7)	`true`	Sibling of D,E
4	Upgrade(A, 7)	`true`	A is unlocked, all descendants [D,E,F] locked by uid=7. A gets locked; D,E,F freed.
5	Lock(B, 9)	`true`	B is free — A's lock doesn't affect B
6	Unlock(Root, 7)	`false`	Root is NOT locked
7	Lock(Root, 7)	`false`	A (descendant, locked) and B (descendant, locked) block this

⚠️ Critical Edge Cases to Remember

Upgrade on leaf node → Always false (no descendants)
Upgrade on already-locked node → Always false
Lock on node with locked ancestor → false, even if no descendants locked
Unlock with wrong uid → false
After Upgrade(X), all descendants of X are unlocked — subsequent Unlock on those descendants will return false
Sibling nodes can both be locked (neither is ancestor/descendant of the other)
Upgrade checks ancestor lock — even if all descendants are by same uid, if an ancestor is locked, Upgrade fails

📊 Complexity Requirements

Operation	Time Complexity	Key Optimization
Lock	O(log_M N)	Store `lockedDescendants` set in each node; check ancestors by walking up
Unlock	O(log_M N)	Walk up to root, remove self from each ancestor's `lockedDescendants`
Upgrade	O(K · log_M N)	K = number of locked descendants; unlock each in O(log_M N)
Space	O(N)	One set per node

Why O(log_M N) for ancestor traversal?
In a balanced M-ary tree with N nodes, the height is log_M(N). Walking from any node to root = O(height) = O(log_M N).

🔧 Key Data Structures

struct TreeNode {
    string name;
    int lockedBy;           // -1 if not locked
    bool isLocked;
    vector<TreeNode*> children;
    TreeNode* parent;
    set<TreeNode*> lockedDescendants;  // CRITICAL for O(1) descendant check
};

Why lockedDescendants is the key insight:

Without it: checking descendants = O(N) BFS every time
With it: checking lockedDescendants.size() == 0 is O(1)
Maintained by calling updateParents() on every lock/unlock

📋 Summary of Constraints

Constraint	Rule
Lock a locked node	❌ false
Lock when ancestor is locked	❌ false
Lock when any descendant is locked	❌ false
Unlock an unlocked node	❌ false
Unlock with wrong uid	❌ false
Upgrade when node is locked	❌ false
Upgrade when ancestor is locked	❌ false
Upgrade with zero locked descendants	❌ false
Upgrade when any descendant locked by different uid	❌ false
Upgrade success → descendants auto-unlock	✅ yes

tree_of_space_problem.md

🌍 Tree of Space — Hackathon Problem Statement

📖 Background

📥 Input Format

📤 Output Format

🔒 Part A — Lock and Unlock

Operations

1. Lock(X, uid) → type 1

2. Unlock(X, uid) → type 2

🌲 Tree Structure Visualization

🧪 Test Cases — Part A

Test Case A-1 (Basic Lock/Unlock)

Test Case A-2 (Ancestor Check)

Test Case A-3 (Already Locked Node)

Test Case A-4 (Sibling Nodes — No Conflict)

Test Case A-5 (Interleaved Lock/Unlock)

Test Case A-6 (Edge — Single Node Tree)

⬆️ Part B — Upgrade Lock

New Operation

3. UpgradeLock(X, uid) → type 3

🧪 Test Cases — Part B

Test Case B-1 (Official Example)

Test Case B-2 (Upgrade Fails — Mixed UIDs)

Test Case B-3 (Official Example 2)

Test Case B-4 (Upgrade then attempt to lock upgraded ancestor's ancestor)

Test Case B-5 (Upgrade with Locked Ancestor → Fails)

Test Case B-6 (Chained Upgrade & Descendant Checks)

Test Case B-6b (Upgrade on Already-Locked Node Fails)

Test Case B-7 (Large M-ary, complex scenario)

⚠️ Critical Edge Cases to Remember

📊 Complexity Requirements

🔧 Key Data Structures

📋 Summary of Constraints

1. Lock(X, uid) → type `1`

2. Unlock(X, uid) → type `2`

3. UpgradeLock(X, uid) → type `3`