Skip to content

Instantly share code, notes, and snippets.

@tomerun
Created June 27, 2020 17:50
Show Gist options
  • Save tomerun/25d54afeb8b8a5354bf135ce32021a7b to your computer and use it in GitHub Desktop.
Save tomerun/25d54afeb8b8a5354bf135ce32021a7b to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment