icpc_challenge_2020.cr

INITIAL_COOLER    = 4e5
FINAL_COOLER      = 2e7
TIME_LIMIT_ALL    = 600 * 1000
TIME_LIMIT_SINGLE = 80 * 1000
init_time = Time.utc.to_unix_ms
edges = [] of Tuple(Int32, Int32)
n = 0
while true
  line = gets
  break if !line
  a, b = line.split.map(&.to_i)
  edges << {a, b}
  n = {a, b, n}.max
end
n += 1
ec = edges.size
STDERR.puts("n:#{n} m:#{ec}")
g = Array.new(n) { [] of Int32 }
edges.each do |e|
  g[e[0]] << e[1]
  g[e[1]] << e[0]
end
# histo = Array.new(g.max_of { |a| a.size } + 1, 0)
# g.each do |a|
#   histo[a.size] += 1
# end
# ((histo.size + 9) // 10).times do |i|
#   STDERR.puts histo[(i * 10)..(i * 10 + 9)]
# end
edges.clear
best_score = 0.0
best = [] of Int32
solver = Solver.new(g, ec)
rnd = XorShift.new
while true
  mod_count = (rnd.next_int % 40).to_i32 + 10
  score, used = solver.solve(mod_count)
  if score > best_score
    best_score = score
    best = used
    puts best_score
    mod_count.times do |i|
      puts (0...n).to_a.select { |v| best[v] == i }.join(" ")
    end
  end
  if Time.utc.to_unix_ms - init_time > TIME_LIMIT_ALL
    break
  end
end

def density(count, ein)
  return count == 0 ? 0.0 : count == 1 ? 1.0 : ein * 2.0 / (count * (count - 1))
end

class Solver
  def initialize(graph : Array(Array(Int32)), @ec : Int32)
    @g = graph
    @rnd = XorShift.new
  end

  def create_init_solution(m)
    n = @g.size
    group = Array.new(n, -1)
    cands = [] of Tuple(Int32, Int32)
    (m * 4).times do |i|
      cands << {i % m, (@rnd.next_int % n).to_i32}
    end
    fill = 0
    while fill < n
      ci = (@rnd.next_int % cands.size).to_i32
      gi, pi = cands[ci]
      cands[ci] = cands[-1]
      cands.pop
      if group[pi] == -1
        group[pi] = gi
        @g[pi].each do |adj|
          if group[adj] == -1
            cands << {gi, adj}
          end
        end
        fill += 1
      end
    end
    return group
  end

  def solve(m)
    STDERR.puts("mod_size:#{m}")
    n = @g.size
    rev_ec = 1.0 / @ec
    group = create_init_solution(m)
    count = Array.new(m, 0i64)
    n.times do |i|
      count[group[i]] += 1
    end
    group_adj_c = Array.new(n) { Array.new(m, 0) }
    ein = Array.new(m, 0i64)
    deg = Array.new(m, 0i64)
    density = Array.new(m, 0.0)
    n.times do |i|
      @g[i].each do |adj|
        group_adj_c[i][group[adj]] += 1
      end
      ein[group[i]] += group_adj_c[i][group[i]]
      deg[group[i]] += @g[i].size
    end
    m.times do |i|
      ein[i] //= 2
    end
    score = -0.5 * m / n
    m.times do |i|
      density[i] = density(count[i], ein[i])
      score += ein[i] * rev_ec - (deg[i] * rev_ec * 0.5) ** 2 + 0.5 / m * density[i]
    end
    best_score = score
    best = group.clone
    turn = 0i64
    cooler = INITIAL_COOLER
    elapsed = 0i64
    start_time = Time.utc.to_unix_ms
    while true
      if (turn & 0xFFFF) == 0
        # if turn > 10000000 && score < 0.5
        #   STDERR.puts("early stop")
        #   break
        # end
        elapsed = Time.utc.to_unix_ms - start_time
        if elapsed > TIME_LIMIT_SINGLE
          break
        end
        ratio = elapsed / TIME_LIMIT_SINGLE
        cooler = Math.exp((1.0 - ratio) * Math.log(INITIAL_COOLER) + ratio * Math.log(FINAL_COOLER))
        STDERR.puts("turn:#{turn} cur_score:#{score} cooler:#{cooler}")
      end
      pos = (@rnd.next_int % n).to_i32
      # if ((turn & 0xFFFF) == 0)
      #   STDERR.puts(group_adj_c[pos])
      # end
      cur_group = group[pos]
      if @g[pos].size > 2 && group_adj_c[pos][cur_group] == @g[pos].size
        next
      end
      new_group = (@rnd.next_int % (m - 1)).to_i32
      new_group += 1 if cur_group <= new_group
      ein_0 = ein[cur_group] - group_adj_c[pos][cur_group]
      ein_1 = ein[new_group] + group_adj_c[pos][new_group]
      deg_0 = deg[cur_group] - @g[pos].size
      deg_1 = deg[new_group] + @g[pos].size
      count_0 = count[cur_group] - 1
      count_1 = count[new_group] + 1
      density_0 = density(count_0, ein_0)
      density_1 = density(count_1, ein_1)
      diff = 0.5 / m * (density_0 + density_1 - density[cur_group] - density[new_group])
      diff += (group_adj_c[pos][new_group] - group_adj_c[pos][cur_group]) * rev_ec
      diff += (deg[cur_group] * 0.5 * rev_ec) ** 2 + (deg[new_group] * 0.5 * rev_ec) ** 2
      diff -= (deg_0 * 0.5 * rev_ec) ** 2 + (deg_1 * 0.5 * rev_ec) ** 2
      # STDERR.puts("diff:#{diff} #{Math.exp(diff * cooler)}")
      if diff >= 0 || @rnd.next_double < Math.exp(diff * cooler)
        group[pos] = new_group
        ein[cur_group] = ein_0
        ein[new_group] = ein_1
        deg[cur_group] = deg_0
        deg[new_group] = deg_1
        count[cur_group] -= 1
        count[new_group] += 1
        density[cur_group] = density_0
        density[new_group] = density_1
        @g[pos].each do |adj|
          group_adj_c[adj][cur_group] -= 1
          group_adj_c[adj][new_group] += 1
        end
        score += diff
        if elapsed > TIME_LIMIT_SINGLE - 1000 && score > best_score
          best_score = score
          best = group.clone
          # STDERR.puts("turn:#{turn} best_score:#{best_score}")
        end
      end
      turn += 1
    end
    if best_score <= 0.4
      best_score = score
      best = group.clone
    end
    return {best_score, best}
  end
end

class XorShift
  TO_DOUBLE = 0.5 / (1u64 << 63)

  def initialize(@x = 123456789u64)
  end

  def next_int
    @x ^= @x << 13
    @x ^= @x >> 17
    @x ^= @x << 5
    return @x
  end

  def next_double
    return TO_DOUBLE * next_int
  end
end