NAACDI's blog

By NAACDI, history, 7 weeks ago, In English

Given a weighted undirected graph with N nodes and N-1 edges, we are also given S special nodes. For each special node, there is a convoy that is sent to the furthest node for each Si (if there are ties, the ending node is chosen at random). We are asked to find the maximum number of convoys that can't reach their target nodes if we remove one node from the graph and the number of ways to achieve this.

Example:

N = 4
0 1 3
1 2 10
1 3 11
S = 3
0 2 3
Ans: 3 1

We have 3 convoys({0 -> 3}, {2 -> 3}, {3 -> 2}), each of the convoys passes through node 1, so if we remove this node we have 3 convoys that can't get to their ending node, and the number of ways to do this is 1.

Read more »

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

By NAACDI, history, 3 months ago, In English

We are given a tree with n nodes. Also at every node, we are given some numbers. We will process q queries, for each query we will be given 4 numbers, the type of the query(addition or subtraction, 1 — addition, 2 — subtraction), the starting node(we go up from this node), the size of the path(tells us at which ancestor of the starting node we finish), and some number p. The addition or subtraction for each node involved in the query will follow the Fibonacci sequence. Let's say x is the starting node, and up[x] is the ancestor of x, then the updates will go as follows: increase/decrease x by 1 * p, increase/decrease up[x] by 1 * p, increase/decrease up[up[x]] by 2 * p, increase/decrease up[up[up[x]]] by 3 *p, increase/decrease up[up[up[up[x]]]] by 5 * p... until we update all nodes on the path from x to the nth ancestor of x(where n is the length of the path). And for each query, we have to tell whether or not every number in the tree is equal to 0.

Constraints: n <= 200000 and q <= 100000
Ex: n = 6, q = 5, mod = 7
1 2
2 3
3 4
2 5
5 6
-2 -3 -1 3 1 1
1 3 3 4 - we increase the number at nodes 3, 2, and 1 (the array is 6, 1, 3, 3, 1, 1)
2 6 3 2 - we decrease the number at nodes 6, 5, and 2 (the array is 6, -3, 3, 3, -1, -1)
2 4 4 3 - we decrease the number at nodes 4, 3, 2, and 1 (the array is -3, -2 (-9 mod 7), 0, 0, -1, -1)
1 6 4 1 - we increase the number at nodes 6, 5, 2, and 1 (the array is 0, 0, 0, 0, 0, 0)
2 2 2 1 - we decrease the number at nodes 2 and 1 (the array is  -1, -1, 0, 0, 0, 0)
Answer:
0
0
0
1
0

For partial points, for each update, I run bfs from starting node going up, updating the values, and checking if they are all zero, for full points i guess we need O(n log n) or O(n).

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By NAACDI, history, 3 months ago, In English

Given an array of size n, with elements between 1 and n find the maximum number of elements that occur exactly twice in any subarray. Constraints (1 <= n <= 100000)

6
1 3 1 3 2 1
Output: 2 (subarray 1-4, 1-5)

12
5 5 1 3 9 9 9 1 3 5 2 1
Output: 3 (subarray 1-9, 2-10, 2-11)

I have partial points, running O(n^2) solution shown below.

        int ans = 0;
	for(int i = 0; i < n; i++){
		map<int,int> cnt;
		int cans = 0;
		for(int j = i; j < n; j++){
			cnt[arr[j]]++;
			if(cnt[arr[j]] == 2)
				cans++;
			else if(cnt[arr[j]] == 3)
				cans--;
				
			ans = max(ans, cans);
		}
	}
	cout<<ans<<endl;

Any ideas how to solve the problem in O(n log n).

Read more »

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