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

Gotchas

• Must wait for ALL parent nodes to be processed before processing a given node (or else you might process it multiple (read: exponential) times)
• Some parent nodes might never be reached (i.e. sources of the topological sort). Therefore we cannot just start with the given start nodes. we must start with ALL sources, whether they have any incoming marbles or not.

Code

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());
	}
}

Solution - C++

#include <stdio.h>
#include <queue>

using namespace std;

typedef struct node
{
    long long int value;
    int leftInd, rightInd;
    int incoming;
    char letter;

    void toggle() {
        if (letter == 'R')
            letter = 'L';
        else
            letter = 'R';
    }
} nodetype;

nodetype node[500005];

int main()
{
    priority_queue<int> sortednodes;
    long long int n;
    int m, i;

    scanf (" %lld %d", &n, &m);

    for (i = 1; i <= m; i++) {
        scanf (" %c %d %d", &node[i].letter, &node[i].leftInd, &node[i].rightInd);
        node[node[i].leftInd].incoming++;
        node[node[i].rightInd].incoming++;
        node[i].value = 0;
    }

    for (i = 1; i <= m; i++)
        if (node[i].incoming == 0)
            sortednodes.push(i);

    node[1].value = n;

    while (!sortednodes.empty() && sortednodes.top() != 0) {
        int at = sortednodes.top();
        sortednodes.pop();

        //printf("DB -- %d: v %lld\n", at, node[at].value);

        long long int leftv, rightv;
        leftv = rightv = node[at].value/2;

        if (node[at].value%2 != 0) {
            //printf("Hallo %c ", node[at].letter);
            if (node[at].letter == 'L')
                leftv++;
            else if (node[at].letter == 'R')
                rightv++;
            node[at].toggle();
            //printf("%c\n", node[at].letter);
        }

        node[node[at].leftInd ].value += leftv;
        node[node[at].rightInd].value += rightv;

        node[node[at].leftInd ].incoming--;
        node[node[at].rightInd].incoming--;

        if (node[node[at].leftInd ].incoming == 0)
            sortednodes.push(node[at].leftInd);
        if (node[node[at].rightInd].incoming == 0 && node[at].rightInd != node[at].leftInd)
            sortednodes.push(node[at].rightInd);
    }


    for (i = 1; i <= m; i++)
        printf ("%c", node[i].letter);
    printf("\n");

    return 0;
}