Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Codeforces Marathon veeroute 2019
// #undef DEBUG
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Diagnostics;
namespace Solver
{
class MainClass
{
const int SUMMON_COST = 240;
const int MAX_TIME = 14000;
static Random random = new Random ();
public static void Main (string[] args)
{
Board board = new Board ();
Solution solution = new Solution (board);
string result = solution.Solve ();
#if !DEBUG
Console.Write (result);
#endif
}
class Solution
{
public Board Board;
public List<Worker> Workers;
public Solution (Board board)
{
this.Board = board;
}
public string Solve ()
{
Stopwatch sw = Stopwatch.StartNew ();
JobPackage.Base = Board.Base;
Worker.Base = Board.Base;
List<JobPackage> packages = Board.Jobs.Select (j => new JobPackage (new Job (j))).ToList ();
List<JobPackage> pack4plus = packages.Where (p => p.Workers >= 4).ToList ();
pack4plus = MergePackages (pack4plus, 2);
List<Job> job4plus = pack4plus.SelectMany (p => p.Jobs).ToList ();
foreach (JobPackage p in pack4plus) {
p.Workers -= 4;
foreach (Job j in p.Jobs)
j.Workers -= 4;
}
packages = packages.Where (p => p.Workers < 4).Union (pack4plus.Where (p => p.Workers > 0)).ToList ();
packages = MergePackages (packages, 20);
job4plus.ForEach (j => j.Workers += 4);
packages.AddRange (pack4plus.Where (p => p.Workers == 0));
pack4plus.ForEach (p => p.Workers = 4);
packages = packages.OrderByDescending (p => p.Workers).ToList ();
packages = packages.Where (p => p.Jobs.Count > 0).ToList ();
packages.ForEach (p => p.Compress ());
Workers = packages.SelectMany (p => p.CreateWorkers (true)).ToList ();
List<Job> jobs = Workers.SelectMany (w => w.Jobs).Distinct ().ToList ();
#if DEBUG
foreach (Job j in jobs) {
if (j.Workers > Workers.Count (w => w.Jobs.Contains (j)))
Console.WriteLine ("too few workers for job " + j.ID);
if (j.Workers < Workers.Count (w => w.Jobs.Contains (j)))
Console.WriteLine ("too many workers for job " + j.ID);
if (Board.Jobs.Find (j2 => j2.ID == j.ID).Workers != j.Workers)
Console.WriteLine ("modified input for job " + j.ID);
if (j.ChosenStart < j.FirstStart || j.ChosenStart > j.LastStart)
Console.WriteLine ("invalid start time for job " + j.ID);
}
foreach (Worker w in Workers) {
if (w.Jobs.Count == 0)
continue;
int t = w.Jobs [0].ChosenStart + w.Jobs [0].Duration;
for (int i = 1; i < w.Jobs.Count; i++) {
t += w.Jobs [i - 1].Dist (w.Jobs [i]);
if (t > w.Jobs [i].ChosenStart)
Console.WriteLine ("colliding start for job " + w.Jobs [i].ID);
t = w.Jobs [i].ChosenStart;
}
}
#endif
CombineWorkers ();
int oldScore = 0;
int bestScore = 0;
int oldWorkers = 0;
string result = "";
while (sw.ElapsedMilliseconds < MAX_TIME) {
int score = jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ());
Console.Error.WriteLine ("score: " + score + " @" + sw.ElapsedMilliseconds + " w:" + Workers.Count);
if (score > bestScore) {
bestScore = score;
result = this.ToString ();
}
ShiftBlockingJobs ();
ShiftJobs ();
bool moveJob = false;
if (score - oldScore < 100 && Workers.Count == oldWorkers) {
moveJob = true;
ChangeJobTime (jobs);
}
oldScore = score;
oldWorkers = Workers.Count;
CombineWorkers ();
CompressWorkers ();
CleanupJobs (moveJob);
}
CombineWorkers ();
CompressWorkers ();
ShiftJobs ();
CompressWorkers ();
if (jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ()) > bestScore)
result = this.ToString ();
//int[] histo = new int[800];
//foreach(Job j in jobs)
//{
// for (int t = j.FirstStart; t < j.LastStart; t++)
// {
// histo[t]++;
// }
//}
//for (int t = 0; t < histo.Length; t++)
//{
// if (histo[t] > 0) Console.Write(t + ": " + histo[t] + "\t");
//}
//Console.Error.WriteLine(string.Join("\n",
// Workers.Select(w => new
// {
// t = w.TotalTime(),
// start = w.Jobs[0].ChosenStart,
// end = w.Jobs.Last().ChosenStart + w.Jobs.Last().Duration,
// jobs = w.Jobs.Count,
// worker = w
// }).OrderBy(x => x.jobs).Select(x => $"t:{x.t} start:{x.start} end:{x.end} jobs:{x.jobs} {string.Join(" ", x.worker.Jobs.Select(j => j.ID))}")));
Console.Error.WriteLine ("");
Console.Error.WriteLine ("swaps: " + swap + "/" + swapTries);
Console.Error.WriteLine ("workers: " + Workers.Count);
Console.Error.WriteLine ("jobs: " + jobs.Count + "/" + Board.Jobs.Count);
Console.Error.WriteLine ("total time: " + Workers.Sum (w => w.TotalTime ()));
Console.Error.WriteLine ("travel time: " + Workers.Sum (w => w.TravelTime ()));
Console.Error.WriteLine ("working time: " + Workers.Sum (w => w.WorkingTime ()));
Console.Error.WriteLine ("idle time: " + Workers.Sum (w => w.IdleTime ()));
Console.Error.WriteLine ("score: " + (jobs.Sum (j => j.Value) - Workers.Sum (w => w.Cost ())) + " @" + sw.ElapsedMilliseconds);
return result;
}
private void ChangeJobTime (List<Job> jobs)
{
for (int i = 0; i < 100; i++) {
Job j = jobs [random.Next (jobs.Count)];
int initialTime = j.ChosenStart;
bool shifted = false;
for (int k = 0; k < 10; k++) {
j.ChosenStart = random.Next (j.FirstStart, j.LastStart + 1);
List<Worker> candidates = new List<Worker> ();
foreach (Worker w in Workers) {
if (w.Jobs.Count == 0 || j.ChosenStart < w.Jobs [0].ChosenStart || j.ChosenStart > w.Jobs [w.Jobs.Count - 1].ChosenStart)
continue;
if (w.Cost (j) == 0) {
candidates.Add (w);
if (candidates.Count == j.Workers)
break;
}
}
if (candidates.Count == j.Workers) {
shifted = true;
foreach (Worker w in Workers) {
if (w.Jobs.Contains (j))
w.Jobs.Remove (j);
}
foreach (Worker w in candidates)
w.AddAction (j);
break;
}
}
if (!shifted)
j.ChosenStart = initialTime;
}
}
private void ShiftBlockingJobs ()
{
int minJobs = Workers.Min (w => w.Jobs.Count);
foreach (Worker worker in Workers) {
if (worker.Jobs.Count != minJobs)
continue;
List<Job> toRemove = worker.Jobs.ToList ();
List<Worker>[] substitutes = new List<Worker>[toRemove.Count];
int[] newTimes = new int[toRemove.Count];
bool[] zero = new bool[toRemove.Count];
HashSet<Worker> allSubstitutes = new HashSet<Worker> ();
for (int jobIndex = 0; jobIndex < toRemove.Count; jobIndex++) {
Job j = toRemove [jobIndex];
int oldStart = j.ChosenStart;
for (int newStart = j.FirstStart; newStart <= j.LastStart; newStart++) {
List<Worker> candidates = new List<Worker> ();
List<Worker> zeroCost = new List<Worker> ();
j.ChosenStart = newStart;
foreach (Worker w in Workers) {
if (allSubstitutes.Contains (w))
continue;
int cost = w.Cost (j);
if (cost == 0)
zeroCost.Add (w);
if (cost < SUMMON_COST)
candidates.Add (w);
}
if (zeroCost.Count >= j.Workers) {
candidates = zeroCost;
zero [jobIndex] = true;
}
if (candidates.Count >= j.Workers) {
candidates = candidates.Take (j.Workers).ToList ();
substitutes [jobIndex] = candidates;
newTimes [jobIndex] = newStart;
candidates.ForEach (c => allSubstitutes.Add (c));
break;
}
}
j.ChosenStart = oldStart;
}
bool replace = !substitutes.Any (s => s == null);
for (int jobIndex = 0; jobIndex < toRemove.Count; jobIndex++) {
if (!replace && !zero [jobIndex])
continue;
Job j = toRemove [jobIndex];
foreach (Worker w in Workers) {
if (w.Jobs.Contains (j))
w.Jobs.Remove (j);
}
j.ChosenStart = newTimes [jobIndex];
foreach (Worker w in substitutes[jobIndex])
w.AddAction (j);
}
}
Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
}
private void CombineWorkers ()
{
List<WorkerPair> pairs = new List<WorkerPair> ();
foreach (Worker w1 in Workers) {
foreach (Worker w2 in Workers) {
if (w1.CanMerge (w2))
pairs.Add (new WorkerPair (w1.Diff (w2), w1, w2));
}
}
pairs = pairs.OrderBy (p => p.Diff).ToList ();
foreach (WorkerPair p in pairs)
p.Merge ();
Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
}
private void ShiftJobs ()
{
Job[] jobs = new Job[Board.Jobs.Count + 2];
List<Worker>[] terminalWorkers = new List<Worker>[jobs.Length];
List<Worker>[] workersByJob = new List<Worker>[jobs.Length];
for (int i = 0; i < workersByJob.Length; i++) {
workersByJob [i] = new List<Worker> ();
terminalWorkers [i] = new List<Worker> ();
}
foreach (Worker w in Workers) {
foreach (Job job in w.Jobs) {
workersByJob [job.ID].Add (w);
jobs [job.ID] = job;
}
Job j = w.Jobs [w.Jobs.Count - 1];
terminalWorkers [j.ID].Add (w);
}
for (int i = 0; i < 1000; i++) {
int index = random.Next (2, jobs.Length);
if (terminalWorkers [index].Count == 0)
continue;
Job current = jobs [index];
List<Job> candidates = new List<Job> ();
foreach (Job j in jobs) {
if (j == null || j.Workers > terminalWorkers [index].Count || j == current)
continue;
if (current.ChosenStart + current.Duration + current.Dist (j) > j.LastStart)
continue;
candidates.Add (j);
}
while (candidates.Count > 0) {
Job after = candidates [random.Next (candidates.Count - 1)];
candidates.Remove (after);
int oldCost = 0;
foreach (Worker w in workersByJob[after.ID])
oldCost += w.CostSavingWithout (after);
int willStart = current.ChosenStart + current.Duration + current.Dist (after);
if (willStart < after.FirstStart)
willStart = after.FirstStart;
int willEnd = willStart + after.Duration + after.Dist (Board.Base);
int oldEnd = current.ChosenStart + current.Duration + current.Dist (Board.Base);
int newCost = current.Workers * (willEnd - oldEnd);
if (newCost <= oldCost) {
foreach (Worker w in workersByJob[after.ID]) {
if (w.Jobs.Count > 1 && w.Jobs [w.Jobs.Count - 1] == after)
terminalWorkers [w.Jobs [w.Jobs.Count - 2].ID].Add (w);
w.Jobs.Remove (after);
}
terminalWorkers [after.ID].Clear ();
workersByJob [after.ID].Clear ();
after.ChosenStart = willStart;
for (int j = 0; j < after.Workers; j++) {
Worker w = terminalWorkers [current.ID] [0];
terminalWorkers [current.ID].RemoveAt (0);
w.AddAction (after);
terminalWorkers [after.ID].Add (w);
workersByJob [after.ID].Add (w);
}
break;
}
}
}
for (int i = 0; i < workersByJob.Length; i++) {
terminalWorkers [i] = new List<Worker> ();
}
foreach (Worker w in Workers) {
if (w.Jobs.Count == 0)
continue;
Job j = w.Jobs [0];
terminalWorkers [j.ID].Add (w);
}
for (int i = 0; i < 1000; i++) {
int index = random.Next (2, jobs.Length);
if (terminalWorkers [index].Count == 0)
continue;
Job current = jobs [index];
List<Job> candidates = new List<Job> ();
foreach (Job j in jobs) {
if (j == null || j.Workers > terminalWorkers [index].Count || j == current)
continue;
if (current.ChosenStart - j.Duration - current.Dist (j) < j.FirstStart)
continue;
candidates.Add (j);
}
while (candidates.Count > 0) {
Job before = candidates [random.Next (candidates.Count - 1)];
candidates.Remove (before);
int oldCost = 0;
foreach (Worker w in workersByJob[before.ID])
oldCost += w.CostSavingWithout (before);
int willStart = current.ChosenStart - before.Duration - current.Dist (before);
if (willStart > before.LastStart)
willStart = before.LastStart;
int willEnd = willStart - before.Dist (Board.Base);
int oldEnd = current.ChosenStart - current.Dist (Board.Base);
int newCost = current.Workers * (oldEnd - willEnd);
if (newCost <= oldCost) {
foreach (Worker w in workersByJob[before.ID]) {
if (w.Jobs.Count > 1 && w.Jobs [0] == before)
terminalWorkers [w.Jobs [1].ID].Add (w);
w.Jobs.Remove (before);
}
terminalWorkers [before.ID].Clear ();
workersByJob [before.ID].Clear ();
before.ChosenStart = willStart;
for (int j = 0; j < before.Workers; j++) {
Worker w = terminalWorkers [current.ID] [0];
terminalWorkers [current.ID].RemoveAt (0);
w.AddAction (before);
terminalWorkers [before.ID].Add (w);
workersByJob [before.ID].Add (w);
}
break;
}
}
}
Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
}
private List<JobPackage> MergePackages (List<JobPackage> packages, int workerDiff)
{
for (int dist = 1; dist <= 200; dist++) {
bool merged = true;
while (merged) {
merged = false;
foreach (JobPackage p1 in packages) {
foreach (JobPackage p2 in packages) {
if (p1.Add (p2, dist, workerDiff)) {
merged = true;
break;
}
}
}
packages = packages.Where (p => p.Jobs.Count > 0).ToList ();
}
}
return packages;
}
private void CompressWorkers ()
{
List<Job> jobs = Workers.SelectMany (w => w.Jobs).Distinct ().ToList ();
List<Worker>[] workersByJob = new List<Worker>[jobs.Max (j => j.ID) + 1];
for (int i = 1; i < workersByJob.Length; i++)
workersByJob [i] = new List<Worker> ();
foreach (Worker w in Workers) {
foreach (Job j in w.Jobs)
workersByJob [j.ID].Add (w);
}
List<Job> waiting = jobs.Where (j => !workersByJob [j.ID].Any (w => j == w.Jobs.Last ())).ToList ();
bool changed = true;
while (changed) {
changed = false;
foreach (Job j in waiting) {
int minDelay = j.LastStart - j.ChosenStart;
foreach (Worker w in workersByJob[j.ID]) {
Job next = w.Jobs.FirstOrDefault (n => n.ChosenStart > j.ChosenStart);
if (next == null)
continue;
minDelay = Math.Min (minDelay, next.ChosenStart - j.ChosenStart - j.Duration - j.Dist (next));
}
j.ChosenStart += minDelay;
if (minDelay > 0)
changed = true;
}
}
waiting = jobs.Where (j => !workersByJob [j.ID].Any (w => j == w.Jobs [0])).ToList ();
changed = true;
while (changed) {
changed = false;
foreach (Job j in waiting) {
int minDelay = j.ChosenStart - j.FirstStart;
foreach (Worker w in workersByJob[j.ID]) {
Job prev = w.Jobs.LastOrDefault (n => n.ChosenStart < j.ChosenStart);
if (prev == null)
continue;
minDelay = Math.Min (minDelay, j.ChosenStart - prev.ChosenStart - prev.Duration - j.Dist (prev));
}
j.ChosenStart -= minDelay;
if (minDelay > 0)
changed = true;
}
}
}
static long swap = 0;
static long swapTries = 0;
public void CleanupJobs (bool moveJob)
{
// move first or last job to another worker
bool[] noMatch = new bool[2010];
foreach (Worker w1 in Workers) {
if (w1.Jobs.Count == 0)
continue;
List<Job> jobs = new List<Job> { w1.Jobs [0] };
if (w1.Jobs.Count > 1)
jobs.Add (w1.Jobs [w1.Jobs.Count - 1]);
foreach (Job job in jobs) {
if (noMatch [job.ID])
continue;
noMatch [job.ID] = true;
int costSavingWithout = w1.CostSavingWithout (job);
List<Worker> candidates = new List<Worker> ();
foreach (Worker w2 in Workers) {
if (w2.Jobs.Count == 0)
continue;
int cost = w2.Cost (job);
if (cost == costSavingWithout)
candidates.Add (w2);
if (cost < costSavingWithout) {
candidates.Clear ();
w2.AddAction (job);
w1.Jobs.Remove (job);
noMatch [job.ID] = false;
break;
}
}
if (candidates.Count > 0) {
Worker w2 = candidates [random.Next (candidates.Count)];
w2.AddAction (job);
w1.Jobs.Remove (job);
}
}
// swap 1 vs 0
if (moveJob) {
for (int i = 0; i < 3000; i++) {
//swapTries++;
if (w1.Jobs.Count == 0)
break;
Worker w2 = Workers [random.Next (Workers.Count)];
if (w2.Jobs.Count == 0 || w2.Jobs.Count < w1.Jobs.Count + 1 || w1 == w2)
continue;
// random swap
Job job = w1.Jobs [random.Next (w1.Jobs.Count)];
if (w2.Cost (job) == 0) {
w2.AddAction (job);
w1.Jobs.Remove (job);
//swap++;
}
}
}
}
List<JobConnection> connections = new List<JobConnection> ();
foreach (Worker w in Workers) {
for (int i = 1; i < w.Jobs.Count; i++) {
int dist = w.Jobs [i - 1].Dist (w.Jobs [i]);
if (dist > 1)
connections.Add (new JobConnection (w, i, dist));
}
}
int take = Math.Max (Math.Min (connections.Count, 1000), connections.Count / 5);
//if (moveJob) take = connections.Count;
connections = connections.OrderByDescending (c => c.Dist).Take (take).ToList ();
connections = connections.OrderByDescending (c => c.Worker.Jobs [c.JobIndex].ChosenStart).ToList ();
// crossover
foreach (JobConnection c in connections) {
Worker w1 = c.Worker;
Job j1 = w1.Jobs [c.JobIndex];
for (int i = 0; i < 100; i++) {
swapTries++;
Worker w2 = Workers [random.Next (Workers.Count)];
if (w2.Jobs.Count == 0 || w1 == w2)
continue;
int j2Index = 0;
while (j2Index < w2.Jobs.Count && w2.Jobs [j2Index].ChosenStart < j1.ChosenStart)
j2Index++;
if (j2Index == w2.Jobs.Count)
continue;
Job j2 = w2.Jobs [j2Index];
// if (w1.Jobs[c.JobIndex - 1].Dist(j2) > c.Dist) continue;
int idx1 = w1.Jobs.IndexOf (j1);
int idx2 = w2.Jobs.IndexOf (j2);
if (idx1 == 0 && idx2 == 0)
continue; // no crossover
if (idx1 > 0 && w1.Jobs [idx1 - 1].ChosenStart + w1.Jobs [idx1 - 1].Duration + w1.Jobs [idx1 - 1].Dist (j2) > j2.ChosenStart)
continue; // time colliding
if (idx2 > 0 && w2.Jobs [idx2 - 1].ChosenStart + w2.Jobs [idx2 - 1].Duration + w2.Jobs [idx2 - 1].Dist (j1) > j1.ChosenStart)
continue;
if (idx1 > 0 && idx2 > 0 && w1.Jobs [idx1 - 1].Dist (j2) >= w1.Jobs [idx1 - 1].Dist (j1) && w2.Jobs [idx2 - 1].Dist (j1) >= w2.Jobs [idx2 - 1].Dist (j2))
continue; // no improvement
Worker w1_ = new Worker ();
Worker w2_ = new Worker ();
for (int k = 0; k < idx1; k++)
w1_.Jobs.Add (w1.Jobs [k]);
for (int k = 0; k < idx2; k++)
w2_.Jobs.Add (w2.Jobs [k]);
for (int k = idx1; k < w1.Jobs.Count; k++)
w2_.Jobs.Add (w1.Jobs [k]);
for (int k = idx2; k < w2.Jobs.Count; k++)
w1_.Jobs.Add (w2.Jobs [k]);
if (w1_.Cost () + w2_.Cost () <= w1.Cost () + w2.Cost ()) {
w1.Jobs = w1_.Jobs;
w2.Jobs = w2_.Jobs;
swap++;
break;
}
}
}
Workers = Workers.Where (w => w.Jobs.Count > 0).ToList ();
}
public override string ToString ()
{
StringBuilder result = new StringBuilder ();
foreach (Worker w in Workers)
result.AppendLine (w.ToString ());
return result.ToString ();
}
}
class JobConnection
{
public Worker Worker;
public int JobIndex;
public int Dist;
public JobConnection (Worker worker, int jobIndex, int dist)
{
this.Worker = worker;
this.JobIndex = jobIndex;
this.Dist = dist;
}
}
class WorkerPair
{
public int Diff;
public Worker Worker1;
public Worker Worker2;
public WorkerPair (int diff, Worker w1, Worker w2)
{
this.Diff = diff;
this.Worker1 = w1;
this.Worker2 = w2;
}
public void Merge ()
{
Worker1.Merge (Worker2);
}
}
class Board
{
public Job Base;
public List<Job> Jobs = new List<Job> ();
public Board ()
{
int n = int.Parse (Console.ReadLine ());
int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
Base = new Job (nums [0], nums [1], 1, 0, 0, 0, 0);
for (int i = 2; i <= n; i++) {
nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
Jobs.Add (new Job (nums [0], nums [1], i, nums [2], nums [3], nums [4], nums [5]));
}
Jobs = Jobs.OrderBy (j => j.FirstStart).ToList ();
}
}
class Job
{
public int X, Y, ID;
public int Duration, FirstStart, LastStart, Workers;
public int Value;
public int Created;
public int ChosenStart;
public Job (int x, int y, int id, int duration, int workers, int firstStart, int lastEnd)
{
this.ID = id;
this.X = x;
this.Y = y;
this.Duration = duration;
this.Workers = workers;
this.FirstStart = firstStart;
this.LastStart = lastEnd - duration;
Value = duration * workers * (workers + 5);
}
public Job (Job j) : this (j.X, j.Y, j.ID, j.Duration, j.Workers, j.FirstStart, j.LastStart + j.Duration)
{
this.ChosenStart = j.ChosenStart;
}
public int Dist (Job job)
{
return Math.Abs (X - job.X) + Math.Abs (Y - job.Y);
}
public override string ToString ()
{
return ID + " @" + ChosenStart;
}
}
class Worker : IComparable<Worker>
{
public List<Job> Jobs = new List<Job> ();
public static Job Base;
public int ExtraCost;
public int ExtraDist;
public int PseudoCost;
public void AddAction (Job job)
{
int index = 0;
while (index < Jobs.Count && Jobs [index].ChosenStart < job.ChosenStart)
index++;
Jobs.Insert (index, job);
}
public int TotalTime ()
{
int start = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
int end = Jobs.Last ().ChosenStart + Jobs.Last ().Duration + Base.Dist (Jobs.Last ());
return end - start;
}
public int WorkingTime ()
{
return Jobs.Sum (j => j.Duration);
}
public int TravelTime ()
{
int result = Base.Dist (Jobs [0]) + Base.Dist (Jobs.Last ());
for (int i = 0; i < Jobs.Count - 1; i++) {
result += Jobs [i].Dist (Jobs [i + 1]);
}
return result;
}
public int IdleTime ()
{
return TotalTime () - TravelTime () - WorkingTime ();
}
public int Cost ()
{
if (Jobs.Count == 0)
return 0;
Job last = Jobs [Jobs.Count - 1];
return SUMMON_COST + (last.ChosenStart + last.Duration - Jobs [0].ChosenStart) + last.Dist (Base) + Jobs [0].Dist (Base);
}
public int Cost (Job job)
{
ExtraCost = 0;
PseudoCost = ExtraCost;
if (Jobs.Count == 0) {
ExtraCost = 2 * job.Dist (Base) + SUMMON_COST;
return ExtraCost;
}
Job prev = null, next = null;
if (job.ChosenStart <= Jobs [0].ChosenStart)
next = Jobs [0];
else if (job.ChosenStart >= Jobs [Jobs.Count - 1].ChosenStart)
prev = Jobs [Jobs.Count - 1];
else {
int left = 0, right = Jobs.Count - 1;
while (left + 1 < right) {
int middle = (left + right) / 2;
if (Jobs [middle].ChosenStart < job.ChosenStart)
left = middle;
else
right = middle;
}
int index = left;
while (Jobs [index + 1].ChosenStart < job.ChosenStart)
index++;
prev = Jobs [index];
if (prev.ChosenStart < job.ChosenStart)
index++;
next = Jobs [index];
}
if (prev != null && prev.ChosenStart + prev.Duration + prev.Dist (job) > job.ChosenStart ||
next != null && job.ChosenStart + job.Duration + job.Dist (next) > next.ChosenStart) {
ExtraCost = int.MaxValue;
PseudoCost = ExtraCost;
return ExtraCost;
}
if (prev != null && next != null) { // in the middle
ExtraDist = job.Dist (next) + job.Dist (prev) - prev.Dist (next); // TODO: bonus for small gap on one end
return ExtraCost;
}
if (prev != null) { // last in chain
int initial = prev.ChosenStart + prev.Duration + prev.Dist (Base);
int final = job.ChosenStart + job.Duration + job.Dist (Base);
ExtraDist = job.Dist (prev) + job.Dist (Base) - prev.Dist (Base);
ExtraCost = final - initial;
PseudoCost = job.ChosenStart - prev.ChosenStart - prev.Duration;
}
if (next != null) { // first in chain
int initial = next.ChosenStart - next.Dist (Base);
int final = job.ChosenStart - job.Dist (Base);
ExtraDist = job.Dist (next) + job.Dist (Base) - next.Dist (Base);
ExtraCost = initial - final;
PseudoCost = next.FirstStart - job.ChosenStart - job.Duration;
}
return ExtraCost;
}
public int CostSavingWithout (Job job)
{
if (Jobs.Count == 1)
return SUMMON_COST + 2 * Base.Dist (job);
if (job == Jobs [0]) {
int initial = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
int final = Jobs [1].ChosenStart - Base.Dist (Jobs [1]);
return final - initial;
}
if (job == Jobs [Jobs.Count - 1]) {
int initial = job.ChosenStart + job.Duration + Base.Dist (job);
int final = Jobs [Jobs.Count - 2].ChosenStart + Jobs [Jobs.Count - 2].Duration + Base.Dist (Jobs [Jobs.Count - 2]);
return initial - final;
}
return 0;
}
public override string ToString ()
{
StringBuilder result = new StringBuilder ();
result.AppendLine ("start " + (Jobs [0].ChosenStart - Base.Dist (Jobs [0])) + " " + Base.ID);
Job prev = Base;
int time = Jobs [0].ChosenStart - Base.Dist (Jobs [0]);
foreach (Job action in Jobs) {
result.AppendLine ("arrive " + (time + prev.Dist (action)) + " " + action.ID);
result.AppendLine ("work " + action.ChosenStart + " " + (action.ChosenStart + action.Duration) + " " + action.ID);
time = action.ChosenStart + action.Duration;
prev = action;
}
result.AppendLine ("arrive " + (Jobs.Last ().ChosenStart + Jobs.Last ().Duration + Jobs.Last ().Dist (Base)) + " " + Base.ID);
result.Append ("end");
return result.ToString ();
}
public int Diff (Worker w)
{
Job last = this.Jobs.Last ();
return w.Jobs [0].ChosenStart - (last.ChosenStart + last.Duration);
}
public bool CanMerge (Worker w)
{
if (this.Jobs.Count == 0 || w.Jobs.Count == 0)
return false;
Job last = this.Jobs.Last ();
return last.ChosenStart + last.Duration + last.Dist (w.Jobs [0]) <= w.Jobs [0].ChosenStart;
}
public void Merge (Worker w)
{
if (!CanMerge (w))
return;
this.Jobs.AddRange (w.Jobs);
w.Jobs.Clear ();
}
public int WorkerDiff ()
{
int result = 0;
for (int i = 1; i < Jobs.Count; i++)
result += Math.Abs (Jobs [i - 1].Workers - Jobs [i].Workers);
return result;
}
public int CompareTo (Worker other)
{
for (int i = 0; i < Jobs.Count; i++) {
if (i == other.Jobs.Count)
return -1;
if (this.Jobs [i] != other.Jobs [i])
return this.Jobs [i].ID.CompareTo (other.Jobs [i].ID);
}
if (this.Jobs.Count < other.Jobs.Count)
return 1;
return 0;
}
}
class JobPackage
{
public int FirstStart;
public int LastStart;
public int Duration;
public List<Job> Jobs = new List<Job> ();
public Job StartLocation { get { return Jobs [0]; } }
public Job EndLocation { get { return Jobs [Jobs.Count - 1]; } }
public int Workers;
public static Job Base;
public JobPackage (Job job)
{
Jobs.Add (job);
FirstStart = job.FirstStart;
LastStart = job.LastStart;
Duration = job.Duration;
Workers = job.Workers;
}
public JobPackage (JobPackage backup)
{
this.Jobs = backup.Jobs.ToList ();
this.FirstStart = backup.FirstStart;
this.LastStart = backup.LastStart;
this.Duration = backup.Duration;
this.Workers = backup.Workers;
}
public bool Add (JobPackage package, int maxDist, int workerDiff)
{
if (this == package || this.Jobs.Count == 0 || package.Jobs.Count == 0)
return false;
int dist = this.Dist (package);
int penalty = workerDiff * Math.Abs (this.Jobs [Jobs.Count - 1].Workers - package.Jobs [0].Workers);
if (dist + penalty > maxDist)
return false;
int firstEnd = Math.Max (FirstStart + Duration + dist, package.FirstStart);
int lastEnd = Math.Min (LastStart + Duration + dist, package.LastStart);
int idleTime = package.FirstStart - (LastStart + Duration + dist);
if (lastEnd < firstEnd && idleTime < 0)
return false;
//JobPackage backup = new JobPackage (this);
if (idleTime > 0) {
int flexibility = Math.Max (LastStart - FirstStart, package.LastStart - package.FirstStart) * 3 / (this.Jobs.Count + package.Jobs.Count);
if (dist + penalty + idleTime + flexibility > maxDist)
return false;
FirstStart = LastStart;
Duration += dist + package.Duration + idleTime;
Jobs.AddRange (package.Jobs);
package.Jobs.Clear ();
//if (!Validate ())
// backup.Add (package, maxDist);
return true;
}
if (Math.Max (FirstStart, firstEnd - Duration - dist) > Math.Min (LastStart, lastEnd - Duration - dist))
return false;
FirstStart = Math.Max (FirstStart, firstEnd - Duration - dist);
LastStart = Math.Min (LastStart, lastEnd - Duration - dist);
Duration += dist + package.Duration;
Jobs.AddRange (package.Jobs);
package.Jobs.Clear ();
//if (!Validate ())
// backup.Add (package, maxDist);
return true;
}
public bool Validate ()
{
int t = FirstStart;
for (int i = 0; i < Jobs.Count; i++) {
Job j = Jobs [i];
if (t < j.FirstStart)
t = j.FirstStart;
if (t > j.LastStart)
return false;
t += j.Duration;
if (i < Jobs.Count - 1)
t += j.Dist (Jobs [i + 1]);
}
return true;
}
public void Compress ()
{
Worker w = CreateWorkers (false).First ();
int time = w.TotalTime ();
int workerDiff = w.WorkerDiff ();
for (int swapIndex = 0; swapIndex < Jobs.Count - 2; swapIndex++) {
for (int type = 0; type < 6; type++) {
List<JobPackage> packages = Jobs.Select (j => new JobPackage (new Job (j))).ToList ();
List<JobPackage> old = packages.ToList ();
int i1 = new int[] { 0, 0, 1, 1, 2, 2 } [0];
int i2 = new int[] { 1, 2, 0, 2, 0, 1 } [0];
int i3 = new int[] { 2, 1, 2, 0, 1, 0 } [0];
packages [swapIndex] = old [swapIndex + i1];
packages [swapIndex + 1] = old [swapIndex + i2];
packages [swapIndex + 2] = old [swapIndex + i3];
bool valid = true;
for (int i = 1; i < packages.Count; i++) {
if (!packages [0].Add (packages [i], 10000, 0))
valid = false;
}
if (!valid)
continue;
Worker w2 = packages [0].CreateWorkers (false).First ();
if (w2.TotalTime () < time || w2.TotalTime () == time && w2.WorkerDiff () < workerDiff) {
time = w2.TotalTime ();
workerDiff = w2.WorkerDiff ();
this.FirstStart = packages [0].FirstStart;
this.LastStart = packages [0].LastStart;
this.Duration = packages [0].Duration;
this.Jobs = packages [0].Jobs;
}
}
}
}
public IEnumerable<Worker> CreateWorkers (bool count)
{
int t = FirstStart;
for (int i = 0; i < Jobs.Count; i++) {
Job j = Jobs [i];
if (t < j.FirstStart)
t = j.FirstStart;
j.ChosenStart = t;
t += j.Duration;
if (i < Jobs.Count - 1)
t += j.Dist (Jobs [i + 1]);
}
for (int i = 0; i < 7; i++) {
Worker w = new Worker ();
foreach (Job j in Jobs) {
if (count) {
if (j.Created < j.Workers) {
w.Jobs.Add (j);
j.Created++;
}
} else if (i < j.Workers)
w.Jobs.Add (j);
}
yield return w;
}
}
public int Dist (JobPackage other)
{
return this.EndLocation.Dist (other.StartLocation);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.