Hỏi về competitive programming

link đề bài : https://www.hackerrank.com/challenges/magic-square-forming/problem
1598566590674.png

có bác nào từng giải bài này trên hackerrank chưa, theo như cách em xem trên youtube thì thấy ông kia xét cả 8 trường hợp magic squares . Không biết có thuật toán nâng cao nào để giải quyết bài này gọn gàng hơn k ạ .
 
Khac Cuong said:
link đề bài : https://www.hackerrank.com/challenges/magic-square-forming/problem
View attachment 170645
có bác nào từng giải bài này trên hackerrank chưa, theo như cách em xem trên youtube thì thấy ông kia xét cả 8 trường hợp magic squares . Không biết có thuật toán nâng cao nào để giải quyết bài này gọn gàng hơn k ạ .
Click to expand...
Ko, constraints rất bé, n = 3 nên nhiều khả năng bài này là NP, chỉ có thể bruteforce.
 
P problems: các bài toán có thể giải trong polynominal time (N^i for i from 0 to very large n).

NP Problems: các bài toán không thể giải trong polynomial time (or có thể giải được [1]) . có thể xác nhận được bằng 1 thuật toán trong trong P time (verifier) nếu được cho 1 kết quả . Kiểu tôi không giải được nhanh, nhưng anh đưa kết quả đây tôi sẽ kêu verifier xác nhận trong P time là kết quả này đúng nay không. Gọi là Nondeterministic Polynomial time.

[1] Chứng minh được P != NP (or P=NP) là một trong 7 bài toán chưa giải được của Millennium Prize Problems.

Nên thím nào giải được sẽ có $1,000,000 đô la trump 😀
 
Last edited:
BigHeadCrew said:
P problems: các bài toán có thể giải trong polynominal time (N^i for i from 0 to very large n).

NP Problems: các bài toàn không thể giải trong polynomial time, nhưng có thể xác nhận được bằng 1 thuật tuán trong trong P time (verifier) nếu được cho 1 kết quả. Gọi là nondeterministic polynomial time.

P = NP là một trong 7 bài toán chưa giải được của Millennium Prize Problems. Nên thím nào giải được sẽ có $1000,000 đô la trump 😀
Click to expand...
Không có vụ này nhé. Định nghĩa của NP chỉ nói về vụ xác nhận trong thời gian đa thức thôi.

Nếu mà khẳng định được có bài toán NP nào đó không giải được trong thời gian đa thức thì xin chúc mừng, bạn đã chứng minh được P != NP.

Sent from Xiaomi Redmi 5A using vozFApp
 
honeyfox said:
Tiếng Việt nó cũng là NP thôi 🤣
https://vi.wikipedia.org/wiki/NP_(độ_phức_tạp)
Click to expand...

Tiếng anh làm mọe gì, ko biết mấy cái keyword hàn lâm thì cũng đ' hiểu nổi.
Nói cho dễ thì NP là tập các bài toán ko thể tìm được best solution. Thường rơi vào các bài toán thể loại trò chơi. Các cuộc thi hay có bài dạng này là bài cuối cùng. Ông nào giỏi + hên thì ăn được nhiều test case. Làm thế này cho dễ chia giải :LOL:
 
Pianist said:
Tiếng anh làm mọe gì, ko biết mấy cái keyword hàn lâm thì cũng đ' hiểu nổi.
Nói cho dễ thì NP là tập các bài toán ko thể tìm được best solution. Thường rơi vào các bài toán thể loại trò chơi. Các cuộc thi hay có bài dạng này là bài cuối cùng. Ông nào giỏi + hên thì ăn được nhiều test case. Làm thế này cho dễ chia giải :LOL:
Click to expand...

Chả liên quan gì luôn, NP là tập hợp các bài toán có thể xác nhận lời giải trong thời gian đa thức. Chỉ có vậy thôi, không có đề cập gì đến việc giải nó như nào cả. Như P là tập con của NP đó.
Chắc bạn đang nhầm với NP-hoàn chỉnh hoặc NP-khó.
 
Mấy thím cho em hỏi làm sao nhai được món quy hoạch động các thím nhể :sosad:, em cứ ngồi giải một bài quy hoạch động là bó giò không biết làm sao để giải luôn :sosad:.
 
