Tìm solution cho bài toán

[kenpi04]

https://2.pik.vn/2020bd67e7a3-4ef3-4562-8be3-e39e051f26dc.jpg

Em mới vừa làm bài test xong, có mỗi câu này là mất time mà vẫn ko pass được hết test case, mấy cao thủ có solution nào để giải quyết ko ạ.

[kenpi04]

em chụp thiếu input output test

input [5,10,4,4,4,5]
output :17

[dreamnight]

Đến chán cái update của bạn thiếu dữ liệu cần input và output ghê. Theo mình hiểu thì:

Input:
5 -> N people
4 -> skill of a[1]
5 -> skill of a[2]
6 -> skill of a[3]
2 -> skill of a[4]
1 -> skill of a[5]
Output:
Power group: [6,2,5]
Maximum power of group: 13

Có phải nó yêu cầu output thế này ko ?

[dreamnight]

em chụp thiếu input output test

input [5,10,4,4,4,5]
output :17

Vơi cái output maximum power này ko make sense vơi đề bài làm vì chuỗi 5 5 4 4 4 mới là chuỗi reliable chứ nhỉ vì ko có skill nào lớn hớn 2 skill cộng lại. Đáp an là 22?

[kenpi04]

Sorry mấy bác. Có 2 input
Input N là số phần tử của mảng và phần tử mảng
Input: là N= 6 và Arr= 5,10,4,4,4,5
Output: 17

Em cũng làm ra output 22 vs 12 bị sai nha mấy bác


P/S là 1 bài test trên https://www.hackerearth.com/

code của mình https://dotnetfiddle.net/18Y16Z

[kenpi04]

Đến chán cái update của bạn thiếu dữ liệu cần input và output ghê. Theo mình hiểu thì:

Input:
5 -> N people
4 -> skill of a[1]
5 -> skill of a[2]
6 -> skill of a[3]
2 -> skill of a[4]
1 -> skill of a[5]
Output:
Power group: [6,2,5]
Maximum power of group: 13

Có phải nó yêu cầu output thế này ko ?

Đúng rồi bác yêu cầu vậy đó bác

[dreamnight]

Sorry mấy bác. Có 2 input
Input N là số phần tử của mảng và phần tử mảng
Input: là N= 6 và Arr= 5,10,4,4,4,5
Output: 17

Em cũng làm ra output 22 vs 12 bị sai nha mấy bác


P/S là 1 bài test trên https://www.hackerearth.com/

code của mình https://dotnetfiddle.net/18Y16Z


Thế thì chuỗi 4 4 4 5 lại đúng với cái if trên à :go: ? Thế thì cái đề nó phải edit lại chứ cái đáp án ko thấy chính xác gì thì bảo sao mà fix cho đúng :stick:. Tự nhiên lúc nào cũng ignore thằng đầu tiên nếu theo code của bạn ?

[dreamnight]

Để dịch tiếng anh ra cho ai thích thì vào coi:

Cho một mảng N phần tử dùng để xác định skill level của người thứ i. a[i] là chỉ số skill của người thứ i. Bạn phải cần tìm nhóm người có tổng số skill là lớn nhất.

Trong đó, một nhóm được gọi là hợp lệ khi không có ai có số skill lớn hơn tổng 2 skill bất kỳ của các thành viên còn lại. Một nhóm có thể có từ 0 đến N người

Dựa trên ràng buộc đó, hãy tìm tổng sức mạnh tối đa từ nhóm người này.

Ngoài ra: N = [1,30000], a[i] = [0,60000]

Input: [5,10,4,4,4,5]
Output: 22 -> Theo mắt thường thì cái này nó mới đúng yêu cầu

[haylachoi]

em chụp thiếu input output test

input [5,10,4,4,4,5]
output :17

mà tính sao ra 17 dc nhỉ, hay bọn nó chỉ chơi dãy liên tiếp.

[6triennguyen]

Bài này cơ bản của cấu trúc dữ liệu giải thuật đặc biệt.
Giới hạn chạy trong nlogn
Dùng interval tree với chặt nhị phân (xem chặt nhị phân ở VNOI)

[kenpi04]

Thế thì chuỗi 4 4 4 5 lại đúng với cái if trên à :go: ? Thế thì cái đề nó phải edit lại chứ cái đáp án ko thấy chính xác gì thì bảo sao mà fix cho đúng :stick:. Tự nhiên lúc nào cũng ignore thằng đầu tiên nếu theo code của bạn ?
Cái này mình code đại cho nó ra 17 thôi bác chứ hết time rồi. Nhưng mà còn nhiều test case nữa ko pass đc

Sent from Samsung SM-N975F using vozFApp

[kenpi04]

mà tính sao ra 17 dc nhỉ, hay bọn nó chỉ chơi dãy liên tiếp.
Theo mình nghĩ là thằng nào được so sánh rồi thì bỏ qua luôn. Nhưng vẫn không hiểu tại sao thăng 5 đầu tiên lại không được tính vào hay thằng 5 cuối cùng ko được tính vào. Hic đề test senior thôi mà gay go quá

Sent from Samsung SM-N975F using vozFApp

[BiGhEad.z]

Sorry mấy bác. Có 2 input
Input N là số phần tử của mảng và phần tử mảng
Input: là N= 6 và Arr= 5,10,4,4,4,5
Output: 17

Em cũng làm ra output 22 vs 12 bị sai nha mấy bác


P/S là 1 bài test trên https://www.hackerearth.com/

code của mình https://dotnetfiddle.net/18Y16Z

Mình lên hackerearth mà sao không tìm ra bài này nhỉ :surrender:

[tthixk]

Nhìn đề làm luôn thì sort rồi vét cạn tìm max power tại từng vị trí. Làm lụi thì On2, optimize thì có lẽ sẽ đc Onlogn vì sorted list.

[hts222]

xin link đề gốc nào chủ thớt, đề mình code rồi sub thử xem :shame: chứ đề với input test mâu thuẫn nhau quá :go: 1584337

[dreamnight]

mà tính sao ra 17 dc nhỉ, hay bọn nó chỉ chơi dãy liên tiếp.

Chắc vậy quá :stick:, mà nếu là chuỗi con thì nó phải điền là "make a new group from array in which a new group is a sub array" :sweat:

[blah02]

Nhìn đề làm luôn thì sort rồi vét cạn tìm max power tại từng vị trí. Làm lụi thì On2, optimize thì có lẽ sẽ đc Onlogn vì sorted list.

Thím này nói chuẩn nè. Nhưng đối với đề bài yêu cầu thời gian xử lý thì gần như vét cạn 100% fail nên tốt nhất cứ đầu tư thời gian suy nghĩ trước khi cắm đầu làm.

B1: Quick sort mảng a[] từ cao -> thấp (Onlogn)
- Nếu a[i] là phần tử lớn nhất trong nhóm đc chọn -> ko có quá 2 phần tử nhỏ hơn a[i]/2
Thử với i=0
B2: Tìm j max sao cho a >= a[i]/2
B3: Nếu a+a[j+1] < a[i] thì tính tổng từ a[i] -> a, nếu ko thì tính tổng từ a[i] -> a[j+1]
B4: Lưu tổng tính đc vào mảng mới t[].
B5: i++ rồi quay lại B2

Kết thúc vòng lặp lấy ra max của t[] là xong

Hướng làm là như vậy, độ phức tạp là On2. Nếu optimize sử dụng thêm nhiều biến hỗ trợ thay vì phải duyệt lại mảng nhiều lần thì có thể xuống được Onlogn