Long Long Strings

This problem asks us whether a two series of inserts and deletes to an arbitrarily long string yield the same result string.

The string is obviously too long to generate the whole thing and simulate. Instead, we only care about the interesting points in the string where something interesting happens, and then for the rest of the ranges, how far they have been shifted.

• maintain a list of "pieces" of the string. these can either be
  • individual characters at a location
  • a range of "unknown" characters from the original string, potentially shifted some offset from their original position

Thus, for an insert operation, we find the appropriate piece of the string where the insert would occur. If it is in the middle of a range, we must split that range. We then have to increment the offset of every piece of the string which occurs later by 1, since it is shifted due to the insert.

A delete is similar. If it is an individual character, it can be removed, and the rest of the pieces shifted. If it is in a range, we have to split that range, and shift the latter half along with all further pieces to the left 1.

At the end, we compare the two lists of pieces made from the two sequences of operations for equality.

The runtime is fast enough. We are limited by 2000 operations which means we only have 2000 pieces. This makes the total runtime 4 million or so.

One implementation detail: when comparing, note that a range might be split in one part, and not in the other, even though they are identical. It may make sense to "merge" ranges to make the comparison simpler. Regardless of how it's done, there is a lot of case work.

import java.util.*;
public class g {

	static Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		thingy_holder all=new thingy_holder();
		all.populate(in);
		thingy_holder second_all=new thingy_holder();
		second_all.populate(in);
		System.out.println(all.equals(second_all)?"0":"1");
	}
}
abstract class thingy implements Comparable<thingy>{
	long curr;
	public thingy(long i) {
		curr=i;
	}
	abstract long get_size();
	public int compareTo(thingy arg0) {
		return (int) Math.signum(this.curr - arg0.curr);
	}
	abstract public Collection<? extends thingy> split(long place);
	abstract public Collection<? extends thingy> split_add(long place, char c);
	void shift(int i) {curr+=i;}
	public Collection<? extends thingy> append(thingy ceiling) {return new ArrayList<thingy>();}
	abstract public boolean combinable();
	abstract public boolean equals(thingy other);
}
class empty extends thingy {
	long size;
	long offset;
	public empty(long i, long j, long l) {
		super(i);
		offset=j;
		size=l;
	}
	long get_size() {return size;}
	public Collection<? extends thingy> split(long place) {
		ArrayList<thingy>out=new ArrayList<>();
		if(place!=curr)out.add(new empty(curr,offset,place-curr));
		if(place!=curr+size-1)out.add(new empty(place,offset-1,size-(place-curr)-1));
		return out;
	}
	public Collection<? extends thingy> split_add(long place, char c) {
		ArrayList<thingy>out=new ArrayList<>();
		if(place!=curr)out.add(new empty(curr,offset,place-curr));
		out.add(new empty(place+1,offset+1,size-(place-curr)));
		out.add(new not_empty(place,c));
		return out;
	}
	@Override
	void shift(int i) {
		offset+=i;
		super.shift(i);
	}
	@Override
	public boolean combinable() {
		return true;
	}
	public Collection<? extends thingy> append(thingy other) {
		empty bla=(empty)other;
		ArrayList<thingy>out=new ArrayList<>();
		out.add(this);
		if(bla.offset==offset&&bla.curr==curr+size) {
			size+=other.get_size();
		} else {
			out.add(other);
		}
		return out;

	}
	@Override
	public boolean equals(thingy other) {
		if (!other.combinable())return false;
		empty bla=(empty)other;
		return curr ==bla.curr&&offset==bla.offset&&size==bla.size;
	}
}
class not_empty extends thingy {
	public not_empty(long i, char l) {
		super(i);
		letter=l;
	}
	char letter;
	long get_size() {return 1;}
	public Collection<? extends thingy> split(long place) {
		return new ArrayList<thingy>();//just return nothing...since we deleted this
	}
	@Override
	public Collection<? extends thingy> split_add(long place, char c) {
		ArrayList<thingy> out=new ArrayList<>();
		out.add(new not_empty(curr+1,letter));
		out.add(new not_empty(place,c));
		return out;
	}
	@Override
	public boolean combinable() {
		return false;
	}
	@Override
	public boolean equals(thingy other) {
		if (other.combinable())return false;
		not_empty bla=(not_empty)other;
		return curr ==bla.curr&&letter==bla.letter;
	}
}
class thingy_holder {
	TreeSet<thingy> all_thingys;
	public thingy_holder() {
		all_thingys=new TreeSet<thingy>();
		all_thingys.add(new empty(1,0,100000000000L));
	}
	public void populate(Scanner in) {
		while(true) {
			String s=in.next();
			switch(s) {
			case "E":return;
			case "D":delete(in.nextLong());break;
			case "I":insert(in.nextLong(),in.next().charAt(0));break;
			}
		}
	}
	public boolean equals(thingy_holder arg0) {//Destructive! :D
		combine();
		arg0.combine();
		while(!all_thingys.isEmpty())if(!all_thingys.pollFirst().equals(arg0.all_thingys.pollFirst()))return false;
		return true;
	}
	private void combine() {
		TreeSet<thingy>copy=new TreeSet<thingy>();
		while(!all_thingys.isEmpty()) {
			thingy i=all_thingys.pollFirst();
			if(all_thingys.isEmpty()||!i.combinable()||!all_thingys.first().combinable()) {
				copy.add(i);
			}else {
				copy.addAll(i.append(all_thingys.pollFirst()));
			}
		}
		all_thingys=copy;
	}
	public void delete(long place) {
		thingy the_one = null;
		for(thingy on:all_thingys) if(on.curr+on.get_size()>place) {//find the one
			the_one=on;
			break;
		}
		all_thingys.remove(the_one);
		for(thingy on:all_thingys)if(on.curr>place)on.shift(-1);
		all_thingys.addAll(the_one.split(place));
	}
	public void insert(long place, char c) {
		thingy the_one = null;
		for(thingy on:all_thingys) if(on.curr+on.get_size()>place) {//find the one
			the_one=on;
			break;
		}
		all_thingys.remove(the_one);
		for(thingy on:all_thingys)if(on.curr>place)on.shift(1);
		all_thingys.addAll(the_one.split_add(place,c));
	}
}