Algorithmic Crush challenge on Hackerrank

#1

Xin chào ae,
Vào thẳng vấn đề luôn nhé, đây là 1 challenge nằm trong subdomain Arrays của Data structures & Algorithms trên Hackerrank (hard): https://www.hackerrank.com/challenges/crush
Đây là code giải của e:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n, m, a, b, k;
    std::cin >> n >> m;
    std::vector<int> arr(n, 0);
    for (int i = 0; i < m; ++i) {
        std::cin >> a >> b >> k;
        for (int j = a - 1; j < b; ++j)
            arr[j] += k;
    }
    auto it = std::max_element(arr.begin(), arr.end());
    std::cout << *it;
    return 0;
}

Code đó bị sai ở testcase 4, 5, 6, còn từ testcase 7 đến 13 là bị Terminated due to timeout!
Có ai bt vi sao sai ko ạ? Còn timeout thì chắc để tính sau, vì đây là hard ^^
Và ai có solution thì hướng dẫn cho e luôn nhé :blush:
E cảm ơn trc

P/S: Đây là I/O của testcase 4:
INPUT: http://codepad.org/1r3UWWfx
OUTPUT: 7542539201.

#2

:smiley: Chắc bạn bị tràn rồi.
Thay = long long thử xem.

1 Like
#3

Code thử cũng bị timeout vụ này có vẻ khó @_@!

#4

O(n*m) với m, n to thì bảo sao chả TLE.
Bài này dùng Interval Tree nhé.

2 Likes
#5

Hình như đây là kiểu số nguyên lớn nhất rồi hả a?

Nó nằm trong subdomain Arrays mà dùng Tree có hơi “lạ” ko a?

#6

Lạ gì, cài Interval Tree dùng mảng mà. Mà cài Interval Tree là dùng Data Structure rồi còn gì, quá chuẩn rồi :slight_smile:
Kiểu số nguyên có dấu lớn nhất là long long, còn không dấu lớn nhất là unsigned long long.

1 Like
#7

Bài này không cần dùng interval tree , chỉ cần dùng mảng và tính chất liên tiếp của việc thêm vào đoạn [L,R]:

  • việc cộng x vào [L,R] sẽ được đánh dấu:
a[L]   += x
a[R+1] -= x
  • việc tính giá trị sau khi update theo query:
for i in [1..n]:
     a[i] += a[i-1]
  • sau đó tìm max của a.
1 Like
#8

Theo mọi người thì phần nào chạy thối thời gian nhất ?
Theo mình phần nhập dữ liệu @_@!

#10

@Phong_Ky_Vo: Nếu dùng Interval Tree thì vừa nhập vừa xử lí là được.

@Gio:
Bạn thử code xem.
À mà bài này cũng có cách dùng Binary Index Tree nữa @@

1 Like
#11
  • xử lý offline
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n,k;
    cin>>n>>k;
    vector<long long> a(n+2,0);
    for(int i=0;i<k;i++){
        long long L,R,x;
        cin>>L>>R>>x;
        a[L]+=x;
        a[R+1]-=x;
    }
    for(int i=1;i<a.size();i++){
        a[i]+=a[i-1];
    }
    cout<<*max_element(a.begin()+1,a.end()-1);
    return 0;
}
3 Likes
#12

Bạn thử submit chưa @@

1 Like
#13

Mình vừa submit xong, accept rôi bạn

2 Likes
#14

Hi Gió.
Làm sao lại nghĩ được cách hay vậy ???

#15

xem mảng n+2 phần tử đó là mảng chênh lệch với quy luật:
diff[i] = arr[i] - arr[i-1]
cái này rất tiện ích, muốn cộng k cho b-a+1 phần tử từ a tới b, thay vì cộng b-a+1 lần, ở đây ta chỉ làm 2 phép toán ở đầu và cuối: diff[a] += k và diff[b+1] -= k, nghĩa là update độ chênh lệch ở đầu và cuối, còn mấy phần tử ở giữa ko cần update độ chênh lệch:

  • nếu arr[a] += k thì đương nhiên arr[a] - arr[a-1] tăng thêm k đơn vị, vì arr[a-1] ko đổi mà arr[a] tăng thêm k. Vậy ta update diff[a] += k.
  • nếu arr[b] += k thì arr[b+1] - arr[b] giảm đi k đơn vị, vì arr[b] tăng thêm k mà arr[b+1] ko tăng. Vậy ta cần update diff[b+1] -= k
  • những phần tử ở giữa có diff ko đổi: diff[a+i] = arr[a+i] - arr[a+i-1] với 0 < i ≤ b-a ko tăng giảm vì arr[a+i] và arr[a+i-1] đều tăng thêm k đơn vị.

thay vì update mn lần, ta chỉ cần update m2 lần, hay giảm từ O(mn) xuống còn O(m)

để chuyển mảng diff thành mảng arr ban đầu, ta chỉ cần cộng diff[i] += diff[i-1] với 1 ≤ i ≤ n là chuyển diff thành arr:

  • diff có index từ 0 tới n+1, arr có index từ 1 tới n
  • Ban đầu ta có diff[0] = arr[0] (giả sử arr tồn tại phần tử arr[0] = 0). Vì diff[1] = arr[1] - arr[0], nên arr[1] = diff[1] + arr[0] = diff[1] + diff[0]. Ta cộng dồn diff[1] = diff[1] + diff[0].
  • Lúc này ta thu được diff[1] = arr[1]. Vì diff[2] = arr[2] - arr[1], nên arr[2] = diff[2] + arr[1] = diff[2] + diff[1]. Ta cộng dồn diff[2] = diff[2] + diff[1].
  • v.v…

vậy là thu được arr sau cùng với O(n) phép cộng, chỉ cần tìm max element (O(n)) nữa là xong. Tổng quát bài toán có đpt O(n+m).

(khi áp dụng thuật toán này diff chỉ cần n+1 phần tử cũng được, bỏ phần tử diff[0])

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?