Tugas

Anda akan diberi satu set lingkaran di pesawat dengan pusatnya di garis y = 0 . Dijamin tidak ada pasangan lingkaran yang memiliki lebih dari satu titik umum.

Tugas Anda adalah menentukan berapa banyak wilayah di mana lingkaran membagi bidang. Wilayah adalah kumpulan titik berdekatan inklusi-maksimal yang tidak memotong lingkaran apa pun.

Anda harus menulis sebuah program yang menghitung jawaban ini ketika diberi deskripsi lingkaran.

Ini sebuah contoh:

Di sisi kiri Anda melihat lingkaran yang tergambar di pesawat. Namun, di bagian kanan gambar, wilayah yang diproduksi oleh lingkaran diwarnai dengan jelas (satu warna per wilayah). Ada enam wilayah dalam contoh ini.

Memasukkan

Baris pertama dari input berisi angka,, Njumlah deskripsi lingkaran untuk diikuti. Baris ini bersifat opsional, jika solusi Anda berfungsi tanpanya, tidak masalah.

Baris berikut Nmasing-masing berisi dua bilangan bulat, x _i dan r _i > 0 , mewakili lingkaran dengan pusat (x _i , 0) dan jari-jari r _i .

Dijamin tidak ada pasangan lingkaran yang memiliki lebih dari satu titik umum. Lebih lanjut dijamin bahwa x _i dan r _i tidak melebihi 10^9nilai absolut (sehingga mereka cocok dengan integer 32-bit).

Inputnya mungkin:

• baca dari STDIN

• baca dari file yang bernama Idi direktori saat ini

Atau, inputnya bisa:

• tersedia sebagai string (termasuk baris baru) dalam variabel global

• di tumpukan

Keluaran

Ini harus berupa bilangan bulat tunggal, jumlah ke daerah yang diproduksi. Ini harus ditulis ke STDOUT atau file bernama Odi direktori saat ini.

Aturan

• Kode terpendek dalam byte menang

• +200 byte penalti jika kode Anda tidak memiliki runtime + kompleksitas ruang polinomial masuk n

• -100 byte bonus untuk runtime + kompleksitas ruang terburuk yang diharapkan O(n log n)

• -50 byte bonus untuk runtime + kompleksitas ruang terburuk yang diharapkan O(n)

• Bonus -100 byte untuk runtime deterministik + kompleksitas ruang O(n)

Saat menilai runtime:

• Asumsikan bahwa tabel hash O(1)mengharapkan runtime untuk memasukkan, menghapus, dan mencari, terlepas dari urutan operasi dan data input. Ini mungkin benar atau tidak benar, tergantung pada apakah penerapannya menggunakan pengacakan.

• Asumsikan bahwa jenis bahasa pemrograman bawaan Anda membutuhkan O(n log n)waktu deterministik , di mana nukuran urutan input.

• Asumsikan bahwa operasi aritmatika pada nomor input hanya memakan O(1)waktu.

• Jangan berasumsi bahwa angka-angka input terikat oleh konstanta, meskipun, karena alasan praktis, mereka. Ini berarti bahwa algoritma seperti jenis radix atau jenis penghitungan bukanlah waktu linier. Secara umum, faktor konstan yang sangat besar harus dihindari.

Contohnya

Memasukkan:

2 
1 3
5 1

Keluaran: 3

Memasukkan:

3
2 2
1 1
3 1

Keluaran: 5

4
7 5
-9 11
11 9
0 20

Memasukkan:

9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2

Keluaran: 11

Petunjuk

Kita dapat menggunakan ide berikut untuk solusi yang sangat ringkas. Mari kita memotong set lingkaran dengan sumbu X dan menafsirkan titik-titik persimpangan sebagai node dalam grafik planar:

Setiap lingkaran menghasilkan tepat 2 tepi dalam grafik ini dan hingga dua node. Kita dapat menghitung jumlah node dengan menggunakan tabel hash untuk melacak jumlah total batas kiri atau kanan yang berbeda.

