Page Contents
Dream and the Multiverse Solution February Challenge 2021
Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with NN nodes (numbered 11 through NN). Node 11 is the root and for each ii (1≤i≤N−11≤i≤N−1), the parent of node i+1i+1 is fifi. All edges of this tree are directed away from the root.
Then, Dream employs a magical superpower and adds MM directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).
Let’s call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events (i,j)(i,j) to be plausible if there is an era whose first event is ii and last event is jj. Note that i<ji<j does not have to hold for a plausible pair.
Dream now wants you to answer QQ queries. In each query, he gives you two positive integers ll and rr, where l≤rl≤r, and he wishes to know the number of plausible pairs of events (i,j)(i,j) such that l≤i<j≤rl≤i<j≤r.
Also See: February Long Challenge 2021 Solutions
Input
- The first line of the input contains two space-separated integers NN and MM.
- The second line contains N−1N−1 space-separated integers f1,f2,…,fN−1f1,f2,…,fN−1.
- MM lines follow. Each of these lines contains two space-separated integers uu and vv describing an additional edge from node uu to node vv.
- The following line contains a single integer QQ.
- QQ lines follow. Each of these lines contains two space-separated integers ll and rr describing a query.
Output
For each query, print a single line containing one integer ― the number of plausible pairs (i,j)(i,j) such that l≤i<j≤rl≤i<j≤r.
Constraints
- 2≤N≤3⋅1052≤N≤3⋅105
- 1≤Q≤3⋅1051≤Q≤3⋅105
- 0≤M≤200≤M≤20
- 1≤fi≤N1≤fi≤N for each valid ii
- 1≤u,v≤N1≤u,v≤N
- the graph described on the input is acyclic
- 1≤l≤r≤N1≤l≤r≤N
Subtasks
Subtask #1 (10 points): the graph is a line ― that is, M=0M=0 and there is a permutation p1,p2,…,pNp1,p2,…,pN such that p1=1p1=1 and nodes p1,p2,…,pNp1,p2,…,pN form a directed path in the tree
Subtask #2 (20 points): M=0M=0
Subtask #3 (30 points): N,Q≤2⋅105N,Q≤2⋅105
Subtask #4 (40 points): original constraints
Example Input
8 2 1 2 5 1 4 3 3 2 4 4 7 3 4 6 5 7 1 8
Example Output
2 2 18
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C++:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAX = 1e6 + 5;
typedef long long ll;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main()
{
int n,m,r;
cin>>n>>m>>r;
map<pair<int,int>, vector<int>> M;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
}
for(int i=1;i<=m;i++)
{
vector<int> PP(3);
cin>>PP[0]>>PP[1]>>PP[2];
sort(PP.begin(), PP.end());
M[{PP[0],PP[1]}].push_back(PP[2]);
M[{PP[0],PP[2]}].push_back(PP[1]);
M[{PP[1],PP[2]}].push_back(PP[0]);
}
for(int i=1;i<=r;i++)
{
int b;
cin>>b;
}
vector<pair<int,int>> Flips;
set<pair<int,int>> Poss_Lines;
for(auto m:M)
{
if(m.second.size()==2)
{
Poss_Lines.insert(m.first);
}
}
// int F = rng()%30;
cout<<"0"<<endl;
// for(int i=0;i<F;i++)
// {
// int which = rng()%Poss_Lines.size();
// int curr=0;
// for(auto f:Poss_Lines)
// {
// if(curr==which)
// {
// cout<<f.first<<" "<<f.second<<endl;
// Flips.push_back(f);
// break;
// }
// curr++;
// }
// Poss_Lines.erase(Flips.back());
// int x = M[Flips.back()][0];
// int y = M[Flips.back()][1];
// if(x>y) swap(x,y);
// M[{x,y}] = {Flips.back().first,Flips.back().second};
// Poss_Lines.insert({x,y});
// }
for(int i=0;i<m-r;i++)
{
int which = rng()%Poss_Lines.size();
int curr=0;
for(auto f:Poss_Lines)
{
if(curr==which)
{
cout<<f.first<<" "<<f.second<<endl;
Poss_Lines.erase(f);
break;
}
curr++;
}
}
}
Program Java:
/* package codechef; // don't place package name! */
import java.math.BigInteger;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class Reader
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader()
{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException
{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException
{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException
{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do
{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException
{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException
{
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (c == '.')
{
while ((c = read()) >= '0' && c <= '9')
{
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
/*----------------------------------------------------------------------------------------------
public static long mod=1000000007;
public static long power(long a, long b) {
if(b == 0)
return 1;
long answer = power(a, b/2)%mod;
answer = (answer*answer)%mod;
if(b%2!=0)
answer = (answer*a)%mod;
return answer;
}
public static long min(long a, long b) {
return a<b?a:b;
}
public static long divide(long a,long b) {
return (a%mod*(power(b, mod-2)%mod))%mod;
}
public static long nCr(long n,long r) {
long answer = 1;
long k = min(r, n-r);
for(long i=0;i<k;i++) {
answer = (answer%mod*(n-i)%mod)%mod;
answer = divide(answer, i+1);
}
return answer%mod;
}
public static boolean plaindrome(String str){
StringBuilder sb=new StringBuilder();
sb.append(str);
return (str.equals((sb.reverse()).toString()));
}
----------------------------------------------------------------------------------------------*/
static class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
//prints BFS traversal from a given source s
Boolean isReachable(int s, int d)
{
LinkedList<Integer>temp;
// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
// 'i' will be used to get all adjacent vertices of a vertex
Iterator<Integer> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
int n;
i = adj[s].listIterator();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();
// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;
// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
// If BFS is complete without visited d
return false;
}
}
public static void main (String[] args) throws java.lang.Exception
{
Reader s=new Reader();
StringBuilder sb=new StringBuilder();
int n=s.nextInt();
int m=s.nextInt();
Graph g = new Graph(n);
for(int i=1;i<n;i++){
int k=s.nextInt();
g.addEdge(i,k);
}
for(int i=0;i<m;i++){
int a=s.nextInt();
int b=s.nextInt();
g.addEdge(a,b);
}
boolean arr[][]=new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
arr[i][j]=g.isReachable(i, j);
}
}
int q=s.nextInt();
while(q-->0){
int a=s.nextInt()-1;
int b=s.nextInt()-1;
int ans=0;
for(int i=a;i<=b;i++){
for(int j=i+1;j<=b;j++){
if(arr[i][j])ans++;
}
}
System.out.println(ans);
}
}
}
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef