Latar Belakang:
Saya awalnya memposting pertanyaan ini tadi malam, dan menerima serangan balik karena ketidakjelasannya. Sejak itu saya telah berkonsultasi dengan banyak personel mengenai tidak hanya kata-kata dari masalah, tetapi juga kerumitannya (yang bukan O (1)). Masalah pemrograman ini adalah putaran jahat pada pertanyaan wawancara Amazon.
Pertanyaan:
Diberikan String bilangan bulat yang disatukan secara acak [0, 250), 0 hingga 250 eksklusif, ada SATU nomor yang hilang dalam urutan. Tugas Anda adalah menulis sebuah program yang akan menghitung angka yang hilang ini. Tidak ada angka lain yang hilang dalam urutan selain yang, dan itulah yang membuat masalah ini sangat sulit, dan mungkin sulit secara komputasi.
Melakukan masalah ini dengan tangan pada Strings yang lebih kecil, seperti contoh 1 dan 2 di bawah ini jelas sangat mudah. Sebaliknya, menghitung angka yang hilang pada kumpulan data yang sangat besar yang melibatkan angka tiga digit atau empat digit akan sangat sulit. Gagasan di balik masalah ini adalah untuk membangun sebuah program yang akan melakukan proses ini UNTUK Anda.
Informasi penting:
Satu hal yang tampak agak membingungkan ketika saya memposting masalah ini tadi malam adalah: apa sebenarnya nomor yang hilang didefinisikan sebagai. Nomor yang hilang adalah nomor di dalam kisaran yang ditentukan di atas; TIDAK harus digit. Dalam contoh 3, Anda akan melihat bahwa nomor yang hilang adalah 9, meskipun muncul dalam urutan. Ada 3 tempat DIGIT 9 akan muncul dalam serangkaian [0, 30): "9", "19", dan "29". Tujuan Anda adalah untuk membedakannya, dan menemukan bahwa 9 adalah NUMBER yang hilang (di dalam contoh 3). Dengan kata lain, bagian yang sulit terletak pada mengetahui urutan urutan digit mana yang lengkap dan yang termasuk nomor lainnya.
Memasukkan:
Input adalah String S, yang berisi bilangan bulat dari 0 hingga 249 inklusif, atau 0 hingga 250 eksklusif (dengan kata lain, [0, 250)). Bilangan bulat ini, seperti yang dinyatakan di atas, diacak untuk membuat urutan acak. Tidak ada pembatas ("42, 31, 23, 44"), atau padding 0's (003076244029002); masalahnya persis seperti yang dijelaskan dalam contoh. Dijamin bahwa hanya ada 1 solusi dalam masalah aktual. Beberapa solusi tidak diizinkan untuk ini.
Kriteria Menang:
Siapa pun yang memiliki penggunaan memori tercepat, dan terendah akan menjadi pemenang. Dalam peristiwa ajaib yang mengikat waktu, memori yang lebih rendah akan digunakan untuk pemecah waktu. Harap sebutkan Big O jika Anda bisa!
Contoh:
Contoh 1 dan 2 memiliki kisaran [0, 10)
Contoh 3 dan 4 memiliki kisaran [0, 30)
(Contoh 1-4 hanya untuk demonstrasi. Program Anda tidak perlu menanganinya.)
Contoh 5 memiliki kisaran [0, 250)
1. 420137659
- Missing number => 8
2. 843216075
- Missing number => 9
3. 2112282526022911192312416102017731561427221884513
- Missing number => 9
4. 229272120623131992528240518810426223161211471711
- Missing number => 15
5. 11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025
- Missing number => 71
Test Data:
Problem 1: 6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102
Problem 2: 14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219
Problem 3: 1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144
Problem 4: 2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851
N
, bukan hanya250
? / Bagaimana dengan232
masalah ini? Semua kemungkinan atau satu? Saya menyadari bahwa Anda tahu tentang masalah itu, tetapi saya merasa tidak jelas dalam pertanyaan itu. / Jika ini kode tercepat, harus ada cara untuk mengukurnya. Tentu saja menjalankan pada komputer super berbeda dengan menjalankan pada komputer lama. / Karena tidak ada yang mengatakan itu, - Selamat datang di PPCG!N
ke, katakanlah, 1000 atau 10000.Jawaban:
Clingo , ≈ 0,03 detik
Ini terlalu cepat untuk diukur secara akurat — Anda harus mengizinkan kasing input yang lebih besar daripada berhenti secara artifisial di angka 250.
Contoh input
Input adalah daftar ( k , k th digit) pasangan. Inilah masalah 1:
Contoh output
sumber
45879362100
dengann = 11
dan1
tidak ada (jawabanmissing(0)
).missing(10)
itu juga valid)?C ++, 5000 kasus uji acak dalam 6,1 detik
Ini praktis cepat, tetapi mungkin ada beberapa testcases yang membuatnya lambat. Kompleksitas tidak diketahui.
Jika ada beberapa solusi, itu akan mencetak semuanya. Contoh .
Penjelasan:
Hitung kemunculan digit.
Tuliskan semua jawaban yang mungkin.
Periksa apakah seorang kandidat adalah jawaban yang valid:
3-1. Cobalah untuk membagi string dengan angka yang hanya muncul sekali dan tandai sebagai diidentifikasi, kecuali kandidat.
Misalnya,
2112282526022911192312416102017731561427221884513
hanya memiliki satu14
, sehingga dapat dibagi menjadi211228252602291119231241610201773156
dan27221884513
.3-2. Jika string yang dipisah memiliki panjang 1, tandai sebagai diidentifikasi.
Jika ada kontradiksi yang dibuat (diidentifikasi lebih dari sekali), kandidat tidak valid.
Jika kami tidak dapat menemukan kandidat di string, kandidat tersebut valid.
3-3. Jika ada pemisahan, ulangi langkah 3-1. Jika tidak, lakukan pencarian brute force untuk memeriksa apakah kandidat tersebut valid.
Cobalah online!
sumber
Bersihkan , ~ 0.3s
Memperbaiki bug besar dalam algoritme, perlu mengoptimalkannya kembali sekarang.
Kompilasi dengan
clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
Ini berfungsi dengan mengambil setiap angka yang harus dikandung string, dan menghitung jumlah tempat urutan digit yang diperlukan ada dalam string. Kemudian berulang kali melakukan langkah-langkah ini:
singles
)singles
)sumber