Kemudian kita bisa menggunakan rumus karakteristik Euler untuk menghitung jumlah wajah dari gambar grafik:

V - E + F - C = 1

F = E - V + C + 1

Untuk menghitung C, jumlah komponen yang terhubung, kita bisa menggunakan pencarian kedalaman-pertama .

^{Catatan: Gagasan masalah ini dipinjam dari kontes pemrograman Kroasia baru - baru ini , tapi tolong jangan menipu dengan melihat garis besar solusinya. :)}

Mathematica, 125 122 - 150 = -28 karakter

Saya tidak tahu kerumitan fungsi bawaan ConnectedComponents.

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&

Pemakaian:

1+{-1,2,1}.Length/@{VertexList@#,EdgeList@#,ConnectedComponents@#}&@Graph[(+##)<->(#-#2)&@@@Rest@ImportString[#,"Table"]]&[
"9
38 14
-60 40
73 19
0 100
98 2
-15 5
39 15
-38 62
94 2"]

11

Ruby - 312 306 285 273 269 259 karakter

Jawaban ini telah digantikan oleh pendekatan saya yang lain yang menggunakan karakter jauh lebih sedikit dan berjalan di O(n log n).

Oke, ayo pergi. Sebagai permulaan, saya hanya ingin implementasi yang berhasil, jadi ini belum dioptimalkan secara algoritmik. Saya mengurutkan lingkaran dari yang terbesar ke yang terkecil, dan membangun pohon (lingkaran yang termasuk dalam lingkaran lain adalah anak-anak dari yang lebih besar). Kedua operasi mengambil yang O(n^2)terburuk dan O(n log n)terbaik. Kemudian saya beralih melalui pohon untuk menghitung area. Jika anak-anak lingkaran mengisi seluruh diameternya, ada dua area baru, jika tidak hanya ada satu. Pengulangan ini dilakukan O(n). Jadi saya memiliki kompleksitas keseluruhan O(n^2)dan memenuhi syarat untuk hadiah maupun penalti.

Kode ini mengharapkan input tanpa jumlah lingkaran untuk disimpan dalam variabel s:

t=[]
s.lines.map{|x|x,r=x.split.map &:to_i;{d:2*r,l:x-r,c:[]}}.sort_by!{|c|-c[:d]}.map{|c|i=-1;n=t
while o=n[i+=1]
if 0>d=c[:l]-o[:l]
break
elsif o[:d]>d
n=o[:c]
i=-1
end
end
n[i,0]=c}
a=1
t.map &(b=->n{d=0
n[:c].each{|c|d+=c[:d]}.map &b
a+=d==n[:d]?2:1})
p a

Versi tidak dikumpulkan (mengharapkan input dalam variabel string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_i
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius, children:[]}
}
list.sort_by! { |circle| -circle[:d] }
tree = []
list.map { |circle|
  i = -1
  node = tree
  while c=node[i+=1]
    if circle[:x]<c[:l]
      break
    elsif circle[:x]<c[:r]
      node = c[:children]
      i = -1
    end
  end
  node[i,0] = circle
}
areas = 1
tree.map &(count = -> node {
  d = 0
  i = -1
  while c=node[:children][i+=1]
    count.call c
    d += c[:d]
  end
  areas += d == node[:d] ? 2 : 1
})
p areas

Ruby, 203 183 173 133 - 100 = 33 karakter

Jadi inilah pendekatan yang berbeda. Kali ini, saya mengurutkan lingkaran berdasarkan titik paling kiri mereka. Lingkaran yang menyentuh pada titik paling kiri diurutkan dari yang terbesar hingga yang terkecil. Ini membutuhkan O(n log n)(well, Ruby menggunakan pengurutan cepat, jadi sebenarnya O(n^2)tetapi menerapkan pengurutan gabungan / heap mungkin di luar cakupan tantangan ini). Kemudian saya beralih ke daftar ini, mengingat semua posisi paling kiri dan paling kanan dari lingkaran yang telah saya kunjungi. Ini memungkinkan saya mendeteksi jika serangkaian lingkaran menghubungkan semua jalan melintasi lingkaran yang lebih besar. Dalam hal ini, ada dua subarea, atau hanya satu. Iterasi ini hanya O(n)memberikan kompleksitas total O(n log n)yang memenuhi syarat untuk hadiah 100 karakter.

