Digi Comp II

Introduction

This problem asks you to simulate moving 10^18 items through a graph (500,000 nodes), where each node has a "next" state which changes whenever an item passes through

Solutions

Brute Force

Idea

Simulate passing every ball through the graph

Runtime

• number of balls * number of nodes = 5 * 10^23

Simulate Nodes in order

Idea

• There are no loops in the graph, so the balls will reach the nodes in topological sort order.
• We only need to determine final node states, and node state only depends on number of balls that passed through the switch
• Take nodes in topo-sort order
• using the node start state, figure out how many balls will go to each successive state (somewhere around n/2)
• Final node state is same if number is even (n%2==0) or different if odd (n%2==1)

Runtime

• topological sort + simulation
• n + n = 1,000,000

It is important to realize that our runtime CANNOT! include the number of balls....10^18 WAY too big

Solution - Java

import java.util.*;
public class d {
Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new d().go();
	}
	private void go() {
		long n=in.nextLong();
		int m=in.nextInt();
		long[][] d=new long[m+1][5];//state,L,R,incoming balls,incoming edges
		for(int i=1;i<m+1;i++){
			d[i][0]=in.next().equals("L")?0:1;
			d[i][1]=in.nextInt();
			d[i][2]=in.nextInt();
			d[(int) d[i][1]][4]++;
			d[(int) d[i][2]][4]++;
		}
		d[0][4]=Long.MAX_VALUE;
		d[1][3]=n;
		Queue<Integer> q=new LinkedList<Integer>();
		for(int i=0;i<m+1;i++)if(d[i][4]==0)q.offer(i);
		while(!q.isEmpty()){
			int on=q.poll();
			d[(int)d[on][(int)(d[on][0])+1]][3]+=d[on][3]/2+d[on][3]%2;//add to first
			d[(int)d[on][(int)((d[on][0]+1)%2)+1]][3]+=d[on][3]/2;//add to second
			if(d[on][3]%2==1)d[on][0]=(d[on][0]+1)%2;//flip switch
			d[(int) d[on][1]][4]--;//decrement incoming counts
			if(d[(int) d[on][1]][4]==0)q.offer((int) d[on][1]);
			d[(int) d[on][2]][4]--;
			if(d[(int) d[on][2]][4]==0)q.offer((int) d[on][2]);
		}
		StringBuilder sb=new StringBuilder("");
		for(int i=1;i<m+1;i++)sb.append(d[i][0]==0?"L":"R");
		System.out.println(sb.toString());
	}
}