Pianist said:
Giống kiểu thi IQ như Olympia ngày xưa, mới ra đề bài có đứa đã đọc đáp án cmnr.
Ko hiểu sao môn này lại gần như trở thành đề tài pv chính. Mặc dù chả áp dụng gì mấy vào cv :sad:
Click to expand...
SoftwareEngineer said:
Nói chung em cũng không thích phỏng vấn kiểu này, quá tốn thời gian cho ứng viên. Thay vì mỗi ngày về bác luyện code, luyện backend, API,... các kiểu thì minh lại ngồi làm DS&A, cái mà cực kì ít áp dụng vào thực tế, ít nhất là cho front end và mobile. 1 năm rữoi vừa qua, ngoài làm trên công ty ra thì toàn bộ thời gian rảnh em đều ngồi làm DS&A, nghĩ lại cực vãi và chán vãi, động lực duy nhất là tiền nhiều cho vợ con :(

Nhưng giờ công ty nó chơi kiểu gì mình phải chơi kiểu đấy chứ sao bây giờ:burn_joss_stick: Em làm Apple tính ra được 5 tháng, nhưng chưa viết 1 dòng Algorithms nào, chắc tại em là mobile.
Click to expand...

Cái này bọn nước ngoài nó cũng kêu trời kêu đất
Giờ mấy ông senior, kinh nghiệm SWE đầy mình nhưng có vợ con rồi thì lấy đéo ra thời gian luyện leetcode mỗi tối
Cái này chỉ hợp bọn nào mới ra trường, ko có exp thực tế + nhiều thời gian rảnh cày
 
WasupMoFucker said:
Cái này bọn nước ngoài nó cũng kêu trời kêu đất
Giờ mấy ông senior, kinh nghiệm SWE đầy mình nhưng có vợ con rồi thì lấy đéo ra thời gian luyện leetcode mỗi tối
Cái này chỉ hợp bọn nào mới ra trường, ko có exp thực tế + nhiều thời gian rảnh cày
Click to expand...
Mình thấy không liên quan đến khâu exp thực tế và thời gian rảnh cày lắm. Thấy nhiều thằng kể bảo nó mỗi ngày dành ra 1 tiếng làm 20 bài leetcode mỗi ngày, 1 tháng là nó phỏng vấn, tính ra có mất thời gian lắm đâu. Chủ yếu bọn nó kiểm tra khả năng tư duy thuật toán của ứng viên, có lẽ bọn nó không quá coi trọng kinh nghiệm bằng tư duy. Thật mình cũng ko dám nói thế là đúng hay sai, nhưng thực tế cho thấy thì những người giỏi cái món này lập trình sang cái khác cũng ko thấy ai kém cả. Công ty nó phải có lý của nó, mình muốn vào thì mình phải chơi theo luật của nó. Mình ko phục thì mình phải giỏi nhất rồi phi vào mà thay đổi. Chứ giờ mấy công ty lớn nhất như thế có cả mấy trăm ngàn người mà bảo những nơi đấy chỉ thích hợp mới ra trường ko kinh nghiệm thực tế thì thực sự mình ko dám gật
 
rosario_1 said:
Mình thấy không liên quan đến khâu exp thực tế và thời gian rảnh cày lắm. Thấy nhiều thằng kể bảo nó mỗi ngày dành ra 1 tiếng làm 20 bài leetcode mỗi ngày, 1 tháng là nó phỏng vấn, tính ra có mất thời gian lắm đâu. Chủ yếu bọn nó kiểm tra khả năng tư duy thuật toán của ứng viên, có lẽ bọn nó không quá coi trọng kinh nghiệm bằng tư duy. Thật mình cũng ko dám nói thế là đúng hay sai, nhưng thực tế cho thấy thì những người giỏi cái món này lập trình sang cái khác cũng ko thấy ai kém cả. Công ty nó phải có lý của nó, mình muốn vào thì mình phải chơi theo luật của nó. Mình ko phục thì mình phải giỏi nhất rồi phi vào mà thay đổi. Chứ giờ mấy công ty lớn nhất như thế có cả mấy trăm ngàn người mà bảo những nơi đấy chỉ thích hợp mới ra trường ko kinh nghiệm thực tế thì thực sự mình ko dám gật
Click to expand...

Thằng nào chém gió vậy ông, ngày làm max 6-7 bài leetcode là đầu óc xây xẩm rồi, thằng nào mà làm 1 tiếng 20 bài leetcode thì tôi không bao giờ tin. Giờ tôi cho mấy ông Senior hơn 7 năm kinh nghiệm, không đụng vào giải thuật trên 5 năm, cho 1 tháng ngồi chuẩn bị cũng chả đâu vào đâu đâu. ít nhất phải gần 2 3 tháng.
 
rosario_1 said:
Mình thấy không liên quan đến khâu exp thực tế và thời gian rảnh cày lắm. Thấy nhiều thằng kể bảo nó mỗi ngày dành ra 1 tiếng làm 20 bài leetcode mỗi ngày, 1 tháng là nó phỏng vấn, tính ra có mất thời gian lắm đâu. Chủ yếu bọn nó kiểm tra khả năng tư duy thuật toán của ứng viên, có lẽ bọn nó không quá coi trọng kinh nghiệm bằng tư duy. Thật mình cũng ko dám nói thế là đúng hay sai, nhưng thực tế cho thấy thì những người giỏi cái món này lập trình sang cái khác cũng ko thấy ai kém cả. Công ty nó phải có lý của nó, mình muốn vào thì mình phải chơi theo luật của nó. Mình ko phục thì mình phải giỏi nhất rồi phi vào mà thay đổi. Chứ giờ mấy công ty lớn nhất như thế có cả mấy trăm ngàn người mà bảo những nơi đấy chỉ thích hợp mới ra trường ko kinh nghiệm thực tế thì thực sự mình ko dám gật
Click to expand...

1 tiếng làm 20 bài leetcode thì đích thị là bạn ngáo đá rồi :D
mình ko phục thì mình kiếm chỗ khác bạn à
đây nhé có hẳn list những cty ko dùng whiteboard
https://github.com/poteto/hiring-without-whiteboards

còn 1 số ít cty như GG FB họ làm được đơn giản vì họ có quá nhiều applicant nên họ dùng bất kỳ cách gì thì cũng sẽ chọn ra được nhưng người xuất sắc và toàn diện thôi, nhưng ko có nghĩa cách của họ là hợp lý nhất
 

Similar threads

TaiChi3901
thắc mắc Build Kernel
Replies
1
Views
309
rongthhieng2007
rongthhieng2007
RuggedJigsaw
Cần các bác tư vấn về ngành nghề ạ
Replies
1
Views
184
namcrypto
N
D
thắc mắc Xử lý Async trong xây dựng hệ thống tải cao
Replies
11
Views
625
aNotHeRNo0b
aNotHeRNo0b
Sử Phú Thọ
Hỏi về việc làm Data Analyst
2
Replies
34
Views
1K
bricks on the wall
bricks on the wall
AwesomeBoy
thắc mắc giới thiệu các bác 1 bạn sv mình đang học IELTS, nhiệt tình giá rẻ, hỏi thoải mái ngoài giờ và thường dạy quá giờ
Replies
4
Views
357
haquangvu
H

Share this page

Back
Top