Cuplikan ini mengharapkan input akan diberikan melalui file dalam argumen baris perintah tanpa jumlah lingkaran:

l,r={},{}
a=1
$<.map{|x|c,q=x.split.map &:to_r;[c-q,-2*q]}.sort.map{|x,y|a+=r[y=x-y]&&l[x]?2:1
l[y]=1 if l[x]&&!r[y]
l[x]=r[y]=1}
p a

Versi tidak dikumpulkan (mengharapkan input dalam variabel string):

list = []
string.split("\n").map { |x|
  m = x.split
  x,radius = m.map &:to_r
  list<<{x:x, d:2*radius, l:x-radius, r:x+radius}
}
list.sort_by! { |circle| circle[:l] + 1/circle[:d] }
l,r={},{}
areas = 1
list.map { |circle|
  x,y=circle[:l],circle[:r]
  if l[x] && r[y]
    areas += 2
  else
    areas += 1
    l[y]=1 if l[x]
  end
  r[y]=1
  l[x]=1
}
p areas

Julia - 260 -100 (bonus?) = 160

Menafsirkan lingkaran sebagai angka dengan simpul (persimpangan), tepi, dan wajah (bidang pesawat) kita dapat saling berhubungan menggunakan karakteristik Euler , jadi kita hanya perlu tahu jumlah "simpul" dan "tepi" untuk memiliki nomor "wajah" atau wilayah pesawat dengan rumus yang ditulis di bawah:

UPDATE: Dengan berpikir sebentar saya menemukan bahwa masalah dengan metode saya hanya ketika lingkaran di mana tidak terhubung, jadi saya datang dengan sebuah ide, mengapa tidak menghubungkan mereka secara artifisial? Jadi keseluruhan akan memenuhi formula Euler.

F = 2 + EV (V = 6, E = 9)

[Jangan bekerja dengan lingkaran bersarang, jadi itu bukan jawaban masalah untuk kasus umum]

Kode :

s=readlines(open("s"))
n=int(s[1])
c=zeros(n,2)
t=[]
for i=1:n
    a=int(split(s[i+1]))
    c[i,1]=a[1]-a[2]
    c[i,2]=a[1]+a[2]
    if i==1 t=[c[1]]end
    append!(t,[c[i,1]:.5:c[i,2]])
end
e=0
t=sort(t)
for i in 1:(length(t)-1) e+=t[i+1]-t[i]>=1?1:0end #adds one edge for every gap
2+2n+e-length(unique(c)) # 2+E-V = 2+(2n+e)-#vertices

Spidermonkey JS, 308, 287 , 273 - 100 = 173

Saya pikir jika saya menulis ulang ini dalam Ruby atau Python saya bisa menyimpan karakter.

Kode:

for(a=[d=readline],e={},u=d(n=1);u--;)[r,q]=d().split(' '),l=r-q,r-=-q,e[l]=e[l]||[0,0],e[r]=e[r]||[0,0],e[r][1]++,e[l][0]++
for(k=Object.keys(e).sort(function(a,b)b-a);i=k.pop();a.length&&a.pop()&a.push(0)){for([l,r]=e[i];r--;)n+=a.pop()
for(n+=l;l--;)a.push(l>0)}print(n)

Algoritma:

n = 1 // this will be the total
e = {x:[numLeftBounds,numRightBounds]} // imagine this as the x axis with a count of zero-crossings
a = [] // this is the stack of circles around the "cursor".  
       // values will be 1 if that circle's never had alone time, else 0
k = sort keys of e on x
for each key in k: // this is the "cursor"
  n += key[numLeftBounds] // each circle that opens has at least one space.
  k[numRightBounds].times {n += a.pop()} // pop the closing circles. if any were never alone, add 1
  k[numLeftBounds].times {a.push(alwaysAlone)} // push the opening circles
  if !a.empty():
     set the innermost circle (top of stack) to false (not never alone)
  fi
loop

Saya tidak terlalu hebat dalam notasi O besar, tapi saya pikir itu O (n) karena saya secara efektif perulangan melalui setiap lingkaran 3 kali (buat, kiri, kanan) dan juga menyortir kunci peta (dan saya mengurutkan untuk O ( n log n) tetapi itu menghilang). Apakah ini deterministik?

JavaScript (ES6) - 255 254 Karakter - 100 250 Bonus = 155 4

R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Mengasumsikan bahwa string input dalam variabel Sdan menampilkan jumlah daerah ke konsol.

R=/(\S+) (\S+)/ym;                  // Regular expression to find centre and width.
N=1;                                // Number of regions
w=l=0;                              // Maximum width and minimum left boundary.
X=[];                               // A 1-indexed array to contain the circles.
                                    // All the above are O(1)
for(;m=R.exec(S);){                 // For each circle
    X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};
                                    // Create an object with w (width), l (left boundary)
                                    // and r (right boundary) attributes.
    l=k<l?k:l;                      // Update the minimum left boundary.
    w=j<w?w:j                       // Update the maximum width.
}                                   // O(1) per iteration = O(N) total.
M=[];                               // An array.
X.map(x=>M[(x.l-l+1)*w-x.w]=x);     // Map the 1-indexed array of circles (X) to a
                                    // sparse array indexed so that the elements are
                                    // sorted by ascending left boundary then descending
                                    // width.
                                    // If there are N circles then only N elements are
                                    // created in the array and it can be treated as if it
                                    // is a hashmap (associative array) with a built in
                                    // ordering and as per the rules set in the question
                                    // is O(1) per insert so is O(N) total cost.
                                    // Since the array is sparse then it is still O(N)
                                    // total memory.
s=[];                               // An empty stack
i=0;                                // The number of circles on the stack.
M.map(x=>{                          // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

Kompleksitas waktu sekarang O (N).

Test Case 1

S='2\n1 3\n5 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Output: 3

Test Case 2

S='3\n2 2\n1 1\n3 1';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Output: 5

Test Case 3

S='4\n7 5\n-9 11\n11 9\n0 20';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Output: 6

Test Case 4

S='9\n38 14\n-60 40\n73 19\n0 100\n98 2\n-15 5\n39 15\n-38 62\n94 2';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Output: 11

Test Case 5

S='87\n-730 4\n-836 2\n-889 1\n-913 15\n-883 5\n-908 8\n-507 77\n-922 2\n-786 2\n-782 2\n-762 22\n-776 2\n-781 3\n-913 3\n-830 2\n-756 4\n-970 30\n-755 5\n-494 506\n-854 4\n15 3\n-914 2\n-840 2\n-833 1\n-505 75\n-888 10\n-856 2\n-503 73\n-745 3\n-903 25\n-897 1\n-896 2\n-848 10\n-878 50\n-864 2\n0 1000\n-934 6\n-792 4\n-271 153\n-917 1\n-891 3\n-833 107\n-847 3\n-758 2\n-754 2\n-892 2\n-738 2\n-876 2\n-52 64\n-882 2\n-270 154\n-763 3\n-868 72\n-846 4\n-427 3\n-771 3\n-767 17\n-852 2\n-765 1\n-772 6\n-831 1\n-582 2\n-910 6\n-772 12\n-764 2\n-907 9\n-909 7\n-578 2\n-872 2\n-848 2\n-528 412\n-731 3\n-879 1\n-862 4\n-909 1\n16 4\n-779 1\n-654 68\n510 490\n-921 3\n-773 5\n-653 69\n-926 2\n-737 3\n-919 1\n-841 1\n-863 3';
R=/(\S+) (\S+)/ym;N=1;i=w=l=0;for(X=[];m=R.exec(S);){X[N++]={w:j=m[2]*1,l:k=m[1]-j,r:k+2*j};l=k<l?k:l;w=j<w?w:j}M=[];X.map(x=>M[(x.l-l+1)*w-x.w]=x);s=[];M.map(x=>{while(i&&s[i-1].r<x.r)N+=s[--i].w?0:1;i&&(s[i-1].w-=x.w);s[i++]=x});while(i)N+=s[--i].w?0:1

Output: 105

Versi sebelumnya

C=S.split('\n');N=1+C.shift()*1;s=[];C.map(x=>x.split(' ')).map(x=>[w=x[1]*1,x[i=0]*1+w]).sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d).map(x=>{while(i&&s[i-1][1]<x[1])N+=s[--i][0]?0:1;i&&(s[i-1][0]-=x[0]);s[i++]=x});while(i)N+=s[--i][0]?0:1

Dengan komentar:

C=S.split('\n');                    // Split the input into an array on the newlines.
                                    // O(N)
N=1+C.shift()*1;                    // Remove the head of the array and store the value as
                                    // if there are N disjoint circles then there will be
                                    // N+1 regions.
                                    // At worst O(N) depending on how .shift() works.
s=[];                               // Initialise an empty stack.
                                    // O(1)
C .map(x=>x.split(' '))             // Split each line into an array of the two values.
                                    // O(1) per line = O(N) total.
  .map(x=>[w=x[1]*1,x[i=0]*1+w])    // Re-map the split values to an array storing the
                                    // radius and the right boundary.
                                    // O(1) per line = O(N) total.

  .sort((a,b)=>(c=a[1]-2*a[0])==(d=b[1]-2*b[0])?b[0]-a[0]:c-d)
                                    // Sort the circles on increasing left boundary and
                                    // then descending radius.
                                    // O(1) per comparison = O(N.log(N)) total.
  .map(x=>{                         // Loop through each circle
    while(i&&s[i-1][1]<x[1])        // Check to see if the current circle  is to the right
                                    // of the circles on the stack;
      N+=s[--i][0]?0:1;             // if so, decrement the length of the stack and if the
                                    // circle that pops off has radius equal to the total
                                    // radii of its children then increment the number of
                                    // regions by 1.

                                    // Since there can be at most N items on the stack then
                                    // there can be at most N items popped off the stack
                                    // over all the iterations; therefore this operation
                                    // has an O(N) total cost.
    i&&(s[i-1][0]-=x[0]);           // If there is a circle on the stack then this circle
                                    // is its child. Decrement the parent's radius by the
                                    // current child's radius.
                                    // O(1) per iteration
    s[i++]=x                        // Add the current circle to the stack.
  });
while(i)N+=s[--i][0]?0:1            // Finally, remove all the remaining circles from the
                                    // stack and if the circle that pops off has radius
                                    // equal to the total radii of its children then
                                    // increment the number of regions by 1.
                                    // Since there will always be at least one circle on the
                                    // stack then this has the added bonus of being the final
                                    // command so the value of N is printed to the console.
                                    // As per the previous comment on the complexity, there
                                    // can be at most N items on the stack so between this
                                    // and the iterations over the circles then there can only
                                    // be N items popped off the stack so the complexity of
                                    // all these tests on the circles on the stack is O(N).

Kompleksitas waktu total adalah O (N) untuk segala sesuatu kecuali jenisnya yaitu O (N.log (N)) - namun dengan mengganti ini dengan jenis ember, ini akan mengurangi kompleksitas total menjadi O (N).

Memori yang diperlukan adalah O (N).

Coba tebak apa yang berikutnya pada daftar todo saya ... ember urutkan kurang dari 150 karakter. Selesai